--- /dev/null
+package org.simantics.scl.compiler.parser.generator.grammar;
+
+import gnu.trove.list.array.TIntArrayList;
+import gnu.trove.map.hash.TIntByteHashMap;
+import gnu.trove.procedure.TIntIntProcedure;
+import gnu.trove.procedure.TIntProcedure;
+import gnu.trove.set.hash.THashSet;
+import gnu.trove.set.hash.TIntHashSet;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+
+import org.simantics.scl.compiler.parser.grammar.Grammar;
+import org.simantics.scl.compiler.parser.grammar.Production;
+import org.simantics.scl.compiler.parser.regexp.Namer;
+import org.simantics.scl.compiler.parser.regexp.automata.DFA;
+
+public class AnaGrammar implements Namer {
+
+ public ArrayList<Prod> prods = new ArrayList<Prod>();
+ public int[] nonterminalPos;
+
+ public final String[] terminalNames;
+ public final String[] nonterminalNames;
+
+ public final int[] initialNonterminals;
+
+ public boolean[] nullable;
+ public int[][] first;
+
+
+ public AnaGrammar(Grammar grammar) {
+ initialNonterminals = grammar.initialNonterminals;
+ terminalNames = Arrays.copyOf(grammar.terminalNames, grammar.terminalNames.length+1);
+ terminalNames[terminalNames.length-1] = "EOF";
+ nonterminalNames = Arrays.copyOf(grammar.nonterminalNames,
+ grammar.nonterminalNames.length+initialNonterminals.length);
+ for(int i=1;i<=initialNonterminals.length;++i)
+ nonterminalNames[nonterminalNames.length-i] = "init$" + i;
+
+ // Convert grammar
+ ArrayList<Prod>[] prodMap = new ArrayList[nonterminalNames.length];
+ for(int i=0;i<nonterminalNames.length;++i)
+ prodMap[i] = new ArrayList<Prod>();
+ for(Production production : grammar.productions) {
+ Prod prod = new Prod(production.name, ~production.lhs,
+ production.rhs.toAutomaton().determinize().minimize(),
+ production.annotations);
+ prodMap[prod.lhs].add(prod);
+ }
+
+ // Initial production
+ for(int i=1;i<=initialNonterminals.length;++i) {
+ DFA dfa = new DFA();
+ int s0 = dfa.newState();
+ dfa.setInitialState(s0);
+ int s1 = dfa.newState();
+ dfa.addTransition(s0, initialNonterminals[i-1], s1);
+ int s2 = dfa.newState();
+ dfa.addTransition(s1, terminalNames.length-1, s2);
+ dfa.setAccepts(s2, true);
+ Prod prod = new Prod("Init", nonterminalNames.length-i, dfa, new TIntByteHashMap());
+ prodMap[prod.lhs].add(prod);
+ }
+
+ TIntArrayList pos = new TIntArrayList();
+ for(int i=0;i<nonterminalNames.length;++i) {
+ pos.add(prods.size());
+ prods.addAll(prodMap[i]);
+ }
+ pos.add(prods.size());
+ nonterminalPos = pos.toArray();
+
+ // Basic analysis
+ computeNullableNonterminals();
+ }
+
+ private static class FrontierItem {
+ public final int production;
+ public final int state;
+
+ public FrontierItem(int production, int state) {
+ this.production = production;
+ this.state = state;
+ }
+
+ @Override
+ public int hashCode() {
+ return 31*state + production;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if(this == obj)
+ return true;
+ if(obj == null || obj.getClass() != getClass())
+ return false;
+ FrontierItem other = (FrontierItem)obj;
+ return other.state == state && other.production == production;
+ }
+ }
+
+ private void computeNullableNonterminals() {
+ int nonterminalCount = nonterminalNames.length;
+ nullable = new boolean[nonterminalCount];
+ final TIntHashSet[] first = new TIntHashSet[nonterminalCount];
+ final TIntHashSet[] gfirst = new TIntHashSet[nonterminalCount];
+ for(int i=0;i<nonterminalCount;++i) {
+ first[i] = new TIntHashSet();
+ gfirst[i] = new TIntHashSet();
+ }
+ final ArrayList<FrontierItem>[] pendingItems = new ArrayList[nonterminalCount];
+ final ArrayList<FrontierItem> stack = new ArrayList<FrontierItem>();
+ THashSet<FrontierItem> handledItems = new THashSet<FrontierItem>();
+ for(int i=0;i<nonterminalCount;++i)
+ pendingItems[i] = new ArrayList<FrontierItem>();
+
+ for(int i=0;i<prods.size();++i)
+ stack.add(new FrontierItem(i, prods.get(i).rhs.getInitialState()));
+ while(!stack.isEmpty()) {
+ final FrontierItem cur = stack.remove(stack.size()-1);
+ if(!handledItems.add(cur))
+ continue;
+ final Prod curProd = prods.get(cur.production);
+ if(curProd.rhs.getAccepts(cur.state)) {
+ nullable[curProd.lhs] = true;
+ stack.addAll(pendingItems[curProd.lhs]);
+ }
+ curProd.rhs.forEachTransition(cur.state, new TIntIntProcedure() {
+ @Override
+ public boolean execute(int symbol, int targetState) {
+ if(symbol < 0) {
+ symbol = ~symbol;
+ gfirst[symbol].add(curProd.lhs);
+ FrontierItem item = new FrontierItem(cur.production, targetState);
+ if(nullable[symbol])
+ stack.add(item);
+ else
+ pendingItems[symbol].add(item);
+ }
+ else
+ first[curProd.lhs].add(symbol);
+ return true;
+ }
+ });
+ }
+
+ gclose(first, gfirst);
+ this.first = new int[first.length][];
+ for(int i=0;i<first.length;++i)
+ this.first[i] = first[i].toArray();
+
+ /*System.out.println("Nullable nonterminals:");
+ for(int i=0;i<nullable.length;++i) {
+ System.out.print(" " + nonterminalNames[i] + " -> ");
+ if(nullable[i])
+ System.out.print(" NULL");
+ for(int s : this.first[i])
+ System.out.print(" " + terminalNames[s]);
+ System.out.println();
+ }*/
+ }
+
+ public static void gclose(TIntHashSet[] sets, TIntHashSet[] graph_) {
+ int[][] graph = new int[graph_.length][];
+ for(int i=0;i<graph.length;++i)
+ graph[i] = graph_[i].toArray();
+
+ final TIntArrayList stack = new TIntArrayList();
+ for(int i=0;i<sets.length;++i) {
+ final int i_ = i;
+ sets[i].forEach(new TIntProcedure() {
+ @Override
+ public boolean execute(int value) {
+ stack.add(i_);
+ stack.add(value);
+ return true;
+ }
+ });
+ }
+
+ while(!stack.isEmpty()) {
+ int sp = stack.size();
+ int value = stack.removeAt(sp-1);
+ int id = stack.removeAt(sp-2);
+ for(int s : graph[id])
+ if(sets[s].add(value)) {
+ stack.add(s);
+ stack.add(value);
+ }
+ }
+ }
+
+ public String getName(int symbolId) {
+ if(symbolId >= 0)
+ return terminalNames[symbolId];
+ else
+ return nonterminalNames[~symbolId];
+ }
+
+ private class AlmostAcceptsProc implements TIntIntProcedure {
+ DFA rhs;
+ TIntHashSet visited = new TIntHashSet();
+
+ boolean result;
+
+ public AlmostAcceptsProc(DFA rhs) {
+ this.rhs = rhs;
+ }
+
+ @Override
+ public boolean execute(int a, int b) {
+ if(a < 0 && nullable[~a])
+ visit(b);
+ return !result;
+ }
+
+ public void visit(int position) {
+ if(visited.add(position)) {
+ if(rhs.getAccepts(position)) {
+ result = true;
+ return;
+ }
+ rhs.forEachTransition(position, this);
+ }
+ }
+ }
+
+ public boolean almostAccepts(DFA rhs, int position) {
+ AlmostAcceptsProc proc = new AlmostAcceptsProc(rhs);
+ proc.visit(position);
+ return proc.result;
+ }
+}
Code Review / simantics / platform.git / blobdiff