1 module gamma.parsgen.lalr1.PennelloDeRemer; 2 3 import gamma.grammar.Alternative; 4 import gamma.grammar.Grammar; 5 import gamma.grammar.GrammarProperties; 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.LRItem; 13 import gamma.parsgen.lalr1.LRMachine; 14 import gamma.parsgen.lalr1.LR1ConflictResolver; 15 import gamma.parsgen.lalr1.LR1ParserGenerator; 16 import gamma.parsgen.lalr1.OrderedLR1Tables; 17 import gamma.parsgen.lalr1.SCCSetComputation; 18 import gamma.util.Indexed; 19 import gamma.util.Position; 20 import log; 21 import std.bitmanip : BitArray; 22 23 private alias State = LRMachine.State; 24 25 private alias Transition = LRMachine.Transition; 26 27 /** 28 * Implementation of Pennello's and DeRemer's efficient LALR(1) look-ahead computation algorithm 29 * given an ("ordered") LR(0) machine. 30 * Covers some extensions to equip the generated LR parsers with automatic error correction according to 31 * 32 * J. Röhrich: "Methods for the Automatic Construction of Error Correcting Parsers", 33 * Acta Informatica 13, 115--139 (1980). 34 * 35 * @author SöKa 36 */ 37 public class PennelloDeRemer : LR1ParserGenerator 38 { 39 private LR1ConflictResolver lr1ConflictResolver; 40 41 private Grammar grammar; 42 43 private GrammarProperties grammarProperties; 44 45 private LRMachine lrMachine; 46 47 private LRMachine.Transition[] nontTransitions; 48 49 private BitArray[] followSet; // [nontTransition.index] 50 51 private LRMachine.Transition[][] includes; // [nontTransition.index] 52 53 private LookbackDependency[] lookback; 54 55 private int[] lookbackIndex; // from=[2*state.index], to=[2*state.index+1] 56 57 public this() 58 { 59 } 60 61 public OrderedLR1Tables computeParser(Grammar grammar, LR1ConflictResolver lr1ConflictResolver) 62 { 63 import std.format : format; 64 65 this.grammar = grammar; 66 this.lr1ConflictResolver = lr1ConflictResolver; 67 68 checkGrammar; 69 this.grammarProperties = new GrammarProperties(this.grammar); 70 71 if (!this.grammarProperties.isReduced) 72 { 73 foreach (nonterminal; this.grammar.nonterminals) { 74 if (!this.grammarProperties.isProductive(nonterminal)) 75 nonPositionMark(format!"Nonterminal %s not productive."(nonterminal)); 76 } 77 foreach (nonterminal; this.grammar.nonterminals) 78 { 79 if (!this.grammarProperties.isReachable(nonterminal)) 80 nonPositionMark(format!"Nonterminal %s not reachable."(nonterminal)); 81 } 82 } 83 84 // TODO: compose single log message 85 trace!"First productive alternatives:"; 86 foreach (nontreminal; grammar.nonterminals) 87 { 88 int i = 0; 89 90 foreach (alternative; grammar.ruleOf(nontreminal).alternatives) 91 { 92 if (this.grammarProperties.isFirstProductiveAlternative(alternative)) 93 trace!"#%s for lhs %s"(i, alternative.lhs.symbol); 94 ++i; 95 } 96 } 97 98 this.lrMachine = new LRMachine(this.grammar, this.grammarProperties); 99 this.lrMachine.computeLR0Machine; 100 101 initLAComputation; 102 computeREAD; 103 computeINCLUDES; 104 computeFOLLOW; 105 computeLOOKBACK; 106 return computeParserTables; 107 } 108 109 /** 110 * Checks whether this.grammar is acceptable for the parser generator. 111 * <p> 112 * The following checks are performed:<br> 113 * (1) that this.grammar is a pure context-free grammar and <br> 114 * (2) that this.grammar is an "extended" context-free grammar, 115 * i.e. its start symbol <ExtendedStartSymbol> has only one alternative 116 * <ExtendedStartSymbol> ::= <StartSymbol> <eofSymbol> such that 117 * <StartSymbol> and <ExtendedStartSymbol> are Nonterminals, <eofSymbol> is a Terminal, 118 * and both <ExtendedStartSymbol> and <eofSymbol> occur only in this grammar rule. 119 */ 120 private void checkGrammar() 121 { 122 Rule startRule = this.grammar.ruleOf(this.grammar.startSymbol); 123 124 if (startRule.alternatives.length != 1) 125 nonPositionMark("Not an extended grammar."); 126 127 auto startAlt = cast(Alternative) startRule.alternatives[0]; 128 129 if (startAlt.rhs is null || startAlt.rhs.length != 2) 130 nonPositionMark("Not an extended grammar."); 131 if (!(cast(Nonterminal) (cast(SymbolNode) startAlt.rhs[0]).symbol)) 132 nonPositionMark("Not an extended grammar."); 133 134 Symbol extendedStartSymbol = this.grammar.startSymbol; 135 Symbol eofSymbol = (cast(SymbolNode) startAlt.rhs[1]).symbol; 136 137 if (!(cast(Terminal) eofSymbol)) 138 nonPositionMark("Not an extended grammar."); 139 140 foreach (rule; this.grammar.rules) 141 { 142 foreach (alternative; rule.alternatives) 143 { 144 if (alternative == startAlt) 145 continue; 146 147 for (size_t i = 0, n = alternative.rhs.length; i < n; ++i) 148 { 149 Node node = alternative.rhs[i]; 150 if (!(cast(SymbolNode) node)) 151 { 152 node.position.markError("Not a pure context-free grammar."); 153 return; 154 } 155 156 auto sn = cast(SymbolNode) node; 157 158 if (sn.symbol == extendedStartSymbol || sn.symbol == eofSymbol) 159 sn.position.markError("Not an extended grammar."); 160 } 161 } 162 } 163 } 164 165 /** 166 * Reports the given message as a "global" problem of this.grammar. 167 * <p> 168 * The problem is reported at the lhs SymbolNode of this.grammar.startSymbol's 169 * first Alternative. 170 * If that Position is null, it is expected that this.grammar is an extended 171 * grammar and that the first SymbolNode of this.grammar.startSymbol's 172 * first Alternative points, from a user's point of view, to the "actual" start 173 * symbol of the grammar. So the problem is reported at that "actual" start symbol's 174 * lhs SymbolNode of its first Alternative. 175 * If this latter Position is also null, the given message is logged with Level.SEVERE. 176 * @param message The problem description text. 177 */ 178 private void nonPositionMark(string message) 179 { 180 if (this.grammar is null) 181 return; 182 183 Position pos = null; 184 Alternative[] alts = this.grammar.ruleOf(this.grammar.startSymbol).alternatives; 185 186 if (alts !is null && alts.length == 1) 187 pos = alts[0].lhs.position; 188 if (pos is null) 189 { 190 Node[] rhs = alts[0].rhs; 191 192 if (rhs !is null && rhs.length == 2 && cast(Nonterminal)(cast(SymbolNode) rhs[0]).symbol) 193 { 194 auto s = cast(Nonterminal)(cast(SymbolNode) rhs[0]).symbol; 195 196 alts = this.grammar.ruleOf(s).alternatives; 197 if (alts !is null) 198 pos = alts[0].lhs.position; 199 } 200 } 201 202 if (pos !is null) 203 pos.markError(message); 204 else 205 error!"%s"(message); 206 } 207 208 private void initLAComputation() 209 { 210 import std.conv : to; 211 212 this.nontTransitions = lrMachine.getNontTransitions; 213 214 int maxNontTransitionIndex = -1; 215 216 foreach (i; 0 .. this.nontTransitions.length) 217 if (this.nontTransitions[i].index.to!int > maxNontTransitionIndex) 218 maxNontTransitionIndex = this.nontTransitions[i].index.to!int; 219 220 this.followSet = new BitArray[maxNontTransitionIndex + 1]; 221 this.includes = new LRMachine.Transition[][maxNontTransitionIndex + 1]; 222 foreach (i; 0 .. this.nontTransitions.length) 223 { 224 LRMachine.Transition t = this.nontTransitions[i]; 225 226 this.followSet[t.index].length = this.grammar.terminals.length; 227 this.includes[t.index] = null; 228 } 229 } 230 231 /** 232 * Computes the "read" relation which associates nonterminal transitions 233 * and (look-ahead) terminal symbols. 234 * <p> 235 * read = reads* directly-reads. 236 */ 237 private void computeREAD() 238 { 239 import std.algorithm : map; 240 import std.array : array; 241 242 // "reads" relation to be traversed by the SCCSetComputation algorithm 243 auto readsRelation = new class SCCSetComputation.TransitionEnumerator 244 { 245 public void visitNeighborsOf(Indexed nontTrans, SCCSetComputation.TransitionWalker walker) 246 { 247 // The "reads" relation is computed on demand. 248 LRMachine.State q = (cast(LRMachine.Transition) nontTrans).to; 249 250 if (q.outgoing !is null) 251 { 252 for (size_t i = 0, n = q.outgoing.length; i < n; ++i) 253 { 254 LRMachine.Transition xTrans = q.outgoing[i]; 255 Symbol x = xTrans.label; 256 257 if (cast(Nonterminal) x && grammarProperties.isNullable(x)) 258 walker.walk(nontTrans, xTrans); 259 } 260 } 261 } 262 }; 263 264 // Set operations for the computation of the "reads" sets 265 auto readSetOps = new class SCCSetComputation.SetOperator 266 { 267 public void initSet(Indexed nontTrans) 268 { 269 // Compute the set of terminals (index) which the LR machine's 270 // nonterminal transition nontTrans "directly-reads". 271 LRMachine.State q = (cast(LRMachine.Transition) nontTrans).to; 272 273 if (q.outgoing !is null) 274 { 275 for (size_t i = 0, n = q.outgoing.length; i < n; ++i) 276 { 277 Symbol x = q.outgoing[i].label; 278 279 if (cast(Terminal) x) 280 this.outer.followSet[nontTrans.index][(cast(Terminal) x).index] = true; 281 } 282 } 283 } 284 285 public void includeSet(Indexed nontTrans1, Indexed nontTrans2) 286 { 287 this.outer.followSet[nontTrans1.index] |= this.outer.followSet[nontTrans2.index]; 288 } 289 }; 290 291 Indexed[] nodes = this.nontTransitions 292 .map!(transition => cast(Indexed) transition) 293 .array; 294 295 SCCSetComputation.computeSets(nodes, readsRelation, readSetOps); 296 } 297 298 /** 299 * Computes the "includes" relation. 300 */ 301 private void computeINCLUDES() 302 { 303 for (size_t i = 0, m = this.nontTransitions.length; i < m; ++i) 304 { 305 LRMachine.Transition qTrans = nontTransitions[i]; 306 LRMachine.State q = qTrans.from; 307 auto lhs = cast(Nonterminal) qTrans.label; 308 309 foreach (alternative; this.grammar.ruleOf(lhs).alternatives) 310 { 311 Node[] rhs = alternative.rhs; 312 size_t k = 0, n = rhs.length; 313 314 while (k < n) 315 { 316 Symbol x = (cast(SymbolNode) rhs[n - k - 1]).symbol; 317 if (cast(Terminal) x) 318 break; 319 ++k; 320 if (!grammarProperties.isNullable(x)) 321 break; 322 } 323 if (k > 0) 324 { 325 LRMachine.State p; 326 int j; 327 328 for (j = 0, p = q; j < n - k; ++j) 329 p = lrMachine.getTransition(p, (cast(SymbolNode) rhs[j]).symbol).to; 330 for (; j < n; ++j) 331 { 332 LRMachine.Transition pTrans = 333 lrMachine.getTransition(p, (cast(SymbolNode) rhs[j]).symbol); 334 335 // pTrans includes qTrans 336 this.includes[pTrans.index] ~= qTrans; 337 p = pTrans.to; 338 } 339 } 340 } 341 } 342 } 343 344 /** 345 * Computes the "follow" relation, which associates nonterminal transitions 346 * and (look-ahead) terminal symbols. 347 * <p> 348 * follow = includes* reads* directly-reads. 349 */ 350 private void computeFOLLOW() 351 { 352 import std.algorithm : map; 353 import std.array : array; 354 355 // "includes" relation to be traversed by the SCCSetComputation algorithm 356 auto includesRelation = new class SCCSetComputation.TransitionEnumerator 357 { 358 public void visitNeighborsOf(Indexed nontTrans, SCCSetComputation.TransitionWalker walker) 359 { 360 foreach (transition; this.outer.includes[nontTrans.index]) 361 { 362 walker.walk(nontTrans, transition); 363 } 364 } 365 }; 366 367 // Set operations for the computation of the "follow" sets 368 auto followSetOps = new class SCCSetComputation.SetOperator 369 { 370 public void initSet(Indexed nontTrans) 371 { 372 // "follow" Set initialization already done! 373 } 374 375 public void includeSet(Indexed nontTrans1, Indexed nontTrans2) 376 { 377 this.outer.followSet[nontTrans1.index] |= this.outer.followSet[nontTrans2.index]; 378 } 379 }; 380 381 Indexed[] nodes = this.nontTransitions 382 .map!(transition => cast(Indexed) transition) 383 .array; 384 385 SCCSetComputation.computeSets(nodes, includesRelation, followSetOps); 386 } 387 388 /** 389 * An instance captures a dependency of the "lookback" relation such that 390 * <p> 391 * (state, alternative) lookback nontTransition. 392 */ 393 private class LookbackDependency 394 { 395 private LRMachine.State state; 396 397 private Alternative alternative; 398 399 private LRMachine.Transition nontTransition; 400 401 this(LRMachine.State state, Alternative alternative, LRMachine.Transition nontTransition) 402 { 403 this.state = state; 404 this.alternative = alternative; 405 this.nontTransition = nontTransition; 406 } 407 } 408 409 /** 410 * Computes the "lookback" relation which has to be combined with the "follow" 411 * relation to yield the "has-LALR-lookahead" relation. "lookback" associates 412 * (LR(0) state, alternative) pairs and nonteminal transitions whereas 413 * "has-LALR-lookahead" associates (LR(0) state, alternative) pairs and 414 * (look-ahead) terminal symbols. 415 * <p> 416 * has-LALR-lookahead = lookback includes* reads* directly-reads. 417 */ 418 private void computeLOOKBACK() 419 { 420 import std.algorithm : sort, SwapStrategy; 421 422 LookbackDependency[] lookback; 423 424 for (size_t i = 0, m = nontTransitions.length; i < m; ++i) 425 { 426 LRMachine.Transition qTrans = nontTransitions[i]; 427 LRMachine.State q = qTrans.from; 428 auto lhs = cast(Nonterminal) qTrans.label; 429 430 foreach (alternative; this.grammar.ruleOf(lhs).alternatives) 431 { 432 Node[] rhs = alternative.rhs; 433 LRMachine.State p = q; 434 435 for (size_t j = 0, n = rhs.length; j < n; ++j) 436 p = lrMachine.getTransition(p, (cast(SymbolNode) rhs[j]).symbol).to; 437 lookback ~= new LookbackDependency(p, alternative, qTrans); 438 } 439 } 440 441 this.lookback = lookback; 442 443 int lookbackPartitioner(LookbackDependency lb1, LookbackDependency lb2) 444 { 445 import std.conv : to; 446 447 int result = lb1.state.index.to!int - lb2.state.index.to!int; 448 449 if (result == 0) 450 result = cast(int) lb1.toHash - cast(int) lb2.toHash; // .index would be better 451 return result; 452 } 453 454 this.lookback.sort!((a, b) => lookbackPartitioner(a, b) < 0, SwapStrategy.stable); 455 this.lookbackIndex = new int[2 * lrMachine.getStates.length]; 456 this.lookbackIndex[] = -1; 457 458 int i = 0; 459 460 while (i < this.lookback.length) 461 { 462 LRMachine.State s = this.lookback[i].state; 463 this.lookbackIndex[2 * s.index] = i; 464 465 int j = i + 1; 466 467 while (j < this.lookback.length && this.lookback[j].state == s) 468 ++j; 469 this.lookbackIndex[2 * s.index + 1] = j; 470 i = j; 471 } 472 473 } 474 475 private BitArray lalrLookaheadsFor(LRItem item, LRMachine.State state) 476 { 477 BitArray lalrLookaheads; 478 int k1 = this.lookbackIndex[2 * state.index]; 479 int k2 = this.lookbackIndex[2 * state.index + 1]; 480 481 lalrLookaheads.length = this.grammar.terminals.length; 482 for (int k = k1; k < k2; ++k) 483 if (this.lookback[k].alternative == item.alt) 484 lalrLookaheads |= this.followSet[lookback[k].nontTransition.index]; 485 return lalrLookaheads; 486 } 487 488 /** 489 * Computes the shift and reduce actions of the resulting canonical LALR(1) parser. 490 */ 491 private OrderedLR1Tables computeParserTables() 492 { 493 State[] states = this.lrMachine.getStates; 494 OrderedLR1Tables.Action[] parserActionRow = new OrderedLR1Tables.Action[grammar.terminals.length]; 495 size_t[] parserActionRowNext = new size_t[grammar.terminals.length + 1]; 496 size_t[] parserActionRowPrev = new size_t[grammar.terminals.length + 1]; 497 size_t HEAD = grammar.terminals.length; 498 499 return new class (grammar) OrderedLR1Tables 500 { 501 private Grammar grammar_; 502 503 private Action[][] parserActionRows; 504 505 private Goto[][] gotoRows; 506 507 private Terminal eofSymbol; 508 509 this(Grammar grammar) 510 { 511 this.grammar_ = grammar; 512 this.parserActionRows = new Action[][states.length]; 513 this.gotoRows = new Goto[][states.length]; 514 this.eofSymbol = cast(Terminal) 515 (cast(SymbolNode)(cast(Alternative) grammar.ruleOf(grammar.startSymbol).alternatives[0]).rhs[1]) 516 .symbol; 517 } 518 519 public Grammar grammar() 520 { 521 return this.grammar_; 522 } 523 524 public size_t stateCount() 525 { 526 return states.length; 527 } 528 529 public Terminal eof() 530 { 531 return eofSymbol; 532 } 533 534 private void unlinkFromParserActionList(size_t lookaheadIndex) 535 { 536 parserActionRowNext[parserActionRowPrev[lookaheadIndex]] = parserActionRowNext[lookaheadIndex]; 537 parserActionRowPrev[parserActionRowNext[lookaheadIndex]] = parserActionRowPrev[lookaheadIndex]; 538 } 539 540 private void prependToParserActionList(size_t lookaheadIndex) 541 { 542 parserActionRowNext[lookaheadIndex] = parserActionRowNext[HEAD]; 543 parserActionRowPrev[lookaheadIndex] = parserActionRowPrev[parserActionRowNext[HEAD]]; 544 parserActionRowPrev[parserActionRowNext[HEAD]] = lookaheadIndex; 545 parserActionRowNext[HEAD] = lookaheadIndex; 546 } 547 548 private void enterReduce(size_t stateIndex, Alternative alt, Terminal lookahead) 549 { 550 size_t lookaheadIndex = lookahead.index; 551 552 if (cast(OrderedLR1Tables.Reduce) parserActionRow[lookaheadIndex]) 553 { 554 auto reduce = cast(OrderedLR1Tables.Reduce) parserActionRow[lookaheadIndex]; 555 Alternative origAlt = reduce.alternative; 556 557 if (alt != origAlt) 558 { 559 Object o = lr1ConflictResolver.resolveReduceReduceConflict(origAlt, alt, 560 grammar.terminal(lookaheadIndex), 561 stateIndex); 562 563 if (o == alt) 564 { 565 // action already entered; prepend anew (1st in list -> continuation!) 566 unlinkFromParserActionList(lookaheadIndex); 567 prependToParserActionList(lookaheadIndex); 568 reduce.alternative = alt; 569 } 570 else if (o != origAlt) 571 { 572 unlinkFromParserActionList(lookaheadIndex); 573 parserActionRow[lookaheadIndex] = null; 574 } 575 } 576 } 577 else if (cast(OrderedLR1Tables.Shift) parserActionRow[lookaheadIndex]) 578 { 579 auto shift = cast(OrderedLR1Tables.Shift) parserActionRow[lookaheadIndex]; 580 Object o = lr1ConflictResolver.resolveShiftReduceConflict(shift.lookahead, alt, stateIndex); 581 582 if (o != shift.lookahead) 583 { 584 if (o == alt) 585 { 586 unlinkFromParserActionList(lookaheadIndex); 587 prependToParserActionList(lookaheadIndex); 588 parserActionRow[lookaheadIndex] = 589 new OrderedLR1Tables.Reduce(grammar.terminal(lookaheadIndex), alt); 590 } 591 else 592 { 593 unlinkFromParserActionList(lookaheadIndex); 594 parserActionRow[lookaheadIndex] = null; 595 } 596 } 597 } 598 else if (parserActionRow[lookaheadIndex] !is null) 599 { 600 // (parserActionRow[lookaheadIndex] instanceof OrderedLR1Tables.Halt) 601 lr1ConflictResolver.noteHaltConflictOn(alt, stateIndex); 602 unlinkFromParserActionList(lookaheadIndex); 603 prependToParserActionList(lookaheadIndex); 604 parserActionRow[lookaheadIndex] = new OrderedLR1Tables.Halt(eof); 605 } 606 else 607 { 608 // (parserActionRow[lookaheadIndex] is null) 609 parserActionRow[lookaheadIndex] = 610 new OrderedLR1Tables.Reduce(grammar.terminal(lookaheadIndex), alt); 611 prependToParserActionList(lookaheadIndex); 612 } 613 } 614 615 private void enterShift(size_t stateIndex, Terminal lookahead, size_t toStateIndex) 616 { 617 size_t lookaheadIndex = lookahead.index; 618 OrderedLR1Tables.Action action = parserActionRow[lookaheadIndex]; 619 620 if (cast(OrderedLR1Tables.Shift) action) 621 { 622 // action already entered; prepend anew (1st in list -> continuation!) 623 unlinkFromParserActionList(lookaheadIndex); 624 prependToParserActionList(lookaheadIndex); 625 } 626 else if (parserActionRow[lookaheadIndex] !is null) 627 { 628 // parserActionRow[lookaheadIndex] instanceof OrderedLR1Tables.Reduce 629 auto reduce = cast(OrderedLR1Tables.Reduce) parserActionRow[lookaheadIndex]; 630 Alternative origAlt = reduce.alternative; 631 Object o = lr1ConflictResolver.resolveShiftReduceConflict(lookahead, origAlt, stateIndex); 632 633 if (o == lookahead) 634 { 635 unlinkFromParserActionList(lookaheadIndex); 636 prependToParserActionList(lookaheadIndex); 637 parserActionRow[lookaheadIndex] = new OrderedLR1Tables.Shift(lookahead, toStateIndex); 638 } 639 else if (o != origAlt) 640 { 641 unlinkFromParserActionList(lookaheadIndex); 642 parserActionRow[lookaheadIndex] = null; 643 } 644 } 645 else 646 { 647 // (parserActionRow[lookaheadIndex] is null) 648 parserActionRow[lookaheadIndex] = new OrderedLR1Tables.Shift(lookahead, toStateIndex); 649 prependToParserActionList(lookaheadIndex); 650 } 651 } 652 653 private void enterHalt(size_t stateIndex) 654 { 655 size_t lookaheadIndex = eof.index; // PROBLEM!! eof not part of original grammar; eof.index?? 656 657 if (parserActionRow[lookaheadIndex] !is null) 658 { 659 // cast(OrderedLR1Tables.Reduce) parserActionRow[lookaheadIndex] 660 auto reduce = cast(OrderedLR1Tables.Reduce) parserActionRow[lookaheadIndex]; 661 Alternative origAlt = reduce.alternative; 662 663 lr1ConflictResolver.noteHaltConflictOn(origAlt, stateIndex); 664 unlinkFromParserActionList(lookaheadIndex); 665 } 666 parserActionRow[lookaheadIndex] = new OrderedLR1Tables.Halt(eof); 667 prependToParserActionList(lookaheadIndex); 668 } 669 670 public Action[] getSortedParserActionRow(size_t stateIndex) 671 { 672 if (parserActionRows[stateIndex] !is null) 673 return parserActionRows[stateIndex]; 674 675 auto state = cast(LRMachine.State) states[stateIndex]; 676 677 parserActionRow[] = null; 678 parserActionRowNext[] = -1; 679 parserActionRowPrev[] = -1; 680 parserActionRowNext[HEAD] = HEAD; // doubly linked list of ... 681 parserActionRowPrev[HEAD] = HEAD; // ... parserActionRow[] entries 682 683 // Make parser action table entries in reverse order of items in ordered item list 684 for (size_t i = state.orderedClosureItems.length; i > 0; --i) 685 { 686 LRItem item = state.orderedClosureItems[i - 1]; 687 688 if (item.complete) 689 { 690 BitArray bs = this.outer.lalrLookaheadsFor(item, state); 691 692 foreach (t; bs.bitsSet) 693 enterReduce(state.index, item.alt, grammar.terminal(t)); 694 } 695 else if (item.symbolBehindDot == eof) 696 enterHalt(state.index); 697 else if (cast(Terminal) item.symbolBehindDot) 698 enterShift(state.index, 699 cast(Terminal) item.symbolBehindDot, 700 lrMachine.getTransition(state, item.symbolBehindDot).to.index); 701 } 702 // Set Action.isContinuationAction field(s) in second pass 703 size_t ca = parserActionRowNext[HEAD]; 704 705 if (ca != HEAD) 706 { 707 if (cast(OrderedLR1Tables.Reduce) parserActionRow[ca]) 708 { 709 auto reduce = cast(OrderedLR1Tables.Reduce) parserActionRow[ca]; 710 Alternative alt = reduce.alternative; 711 712 for (; ca != HEAD; ca = parserActionRowNext[ca]) 713 { 714 OrderedLR1Tables.Action a = parserActionRow[ca]; 715 if (cast(OrderedLR1Tables.Reduce) a 716 && (cast(OrderedLR1Tables.Reduce) a).alternative == alt) 717 a.isContinuationAction = true; 718 } 719 } 720 else 721 parserActionRow[ca].isContinuationAction = true; 722 } 723 724 Action[] rowAsList; 725 726 for (size_t t = 0; t < parserActionRow.length; ++t) 727 if (parserActionRow[t] !is null) 728 rowAsList ~= parserActionRow[t]; 729 parserActionRows[stateIndex] = rowAsList; 730 return parserActionRows[stateIndex]; 731 } 732 733 public Goto[] getSortedGotoRow(size_t stateIndex) 734 { 735 if (gotoRows[stateIndex] !is null) 736 return gotoRows[stateIndex]; 737 738 auto state = cast(LRMachine.State) states[stateIndex]; 739 740 Goto[] rowAsList; 741 742 // Output nonterminal transitions 743 if (state.outgoing !is null) 744 { 745 for (size_t i = 0; i < state.outgoing.length; ++i) 746 { 747 LRMachine.Transition transition = state.outgoing[i]; 748 749 if (cast(Nonterminal) transition.label) 750 { 751 rowAsList ~= 752 new OrderedLR1Tables.Goto(cast(Nonterminal) transition.label, transition.to.index); 753 } 754 } 755 } 756 gotoRows[stateIndex] = rowAsList; 757 return gotoRows[stateIndex]; 758 } 759 }; 760 } 761 }