[pseudo] Implement guard extension.

[hokein]

Summary

• Extend the GLR parser to allow conditional reduction based on the guard functions;
• Implement two simple guards (contextual-override/final) for cxx.bnf;
• layering: clangPseudoCXX depends on clangPseudo (as the guard function need to access the TokenStream);

[hokein]

• add comments;
• add unittest and lit test;
• misc improvements;

[sammccall]

The ParseLang + CLI library seem clearly separate from everything else, I think this patch should be split.

Comments on that part first...

clang-tools-extra/pseudo/benchmarks/Benchmark.cpp

70

getLanguage() should not be inside the loop. This is happening in a few places

Maybe it should stay in setupGrammarAndSource?

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

35

why are these all references with ParseLang (presumably) passed by value, instead of values with ParseLang passed by reference?

clang-tools-extra/pseudo/include/clang-pseudo/cli/CLI.h

24 ↗

(On Diff #435889)

nit: I don't think a namespace is needed here, compared to just getLanguageFromFlags()

26 ↗

(On Diff #435889)

either "language" is a clear enough name or it isn't - given naming elsewhere this should be getParseLang I think

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

268–269

I'm not sure exactly what the best thing to do about this is, but Params.Lang.G is hard to read - it's a long complicated name that doesn't even name the thing.

I think probably we should split ParseParams up instead of nesting ParseLang in it, e.g.

struct GLRStorage { ForestArena&, GSS }
glrReduce(vector<ParseStep>, const ParseLang&, GLStorage&, NewHeadCallback)

Or even put a forest pointer in the GSS just for convenience.

clang-tools-extra/pseudo/lib/cli/CLI.cpp

52

huh? diagnostics aren't fatal (at least haven't been considered so before)

53

"missing guard function" is probably a grammar diagnostic, maybe we should add some logic to validate extensions?
Probably a FIXME for now

57–58

I don't think the CLI library should be in charge of knowing the fallback logic for each type of extension.
Could the parser handle a missing guard itself instead?

clang-tools-extra/pseudo/tool/ClangPseudo.cpp

146–147

drop if(true)?

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

54–60

either do it or don't - this is too small to check in a fixme IMO

60

can this just be a member?

[sammccall]

(comments for guard part)

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

22

nit: I think the first sentence should try to describe what this *is* in as simple terms as possible, rather than how it interacts with the rest of the system.

// A guard restricts when a grammar rule can be used

25

I think it's worth including an example here. "e.g. a guard may allow virt-specifier := IDENTIFIER only if the identifier's text is 'override'".

27

I think this sentence adds more confusion than it helps. (Not sure it's true depending on what you mean by "parsing branch" - the guard runs before the reduce not after, so the branch never exists)

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

275

I think diagnosing missing guards but then treating them as always-passing is less surprising and more ergonomic while modifying a grammar

[hokein]

rebase and address comments.

[hokein]

fix format.

[hokein]

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

268–269

Changed the signature of glrShift/Reduce/Parse.

275

I wanted to make this as a contract (guard in each rule must refer to a valid extension function) in GLR parser.

I think loosing the restriction is also fine -- the only downside I can see is that if we have a typo guard in the grammar file, which we don't have a corresponding function, the parser will run and emit confusing results. We can fix it by adding "missing guard function" diagnostics.

[sammccall]

Great!

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

117–118

delete "being".
Or possibly the whole comment, this seems obvious?

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

254

nit: hadn't really intended SequenceRef to be a general vocabulary type, you might just want ArrayRef to match the guard signature, up to you

258

this should be guarded by LLVM_DEBUG

this whole thing might be clearer with lookup

if (auto Guard = Lang.Guards.lookup(GuardID))
  return Guard(RHS.S, Params.Code);

LLVM_DEBUG(...);
return true;

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

467

insert(make_pair(...)) => emplace(...)?

470

remove

[hokein]

address comments.

clang-tools-extra/pseudo/benchmarks/Benchmark.cpp

auto ReadFile = [](llvm::StringRef FilePath) -> std::string {
     return GrammarText.get()->getBuffer().str();
   };
   SourceText = new std::string(ReadFile(Source));
   Lang = &getLanguageFromFlags();
 }
 
 static void buildSLR(benchmark::State &State) {
   for (auto _ : State)
     LRTable::buildSLR(Lang->G);
 }
 BENCHMARK(buildSLR);
 
 TokenStream lexAndPreprocess() {
   clang::LangOptions LangOpts = genericLangOpts();
   TokenStream RawStream = pseudo::lex(*SourceText, LangOpts);
   auto DirectiveStructure = DirectiveTree::parse(RawStream);
   chooseConditionalBranches(DirectiveStructure, RawStream);

 BENCHMARK(preprocess);
 
 static void glrParse(benchmark::State &State) {
   SymbolID StartSymbol = *Lang->G.findNonterminal("translation-unit");
   TokenStream Stream = lexAndPreprocess();
   for (auto _ : State) {
     pseudo::ForestArena Forest;
     pseudo::GSS GSS;
-    pseudo::glrParse(Stream, ParseParams{Lang->G, Lang->Table, Forest, GSS},
-                     StartSymbol);
+    pseudo::glrParse(ParseParams{Stream, Forest, GSS}, StartSymbol, *Lang);
   }
   State.SetBytesProcessed(static_cast<uint64_t>(State.iterations()) *
                           SourceText->size());
 }
 BENCHMARK(glrParse);
 
 static void full(benchmark::State &State) {
   SymbolID StartSymbol = *Lang->G.findNonterminal("translation-unit");
   for (auto _ : State) {
     TokenStream Stream = lexAndPreprocess();
     pseudo::ForestArena Forest;
     pseudo::GSS GSS;
-    pseudo::glrParse(lexAndPreprocess(),
-                     ParseParams{Lang->G, Lang->Table, Forest, GSS},
-                     StartSymbol);
+    pseudo::glrParse(ParseParams{Stream, Forest, GSS}, StartSymbol, *Lang);
   }
   State.SetBytesProcessed(static_cast<uint64_t>(State.iterations()) *
                           SourceText->size());
 }
 BENCHMARK(full);
 
 } // namespace
 } // namespace bench

clang-tools-extra/pseudo/fuzzer/Fuzzer.cpp

void operator()(llvm::StringRef Code) {
     // FIXME: strip preprocessor directives
     auto ParseableStream =
         clang::pseudo::stripComments(cook(RawStream, LangOpts));
 
     clang::pseudo::ForestArena Arena;
     clang::pseudo::GSS GSS;
     const Language &Lang = getLanguageFromFlags();
     auto &Root =
-        glrParse(ParseableStream,
-                 clang::pseudo::ParseParams{Lang.G, Lang.Table, Arena, GSS},
-                 *Lang.G.findNonterminal("translation-unit"));
+        glrParse(clang::pseudo::ParseParams{ParseableStream, Arena, GSS},
+                 *Lang.G.findNonterminal("translation-unit"), Lang);
     if (Print)
       llvm::outs() << Root.dumpRecursive(Lang.G);
   }
 };
 
 Fuzzer *Fuzz = nullptr;
 
 } // namespace

clang-tools-extra/pseudo/gen/Main.cpp

int main(int argc, char *argv[]) {
   llvm::ToolOutputFile Out{OutputFilename, EC, llvm::sys::fs::OF_None};
   if (EC) {
     llvm::errs() << EC.message() << '\n';
     return 1;
   }
 
   switch (Emit) {
   case EmitSymbolList:
+    Out.os() << R"cpp(
+#ifndef NONTERMINAL
+#define NONTERMINAL(X, Y)
+#endif
+#ifndef EXTENSION
+#define EXTENSION(X, Y)
+#endif
+    )cpp";
     for (clang::pseudo::SymbolID ID = 0; ID < G.table().Nonterminals.size();
          ++ID) {
       std::string Name = G.symbolName(ID).str();
       // translation-unit -> translation_unit
       std::replace(Name.begin(), Name.end(), '-', '_');
       Out.os() << llvm::formatv("NONTERMINAL({0}, {1})\n", Name, ID);
     }
+    for (clang::pseudo::ExtensionID EID = 1 /*skip the sentinel 0 value*/;
+         EID < G.table().AttributeValues.size(); ++EID) {
+      llvm::StringRef Name = G.table().AttributeValues[EID];
+      assert(!Name.empty());
+      Out.os() << llvm::formatv("EXTENSION({0}, {1})\n", Name, EID);
+    }
+    Out.os() << R"cpp(
+#undef NONTERMINAL
+#undef EXTENSION
+    )cpp";
     break;
   case EmitGrammarContent:
     for (llvm::StringRef Line : llvm::split(GrammarText, '\n')) {
       Out.os() << '"';
       Out.os().write_escaped((Line + "\n").str());
       Out.os() << "\"\n";
     }
     break;
   }
 
   Out.keep();
 
   return 0;
 }

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

 //    processes have performed all reduce actions.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef CLANG_PSEUDO_GLR_H
 #define CLANG_PSEUDO_GLR_H
 
 #include "clang-pseudo/Forest.h"
+#include "clang-pseudo/Language.h"
 #include "clang-pseudo/grammar/Grammar.h"
 #include "clang-pseudo/grammar/LRTable.h"
 #include "llvm/Support/Allocator.h"
 #include <vector>
 
 namespace clang {
 namespace pseudo {
 
private:
   bool GCParity = false; // All nodes should match this, except during GC.
 
   llvm::BumpPtrAllocator Arena;
   unsigned NodesCreated = 0;
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const GSS::Node &);
 
 // Parameters for the GLR parsing.
-// FIXME: refine it with the ParseLang struct.
 struct ParseParams {
-  // The grammar of the language we're going to parse.
-  const Grammar &G;
-  // The LR table which GLR uses to parse the input, should correspond to the
-  // Grammar G.
-  const LRTable &Table;
+  // The token stream to parse.
+  const TokenStream &Code;
 
   // Arena for data structure used by the GLR algorithm.
   ForestArena &Forest;  // Storage for the output forest.
   GSS &GSStack;         // Storage for parsing stacks.
 };
+
 // Parses the given token stream as the start symbol with the GLR algorithm,
 // and returns a forest node of the start symbol.
 //
 // A rule `_ := StartSymbol` must exit for the chosen start symbol.
 //
 // If the parsing fails, we model it as an opaque node in the forest.
-const ForestNode &glrParse(const TokenStream &Code, const ParseParams &Params,
-                           SymbolID StartSymbol);
+const ForestNode &glrParse(const ParseParams &Params, SymbolID StartSymbol,
+                           const Language &Lang);
 
 // Shift a token onto all OldHeads, placing the results into NewHeads.
 //
 // Exposed for testing only.
 void glrShift(llvm::ArrayRef<const GSS::Node *> OldHeads,
               const ForestNode &NextTok, const ParseParams &Params,
-              std::vector<const GSS::Node *> &NewHeads);
+              const Language &Lang, std::vector<const GSS::Node *> &NewHeads);
 // Applies available reductions on Heads, appending resulting heads to the list.
 //
 // Exposed for testing only.
 void glrReduce(std::vector<const GSS::Node *> &Heads, SymbolID Lookahead,
-               const ParseParams &Params);
+               const ParseParams &Params, const Language &Lang);
 
 } // namespace pseudo
 } // namespace clang
 
 #endif // CLANG_PSEUDO_GLR_H

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

 //===--- Language.h -------------------------------------------- -*- C++-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef CLANG_PSEUDO_GRAMMAR_LANGUAGE_H
 #define CLANG_PSEUDO_GRAMMAR_LANGUAGE_H
 
 #include "clang-pseudo/grammar/Grammar.h"
 #include "clang-pseudo/grammar/LRTable.h"
 
 namespace clang {
 namespace pseudo {
+class ForestNode;
+class TokenStream;
+class LRTable;
+
+// A guard restricts when a grammar rule can be used.
+//
+// The GLR parser will use the guard to determine whether a rule reduction will
+// be conducted. For example, e.g. a guard may allow the rule
+// `virt-specifier := IDENTIFIER` only if the identifier's text is 'override`.
+//
+// Return true if the guard is satisfied.
+using RuleGuard = llvm::function_ref<bool(
+    llvm::ArrayRef<const ForestNode *> RHS, const TokenStream &)>;
 
 // Specify a language that can be parsed by the pseduoparser.
 struct Language {
   Grammar G;
   LRTable Table;
 
+  // Binding "guard" extension id to a piece of C++ code.
+  llvm::DenseMap<ExtensionID, RuleGuard> Guards;
+
   // FIXME: add clang::LangOptions.
   // FIXME: add default start symbols.
 };
 
 } // namespace pseudo
 } // namespace clang
 
 #endif // CLANG_PSEUDO_GRAMMAR_LANGUAGE_H

clang-tools-extra/pseudo/include/clang-pseudo/cxx/CXX.h

 // Symbol represents nonterminal symbols in the C++ grammar.
 // It provides a simple uniform way to access a particular nonterminal.
 enum class Symbol : SymbolID {
 #define NONTERMINAL(X, Y) X = Y,
 #include "CXXSymbols.inc"
 #undef NONTERMINAL
 };
 
+enum class Extension : ExtensionID {
+#define EXTENSION(X, Y) X = Y,
+#include "CXXSymbols.inc"
+#undef EXTENSION
+};
+
 // Returns the Language for the cxx.bnf grammar.
 const Language &getLanguage();
 
 } // namespace cxx
 
 } // namespace pseudo
 } // namespace clang
 
 #endif // CLANG_PSEUDO_CXX_CXX_H

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

 //===--- GLR.cpp   -----------------------------------------------*- C++-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang-pseudo/GLR.h"
+#include "clang-pseudo/Language.h"
 #include "clang-pseudo/grammar/Grammar.h"
 #include "clang-pseudo/grammar/LRTable.h"
 #include "clang/Basic/TokenKinds.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/Debug.h"

 // E.g. we have two heads (2, 3) in the GSS, and will shift both to reach 4:
 //   0---1---2
 //       └---3
 // After the shift action, the GSS is:
 //   0---1---2---4
 //       └---3---┘
 void glrShift(llvm::ArrayRef<const GSS::Node *> OldHeads,
               const ForestNode &NewTok, const ParseParams &Params,
-              std::vector<const GSS::Node *> &NewHeads) {
+              const Language &Lang, std::vector<const GSS::Node *> &NewHeads) {
   assert(NewTok.kind() == ForestNode::Terminal);
   LLVM_DEBUG(llvm::dbgs() << llvm::formatv("  Shift {0} ({1} active heads):\n",
-                                           Params.G.symbolName(NewTok.symbol()),
+                                           Lang.G.symbolName(NewTok.symbol()),
                                            OldHeads.size()));
 
   // We group pending shifts by their target state so we can merge them.
   llvm::SmallVector<std::pair<StateID, const GSS::Node *>, 8> Shifts;
   for (const auto *H : OldHeads)
-    if (auto S = Params.Table.getShiftState(H->State, NewTok.symbol()))
+    if (auto S = Lang.Table.getShiftState(H->State, NewTok.symbol()))
       Shifts.push_back({*S, H});
   llvm::stable_sort(Shifts, llvm::less_first{});
 
   auto Rest = llvm::makeArrayRef(Shifts);
   llvm::SmallVector<const GSS::Node *> Parents;
   while (!Rest.empty()) {
     // Collect the batch of PendingShift that have compatible shift states.
     // Their heads become TempParents, the parents of the new GSS node.

 //   After reducing 3 by `pointer := class-name STAR` and
 //                  2 by`enum-name := class-name STAR`:
 //     0--5(pointer)       // 5 is goto(0, pointer)
 //
 // (This is a functor rather than a function to allow it to reuse scratch
 // storage across calls).
 class GLRReduce {
   const ParseParams &Params;
-
+  const Language& Lang;
   // There are two interacting complications:
   // 1.  Performing one reduce can unlock new reduces on the newly-created head.
   // 2a. The ambiguous ForestNodes must be complete (have all sequence nodes).
   //     This means we must have unlocked all the reduces that contribute to it.
   // 2b. Similarly, the new GSS nodes must be complete (have all parents).
   //
   // We define a "family" of reduces as those that produce the same symbol and
   // cover the same range of tokens. These are exactly the set of reductions
class GLRReduce {
   // We treat Heads as a queue of Pop operations still to be performed.
   // PoppedHeads is our position within it.
   std::vector<const GSS::Node *> *Heads;
   unsigned NextPopHead;
   SymbolID Lookahead;
 
   Sequence TempSequence;
 public:
-  GLRReduce(const ParseParams &Params) : Params(Params) {}
+  GLRReduce(const ParseParams &Params, const Language &Lang)
+      : Params(Params), Lang(Lang) {}
 
   void operator()(std::vector<const GSS::Node *> &Heads, SymbolID Lookahead) {
     assert(isToken(Lookahead));
 
     NextPopHead = 0;
     this->Heads = &Heads;
     this->Lookahead = Lookahead;
     assert(Sequences.empty());
     SequenceStorageCount = 0;
 
     popPending();
     while (!Sequences.empty()) {
       pushNext();
       popPending();
     }
   }
 
 private:
+  bool canReduce(ExtensionID GuardID, RuleID RID,
+                 llvm::ArrayRef<const ForestNode *> RHS) const {
+    if (!GuardID)
+      return true;
+    if (auto Guard = Lang.Guards.lookup(GuardID))
+      return Guard(RHS, Params.Code);
+    LLVM_DEBUG(llvm::dbgs()
+               << llvm::formatv("missing guard implementation for rule {0}\n",
+                                Lang.G.dumpRule(RID)));
+    return true;
+  }
   // pop walks up the parent chain(s) for a reduction from Head by to Rule.
   // Once we reach the end, record the bases and sequences.
   void pop(const GSS::Node *Head, RuleID RID, const Rule &Rule) {
-    LLVM_DEBUG(llvm::dbgs() << "  Pop " << Params.G.dumpRule(RID) << "\n");
+    LLVM_DEBUG(llvm::dbgs() << "  Pop " << Lang.G.dumpRule(RID) << "\n");
     Family F{/*Start=*/0, /*Symbol=*/Rule.Target, /*Rule=*/RID};
     TempSequence.resize_for_overwrite(Rule.Size);
     auto DFS = [&](const GSS::Node *N, unsigned I, auto &DFS) {
       TempSequence[Rule.Size - 1 - I] = N->Payload;
       if (I + 1 == Rule.Size) {
         F.Start = TempSequence.front()->startTokenIndex();
         LLVM_DEBUG({
           for (const auto *B : N->parents())
             llvm::dbgs() << "    --> base at S" << B->State << "\n";
         });
-
+        if (!canReduce(Rule.Guard, RID, TempSequence))
+          return;
         // Copy the chain to stable storage so it can be enqueued.
         if (SequenceStorageCount == SequenceStorage.size())
           SequenceStorage.emplace_back();
         SequenceStorage[SequenceStorageCount] = TempSequence;
         Sequence *Seq = &SequenceStorage[SequenceStorageCount++];
 
         Sequences.emplace(F, PushSpec{N, Seq});
         return;
       }
       for (const GSS::Node *Parent : N->parents())
         DFS(Parent, I + 1, DFS);
     };
     DFS(Head, 0, DFS);
   }
 
   // popPending pops every available reduction.
   void popPending() {
     for (; NextPopHead < Heads->size(); ++NextPopHead) {
       // In trivial cases, we perform the complete reduce here!
       if (popAndPushTrivial())
         continue;
       for (RuleID RID :
-           Params.Table.getReduceRules((*Heads)[NextPopHead]->State)) {
-        const auto &Rule = Params.G.lookupRule(RID);
-        if (Params.Table.canFollow(Rule.Target, Lookahead))
+           Lang.Table.getReduceRules((*Heads)[NextPopHead]->State)) {
+        const auto &Rule = Lang.G.lookupRule(RID);
+        if (Lang.Table.canFollow(Rule.Target, Lookahead))
           pop((*Heads)[NextPopHead], RID, Rule);
       }
     }
   }
 
   // Storage reused by each call to pushNext.
   std::vector<std::pair</*Goto*/ StateID, const GSS::Node *>> FamilyBases;
   std::vector<std::pair<RuleID, SequenceRef>> FamilySequences;
   std::vector<const GSS::Node *> Parents;
   std::vector<const ForestNode *> SequenceNodes;
 
   // Process one push family, forming a forest node.
   // This produces new GSS heads which may enable more pops.
   void pushNext() {
     assert(!Sequences.empty());
     Family F = Sequences.top().first;
 
-    LLVM_DEBUG(llvm::dbgs() << "  Push " << Params.G.symbolName(F.Symbol)
+    LLVM_DEBUG(llvm::dbgs() << "  Push " << Lang.G.symbolName(F.Symbol)
                             << " from token " << F.Start << "\n");
 
     // Grab the sequences and bases for this family.
     // We don't care which rule yielded each base. If Family.Symbol is S, the
     // base includes an item X := ... • S ... and since the grammar is
     // context-free, *all* parses of S are valid here.
     FamilySequences.clear();
     FamilyBases.clear();
     do {
       const PushSpec &Push = Sequences.top().second;
       FamilySequences.emplace_back(Sequences.top().first.Rule, *Push.Seq);
       for (const GSS::Node *Base : Push.LastPop->parents()) {
-        auto NextState = Params.Table.getGoToState(Base->State, F.Symbol);
+        auto NextState = Lang.Table.getGoToState(Base->State, F.Symbol);
         assert(NextState.hasValue() && "goto must succeed after reduce!");
         FamilyBases.emplace_back(*NextState, Base);
       }
 
       Sequences.pop();
     } while (!Sequences.empty() && Sequences.top().first == F);
     // Build a forest node for each unique sequence.
     sortAndUnique(FamilySequences);
     SequenceNodes.clear();
     for (const auto &SequenceSpec : FamilySequences)
       SequenceNodes.push_back(&Params.Forest.createSequence(
           F.Symbol, SequenceSpec.first, SequenceSpec.second.S));
     // Wrap in an ambiguous node if needed.
     const ForestNode *Parsed =
         SequenceNodes.size() == 1
             ? SequenceNodes.front()
             : &Params.Forest.createAmbiguous(F.Symbol, SequenceNodes);
-    LLVM_DEBUG(llvm::dbgs() << "    --> " << Parsed->dump(Params.G) << "\n");
+    LLVM_DEBUG(llvm::dbgs() << "    --> " << Parsed->dump(Lang.G) << "\n");
 
     // Bases for this family, deduplicate them, and group by the goTo State.
     sortAndUnique(FamilyBases);
     // Create a GSS node for each unique goto state.
     llvm::ArrayRef<decltype(FamilyBases)::value_type> BasesLeft = FamilyBases;
     while (!BasesLeft.empty()) {
       StateID NextState = BasesLeft.front().first;
       Parents.clear();
private:
   // (Roughly this means there's no local ambiguity, so the LR algorithm works).
   //
   // Returns true if we successfully consumed the next unpopped head.
   bool popAndPushTrivial() {
     if (!Sequences.empty() || Heads->size() != NextPopHead + 1)
       return false;
     const GSS::Node *Head = Heads->back();
     llvm::Optional<RuleID> RID;
-    for (RuleID R : Params.Table.getReduceRules(Head->State)) {
+    for (RuleID R : Lang.Table.getReduceRules(Head->State)) {
       if (RID.hasValue())
         return false;
       RID = R;
     }
     if (!RID)
       return true; // no reductions available, but we've processed the head!
-    const auto &Rule = Params.G.lookupRule(*RID);
-    if (!Params.Table.canFollow(Rule.Target, Lookahead))
+    const auto &Rule = Lang.G.lookupRule(*RID);
+    if (!Lang.Table.canFollow(Rule.Target, Lookahead))
       return true; // reduction is not available
     const GSS::Node *Base = Head;
     TempSequence.resize_for_overwrite(Rule.Size);
     for (unsigned I = 0; I < Rule.Size; ++I) {
       if (Base->parents().size() != 1)
         return false;
       TempSequence[Rule.Size - 1 - I] = Base->Payload;
       Base = Base->parents().front();
     }
+    if (!canReduce(Rule.Guard, *RID, TempSequence))
+      return true; // reduction is not available
     const ForestNode *Parsed =
         &Params.Forest.createSequence(Rule.Target, *RID, TempSequence);
-    auto NextState = Params.Table.getGoToState(Base->State, Rule.Target);
+    auto NextState = Lang.Table.getGoToState(Base->State, Rule.Target);
     assert(NextState.hasValue() && "goto must succeed after reduce!");
     Heads->push_back(Params.GSStack.addNode(*NextState, Parsed, {Base}));
     return true;
   }
 };
 
 } // namespace
 
-const ForestNode &glrParse(const TokenStream &Tokens, const ParseParams &Params,
-                           SymbolID StartSymbol) {
-  GLRReduce Reduce(Params);
+const ForestNode &glrParse( const ParseParams &Params, SymbolID StartSymbol,
+                           const Language& Lang) {
+  GLRReduce Reduce(Params, Lang);
   assert(isNonterminal(StartSymbol) && "Start symbol must be a nonterminal");
-  llvm::ArrayRef<ForestNode> Terminals = Params.Forest.createTerminals(Tokens);
-  auto &G = Params.G;
-  (void)G;
+  llvm::ArrayRef<ForestNode> Terminals = Params.Forest.createTerminals(Params.Code);
   auto &GSS = Params.GSStack;
 
-  StateID StartState = Params.Table.getStartState(StartSymbol);
+  StateID StartState = Lang.Table.getStartState(StartSymbol);
   // Heads correspond to the parse of tokens [0, I), NextHeads to [0, I+1).
   std::vector<const GSS::Node *> Heads = {GSS.addNode(/*State=*/StartState,
                                                       /*ForestNode=*/nullptr,
                                                       {})};
   std::vector<const GSS::Node *> NextHeads;
   auto MaybeGC = [&, Roots(std::vector<const GSS::Node *>{}), I(0u)]() mutable {
     assert(NextHeads.empty() && "Running GC at the wrong time!");
     if (++I != 20) // Run periodically to balance CPU and memory usage.
       return;
     I = 0;
 
     // We need to copy the list: Roots is consumed by the GC.
     Roots = Heads;
     GSS.gc(std::move(Roots));
   };
   // Each iteration fully processes a single token.
   for (unsigned I = 0; I < Terminals.size(); ++I) {
     LLVM_DEBUG(llvm::dbgs() << llvm::formatv(
                    "Next token {0} (id={1})\n",
-                   G.symbolName(Terminals[I].symbol()), Terminals[I].symbol()));
+                  Lang.G.symbolName(Terminals[I].symbol()), Terminals[I].symbol()));
     // Consume the token.
-    glrShift(Heads, Terminals[I], Params, NextHeads);
+    glrShift(Heads, Terminals[I], Params, Lang, NextHeads);
     // Form nonterminals containing the token we just consumed.
     SymbolID Lookahead = I + 1 == Terminals.size() ? tokenSymbol(tok::eof)
                                                    : Terminals[I + 1].symbol();
     Reduce(NextHeads, Lookahead);
     // Prepare for the next token.
     std::swap(Heads, NextHeads);
     NextHeads.clear();
     MaybeGC();
   }
   LLVM_DEBUG(llvm::dbgs() << llvm::formatv("Reached eof\n"));
 
-  auto AcceptState = Params.Table.getGoToState(StartState, StartSymbol);
+  auto AcceptState = Lang.Table.getGoToState(StartState, StartSymbol);
   assert(AcceptState.hasValue() && "goto must succeed after start symbol!");
   const ForestNode *Result = nullptr;
   for (const auto *Head : Heads) {
     if (Head->State == AcceptState) {
       assert(Head->Payload->symbol() == StartSymbol);
       assert(Result == nullptr && "multiple results!");
       Result = Head->Payload;
     }
   }
   if (Result)
     return *Result;
   // We failed to parse the input, returning an opaque forest node for recovery.
   //
   // FIXME: We will need to invoke our generic error-recovery handlers when we
   // reach EOF without reaching accept state, and involving the eof
   // token in the above main for-loopmay be the best way to reuse the code).
   return Params.Forest.createOpaque(StartSymbol, /*Token::Index=*/0);
 }
 
 void glrReduce(std::vector<const GSS::Node *> &Heads, SymbolID Lookahead,
-               const ParseParams &Params) {
+               const ParseParams &Params, const Language &Lang) {
   // Create a new GLRReduce each time for tests, performance doesn't matter.
-  GLRReduce{Params}(Heads, Lookahead);
+  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<unsigned>(Parents.size())});
   Alive.push_back(Result);
   ++NodesCreated;

clang-tools-extra/pseudo/lib/cli/CLI.cpp

 //===--- CLI.cpp -  ----------------------------------------------*- C++-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang-pseudo/cli/CLI.h"
 #include "clang-pseudo/cxx/CXX.h"
+#include "clang-pseudo/grammar/Grammar.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/MemoryBuffer.h"
 
 static llvm::cl::opt<std::string> Grammar(
     "grammar",
     llvm::cl::desc(
         "Specify a BNF grammar file path, or a builtin language (cxx)."),
if (std::error_code EC = GrammarText.getError()) {
                    << "': " << EC.message() << "\n";
       std::exit(1);
     }
     std::vector<std::string> Diags;
     auto G = Grammar::parseBNF(GrammarText->get()->getBuffer(), Diags);
     for (const auto &Diag : Diags)
       llvm::errs() << Diag << "\n";
     auto Table = LRTable::buildSLR(G);
-    return new Language{std::move(G), std::move(Table)};
+    return new Language{std::move(G), std::move(Table),
+                        llvm::DenseMap<ExtensionID, RuleGuard>()};
   }();
   return *Lang;
 }
 
 } // namespace pseudo
 } // namespace clang

clang-tools-extra/pseudo/lib/cxx/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
 add_clang_library(clangPseudoCXX
   CXX.cpp
 
   DEPENDS
   cxx_gen
 
   LINK_LIBS
+  clangPseudo
   clangPseudoGrammar
   )

clang-tools-extra/pseudo/lib/cxx/CXX.cpp

 //===--- CXX.cpp - Define public interfaces for C++ grammar ---------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang-pseudo/cxx/CXX.h"
+#include "clang-pseudo/Forest.h"
 #include "clang-pseudo/Language.h"
 #include "clang-pseudo/grammar/Grammar.h"
 #include "clang-pseudo/grammar/LRTable.h"
 #include <utility>
 
 namespace clang {
 namespace pseudo {
 namespace cxx {
 namespace {
 static const char *CXXBNF =
 #include "CXXBNF.inc"
     ;
+
+bool guardOverride(llvm::ArrayRef<const ForestNode *> RHS,
+                   const TokenStream &Tokens) {
+  assert(RHS.size() == 1 &&
+         RHS.front()->symbol() == tokenSymbol(clang::tok::identifier));
+  return Tokens.tokens()[RHS.front()->startTokenIndex()].text() == "override";
+}
+bool guardFinal(llvm::ArrayRef<const ForestNode *> RHS,
+                const TokenStream &Tokens) {
+  assert(RHS.size() == 1 &&
+         RHS.front()->symbol() == tokenSymbol(clang::tok::identifier));
+  return Tokens.tokens()[RHS.front()->startTokenIndex()].text() == "final";
+}
+
+llvm::DenseMap<ExtensionID, RuleGuard> buildGuards() {
+  return llvm::DenseMap<ExtensionID, RuleGuard>(
+      {{(ExtensionID)Extension::Override, guardOverride},
+       {(ExtensionID)Extension::Final, guardFinal}});
+}
+
 } // namespace
 
 const Language &getLanguage() {
   static const auto &CXXLanguage = []() -> const Language & {
     std::vector<std::string> Diags;
     auto G = Grammar::parseBNF(CXXBNF, Diags);
     assert(Diags.empty());
     LRTable Table = LRTable::buildSLR(G);
-    const Language *PL = new Language{
-        std::move(G),
-        std::move(Table),
-    };
+    const Language *PL =
+        new Language{std::move(G), std::move(Table), buildGuards()};
     return *PL;
   }();
   return CXXLanguage;
 }
 
 } // namespace cxx
 } // namespace pseudo
 } // namespace clang

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

 user-defined-character-literal := UTF16_CHAR_CONSTANT
 user-defined-character-literal := UTF32_CHAR_CONSTANT
 boolean-literal := FALSE
 boolean-literal := TRUE
 pointer-literal := NULLPTR
 
 #! Contextual keywords -- clang lexer always lexes them as identifier tokens.
 #! Placeholders for literal text in the grammar that lex as other things.
-contextual-override := IDENTIFIER
-contextual-final := IDENTIFIER
+contextual-override := IDENTIFIER [guard=Override]
+contextual-final := IDENTIFIER [guard=Final]
 contextual-zero := NUMERIC_CONSTANT
 module-keyword := IDENTIFIER
 import-keyword := IDENTIFIER
 export-keyword := IDENTIFIER
 
 #! greatergreater token -- clang lexer always lexes it as a single token, we
 #! split it into two tokens to make the GLR parser aware of the nested-template
 #! case.
 greatergreater := > >
 
 #! C++ predefined identifier, __func__ [dcl.fct.def.general] p8
 #! FIXME: add other (MSVC, GNU extension) predefined identifiers.
 primary-expression := predefined-expression
 predefined-expression := __FUNC__

clang-tools-extra/pseudo/test/cxx/contextual-keywords.cpp

+// RUN: clang-pseudo -grammar=cxx -source=%s --print-forest | FileCheck %s
+// Verify that the contextual-{final,override} rules are guarded conditionally,
+// No ambiguous parsing for the virt-specifier.
+class Foo {
+    void foo1() override;
+// CHECK: virt-specifier-seq~IDENTIFIER := tok[7]
+    void foo2() final;
+// CHECK: virt-specifier-seq~IDENTIFIER := tok[13]
+};

clang-tools-extra/pseudo/tool/ClangPseudo.cpp

if (ParseableStream) {
     clang::pseudo::ForestArena Arena;
     clang::pseudo::GSS GSS;
     llvm::Optional<clang::pseudo::SymbolID> StartSymID =
         Lang.G.findNonterminal(StartSymbol);
     if (!StartSymID) {
       llvm::errs() << llvm::formatv(
           "The start symbol {0} doesn't exit in the grammar!\n", StartSymbol);
       return 2;
     }
     auto &Root =
-        glrParse(*ParseableStream,
-                 clang::pseudo::ParseParams{Lang.G, Lang.Table, Arena, GSS},
-                 *StartSymID);
+        glrParse(clang::pseudo::ParseParams{*ParseableStream, Arena, GSS},
+                 *StartSymID, Lang);
     if (PrintForest)
       llvm::outs() << Root.dumpRecursive(Lang.G, /*Abbreviated=*/true);
 
     if (PrintStatistics) {
       llvm::outs() << "Forest bytes: " << Arena.bytes()
                    << " nodes: " << Arena.nodeCount() << "\n";
       llvm::outs() << "GSS bytes: " << GSS.bytes()
                    << " nodes: " << GSS.nodesCreated() << "\n";

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

 }
 
 class GLRTest : public ::testing::Test {
 public:
   void build(llvm::StringRef GrammarBNF) {
     std::vector<std::string> Diags;
     TestLang.G = Grammar::parseBNF(GrammarBNF, Diags);
   }
 
   TokenStream emptyTokenStream() {
     TokenStream Empty;
     Empty.finalize();
     return Empty;
   }
  
   void buildGrammar(std::vector<std::string> Nonterminals,
                     std::vector<std::string> Rules) {
     Nonterminals.push_back("_");
     llvm::sort(Nonterminals);
     Nonterminals.erase(std::unique(Nonterminals.begin(), Nonterminals.end()),
                        Nonterminals.end());
     std::string FakeTestBNF;
     for (const auto &NT : Nonterminals)
       FakeTestBNF += llvm::formatv("{0} := {1}\n", "_", NT);
     FakeTestBNF += llvm::join(Rules, "\n");
     build(FakeTestBNF);
   }
 
   SymbolID id(llvm::StringRef Name) const {
     for (unsigned I = 0; I < NumTerminals; ++I)
       if (TestLang.G.table().Terminals[I] == Name)
         return tokenSymbol(static_cast<tok::TokenKind>(I));
     for (SymbolID ID = 0; ID < TestLang.G.table().Nonterminals.size(); ++ID)
       if (TestLang.G.table().Nonterminals[ID].Name == Name)
         return ID;
     ADD_FAILURE() << "No such symbol found: " << Name;
     return 0;
   }
+  ExtensionID extensionID(llvm::StringRef AttrValueName) const {
+    for (ExtensionID EID = 0; EID < TestLang.G.table().AttributeValues.size();
+         ++EID)
+      if (TestLang.G.table().AttributeValues[EID] == AttrValueName)
+        return EID;
+    ADD_FAILURE() << "No such attribute value found: " << AttrValueName;
+    return 0;
+  }
 
   RuleID ruleFor(llvm::StringRef NonterminalName) const {
     auto RuleRange =
         TestLang.G.table().Nonterminals[id(NonterminalName)].RuleRange;
     if (RuleRange.End - RuleRange.Start == 1)
       return TestLang.G.table()
           .Nonterminals[id(NonterminalName)]
           .RuleRange.Start;
TEST_F(GLRTest, ShiftMergingHeads) {
   B.Transition[{StateID{1}, tokenSymbol(tok::semi)}] = StateID{4};
   B.Transition[{StateID{2}, tokenSymbol(tok::semi)}] = StateID{4};
   B.Transition[{StateID{3}, tokenSymbol(tok::semi)}] = StateID{5};
   TestLang.Table = std::move(B).build();
 
   ForestNode &SemiTerminal = Arena.createTerminal(tok::semi, 0);
   std::vector<const GSS::Node *> NewHeads;
   glrShift({GSSNode1, GSSNode2, GSSNode3}, SemiTerminal,
-           {TestLang.G, TestLang.Table, Arena, GSStack}, NewHeads);
+           {emptyTokenStream(), Arena, GSStack}, TestLang, NewHeads);
 
   EXPECT_THAT(NewHeads,
               UnorderedElementsAre(AllOf(state(4), parsedSymbol(&SemiTerminal),
                                          parents({GSSNode1, GSSNode2})),
                                    AllOf(state(5), parsedSymbol(&SemiTerminal),
                                          parents({GSSNode3}))))
       << NewHeads;
 }
TEST_F(GLRTest, ReduceConflictsSplitting) {
 
   const auto *GSSNode0 =
       GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr, /*Parents=*/{});
   const auto *GSSNode1 =
       GSStack.addNode(1, &Arena.createTerminal(tok::identifier, 0), {GSSNode0});
 
   std::vector<const GSS::Node *> Heads = {GSSNode1};
   glrReduce(Heads, tokenSymbol(tok::eof),
-            {TestLang.G, TestLang.Table, Arena, GSStack});
+            {emptyTokenStream(), Arena, GSStack}, TestLang);
   EXPECT_THAT(Heads, UnorderedElementsAre(
                          GSSNode1,
                          AllOf(state(2), parsedSymbolID(id("class-name")),
                                parents({GSSNode0})),
                          AllOf(state(3), parsedSymbolID(id("enum-name")),
                                parents({GSSNode0}))))
       << Heads;
 }
TEST_F(GLRTest, ReduceSplittingDueToMultipleBases) {
 
   LRTable::Builder B(TestLang.G);
   B.Transition[{StateID{2}, id("ptr-operator")}] = StateID{5};
   B.Transition[{StateID{3}, id("ptr-operator")}] = StateID{6};
   B.Reduce[StateID{4}].insert(ruleFor("ptr-operator"));
   TestLang.Table = std::move(B).build();
 
   std::vector<const GSS::Node *> Heads = {GSSNode4};
-  glrReduce(Heads, tokenSymbol(tok::eof), {TestLang.G, TestLang.Table, Arena, GSStack});
+  glrReduce(Heads, tokenSymbol(tok::eof), {emptyTokenStream(), Arena, GSStack},
+            TestLang);
 
   EXPECT_THAT(Heads, UnorderedElementsAre(
                          GSSNode4,
                          AllOf(state(5), parsedSymbolID(id("ptr-operator")),
                                parents({GSSNode2})),
                          AllOf(state(6), parsedSymbolID(id("ptr-operator")),
                                parents({GSSNode3}))))
       << Heads;
TEST_F(GLRTest, ReduceJoiningWithMultipleBases) {
   LRTable::Builder B(TestLang.G);
   B.Transition[{StateID{1}, id("type-name")}] = StateID{5};
   B.Transition[{StateID{2}, id("type-name")}] = StateID{5};
   B.Reduce[StateID{3}].insert(/* type-name := class-name */ RuleID{0});
   B.Reduce[StateID{4}].insert(/* type-name := enum-name */ RuleID{1});
   TestLang.Table = std::move(B).build();
 
   std::vector<const GSS::Node *> Heads = {GSSNode3, GSSNode4};
-  glrReduce(Heads, tokenSymbol(tok::eof), {TestLang.G, TestLang.Table, Arena, GSStack});
+  glrReduce(Heads, tokenSymbol(tok::eof), {emptyTokenStream(), Arena, GSStack},
+            TestLang);
 
   // Verify that the stack heads are joint at state 5 after reduces.
   EXPECT_THAT(Heads, UnorderedElementsAre(GSSNode3, GSSNode4,
                                           AllOf(state(5),
                                                 parsedSymbolID(id("type-name")),
                                                 parents({GSSNode1, GSSNode2}))))
       << Heads;
   // Verify that we create an ambiguous ForestNode of two parses of `type-name`.
TEST_F(GLRTest, ReduceJoiningWithSameBase) {
   LRTable::Builder B(TestLang.G);
   B.Transition[{StateID{0}, id("pointer")}] = StateID{5};
   B.Reduce[StateID{3}].insert(/* pointer := class-name */ RuleID{0});
   B.Reduce[StateID{4}].insert(/* pointer := enum-name */ RuleID{1});
   TestLang.Table = std::move(B).build();
 
   std::vector<const GSS::Node *> Heads = {GSSNode3, GSSNode4};
   glrReduce(Heads, tokenSymbol(tok::eof),
-            {TestLang.G, TestLang.Table, Arena, GSStack});
+            {emptyTokenStream(), Arena, GSStack}, TestLang);
 
   EXPECT_THAT(
       Heads, UnorderedElementsAre(GSSNode3, GSSNode4,
                                   AllOf(state(5), parsedSymbolID(id("pointer")),
                                         parents({GSSNode0}))))
       << Heads;
   EXPECT_EQ(Heads.back()->Payload->dumpRecursive(TestLang.G),
             "[  0, end) pointer := <ambiguous>\n"
TEST_F(GLRTest, ReduceLookahead) {
 
   const auto *Root =
       GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr, /*Parents=*/{});
   const auto *GSSNode1 =
       GSStack.addNode(/*State=*/1, /*ForestNode=*/Identifier, {Root});
 
   // When the lookahead is +, reduce is performed.
   std::vector<const GSS::Node *> Heads = {GSSNode1};
-  glrReduce(Heads, tokenSymbol(tok::plus), {TestLang.G, TestLang.Table, Arena, GSStack});
+  glrReduce(Heads, tokenSymbol(tok::plus), {emptyTokenStream(), Arena, GSStack},
+            TestLang);
   EXPECT_THAT(Heads,
               ElementsAre(GSSNode1, AllOf(state(2), parsedSymbolID(id("term")),
                                           parents(Root))));
 
   // When the lookahead is -, reduce is not performed.
   Heads = {GSSNode1};
-  glrReduce(Heads, tokenSymbol(tok::minus), {TestLang.G, TestLang.Table, Arena, GSStack});
+  glrReduce(Heads, tokenSymbol(tok::minus),
+            {emptyTokenStream(), Arena, GSStack}, TestLang);
   EXPECT_THAT(Heads, ElementsAre(GSSNode1));
 }
 
 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
build(R"bnf(
     left-paren := {
     expr := IDENTIFIER
   )bnf");
   TestLang.Table = LRTable::buildSLR(TestLang.G);
   clang::LangOptions LOptions;
   const TokenStream &Tokens = cook(lex("{ abc", LOptions), LOptions);
 
   const ForestNode &Parsed =
-      glrParse(Tokens, {TestLang.G, TestLang.Table, Arena, GSStack}, id("test"));
+      glrParse({Tokens, Arena, GSStack}, id("test"), TestLang);
   // Verify that there is no duplicated sequence node of `expr := IDENTIFIER`
   // in the forest, see the `#1` and `=#1` in the dump string.
   EXPECT_EQ(Parsed.dumpRecursive(TestLang.G),
             "[  0, end) test := <ambiguous>\n"
             "[  0, end) ├─test := { expr\n"
             "[  0,   1) │ ├─{ := tok[0]\n"
             "[  1, end) │ └─expr := IDENTIFIER #1\n"
             "[  1, end) │   └─IDENTIFIER := tok[1]\n"
build(R"bnf(
     test := foo
     foo := IDENTIFIER
   )bnf");
   clang::LangOptions LOptions;
   const TokenStream &Tokens = cook(lex("IDENTIFIER", LOptions), LOptions);
   TestLang.Table = LRTable::buildSLR(TestLang.G);
 
   const ForestNode &Parsed =
-      glrParse(Tokens, {TestLang.G, TestLang.Table, Arena, GSStack}, id("test"));
+      glrParse({Tokens, Arena, GSStack}, id("test"), TestLang);
   EXPECT_EQ(Parsed.dumpRecursive(TestLang.G),
             "[  0, end) test := <ambiguous>\n"
             "[  0, end) ├─test := IDENTIFIER\n"
             "[  0, end) │ └─IDENTIFIER := tok[0]\n"
             "[  0, end) └─test := foo\n"
             "[  0, end)   └─foo := IDENTIFIER\n"
             "[  0, end)     └─IDENTIFIER := tok[0]\n");
 }
 
 TEST_F(GLRTest, NoExplicitAccept) {
   build(R"bnf(
     _ := test
 
     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, {TestLang.G, TestLang.Table, Arena, GSStack}, id("test"));
+      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 := IDENTIFIER [guard=TestOnly]
+  )bnf");
+  TestLang.Guards.try_emplace(
+      extensionID("TestOnly"),
+      [&](llvm::ArrayRef<const ForestNode *> RHS, const TokenStream &Tokens) {
+        assert(RHS.size() == 1 &&
+               RHS.front()->symbol() == tokenSymbol(clang::tok::identifier));
+        return Tokens.tokens()[RHS.front()->startTokenIndex()].text() == "test";
+      });
+  clang::LangOptions LOptions;
+  TestLang.Table = LRTable::buildSLR(TestLang.G);
+
+  std::string Input = "test";
+  const TokenStream &Succeeded = cook(lex(Input, LOptions), LOptions);
+  EXPECT_EQ(glrParse({Succeeded, Arena, GSStack}, id("start"), TestLang)
+                .dumpRecursive(TestLang.G),
+            "[  0, end) start := IDENTIFIER [guard=TestOnly]\n"
+            "[  0, end) └─IDENTIFIER := tok[0]\n");
+
+  Input = "notest";
+  const TokenStream &Failed = cook(lex(Input, LOptions), LOptions);
+  EXPECT_EQ(glrParse({Failed, Arena, GSStack}, id("start"), TestLang)
+                .dumpRecursive(TestLang.G),
+            "[  0, end) start := <opaque>\n");
+}
+
 TEST(GSSTest, GC) {
   //      ┌-A-┬-AB
   //      ├-B-┘
   // Root-+-C
   //      ├-D
   //      └-E
   GSS GSStack;
   auto *Root = GSStack.addNode(0, nullptr, {});