[pseudo] Start rules are `_ := start-symbol EOF`, improve recovery.

[sammccall]

Summary

Previously we were calling glrRecover() ad-hoc at the end of input.
Two main problems with this:

• glrRecover() on two separate code paths is inelegant
• We may have to recover several times in succession (e.g. to exit from nested scopes), so we need a loop at end-of-file

Having an actual shift action for an EOF terminal allows us to handle
both concerns in the main shift/recover/reduce loop.

This revealed a recovery design bug where recovery could enter a loop by
repeatedly choosing the same parent to identically recover from.
Addressed this by allowing each node to be used as a recovery base once.

[hokein]

+1 on this change, it would make the expose-lookahead-index-to-guard change easier.

clang-tools-extra/pseudo/include/clang-pseudo/GLR.h

74

haven't look at it deeply -- is this bug related to this eof change? This looks like a different bug in recovery.

clang-tools-extra/pseudo/lib/Forest.cpp

191

nit: in the underlying TokenStream implementation, tokens() has a trailing eof token, I think we can fold this into the above loop (if we expose a token_eof() method in TokenStream). Not sure we should do this.

[sammccall]

clang-tools-extra/pseudo/include/clang-pseudo/GLR.h

74

They're "related" in that they both fix repeated-recovery scenarios.
This change fixes that we can hit an infinite loop when applying recovery repeatedly.
The eof change fixes that recovery is (erroneously) only applied once at eof.

I hoped to cover them with the same testcase, which tests repeated recovery at EOF. I can extract this change with a separate test if you like, though it will be very similar to the one I have here.

clang-tools-extra/pseudo/lib/Forest.cpp

191

I think this doesn't generalize well... at the moment we're parsing the whole stream, but in future we likely want to parse a subrange (pp-disabled regions?). In such a case we would still want the terminating EOF terminal as a device for parsing, even though there's no corresponding token.

[hokein]

clang-tools-extra/pseudo/include/clang-pseudo/GLR.h

74

This change fixes that we can hit an infinite loop when applying recovery repeatedly.

I'm more worried about this bug, I think this is an important bug, worth a separate patch to fix it, right now it looks like a join-effort in the eof change.

The eof change fixes that recovery is (erroneously) only applied once at eof.

Not sure I follow this. I think the eof change is basically to remove a technical debt (avoid the special case and repeated code after main parsing loop). Am I missing something?

clang-tools-extra/pseudo/lib/Forest.cpp

191

oh, ok, that's fair enough.

clang-tools-extra/pseudo/test/lr-build-basic.test

16–18

there should be a State 4 (with a _ := expr EOF • item)

clang-tools-extra/pseudo/unittests/GLRTest.cpp

622

remove the debugging statement.

[sammccall]

clang-tools-extra/pseudo/include/clang-pseudo/GLR.h

74

Not sure I follow this. I think the eof change is basically to remove a technical debt (avoid the special case and repeated code after main parsing loop). Am I missing something?

There's a bug lurking in that tech debt: if recovery does not advance the cursor then we should go around the loop again, but if it happens at eof then (in the old code) there's no loop to go around at all.

clang-tools-extra/pseudo/include/clang-pseudo/GLR.h

struct GSS {
   // Nodes are not exactly pushed and popped on the stack: pushing is just
   // allocating a new head node with a parent pointer to the old head. Popping
   // is just forgetting about a node and remembering its parent instead.
   struct alignas(struct Node *) Node {
     // LR state describing how parsing should continue from this head.
     LRTable::StateID State;
     // Used internally to track reachability during garbage collection.
     bool GCParity;
+    // Have we already used this node for error recovery? (prevents loops)
+    mutable bool Recovered = false;
     // Number of the parents of this node.
     // The parents hold previous parsed symbols, and may resume control after
     // this node is reduced.
     unsigned ParentCount;
     // The parse node for the last parsed symbol.
     // This symbol appears on the left of the dot in the parse state's items.
     // (In the literature, the node is attached to the *edge* to the parent).
     const ForestNode *Payload = nullptr;

clang-tools-extra/pseudo/lib/Forest.cpp

std::function<void(const ForestNode *, Token::Index, llvm::Optional<SymbolID>,
       };
   LineDecoration LineDec;
   Dump(this, KEnd, llvm::None, LineDec);
   return Result;
 }
 
 llvm::ArrayRef<ForestNode>
 ForestArena::createTerminals(const TokenStream &Code) {
-  ForestNode *Terminals = Arena.Allocate<ForestNode>(Code.tokens().size());
+  ForestNode *Terminals = Arena.Allocate<ForestNode>(Code.tokens().size() + 1);
   size_t Index = 0;
   for (const auto &T : Code.tokens()) {
     new (&Terminals[Index])
         ForestNode(ForestNode::Terminal, tokenSymbol(T.Kind),
                    /*Start=*/Index, /*TerminalData*/ 0);
     ++Index;
   }
+  // Include an `eof` terminal.
+  // This is important to drive the final shift/recover/reduce loop.
+  new (&Terminals[Index])
+      ForestNode(ForestNode::Terminal, tokenSymbol(tok::eof),
+                 /*Start=*/Index, /*TerminalData*/ 0);
+  ++Index;
   NodeCount = Index;
   return llvm::makeArrayRef(Terminals, Index);
 }
 
 } // namespace pseudo
 } // namespace clang

clang-tools-extra/pseudo/lib/GLR.cpp

void glrRecover(llvm::ArrayRef<const GSS::Node *> OldHeads,
   // (e.g. in the expr recovery above, stay inside the parentheses).
   // FIXME: find a more satisfying way to avoid such false recovery.
   // FIXME: Add a test for spurious recovery once tests can define strategies.
   std::vector<const ForestNode *> Path;
   llvm::DenseSet<const GSS::Node *> Seen;
   auto WalkUp = [&](const GSS::Node *N, Token::Index NextTok, auto &WalkUp) {
     if (!Seen.insert(N).second)
       return;
+    if (!N->Recovered) { // Don't recover the same way twice!
       for (auto Strategy : Lang.Table.getRecovery(N->State)) {
         Options.push_back(PlaceholderRecovery{
             NextTok,
             Strategy.Result,
             Strategy.Strategy,
             N,
             Path,
         });
         LLVM_DEBUG(llvm::dbgs()
                    << "Option: recover " << Lang.G.symbolName(Strategy.Result)
                    << " at token " << NextTok << "\n");
       }
+    }
     Path.push_back(N->Payload);
     for (const GSS::Node *Parent : N->parents())
       WalkUp(Parent, N->Payload->startTokenIndex(), WalkUp);
     Path.pop_back();
   };
   for (auto *N : OldHeads)
     WalkUp(N, TokenIndex, WalkUp);
 
void glrRecover(llvm::ArrayRef<const GSS::Node *> OldHeads,
   });
   // FIXME: in general, we might have the same Option->Symbol multiple times,
   // and we risk creating redundant Forest and GSS nodes.
   // We also may inadvertently set up the next glrReduce to create a sequence
   // node duplicating an opaque node that we're creating here.
   // There are various options, including simply breaking ties between options.
   // For now it's obscure enough to ignore.
   for (const PlaceholderRecovery *Option : BestOptions) {
+    Option->RecoveryNode->Recovered = true;
     const ForestNode &Placeholder =
         Params.Forest.createOpaque(Option->Symbol, RecoveryRange->Begin);
     LRTable::StateID OldState = Option->RecoveryNode->State;
     LRTable::StateID NewState =
         isToken(Option->Symbol)
             ? *Lang.Table.getShiftState(OldState, Option->Symbol)
             : *Lang.Table.getGoToState(OldState, Option->Symbol);
     const GSS::Node *NewHead =
bool popAndPushTrivial() {
     }
     if (!canReduce(Rule, *RID, TempSequence))
       return true; // reduction is not available
     const ForestNode *Parsed =
         &Params.Forest.createSequence(Rule.Target, *RID, TempSequence);
     auto NextState = Lang.Table.getGoToState(Base->State, Rule.Target);
     assert(NextState.has_value() && "goto must succeed after reduce!");
     Heads->push_back(Params.GSStack.addNode(*NextState, Parsed, {Base}));
+    LLVM_DEBUG(llvm::dbgs()
+               << "  Reduce (trivial) " << Lang.G.dumpRule(*RID) << "\n"
+               << "    --> S" << Heads->back()->State << "\n");
     return true;
   }
 };
 
 } // namespace
 
 const ForestNode &glrParse(const ParseParams &Params, SymbolID StartSymbol,
                            const Language &Lang) {
for (unsigned I = 0; I < Terminals.size();) {
     if (NextHeads.empty()) {
       // The reduction in the previous round was constrained by lookahead.
       // On valid code this only rejects dead ends, but on broken code we should
       // consider all possibilities.
       //
       // We discard all heads formed by reduction, and recreate them without
       // this constraint. This may duplicate some nodes, but it's rare.
       LLVM_DEBUG(llvm::dbgs() << "Shift failed, will attempt recovery. "
-                                 "Re-reducing without lookahead.");
+                                 "Re-reducing without lookahead.\n");
       Heads.resize(HeadsPartition);
       Reduce(Heads, /*allow all reductions*/ tokenSymbol(tok::unknown));
 
       glrRecover(Heads, I, Params, Lang, NextHeads);
       if (NextHeads.empty())
         // FIXME: Ensure the `_ := start-symbol` rules have a fallback
         // error-recovery strategy attached. Then this condition can't happen.
         return Params.Forest.createOpaque(StartSymbol, /*Token::Index=*/0);
     } else
       ++I;
 
     // Form nonterminals containing the token we just consumed.
     SymbolID Lookahead =
         I == Terminals.size() ? tokenSymbol(tok::eof) : Terminals[I].symbol();
     HeadsPartition = NextHeads.size();
     Reduce(NextHeads, Lookahead);
     // Prepare for the next token.
     std::swap(Heads, NextHeads);
     NextHeads.clear();
     MaybeGC();
   }
   LLVM_DEBUG(llvm::dbgs() << llvm::formatv("Reached eof\n"));
 
-  // The parse was successful if we're in state `_ := start-symbol .`
-  auto AcceptState = Lang.Table.getGoToState(StartState, StartSymbol);
-  assert(AcceptState.has_value() && "goto must succeed after start symbol!");
+  // The parse was successful if in state `_ := start-symbol EOF .`
+  // The GSS parent has `_ := start-symbol . EOF`; its payload is the parse.
+  auto AfterStart = Lang.Table.getGoToState(StartState, StartSymbol);
+  assert(AfterStart.has_value() && "goto must succeed after start symbol!");
+  auto Accept = Lang.Table.getShiftState(*AfterStart, tokenSymbol(tok::eof));
+  assert(Accept.has_value() && "shift EOF must succeed!");
   auto SearchForAccept = [&](llvm::ArrayRef<const GSS::Node *> Heads) {
     const ForestNode *Result = nullptr;
     for (const auto *Head : Heads) {
-      if (Head->State == *AcceptState) {
-        assert(Head->Payload->symbol() == StartSymbol);
+      if (Head->State == *Accept) {
+        assert(Head->Payload->symbol() == tokenSymbol(tok::eof));
         assert(Result == nullptr && "multiple results!");
-        Result = Head->Payload;
+        Result = Head->parents().front()->Payload;
+        assert(Result->symbol() == StartSymbol);
       }
     }
     return Result;
   };
   if (auto *Result = SearchForAccept(Heads))
     return *Result;
-  // Failed to parse the input, attempt to run recovery.
-  // FIXME: this awkwardly repeats the recovery in the loop, when shift fails.
-  // More elegant is to include EOF in the token stream, and make the
-  // augmented rule: `_ := translation-unit EOF`. In this way recovery at EOF
-  // would not be a special case: it show up as a failure to shift the EOF
-  // token.
-  unsigned I = Terminals.size();
-  glrRecover(Heads, I, Params, Lang, NextHeads);
-  Reduce(NextHeads, tokenSymbol(tok::eof));
-  if (auto *Result = SearchForAccept(NextHeads))
-    return *Result;
-
   // We failed to parse the input, returning an opaque forest node for recovery.
   // FIXME: as above, we can add fallback error handling so this is impossible.
   return Params.Forest.createOpaque(StartSymbol, /*Token::Index=*/0);
 }
 
 void glrReduce(std::vector<const GSS::Node *> &Heads, SymbolID Lookahead,
                const ParseParams &Params, const Language &Lang) {
   // Create a new GLRReduce each time for tests, performance doesn't matter.
   GLRReduce{Params, Lang}(Heads, Lookahead);
 }
 
 const GSS::Node *GSS::addNode(LRTable::StateID State, const ForestNode *Symbol,
 
                               llvm::ArrayRef<const Node *> Parents) {
-  Node *Result = new (allocate(Parents.size()))
-      Node({State, GCParity, static_cast<uint16_t>(Parents.size())});
+  Node *Result = new (allocate(Parents.size())) Node();
+  Result->State = State;
+  Result->GCParity = GCParity;
+  Result->ParentCount = Parents.size();
   Alive.push_back(Result);
   ++NodesCreated;
   Result->Payload = Symbol;
   if (!Parents.empty())
     llvm::copy(Parents, reinterpret_cast<const Node **>(Result + 1));
   return Result;
 }
 

clang-tools-extra/pseudo/lib/cxx/cxx.bnf

 #
 # [1] https://isocpp.org/files/papers/N4860.pdf
 
 # _ lists all the start-symbols which we support parsing.
 #
 # We list important nonterminals as start symbols, rather than doing it for all
 # nonterminals by default, this reduces the number of states by 30% and LRTable
 # actions by 16%.
-_ := translation-unit
-_ := statement-seq
-_ := declaration-seq
+_ := translation-unit EOF
+_ := statement-seq EOF
+_ := declaration-seq EOF
 
 # gram.key
 #! we don't distinguish between namespaces and namespace aliases, as it's hard
 #! and uninteresting.
 namespace-name := IDENTIFIER
 template-name := IDENTIFIER
 
 # gram.basic

clang-tools-extra/pseudo/lib/grammar/LRGraph.cpp

LRGraph LRGraph::buildLR0(const Grammar &G) {
   auto RRange = G.table().Nonterminals[G.underscore()].RuleRange;
   for (RuleID RID = RRange.Start; RID < RRange.End; ++RID) {
     auto StartState = std::vector<Item>{Item::start(RID, G)};
     auto Result = Builder.insert(std::move(StartState));
     assert(Result.second && "State must be new");
     PendingStates.push_back(Result.first);
 
     const Rule &StartRule = G.lookupRule(RID);
-    assert(StartRule.Size == 1 &&
-           "Start rule must have exactly one symbol in its body!");
+    assert(StartRule.Size == 2 &&
+           StartRule.seq().back() == tokenSymbol(tok::eof) &&
+           "Start rule must be of the form `_ := start-symbol EOF`!");
     Builder.addStartState(StartRule.seq().front(), Result.first);
   }
 
   while (!PendingStates.empty()) {
     auto StateID = PendingStates.back();
     PendingStates.pop_back();
     for (auto Next : nextAvailableKernelItems(Builder.find(StateID), G)) {
       auto Insert = Builder.insert(Next.second);

clang-tools-extra/pseudo/test/lr-build-basic.test

-_ := expr
+_ := expr EOF
 expr := id
 id := IDENTIFIER
 
 # RUN: clang-pseudo -grammar %s -print-graph | FileCheck %s --check-prefix=GRAPH
 #      GRAPH: States:
 # GRAPH-NEXT: State 0
-# GRAPH-NEXT:     _ :=  • expr
+# GRAPH-NEXT:     _ :=  • expr EOF
 # GRAPH-NEXT:     expr :=  • id
 # GRAPH-NEXT:     id :=  • IDENTIFIER
 # GRAPH-NEXT: State 1
-# GRAPH-NEXT:     _ := expr • 
+# GRAPH-NEXT:     _ := expr • EOF
 # GRAPH-NEXT: State 2
 # GRAPH-NEXT:     expr := id • 
 # GRAPH-NEXT: State 3
 # GRAPH-NEXT:     id := IDENTIFIER • 
+# GRAPH-NEXT: State 4
+# GRAPH-NEXT:     _ := expr EOF • 
 
 # RUN: clang-pseudo -grammar %s -print-table | FileCheck %s --check-prefix=TABLE
 #      TABLE: LRTable:
 # TABLE-NEXT: State 0
 # TABLE-NEXT:     IDENTIFIER: shift state 3
 # TABLE-NEXT:     expr: go to state 1
 # TABLE-NEXT:     id: go to state 2
 # TABLE-NEXT: State 1
+# TABLE-NEXT:     EOF: shift state 4
 # TABLE-NEXT: State 2
-# TABLE-NEXT:     EOF: reduce by rule 1 'expr := id'
+# TABLE-NEXT:     EOF: reduce by rule 2 'expr := id'
 # TABLE-NEXT: State 3
-# TABLE-NEXT:     EOF: reduce by rule 0 'id := IDENTIFIER'
+# TABLE-NEXT:     EOF: reduce by rule 1 'id := IDENTIFIER'
+# TABLE-NEXT: State 4

clang-tools-extra/pseudo/test/lr-build-conflicts.test

-_ := expr
+_ := expr EOF
 expr := expr - expr  # S/R conflict at state 4 on '-' token
 expr := IDENTIFIER
 
 # RUN: clang-pseudo -grammar %s -print-graph | FileCheck %s --check-prefix=GRAPH
 #      GRAPH: States
 # GRAPH-NEXT: State 0
+# GRAPH-NEXT:     _ :=  • expr EOF
 # GRAPH-NEXT:     expr :=  • expr - expr
-# GRAPH-NEXT:     _ :=  • expr
 # GRAPH-NEXT:     expr :=  • IDENTIFIER
 # GRAPH-NEXT: State 1
-# GRAPH-NEXT:     _ := expr • 
+# GRAPH-NEXT:     _ := expr • EOF
 # GRAPH-NEXT:     expr := expr • - expr
 # GRAPH-NEXT: State 2
 # GRAPH-NEXT:     expr := IDENTIFIER • 
 # GRAPH-NEXT: State 3
+# GRAPH-NEXT:     _ := expr EOF •
+# GRAPH-NEXT: State 4
 # GRAPH-NEXT:     expr :=  • expr - expr
 # GRAPH-NEXT:     expr := expr - • expr
 # GRAPH-NEXT:     expr :=  • IDENTIFIER
-# GRAPH-NEXT: State 4
+# GRAPH-NEXT: State 5
 # GRAPH-NEXT:     expr := expr - expr • 
 # GRAPH-NEXT:     expr := expr • - expr
 # GRAPH-NEXT: 0 ->[expr] 1
 # GRAPH-NEXT: 0 ->[IDENTIFIER] 2
-# GRAPH-NEXT: 1 ->[-] 3
-# GRAPH-NEXT: 3 ->[expr] 4
-# GRAPH-NEXT: 3 ->[IDENTIFIER] 2
-# GRAPH-NEXT: 4 ->[-] 3
+# GRAPH-NEXT: 1 ->[EOF] 3
+# GRAPH-NEXT: 1 ->[-] 4
+# GRAPH-NEXT: 4 ->[expr] 5
+# GRAPH-NEXT: 4 ->[IDENTIFIER] 2
+# GRAPH-NEXT: 5 ->[-] 4
 
 # RUN: clang-pseudo -grammar %s -print-table | FileCheck %s --check-prefix=TABLE
 #      TABLE: LRTable:
 # TABLE-NEXT: State 0
 # TABLE-NEXT:     IDENTIFIER: shift state 2
 # TABLE-NEXT:     expr: go to state 1
 # TABLE-NEXT: State 1
-# TABLE-NEXT:     -: shift state 3
+# TABLE-NEXT:     EOF: shift state 3
+# TABLE-NEXT:     -: shift state 4
 # TABLE-NEXT: State 2
-# TABLE-NEXT:     EOF -: reduce by rule 1 'expr := IDENTIFIER'
+# TABLE-NEXT:     EOF -: reduce by rule 2 'expr := IDENTIFIER'
 # TABLE-NEXT: State 3
-# TABLE-NEXT:     IDENTIFIER: shift state 2
-# TABLE-NEXT:     expr: go to state 4
 # TABLE-NEXT: State 4
-# TABLE-NEXT:     -: shift state 3
-# TABLE-NEXT:     EOF -: reduce by rule 0 'expr := expr - expr'
+# TABLE-NEXT:     IDENTIFIER: shift state 2
+# TABLE-NEXT:     expr: go to state 5
+# TABLE-NEXT: State 5
+# TABLE-NEXT:     -: shift state 4
+# TABLE-NEXT:     EOF -: reduce by rule 1 'expr := expr - expr'

clang-tools-extra/pseudo/unittests/ForestTest.cpp

 
 protected:
   Grammar G;
   std::vector<std::string> Diags;
 };
 
 TEST_F(ForestTest, DumpBasic) {
   build(R"cpp(
-    _ := add-expression
+    _ := add-expression EOF
     add-expression := id-expression + id-expression
     id-expression := IDENTIFIER
   )cpp");
   ASSERT_TRUE(Diags.empty());
   ForestArena Arena;
   const auto &TS =
       cook(lex("a + b", clang::LangOptions()), clang::LangOptions());
 
   auto T = Arena.createTerminals(TS);
-  ASSERT_EQ(T.size(), 3u);
+  ASSERT_EQ(T.size(), 4u);
   const auto *Left = &Arena.createSequence(
       symbol("id-expression"), ruleFor("id-expression"), {&T.front()});
   const auto *Right = &Arena.createSequence(symbol("id-expression"),
                                             ruleFor("id-expression"), {&T[2]});
 
   const auto *Add =
       &Arena.createSequence(symbol("add-expression"), ruleFor("add-expression"),
                             {Left, &T[1], Right});
   EXPECT_EQ(Add->dumpRecursive(G, true),
             "[  0, end) add-expression := id-expression + id-expression\n"
             "[  0,   1) ├─id-expression~IDENTIFIER := tok[0]\n"
             "[  1,   2) ├─+ := tok[1]\n"
             "[  2, end) └─id-expression~IDENTIFIER := tok[2]\n");
   EXPECT_EQ(Add->dumpRecursive(G, false),
             "[  0, end) add-expression := id-expression + id-expression\n"
             "[  0,   1) ├─id-expression := IDENTIFIER\n"
             "[  0,   1) │ └─IDENTIFIER := tok[0]\n"
             "[  1,   2) ├─+ := tok[1]\n"
             "[  2, end) └─id-expression := IDENTIFIER\n"
             "[  2, end)   └─IDENTIFIER := tok[2]\n");
 }
 
 TEST_F(ForestTest, DumpAmbiguousAndRefs) {
   build(R"cpp(
-    _ := type
-    type := class-type # rule 3
-    type := enum-type # rule 4
+    _ := type EOF
+    type := class-type # rule 4
+    type := enum-type # rule 5
     class-type := shared-type
     enum-type := shared-type
     shared-type := IDENTIFIER)cpp");
   ASSERT_TRUE(Diags.empty());
   ForestArena Arena;
   const auto &TS = cook(lex("abc", clang::LangOptions()), clang::LangOptions());
 
   auto Terminals = Arena.createTerminals(TS);
-  ASSERT_EQ(Terminals.size(), 1u);
+  ASSERT_EQ(Terminals.size(), 2u);
 
   const auto *SharedType = &Arena.createSequence(
       symbol("shared-type"), ruleFor("shared-type"), {Terminals.begin()});
   const auto *ClassType = &Arena.createSequence(
       symbol("class-type"), ruleFor("class-type"), {SharedType});
   const auto *EnumType = &Arena.createSequence(
       symbol("enum-type"), ruleFor("enum-type"), {SharedType});
   const auto *Alternative1 =
-      &Arena.createSequence(symbol("type"), /*RuleID=*/3, {ClassType});
+      &Arena.createSequence(symbol("type"), /*RuleID=*/4, {ClassType});
   const auto *Alternative2 =
-      &Arena.createSequence(symbol("type"), /*RuleID=*/4, {EnumType});
+      &Arena.createSequence(symbol("type"), /*RuleID=*/5, {EnumType});
   const auto *Type =
       &Arena.createAmbiguous(symbol("type"), {Alternative1, Alternative2});
   EXPECT_EQ(Type->dumpRecursive(G),
             "[  0, end) type := <ambiguous>\n"
             "[  0, end) ├─type := class-type\n"
             "[  0, end) │ └─class-type := shared-type\n"
             "[  0, end) │   └─shared-type := IDENTIFIER #1\n"
             "[  0, end) │     └─IDENTIFIER := tok[0]\n"

clang-tools-extra/pseudo/unittests/GLRTest.cpp

TEST_F(GLRTest, PerfectForestNodeSharing) {
   // Run the GLR on a simple grammar and test that we build exactly one forest
   // node per (SymbolID, token range).
 
   // This is a grmammar where the original parsing-stack-based forest node
   // sharing approach will fail. In its LR0 graph, it has two states containing
   // item `expr := • IDENTIFIER`, and both have different goto states on the
   // nonterminal `expr`.
   build(R"bnf(
-    _ := test
+    _ := test EOF
 
     test := { expr
     test := { IDENTIFIER
     test := left-paren expr
     left-paren := {
     expr := IDENTIFIER
   )bnf");
   TestLang.Table = LRTable::buildSLR(TestLang.G);

 TEST_F(GLRTest, GLRReduceOrder) {
   // Given the following grammar, and the input `IDENTIFIER`, reductions should
   // be performed in the following order:
   //  1. foo := IDENTIFIER
   //  2. { test := IDENTIFIER, test := foo }
   // foo should be reduced first, so that in step 2 we have completed reduces
   // for test, and form an ambiguous forest node.
   build(R"bnf(
-    _ := test
+    _ := test EOF
 
     test := IDENTIFIER
     test := foo
     foo := IDENTIFIER
   )bnf");
   clang::LangOptions LOptions;
   const TokenStream &Tokens = cook(lex("IDENTIFIER", LOptions), LOptions);
   TestLang.Table = LRTable::buildSLR(TestLang.G);

 }
 
 TEST_F(GLRTest, RecoveryEndToEnd) {
   // Simple example of brace-based recovery showing:
   //  - recovered region includes tokens both ahead of and behind the cursor
   //  - multiple possible recovery rules
   //  - recovery from outer scopes is rejected
   build(R"bnf(
-    _ := block
+    _ := block EOF
 
     block := { block [recover=Braces] }
     block := { numbers [recover=Braces] }
     numbers := NUMERIC_CONSTANT NUMERIC_CONSTANT
   )bnf");
   TestLang.Table = LRTable::buildSLR(TestLang.G);
   TestLang.RecoveryStrategies.try_emplace(extensionID("Braces"), recoverBraces);
   clang::LangOptions LOptions;
EXPECT_EQ(Parsed.dumpRecursive(TestLang.G),
             "[  1,   2) │   ├─{ := tok[1]\n"
             "[  2,   4) │   ├─numbers := <opaque>\n"
             "[  4,   5) │   └─} := tok[4]\n"
             "[  5, end) └─} := tok[5]\n");
 }
 
 TEST_F(GLRTest, RecoverTerminal) {
   build(R"bnf(
-    _ := stmt
+    _ := stmt EOF
 
     stmt := IDENTIFIER ; [recover=Skip]
   )bnf");
   TestLang.Table = LRTable::buildSLR(TestLang.G);
   TestLang.RecoveryStrategies.try_emplace(
       extensionID("Skip"),
-      [](Token::Index Start, const TokenStream &) { return Start + 1; });
+      [](Token::Index Start, const TokenStream &) { return Start; });
   clang::LangOptions LOptions;
   TokenStream Tokens = cook(lex("foo", LOptions), LOptions);
 
   const ForestNode &Parsed =
       glrParse({Tokens, Arena, GSStack}, id("stmt"), TestLang);
   EXPECT_EQ(Parsed.dumpRecursive(TestLang.G),
             "[  0, end) stmt := IDENTIFIER ; [recover=Skip]\n"
             "[  0,   1) ├─IDENTIFIER := tok[0]\n"
             "[  1, end) └─; := <opaque>\n");
 }
 
 TEST_F(GLRTest, RecoverUnrestrictedReduce) {
   // Here, ! is not in any rule and therefore not in the follow set of `word`.
   // We would not normally reduce `word := IDENTIFIER`, but do so for recovery.
 
   build(R"bnf(
-    _ := sentence
+    _ := sentence EOF
 
     word := IDENTIFIER
     sentence := word word [recover=AcceptAnyTokenInstead]
   )bnf");
 
   clang::LangOptions LOptions;
   const TokenStream &Tokens = cook(lex("id !", LOptions), LOptions);
   TestLang.Table = LRTable::buildSLR(TestLang.G);
   TestLang.RecoveryStrategies.try_emplace(
       extensionID("AcceptAnyTokenInstead"),
       [](Token::Index Start, const TokenStream &Stream) { return Start + 1; });
 
   const ForestNode &Parsed =
       glrParse({Tokens, Arena, GSStack}, id("sentence"), TestLang);
   EXPECT_EQ(Parsed.dumpRecursive(TestLang.G),
             "[  0, end) sentence := word word [recover=AcceptAnyTokenInstead]\n"
             "[  0,   1) ├─word := IDENTIFIER\n"
             "[  0,   1) │ └─IDENTIFIER := tok[0]\n"
             "[  1, end) └─word := <opaque>\n");
 }
 
+TEST_F(GLRTest, RepeatedRecovery) {
+  // We require multiple steps of recovery at eof and then a reduction in order
+  // to successfully parse.
+  build(R"bnf(
+    _ := function EOF
+    # FIXME: this forces EOF to be in follow(signature).
+    # Remove it once we use unconstrained reduction for recovery.
+    _ := signature EOF
+
+    function := signature body [recover=Skip]
+    signature := IDENTIFIER params [recover=Skip]
+    params := ( )
+    body := { }
+  )bnf");
+  TestLang.Table = LRTable::buildSLR(TestLang.G);
+  TestLang.RecoveryStrategies.try_emplace(
+      extensionID("Skip"),
+      [](Token::Index Start, const TokenStream &) { return Start; });
+  clang::LangOptions LOptions;
+  TokenStream Tokens = cook(lex("main", LOptions), LOptions);
+
+  const ForestNode &Parsed =
+      glrParse({Tokens, Arena, GSStack}, id("function"), TestLang);
+  EXPECT_EQ(Parsed.dumpRecursive(TestLang.G),
+            "[  0, end) function := signature body [recover=Skip]\n"
+            "[  0,   1) ├─signature := IDENTIFIER params [recover=Skip]\n"
+            "[  0,   1) │ ├─IDENTIFIER := tok[0]\n"
+            "[  1,   1) │ └─params := <opaque>\n"
+            "[  1, end) └─body := <opaque>\n");
+}
+
 TEST_F(GLRTest, NoExplicitAccept) {
   build(R"bnf(
-    _ := test
+    _ := test EOF
 
     test := IDENTIFIER test
     test := IDENTIFIER
   )bnf");
   clang::LangOptions LOptions;
   // Given the following input, and the grammar above, we perform two reductions
   // of the nonterminal `test` when the next token is `eof`, verify that the
   // parser stops at the right state.
   const TokenStream &Tokens = cook(lex("id id", LOptions), LOptions);
   TestLang.Table = LRTable::buildSLR(TestLang.G);
 
   const ForestNode &Parsed =
       glrParse({Tokens, Arena, GSStack}, id("test"), TestLang);
   EXPECT_EQ(Parsed.dumpRecursive(TestLang.G),
             "[  0, end) test := IDENTIFIER test\n"
             "[  0,   1) ├─IDENTIFIER := tok[0]\n"
             "[  1, end) └─test := IDENTIFIER\n"
             "[  1, end)   └─IDENTIFIER := tok[1]\n");
 }
 
 TEST_F(GLRTest, GuardExtension) {
   build(R"bnf(
-    _ := start
+    _ := start EOF
 
     start := IDENTIFIER [guard]
   )bnf");
   TestLang.Guards.try_emplace(
       ruleFor("start"), [&](const GuardParams &P) {
         assert(P.RHS.size() == 1 &&
                P.RHS.front()->symbol() ==
                    tokenSymbol(clang::tok::identifier));