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 }