1 module gamma.parsgen.lalr1.run.LR1ParserTablesReader;
2 
3 import gamma.grammar.Alternative;
4 import gamma.grammar.Grammar;
5 import gamma.grammar.GrammarBuilder;
6 import gamma.grammar.Node;
7 import gamma.grammar.Nonterminal;
8 import gamma.grammar.Rule;
9 import gamma.grammar.Symbol;
10 import gamma.grammar.SymbolNode;
11 import gamma.grammar.Terminal;
12 import gamma.parsgen.lalr1.OrderedLR1Tables;
13 import gamma.util.Position;
14 import std.algorithm;
15 import std.exception;
16 import std.format;
17 import std.json;
18 import std.stdio;
19 
20 /**
21  * Reads an OrderedLR1Tables representation from a given input file.
22  */
23 public class LR1ParserTablesReader
24 {
25     private OrderedLR1Tables.Action[][] parserActionRows;
26 
27     private OrderedLR1Tables.Goto[][] gotoRows;
28 
29     private GrammarBuilder grammarBuilder;
30 
31     private Nonterminal[size_t] index2Nonterminal;
32 
33     private Terminal[size_t] index2Terminal;
34 
35     private Alternative[size_t] index2Alternative;
36 
37     private long maxState;
38 
39     static public class SimplePosition : Position
40     {
41         private string repr;
42 
43         public this(string repr)
44         {
45             this.repr = repr;
46         }
47 
48         public void markError(string message)
49         {
50             import log;
51 
52             error!"%s: %s"(repr, message);
53         }
54     }
55 
56     static private string ruleReprFor(Alternative alt)
57     {
58         return format!"%s ::=%-( %s%)"(alt.lhs.symbol, alt.rhs.map!(node => (cast(SymbolNode) node).symbol));
59     }
60 
61     private this()
62     {
63         this.maxState = -1;
64     }
65 
66     public static OrderedLR1Tables read(File input)
67     {
68         import std.array : array;
69 
70         auto text = cast(char[]) input.byChunk(4096).joiner.array;
71         auto value = parseJSON(text);
72 
73         return new LR1ParserTablesReader().parseLR1Parser(value);
74     }
75 
76     private OrderedLR1Tables parseLR1Parser(JSONValue value)
77     {
78         import gamma.parsgen.lalr1.run.OrderedLR1TablesImpl : OrderedLR1TablesImpl;
79 
80         JSONValue[string] object = value.object;
81         Grammar grammar = parseGrammar(object["grammar"]);
82 
83         parseActions(object["states"]);
84         return new OrderedLR1TablesImpl(grammar, this.parserActionRows, this.gotoRows);
85     }
86 
87     private Grammar parseGrammar(JSONValue value)
88     {
89         JSONValue[string] object = value.object;
90 
91         parseNonterminals(object["nonterminals"]);
92         parseTerminals(object["terminals"]);
93         parseRules(object["rules"]);
94 
95         Nonterminal startSymbol = parseStartSymbol(object["startSymbol"]);
96 
97         Grammar grammar = grammarBuilder.getGrammar(startSymbol);
98 
99         enforce(startSymbol == grammar.startSymbol,
100             "sorry, not able to build a grammar with the required start symbol");
101 
102         checkGrammar(grammar);
103         return grammar;
104     }
105 
106     private void parseNonterminals(JSONValue value)
107     {
108         foreach (nonterminalValue; value.array)
109         {
110             JSONValue[string] object = nonterminalValue.object;
111             const index = object["index"].integer;
112             const repr = object["repr"].str;
113             Nonterminal nonterminal = grammarBuilder.buildNonterminal(repr);
114 
115             enforce(nonterminal.index == index,
116                 "bad nonterminal index...");
117 
118 
119             index2Nonterminal[index] = nonterminal;
120         }
121     }
122 
123     private void parseTerminals(JSONValue value)
124     {
125         foreach (terminalValue; value.array)
126         {
127             JSONValue[string] object = terminalValue.object;
128             const index = object["index"].integer;
129             const repr = object["repr"].str;
130             Terminal terminal = grammarBuilder.buildTerminal(repr);
131 
132             enforce(terminal.index == index,
133                 "bad terminal index...");
134 
135 
136             index2Terminal[index] = terminal;
137         }
138     }
139 
140     private void parseRules(JSONValue value)
141     {
142         foreach (ruleValue; value.array)
143             parseRule(ruleValue);
144     }
145 
146     private void parseRule(JSONValue value)
147     {
148         JSONValue[string] object = value.object;
149         const index = object["lhs"].integer;
150         Nonterminal lhs = index2Nonterminal[index];
151 
152         foreach (alternativeValue; object["alternatives"].array)
153             parseAlternative(lhs, alternativeValue);
154     }
155 
156     private void parseAlternative(Nonterminal lhs, JSONValue value)
157     {
158         JSONValue[string] object = value.object;
159         const index = object["index"].integer;
160 
161         Node[] rhs;
162 
163         foreach (nodeValue; object["rhs"].array)
164         {
165             Symbol symbol;
166 
167             if (nodeValue.object["type"].str == "nonterminal")
168                 symbol = parseNonterminal(nodeValue);
169             else if (nodeValue.object["type"].str == "terminal")
170                 symbol = parseTerminal(nodeValue);
171             else
172                 break;
173             rhs ~= new SymbolNode(symbol, new SimplePosition(symbol.toString));
174         }
175 
176         auto alternative = new Alternative(
177             new SymbolNode(lhs, new SimplePosition(lhs.toString)),
178             rhs,
179             new SimplePosition(format!"alternative #%s"(index)));
180 
181         this.index2Alternative[index] = alternative;
182         grammarBuilder.add(alternative);
183     }
184 
185     private Nonterminal parseNonterminal(JSONValue value)
186     {
187         JSONValue[string] object = value.object;
188         const index = object["index"].integer;
189         Nonterminal nonterminal = index2Nonterminal[index];
190 
191         return nonterminal;
192     }
193 
194     private Terminal parseTerminal(JSONValue value)
195     {
196         JSONValue[string] object = value.object;
197         const index = object["index"].integer;
198         Terminal terminal = index2Terminal[index];
199 
200         return terminal;
201     }
202 
203     private Nonterminal parseStartSymbol(JSONValue value)
204     {
205         JSONValue[string] object = value.object;
206         const index = object["index"].integer;
207         Nonterminal nonterminal = index2Nonterminal[index];
208 
209         return nonterminal;
210     }
211 
212     private void parseActions(JSONValue value)
213     {
214         foreach (stateValue; value.array)
215         {
216             JSONValue[string] object = stateValue.object;
217             const index = object["index"].integer;
218 
219             enforce(index == parserActionRows.length,
220                 format!"illegal state %s"(index));
221 
222             OrderedLR1Tables.Action[] parserActionRow;
223 
224             foreach (actionValue; object["actions"].array)
225                 if (actionValue.object["type"].str == "shift")
226                     parserActionRow ~= parseShift(actionValue);
227                 else if (actionValue.object["type"].str == "reduce")
228                     parserActionRow ~= parseReduce(actionValue);
229                 else if (actionValue.object["type"].str == "halt")
230                     parserActionRow ~= parseHalt(actionValue);
231             parserActionRows ~= parserActionRow;
232 
233             OrderedLR1Tables.Goto[] gotoRow;
234 
235             foreach (transitionValue; object["transitions"].array)
236                 gotoRow ~= parseGoto(transitionValue);
237             gotoRows ~= gotoRow;
238         }
239 
240         enforce(this.maxState < parserActionRows.length,
241             "something went wrong...");
242     }
243 
244     private OrderedLR1Tables.Shift parseShift(JSONValue value)
245     {
246         Terminal lookahead = parseOnTerminal(value);
247         const toState = parseTo(value);
248         const continues = parseContinues(value);
249         OrderedLR1Tables.Shift shift = new OrderedLR1Tables.Shift(lookahead, toState);
250 
251         shift.isContinuationAction = continues;
252         return shift;
253     }
254 
255     private OrderedLR1Tables.Reduce parseReduce(JSONValue value)
256     {
257         Terminal lookahead = parseOnTerminal(value);
258         Alternative alternative = parseRuleAlt(value);
259         const continues = parseContinues(value);
260         OrderedLR1Tables.Reduce reduce = new OrderedLR1Tables.Reduce(lookahead, alternative);
261 
262         reduce.isContinuationAction = continues;
263         return reduce;
264     }
265 
266     private OrderedLR1Tables.Halt parseHalt(JSONValue value)
267     {
268         Terminal lookahead = parseOnTerminal(value);
269         const continues = parseContinues(value);
270         OrderedLR1Tables.Halt halt = new OrderedLR1Tables.Halt(lookahead);
271 
272         halt.isContinuationAction = continues;
273         return halt;
274     }
275 
276     private OrderedLR1Tables.Goto parseGoto(JSONValue value)
277     {
278         Nonterminal lhs = parseOnNonterminal(value);
279         const to = parseTo(value);
280         OrderedLR1Tables.Goto goTo = new OrderedLR1Tables.Goto(lhs, to);
281 
282         return goTo;
283     }
284 
285     private Terminal parseOnTerminal(JSONValue value)
286     {
287         JSONValue[string] object = value.object;
288         const on = object["on"].integer;
289         Terminal terminal = index2Terminal[on];
290 
291         return terminal;
292     }
293 
294     private Nonterminal parseOnNonterminal(JSONValue value)
295     {
296         JSONValue[string] object = value.object;
297         const on = object["on"].integer;
298         Nonterminal lhs = index2Nonterminal[on];
299 
300         return lhs;
301     }
302 
303     private long parseTo(JSONValue value)
304     {
305         JSONValue[string] object = value.object;
306         const to = object["to"].integer;
307 
308         maxState = max(maxState, to); // for final check if all referred stated have been seen
309 
310         return to;
311     }
312 
313     private Alternative parseRuleAlt(JSONValue value)
314     {
315         JSONValue[string] object = value.object;
316         const ruleAlt = object["ruleAlt"].integer;
317         Alternative alternative = index2Alternative[ruleAlt];
318 
319         return alternative;
320     }
321 
322     private bool parseContinues(JSONValue value)
323     {
324         JSONValue[string] object = value.object;
325 
326         if ("continues" in object)
327             return object["continues"].boolean;
328         return false;
329     }
330 
331     /**
332      * Checks whether this.grammar is acceptable for the parser generator.
333      * <p>
334      * The following checks are performed:<br>
335      * (1) that this.grammar is a pure context-free grammar and <br>
336      * (2) that this.grammar is an "extended" context-free grammar,
337      * i.e. its start symbol &lt;ExtendedStartSymbol> has only one alternative
338      * &lt;ExtendedStartSymbol> ::= &lt;StartSymbol> &lt;eofSymbol> such that
339      * &lt;StartSymbol> and &lt;ExtendedStartSymbol> are Nonterminals, &lt;eofSymbol> is a Terminal,
340      * and both &lt;ExtendedStartSymbol> and &lt;eofSymbol> occur only in this grammar rule.
341      * <p>
342      * If this.grammar is not acceptable, the method throws an IllegalArgumentException.
343      */
344     private void checkGrammar(Grammar grammar)
345     {
346         Rule startRule = grammar.ruleOf(grammar.startSymbol);
347 
348         enforce(startRule.alternatives.length == 1,
349             "not an extended grammar");
350 
351         auto startAlternative = cast(Alternative) startRule.alternatives[0];
352 
353         enforce(startAlternative.rhs.length == 2,
354             "not an extended grammar");
355         enforce(cast(Nonterminal)((cast(SymbolNode) startAlternative.rhs[0]).symbol),
356             "not an extended grammar");
357 
358         Symbol extendedStartSymbol = grammar.startSymbol;
359         Symbol eofSymbol = (cast(SymbolNode) startAlternative.rhs[1]).symbol;
360 
361         enforce(cast(Terminal) eofSymbol,
362             "not an extended grammar");
363 
364         foreach (oldRule; grammar.rules)
365         {
366             foreach (alternative; oldRule.alternatives)
367             {
368                 if (alternative == startAlternative)
369                     continue;
370 
371                 foreach (node; alternative.rhs)
372                 {
373                     enforce(cast(SymbolNode) node,
374                         "not a pure context-free grammar");
375 
376                     auto symbolNode = cast(SymbolNode) node;
377 
378                     enforce(symbolNode.symbol != extendedStartSymbol && symbolNode.symbol != eofSymbol,
379                         "not an extended grammar");
380                 }
381             }
382         }
383     }
384 }