1 package org.simantics.scl.compiler.parser.generator.grammar;
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;
10 import java.util.ArrayList;
11 import java.util.Arrays;
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;
18 public class AnaGrammar implements Namer {
20 public ArrayList<Prod> prods = new ArrayList<Prod>();
21 public int[] nonterminalPos;
23 public final String[] terminalNames;
24 public final String[] nonterminalNames;
26 public final int[] initialNonterminals;
28 public boolean[] nullable;
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;
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);
53 for(int i=1;i<=initialNonterminals.length;++i) {
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);
66 TIntArrayList pos = new TIntArrayList();
67 for(int i=0;i<nonterminalNames.length;++i) {
68 pos.add(prods.size());
69 prods.addAll(prodMap[i]);
71 pos.add(prods.size());
72 nonterminalPos = pos.toArray();
75 computeNullableNonterminals();
78 private static class FrontierItem {
79 public final int production;
80 public final int state;
82 public FrontierItem(int production, int state) {
83 this.production = production;
88 public int hashCode() {
89 return 31*state + production;
93 public boolean equals(Object obj) {
96 if(obj == null || obj.getClass() != getClass())
98 FrontierItem other = (FrontierItem)obj;
99 return other.state == state && other.production == production;
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();
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>();
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))
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]);
129 curProd.rhs.forEachTransition(cur.state, new TIntIntProcedure() {
131 public boolean execute(int symbol, int targetState) {
134 gfirst[symbol].add(curProd.lhs);
135 FrontierItem item = new FrontierItem(cur.production, targetState);
139 pendingItems[symbol].add(item);
142 first[curProd.lhs].add(symbol);
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();
153 /*System.out.println("Nullable nonterminals:");
154 for(int i=0;i<nullable.length;++i) {
155 System.out.print(" " + nonterminalNames[i] + " -> ");
157 System.out.print(" NULL");
158 for(int s : this.first[i])
159 System.out.print(" " + terminalNames[s]);
160 System.out.println();
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();
169 final TIntArrayList stack = new TIntArrayList();
170 for(int i=0;i<sets.length;++i) {
172 sets[i].forEach(new TIntProcedure() {
174 public boolean execute(int value) {
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)) {
194 public String getName(int symbolId) {
196 return terminalNames[symbolId];
198 return nonterminalNames[~symbolId];
201 private class AlmostAcceptsProc implements TIntIntProcedure {
203 TIntHashSet visited = new TIntHashSet();
207 public AlmostAcceptsProc(DFA rhs) {
212 public boolean execute(int a, int b) {
213 if(a < 0 && nullable[~a])
218 public void visit(int position) {
219 if(visited.add(position)) {
220 if(rhs.getAccepts(position)) {
224 rhs.forEachTransition(position, this);
229 public boolean almostAccepts(DFA rhs, int position) {
230 AlmostAcceptsProc proc = new AlmostAcceptsProc(rhs);
231 proc.visit(position);