bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/parser/generator/grammar/AnaGrammar.java

   1 package org.simantics.scl.compiler.parser.generator.grammar;
   2
   3 import gnu.trove.list.array.TIntArrayList;
   4 import gnu.trove.map.hash.TIntByteHashMap;
   5 import gnu.trove.procedure.TIntIntProcedure;
   6 import gnu.trove.procedure.TIntProcedure;
   7 import gnu.trove.set.hash.THashSet;
   8 import gnu.trove.set.hash.TIntHashSet;
   9
  10 import java.util.ArrayList;
  11 import java.util.Arrays;
  12
  13 import org.simantics.scl.compiler.parser.grammar.Grammar;
  14 import org.simantics.scl.compiler.parser.grammar.Production;
  15 import org.simantics.scl.compiler.parser.regexp.Namer;
  16 import org.simantics.scl.compiler.parser.regexp.automata.DFA;
  17
  18 public class AnaGrammar implements Namer {
  19
  20     public ArrayList<Prod> prods = new ArrayList<Prod>();
  21     public int[] nonterminalPos;
  22
  23     public final String[] terminalNames;
  24     public final String[] nonterminalNames;
  25
  26     public final int[] initialNonterminals;
  27
  28     public boolean[] nullable;
  29     public int[][] first;
  30
  31
  32     public AnaGrammar(Grammar grammar) {
  33         initialNonterminals = grammar.initialNonterminals;
  34         terminalNames = Arrays.copyOf(grammar.terminalNames, grammar.terminalNames.length+1);
  35         terminalNames[terminalNames.length-1] = "EOF";
  36         nonterminalNames = Arrays.copyOf(grammar.nonterminalNames,
  37                 grammar.nonterminalNames.length+initialNonterminals.length);
  38         for(int i=1;i<=initialNonterminals.length;++i)
  39             nonterminalNames[nonterminalNames.length-i] = "init$" + i;
  40
  41         // Convert grammar
  42         ArrayList<Prod>[] prodMap = new ArrayList[nonterminalNames.length];
  43         for(int i=0;i<nonterminalNames.length;++i)
  44             prodMap[i] = new ArrayList<Prod>();
  45         for(Production production : grammar.productions) {
  46             Prod prod = new Prod(production.name, ~production.lhs,
  47                     production.rhs.toAutomaton().determinize().minimize(),
  48                     production.annotations);
  49             prodMap[prod.lhs].add(prod);
  50         }
  51
  52         // Initial production
  53         for(int i=1;i<=initialNonterminals.length;++i) {
  54             DFA dfa = new DFA();
  55             int s0 = dfa.newState();
  56             dfa.setInitialState(s0);
  57             int s1 = dfa.newState();
  58             dfa.addTransition(s0, initialNonterminals[i-1], s1);
  59             int s2 = dfa.newState();
  60             dfa.addTransition(s1, terminalNames.length-1, s2);
  61             dfa.setAccepts(s2, true);
  62             Prod prod = new Prod("Init", nonterminalNames.length-i, dfa, new TIntByteHashMap());
  63             prodMap[prod.lhs].add(prod);
  64         }
  65
  66         TIntArrayList pos = new TIntArrayList();
  67         for(int i=0;i<nonterminalNames.length;++i) {
  68             pos.add(prods.size());
  69             prods.addAll(prodMap[i]);
  70         }
  71         pos.add(prods.size());
  72         nonterminalPos = pos.toArray();
  73
  74         // Basic analysis
  75         computeNullableNonterminals();
  76     }
  77
  78     private static class FrontierItem {
  79         public final int production;
  80         public final int state;
  81
  82         public FrontierItem(int production, int state) {
  83             this.production = production;
  84             this.state = state;
  85         }
  86
  87         @Override
  88         public int hashCode() {
  89             return 31*state + production;
  90         }
  91
  92         @Override
  93         public boolean equals(Object obj) {
  94             if(this == obj)
  95                 return true;
  96             if(obj == null || obj.getClass() != getClass())
  97                 return false;
  98             FrontierItem other = (FrontierItem)obj;
  99             return other.state == state && other.production == production;
 100         }
 101     }
 102
 103     private void computeNullableNonterminals() {
 104         int nonterminalCount = nonterminalNames.length;
 105         nullable = new boolean[nonterminalCount];
 106         final TIntHashSet[] first = new TIntHashSet[nonterminalCount];
 107         final TIntHashSet[] gfirst = new TIntHashSet[nonterminalCount];
 108         for(int i=0;i<nonterminalCount;++i) {
 109             first[i] = new TIntHashSet();
 110             gfirst[i] = new TIntHashSet();
 111         }
 112         final ArrayList<FrontierItem>[] pendingItems = new ArrayList[nonterminalCount];
 113         final ArrayList<FrontierItem> stack = new ArrayList<FrontierItem>();
 114         THashSet<FrontierItem> handledItems = new THashSet<FrontierItem>();
 115         for(int i=0;i<nonterminalCount;++i)
 116             pendingItems[i] = new ArrayList<FrontierItem>();
 117
 118         for(int i=0;i<prods.size();++i)
 119             stack.add(new FrontierItem(i, prods.get(i).rhs.getInitialState()));
 120         while(!stack.isEmpty()) {
 121             final FrontierItem cur = stack.remove(stack.size()-1);
 122             if(!handledItems.add(cur))
 123                 continue;
 124             final Prod curProd = prods.get(cur.production);
 125             if(curProd.rhs.getAccepts(cur.state)) {
 126                 nullable[curProd.lhs] = true;
 127                 stack.addAll(pendingItems[curProd.lhs]);
 128             }
 129             curProd.rhs.forEachTransition(cur.state, new TIntIntProcedure() {
 130                 @Override
 131                 public boolean execute(int symbol, int targetState) {
 132                     if(symbol < 0) {
 133                         symbol = ~symbol;
 134                         gfirst[symbol].add(curProd.lhs);
 135                         FrontierItem item = new FrontierItem(cur.production, targetState);
 136                         if(nullable[symbol])
 137                             stack.add(item);
 138                         else
 139                             pendingItems[symbol].add(item);
 140                     }
 141                     else
 142                         first[curProd.lhs].add(symbol);
 143                     return true;
 144                 }
 145             });
 146         }
 147
 148         gclose(first, gfirst);
 149         this.first = new int[first.length][];
 150         for(int i=0;i<first.length;++i)
 151             this.first[i] = first[i].toArray();
 152
 153         /*System.out.println("Nullable nonterminals:");
 154         for(int i=0;i<nullable.length;++i) {
 155             System.out.print("    " + nonterminalNames[i] + " -> ");
 156             if(nullable[i])
 157                 System.out.print(" NULL");
 158             for(int s : this.first[i])
 159                 System.out.print(" " + terminalNames[s]);
 160             System.out.println();
 161         }*/
 162     }
 163
 164     public static void gclose(TIntHashSet[] sets, TIntHashSet[] graph_) {
 165         int[][] graph = new int[graph_.length][];
 166         for(int i=0;i<graph.length;++i)
 167             graph[i] = graph_[i].toArray();
 168
 169         final TIntArrayList stack = new TIntArrayList();
 170         for(int i=0;i<sets.length;++i) {
 171             final int i_ = i;
 172             sets[i].forEach(new TIntProcedure() {
 173                 @Override
 174                 public boolean execute(int value) {
 175                     stack.add(i_);
 176                     stack.add(value);
 177                     return true;
 178                 }
 179             });
 180         }
 181
 182         while(!stack.isEmpty()) {
 183             int sp = stack.size();
 184             int value = stack.removeAt(sp-1);
 185             int id = stack.removeAt(sp-2);
 186             for(int s : graph[id])
 187                 if(sets[s].add(value)) {
 188                     stack.add(s);
 189                     stack.add(value);
 190                 }
 191         }
 192     }
 193
 194     public String getName(int symbolId) {
 195         if(symbolId >= 0)
 196             return terminalNames[symbolId];
 197         else
 198             return nonterminalNames[~symbolId];
 199     }
 200
 201     private class AlmostAcceptsProc implements  TIntIntProcedure {
 202         DFA rhs;
 203         TIntHashSet visited = new TIntHashSet();
 204
 205         boolean result;
 206
 207         public AlmostAcceptsProc(DFA rhs) {
 208             this.rhs = rhs;
 209         }
 210
 211         @Override
 212         public boolean execute(int a, int b) {
 213             if(a < 0 && nullable[~a])
 214                 visit(b);
 215             return !result;
 216         }
 217
 218         public void visit(int position) {
 219             if(visited.add(position)) {
 220                 if(rhs.getAccepts(position)) {
 221                     result = true;
 222                     return;
 223                 }
 224                 rhs.forEachTransition(position, this);
 225             }
 226         }
 227     }
 228
 229     public boolean almostAccepts(DFA rhs, int position) {
 230         AlmostAcceptsProc proc = new AlmostAcceptsProc(rhs);
 231         proc.visit(position);
 232         return proc.result;
 233     }
 234 }