1 module gamma.parsgen.lalr1.run.LR1Parser;
2 
3 import gamma.grammar.Alternative;
4 import gamma.grammar.Node;
5 import gamma.grammar.Nonterminal;
6 import gamma.grammar.SymbolNode;
7 import gamma.parsgen.lalr1.OrderedLR1Tables;
8 import gamma.runtime.Scanner;
9 import log;
10 import std.algorithm;
11 import std.bitmanip : BitArray;
12 import std.format;
13 import std.range;
14 
15 private alias Action = OrderedLR1Tables.Action;
16 
17 /**
18  * A *LR(1) parser.
19  * Expects "ordered" LR(1) tables to be passed and realizes automatic error correction according to
20  * J. Röhrich: "Methods for the Automatic Construction of Error Correcting Parsers",
21  *     Acta Informatica 13, 115--139 (1980).
22  *
23  * @author SöKa
24  */
25 public class LR1Parser
26 {
27     private OrderedLR1Tables parserTables;
28 
29     private Scanner scanner;
30 
31     private bool haveLookahead;
32 
33     private int lookahead;
34 
35     private size_t state;
36 
37     private ParserStack stack;
38 
39     private class ParserStack
40     {
41         size_t[] stack;
42 
43         this()
44         {
45             // do nothing
46         }
47 
48         private this(size_t[] stack)
49         {
50             this.stack = stack.dup;
51         }
52 
53         void push(size_t x)
54         {
55             stack ~= x;
56         }
57 
58         size_t top()
59         {
60             return stack.back;
61         }
62 
63         void pop(size_t n)
64         in (n >= stack.length)
65         {
66         	foreach (i; 0 .. n)
67             {
68 				stack.popBack;
69 			}
70         }
71 
72         public Object clone()
73         {
74             return new ParserStack(stack);
75         }
76 
77         public override string toString()
78         {
79             import std.format : format;
80 
81             return format!"%s"(stack);
82         }
83     }
84 
85     public this(OrderedLR1Tables parserTables, Scanner scanner)
86     {
87         this.parserTables = parserTables;
88         this.scanner = scanner;
89         this.haveLookahead = false;
90         this.state = 0;
91         this.stack = new ParserStack;
92     }
93 
94     private void needLookadead()
95     {
96         if (!haveLookahead)
97         {
98             haveLookahead = true;
99             lookahead = scanner.nextToken;
100         }
101     }
102 
103     private Action nextAction()
104     {
105         Action[] sortedParserActionRow = this.parserTables.getSortedParserActionRow(this.state);
106 
107         foreach (action; sortedParserActionRow)
108         {
109             needLookadead;
110             if (action.lookahead.index == this.lookahead)
111                 return action;
112         }
113         return null;
114     }
115 
116     private bool canShift(int terminal)
117     {
118         Action[] sortedParserActionRow = this.parserTables.getSortedParserActionRow(this.state);
119 
120         foreach (action; sortedParserActionRow)
121         {
122             if (action.lookahead.index == terminal)
123                 return true;
124         }
125         return false;
126     }
127 
128     private Action nextContinuationAction()
129     {
130         Action[] sortedParserActionRow = this.parserTables.getSortedParserActionRow(this.state);
131 
132         foreach (action; sortedParserActionRow)
133         {
134             if (action.isContinuationAction)
135                 return action;
136         }
137 
138         assert(false,
139             format!"No continuation action found for state %s"(this.state));
140     }
141 
142     private void reduce(Alternative alt)
143     {
144         this.stack.pop(alt.rhs.length);
145 
146         OrderedLR1Tables.Goto[] gotoRow = this.parserTables.getSortedGotoRow(this.stack.top);
147 
148         foreach (goTo; gotoRow)
149         {
150             if (goTo.lhs.index == (cast(Nonterminal) alt.lhs.symbol).index)
151             {
152                 this.state = goTo.state;
153                 this.stack.push(this.state);
154                 return;
155             }
156         }
157         // TODO: IllegalStateException
158         throw new Exception("Error in reduce action");
159     }
160 
161     private void repairInput()
162     {
163         // Phase 1: Compute a parse continuation given the parser stack at the moment the syntax error was detected.
164         // While computing this, the set of anchor symbol candidates is collected.
165         // The current state and stack of the parser is remembered for later
166         auto stackSnapshot = cast(ParserStack) this.stack.clone;
167         size_t stateSnapshot = this.state;
168         BitArray anchors;
169 
170         while (true)
171         {
172             // Collect all terminal-labeled edges in the LR(0) machine departing from state1 as anchor candidates...
173             Action[] sortedParserActionRow = this.parserTables.getSortedParserActionRow(this.state);
174 
175             if (sortedParserActionRow !is null)
176             {
177                 foreach (action; sortedParserActionRow)
178                 {
179                     if (cast(OrderedLR1Tables.Shift) action)
180                         anchors[action.lookahead.index] = true;
181                 }
182             }
183             anchors[this.parserTables.eof.index] = true; // eof to the anchors to avoid loop at file end
184             // ... and execute the continuation action at this.state.
185 
186             Action action = nextContinuationAction;
187 
188             assert(action !is null,
189                 format!"No continuation action at state %s"(this.state));
190 
191             if (cast(OrderedLR1Tables.Halt) action)
192             {
193                 trace!"(C)Halt";
194                 break;
195             }
196             else if (cast(OrderedLR1Tables.Shift) action)
197             {
198                 OrderedLR1Tables.Shift shiftAction = cast(OrderedLR1Tables.Shift) action;
199                 trace!"(C)Shift %s"(shiftAction.lookahead);
200                 this.state = shiftAction.state;
201                 this.stack.push(this.state);
202             }
203             else if (cast(OrderedLR1Tables.Reduce) action)
204             {
205                 OrderedLR1Tables.Reduce reduceAction = cast(OrderedLR1Tables.Reduce) action;
206 
207                 trace!"(C)Reduce %s ::=%-( %s%)"(reduceAction.alternative.lhs.symbol,
208                     reduceAction.alternative.rhs.map!(node => (cast(SymbolNode) node).symbol));
209                 reduce(reduceAction.alternative);
210                 trace!"%s"(stack);
211             }
212         }
213         // Phase 2: Read ahead in the current input until a terminal symbol from the achors is met.
214         // The tokens thus read are deleted from the input in order to repair it.
215         needLookadead;
216         while (!anchors[this.lookahead])
217         {
218             info!"Deleting %s"(this.parserTables.grammar.terminal(this.lookahead));
219             this.haveLookahead = false;
220             needLookadead;
221         }
222         // Phase 3: Reestablish the initial this.state and this.stack and perform the prefix of the continuation
223         // parse of phase 1 until the anchor (head token) of the remaining input can be shifted.
224         // Any shift actions executed until the anchor is shifted denote tokens to be inserted.
225         this.state = stateSnapshot;
226         this.stack = stackSnapshot;
227         while (true)
228         {
229             if (canShift(this.lookahead))
230                 break;
231 
232             Action action = nextContinuationAction;
233 
234             assert(action !is null,
235                 format!"No continuation action at state %s"(this.state));
236             assert(cast(OrderedLR1Tables.Halt) action,
237                 format!"Expecting a shift or reduce action at state %s"(this.state));
238 
239             if (cast(OrderedLR1Tables.Shift) action)
240             {
241                 auto shiftAction = cast(OrderedLR1Tables.Shift) action;
242 
243                 info!"Inserting %s"(shiftAction.lookahead);
244                 this.state = shiftAction.state;
245                 this.stack.push(this.state);
246             }
247             else if (cast(OrderedLR1Tables.Reduce) action)
248             {
249                 auto reduceAction = cast(OrderedLR1Tables.Reduce) action;
250 
251                 trace!"(I)Reduce %s ::=%-( %s%)"(reduceAction.alternative.lhs.symbol,
252                     reduceAction.alternative.rhs.map!(node => (cast(SymbolNode) node).symbol));
253                 reduce(reduceAction.alternative);
254                 trace!"%s"(stack);
255             }
256         }
257 
258         // The erroneous input has now been repaired.
259         info!"Continuing parse in normal mode.";
260     }
261 
262     public void parse()
263     {
264         stack.push(0);
265         while (true)
266         {
267             // The parser is acting normally: it consumes input and does shift and reduce actions
268             // until a systax error or halt is detected.
269             Action action = nextAction;
270 
271             if (action is null)
272             {
273                 info!"line %s, column %s: Syntax error! Repairing input..."(this.scanner.line, this.scanner.column);
274                 repairInput;
275             }
276             else if (cast(OrderedLR1Tables.Halt) action)
277             {
278                 info!"End of parsing";
279                 return;
280             }
281             else if (cast(OrderedLR1Tables.Shift) action)
282             {
283                 auto shiftAction = cast(OrderedLR1Tables.Shift) action;
284 
285                 trace!"Shift %s"(shiftAction.lookahead);
286                 this.haveLookahead = false;
287                 this.state = shiftAction.state;
288                 this.stack.push(this.state);
289                 trace!"%s"(stack);
290             }
291             else if (cast(OrderedLR1Tables.Reduce) action)
292             {
293                 auto reduceAction = cast(OrderedLR1Tables.Reduce) action;
294 
295                 trace!"Reduce %s ::=%-( %s%)"(reduceAction.alternative.lhs.symbol,
296                     reduceAction.alternative.rhs.map!(node => (cast(SymbolNode) node).symbol));
297                 reduce(reduceAction.alternative);
298                 trace!"%s"(stack);
299             }
300         }
301     }
302 
303 }