diff --git a/clang-tools-extra/pseudo/lib/GLR.cpp b/clang-tools-extra/pseudo/lib/GLR.cpp
--- a/clang-tools-extra/pseudo/lib/GLR.cpp
+++ b/clang-tools-extra/pseudo/lib/GLR.cpp
@@ -648,10 +648,7 @@
       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);
+      assert(!NextHeads.empty() &&  "no fallback recovery strategy!" );
     } else
       ++I;
 
@@ -685,11 +682,9 @@
     }
     return Result;
   };
-  if (auto *Result = SearchForAccept(Heads))
-    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);
+  auto *Result = SearchForAccept(Heads);
+  assert(Result);
+  return *Result;
 }
 
 void glrReduce(std::vector<const GSS::Node *> &Heads, SymbolID Lookahead,
diff --git a/clang-tools-extra/pseudo/lib/cxx/CXX.cpp b/clang-tools-extra/pseudo/lib/cxx/CXX.cpp
--- a/clang-tools-extra/pseudo/lib/cxx/CXX.cpp
+++ b/clang-tools-extra/pseudo/lib/cxx/CXX.cpp
@@ -389,9 +389,14 @@
   return Token::Invalid;
 }
 
+Token::Index recoverEof(Token::Index, const TokenStream &Tokens) {
+  return Tokens.tokens().size();
+}
+
 llvm::DenseMap<ExtensionID, RecoveryStrategy> buildRecoveryStrategies() {
   return {
       {Extension::Brackets, recoverBrackets},
+      {Extension::Eof, recoverEof},
   };
 }
 
diff --git a/clang-tools-extra/pseudo/lib/grammar/GrammarBNF.cpp b/clang-tools-extra/pseudo/lib/grammar/GrammarBNF.cpp
--- a/clang-tools-extra/pseudo/lib/grammar/GrammarBNF.cpp
+++ b/clang-tools-extra/pseudo/lib/grammar/GrammarBNF.cpp
@@ -76,6 +76,8 @@
     });
     // Add an empty string for the corresponding sentinel unset attribute.
     T->AttributeValues.push_back("");
+    // Add the fallback EOF error recovery strategy.
+    UniqueAttributeValues.insert("Eof");
     UniqueAttributeValues.erase("");
     for (llvm::StringRef Name : UniqueAttributeValues) {
       T->AttributeValues.emplace_back();
@@ -269,6 +271,10 @@
         }
       }
     }
+    if (Spec.Target == StartSymbol) {
+      R.Recovery = LookupExtensionID("Eof");
+      R.RecoveryIndex = 0;
+    }
   }
 
   // Inlines all _opt symbols.
diff --git a/clang-tools-extra/pseudo/unittests/GLRTest.cpp b/clang-tools-extra/pseudo/unittests/GLRTest.cpp
--- a/clang-tools-extra/pseudo/unittests/GLRTest.cpp
+++ b/clang-tools-extra/pseudo/unittests/GLRTest.cpp
@@ -654,27 +654,24 @@
 
 TEST_F(GLRTest, RecoveryFromStartOfInput) {
   build(R"bnf(
-    _ := start [recover=Fallback] EOF
+    _ := start EOF
 
     start := IDENTIFIER
   )bnf");
   TestLang.Table = LRTable::buildSLR(TestLang.G);
   bool fallback_recovered = false;
-  auto fallback = [&](Token::Index Start, const TokenStream & Code) {
+  auto fallback = [&](Token::Index Start, const TokenStream &Code) {
     fallback_recovered = true;
     return Code.tokens().size();
   };
-  TestLang.RecoveryStrategies.try_emplace(
-      extensionID("Fallback"),
-      fallback);
+  TestLang.RecoveryStrategies.try_emplace(extensionID("Eof"), fallback);
   clang::LangOptions LOptions;
   TokenStream Tokens = cook(lex("?", LOptions), LOptions);
 
   const ForestNode &Parsed =
       glrParse({Tokens, Arena, GSStack}, id("start"), TestLang);
   EXPECT_TRUE(fallback_recovered);
-  EXPECT_EQ(Parsed.dumpRecursive(TestLang.G),
-            "[  0, end) start := <opaque>\n");
+  EXPECT_EQ(Parsed.dumpRecursive(TestLang.G), "[  0, end) start := <opaque>\n");
 }
 
 TEST_F(GLRTest, RepeatedRecovery) {
@@ -756,6 +753,10 @@
             "[  0, end) └─IDENTIFIER := tok[0]\n");
 
   Input = "notest";
+  TestLang.RecoveryStrategies.try_emplace(
+      extensionID("Eof"), [](Token::Index Begin, const TokenStream &Code) {
+        return Code.tokens().size();
+      });
   const TokenStream &Failed = cook(lex(Input, LOptions), LOptions);
   EXPECT_EQ(glrParse({Failed, Arena, GSStack}, id("start"), TestLang)
                 .dumpRecursive(TestLang.G),