[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

68

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

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

26

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

298

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

94

drop if(true)?

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

51

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

57

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

306

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

298

Changed the signature of glrShift/Reduce/Parse.

306

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

116–117

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

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

295

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

299

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

441

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

444

remove

[hokein]

address comments.

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

 //===----------------------------------------------------------------------===//
 
 #include "benchmark/benchmark.h"
 #include "clang-pseudo/Bracket.h"
 #include "clang-pseudo/DirectiveTree.h"
 #include "clang-pseudo/Forest.h"
 #include "clang-pseudo/GLR.h"
 #include "clang-pseudo/Token.h"
+#include "clang-pseudo/cli/CLI.h"
 #include "clang-pseudo/grammar/Grammar.h"
 #include "clang-pseudo/grammar/LRTable.h"
 #include "clang/Basic/LangOptions.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/raw_ostream.h"
 #include <string>
 
 using llvm::cl::desc;
 using llvm::cl::opt;
 using llvm::cl::Required;
 
-static opt<std::string> GrammarFile("grammar",
-                                    desc("Parse and check a BNF grammar file."),
-                                    Required);
 static opt<std::string> Source("source", desc("Source file"), Required);
 
 namespace clang {
 namespace pseudo {
 namespace bench {
 namespace {
 
-const std::string *GrammarText = nullptr;
 const std::string *SourceText = nullptr;
-const Grammar *G = nullptr;
 
-void setupGrammarAndSource() {
+void setupSource() {
   auto ReadFile = [](llvm::StringRef FilePath) -> std::string {
     llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> GrammarText =
         llvm::MemoryBuffer::getFile(FilePath);
     if (std::error_code EC = GrammarText.getError()) {
       llvm::errs() << "Error: can't read file '" << FilePath
                    << "': " << EC.message() << "\n";
       std::exit(1);
     }
     return GrammarText.get()->getBuffer().str();
   };
-  GrammarText = new std::string(ReadFile(GrammarFile));
   SourceText = new std::string(ReadFile(Source));
-  std::vector<std::string> Diags;
-  G = Grammar::parseBNF(*GrammarText, Diags).release();
 }
 
-static void parseBNF(benchmark::State &State) {
-  std::vector<std::string> Diags;
-  for (auto _ : State)
-    Grammar::parseBNF(*GrammarText, Diags);
-}
-BENCHMARK(parseBNF);
-
 static void buildSLR(benchmark::State &State) {
   for (auto _ : State)
-    LRTable::buildSLR(*G);
+    LRTable::buildSLR(cli::getLanguage().G);
 }
 BENCHMARK(buildSLR);
 
 TokenStream lexAndPreprocess() {
   clang::LangOptions LangOpts = genericLangOpts();
   TokenStream RawStream = pseudo::lex(*SourceText, LangOpts);
   auto DirectiveStructure = DirectiveTree::parse(RawStream);
   chooseConditionalBranches(DirectiveStructure, RawStream);
stripComments(
         cook(DirectiveStructure.stripDirectives(RawStream), LangOpts));
   }
   State.SetBytesProcessed(static_cast<uint64_t>(State.iterations()) *
                           SourceText->size());
 }
 BENCHMARK(preprocess);
 
 static void glrParse(benchmark::State &State) {
-  LRTable Table = clang::pseudo::LRTable::buildSLR(*G);
-  SymbolID StartSymbol = *G->findNonterminal("translation-unit");
+  SymbolID StartSymbol =
+      *cli::getLanguage().G.findNonterminal("translation-unit");
   TokenStream Stream = lexAndPreprocess();
   for (auto _ : State) {
     pseudo::ForestArena Forest;
     pseudo::GSS GSS;
-    pseudo::glrParse(Stream, ParseParams{*G, Table, Forest, GSS}, StartSymbol);
+    pseudo::glrParse(Stream, ParseParams{cli::getLanguage(), Forest, GSS},
+                     StartSymbol);
   }
   State.SetBytesProcessed(static_cast<uint64_t>(State.iterations()) *
                           SourceText->size());
 }
 BENCHMARK(glrParse);
 
 static void full(benchmark::State &State) {
-  LRTable Table = clang::pseudo::LRTable::buildSLR(*G);
-  SymbolID StartSymbol = *G->findNonterminal("translation-unit");
+  SymbolID StartSymbol =
+      *cli::getLanguage().G.findNonterminal("translation-unit");
   for (auto _ : State) {
     TokenStream Stream = lexAndPreprocess();
     pseudo::ForestArena Forest;
     pseudo::GSS GSS;
-    pseudo::glrParse(lexAndPreprocess(), ParseParams{*G, Table, Forest, GSS},
-                     StartSymbol);
+    pseudo::glrParse(lexAndPreprocess(),
+                     ParseParams{cli::getLanguage(), Forest, GSS}, StartSymbol);
   }
   State.SetBytesProcessed(static_cast<uint64_t>(State.iterations()) *
                           SourceText->size());
 }
 BENCHMARK(full);
 
 } // namespace
 } // namespace bench
 } // namespace pseudo
 } // namespace clang
 
 int main(int argc, char *argv[]) {
   benchmark::Initialize(&argc, argv);
   llvm::cl::ParseCommandLineOptions(argc, argv);
-  clang::pseudo::bench::setupGrammarAndSource();
+  clang::pseudo::bench::setupSource();
   benchmark::RunSpecifiedBenchmarks();
   return 0;
 }

clang-tools-extra/pseudo/benchmarks/CMakeLists.txt

 add_benchmark(ClangPseudoBenchmark Benchmark.cpp)
 
 target_link_libraries(ClangPseudoBenchmark
   PRIVATE
   clangPseudo
+  clangPseudoCLI
   clangPseudoGrammar
   LLVMSupport
   )

clang-tools-extra/pseudo/fuzzer/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   FuzzerCLI
   Support
   )
 
 add_llvm_fuzzer(clang-pseudo-fuzzer
   Fuzzer.cpp
   DUMMY_MAIN Main.cpp
   )
 
 target_link_libraries(clang-pseudo-fuzzer
   PRIVATE
   clangPseudo
+  clangPseudoCLI
   clangPseudoGrammar
   )

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

 //===-- Fuzzer.cpp - Fuzz the pseudoparser --------------------------------===//
 //
 // 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/DirectiveTree.h"
 #include "clang-pseudo/Forest.h"
 #include "clang-pseudo/GLR.h"
 #include "clang-pseudo/Token.h"
+#include "clang-pseudo/cli/CLI.h"
 #include "clang-pseudo/grammar/Grammar.h"
 #include "clang-pseudo/grammar/LRTable.h"
 #include "clang/Basic/LangOptions.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 
 namespace clang {
 namespace pseudo {
 namespace {
 
 class Fuzzer {
   clang::LangOptions LangOpts = clang::pseudo::genericLangOpts();
-  std::unique_ptr<Grammar> G;
   LRTable T;
   bool Print;
 
 public:
-  Fuzzer(llvm::StringRef GrammarPath, bool Print) : Print(Print) {
-    llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> GrammarText =
-        llvm::MemoryBuffer::getFile(GrammarPath);
-    if (std::error_code EC = GrammarText.getError()) {
-      llvm::errs() << "Error: can't read grammar file '" << GrammarPath
-                   << "': " << EC.message() << "\n";
-      std::exit(1);
-    }
-    std::vector<std::string> Diags;
-    G = Grammar::parseBNF(GrammarText->get()->getBuffer(), Diags);
-    if (!Diags.empty()) {
-      for (const auto &Diag : Diags)
-        llvm::errs() << Diag << "\n";
-      std::exit(1);
-    }
-    T = LRTable::buildSLR(*G);
-  }
+  Fuzzer(bool Print) : Print(Print) {}
 
   void operator()(llvm::StringRef Code) {
     std::string CodeStr = Code.str(); // Must be null-terminated.
     auto RawStream = lex(CodeStr, LangOpts);
     auto DirectiveStructure = DirectiveTree::parse(RawStream);
     clang::pseudo::chooseConditionalBranches(DirectiveStructure, RawStream);
     // FIXME: strip preprocessor directives
     auto ParseableStream =
         clang::pseudo::stripComments(cook(RawStream, LangOpts));
 
     clang::pseudo::ForestArena Arena;
     clang::pseudo::GSS GSS;
     auto &Root =
-        glrParse(ParseableStream, clang::pseudo::ParseParams{*G, T, Arena, GSS},
-                 *G->findNonterminal("translation-unit"));
+        glrParse(ParseableStream,
+                 clang::pseudo::ParseParams{cli::getLanguage(), Arena, GSS},
+                 *cli::getLanguage().G.findNonterminal("translation-unit"));
     if (Print)
-      llvm::outs() << Root.dumpRecursive(*G);
+      llvm::outs() << Root.dumpRecursive(cli::getLanguage().G);
   }
 };
 
 Fuzzer *Fuzz = nullptr;
 
 } // namespace
 } // namespace pseudo
 } // namespace clang
 
 extern "C" {
 
 // Set up the fuzzer from command line flags:
-//  -grammar=<file> (required) - path to cxx.bnf
 //  -print                     - used for testing the fuzzer
 int LLVMFuzzerInitialize(int *Argc, char ***Argv) {
-  llvm::StringRef GrammarFile;
   bool PrintForest = false;
   auto ConsumeArg = [&](llvm::StringRef Arg) -> bool {
-    if (Arg.consume_front("-grammar=")) {
-      GrammarFile = Arg;
-      return true;
-    } else if (Arg == "-print") {
+    if (Arg == "-print") {
       PrintForest = true;
       return true;
     }
     return false;
   };
   *Argc = std::remove_if(*Argv + 1, *Argv + *Argc, ConsumeArg) - *Argv;
 
-  if (GrammarFile.empty()) {
-    fprintf(stderr, "Fuzzer needs -grammar=/path/to/cxx.bnf\n");
-    exit(1);
-  }
-  clang::pseudo::Fuzz = new clang::pseudo::Fuzzer(GrammarFile, PrintForest);
+  clang::pseudo::Fuzz = new clang::pseudo::Fuzzer(PrintForest);
   return 0;
 }
 
 int LLVMFuzzerTestOneInput(uint8_t *Data, size_t Size) {
   (*clang::pseudo::Fuzz)(llvm::StringRef(reinterpret_cast<char *>(Data), Size));
   return 0;
 }
 }

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 AID = 1 /*skip the sentinel 0 value*/;
+         AID < G->table().AttributeValues.size(); ++AID) {
+      llvm::StringRef Name = G->table().AttributeValues[AID];
+      assert(!Name.empty());
+      Out.os() << llvm::formatv("EXTENSION({0}, {1})\n", Name, AID);
+    }
+    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.
 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;
-
+  const ParseLang &Lang;
   // 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.
void glrShift(std::vector<ParseStep> &PendingShift, const ForestNode &NextTok,
               const ParseParams &Params, NewHeadCallback NewHeadCB);
 // Applies PendingReduce actions, until no more reduce actions are available.
 //
 // When this function returns, PendingReduce is empty. Calls to NewHeadCB may
 // add elements to PendingReduce
 //
 // Exposed for testing only.
 void glrReduce(std::vector<ParseStep> &PendingReduce, const ParseParams &Params,
-               NewHeadCallback NewHeadCB);
+               const TokenStream &Tokens, NewHeadCallback NewHeadCB);
 
 } // 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_LANGUAGE_H
+#define CLANG_PSEUDO_LANGUAGE_H
+
+#include "clang-pseudo/grammar/Grammar.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/STLFunctionalExtras.h"
+
+namespace clang {
+namespace pseudo {
+class ForestNode;
+class TokenStream;
+class LRTable;
+
+// Interface for implementing the grammar "guard" attribute.
+//
+// It is used by the GLR parser to determine whether a reduction of a rule will
+// be conducted during the reduce time.
+//
+// Returns false if the reduction is not conducted (this parsing branch in GLR
+// will die).
+using Guard = llvm::function_ref<bool(llvm::ArrayRef<const ForestNode *> RHS,
+                                      const TokenStream &)>;
+
+// Specify a language that can be parsed by the pseduoparser.
+// Manifest generated from a bnf grammar file.
+struct ParseLang {
+  const Grammar &G;
+  const LRTable &Table;
+  // Binding "guard" extension id to a piece of C++ code.
+  const llvm::DenseMap<ExtensionID, Guard> &Guards;
+
+  // FIXME: add clang::LangOptions.
+  // FIXME: add default start symbols.
+};
+
+} // namespace pseudo
+} // namespace clang
+
+#endif // CLANG_PSEUDO_LANGUAGE_H
 No newline at end of file

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

+//===--- CLI.h - Get grammar from variant sources ----------------*- 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
+//
+//===----------------------------------------------------------------------===//
+//
+// A library shared among different pseudoparser-based tools. It provides a
+// uniform way to get basic pieces of the parser (Grammar, LRTable etc) from
+// variant grammar sources.
+// It defines a `--grammar` CLI flag, which supports 1) using a grammar from a
+// file (--grammar=/path/to/lang.bnf) or using the prebuilt cxx language
+// (--grammar=cxx).
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef CLANG_PSEUDO_CLI_CLI_H
+#define CLANG_PSEUDO_CLI_CLI_H
+
+namespace clang {
+namespace pseudo {
+struct ParseLang;
+namespace cli {
+// Returns the corresponding language from the '--grammar' command-line flag.
+const ParseLang &getLanguage();
+} // namespace cli
+} // namespace pseudo
+} // namespace clang
+
+#endif // CLANG_PSEUDO_CLI_CLI_H

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

 #ifndef CLANG_PSEUDO_CXX_CXX_H
 #define CLANG_PSEUDO_CXX_CXX_H
 
 #include "clang-pseudo/grammar/Grammar.h"
 
 namespace clang {
 namespace pseudo {
 class LRTable;
-
+class ParseLang;
 namespace cxx {
 // 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
 };
 
-// Returns the C++ grammar.
-const Grammar &getGrammar();
-// Returns the corresponding LRTable for the C++ grammar.
-const LRTable &getLRTable();
+enum class Extension : ExtensionID {
+#define EXTENSION(X, Y) X = Y,
+#include "CXXSymbols.inc"
+#undef EXTENSION
+};
+
+const ParseLang &getLanguage();
 
 } // namespace cxx
 
 } // namespace pseudo
 } // namespace clang
 
 #endif // CLANG_PSEUDO_CXX_CXX_H

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

+add_subdirectory(cli)
 add_subdirectory(cxx)
 add_subdirectory(grammar)
 
 set(LLVM_LINK_COMPONENTS Support)
 
 add_clang_library(clangPseudo
   Bracket.cpp
   DirectiveTree.cpp

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

OS << llvm::formatv("state {0}, parsed symbol {1}, parents {2}", N.State,
                       N.Payload->symbol(), llvm::join(ParentStates, ", "));
   return OS;
 }
 
 const ForestNode &glrParse(const TokenStream &Tokens, const ParseParams &Params,
                            SymbolID StartSymbol) {
   assert(isNonterminal(StartSymbol) && "Start symbol must be a nonterminal");
   llvm::ArrayRef<ForestNode> Terminals = Params.Forest.createTerminals(Tokens);
-  auto &G = Params.G;
+  auto &G = Params.Lang.G;
   (void)G;
   auto &GSS = Params.GSStack;
 
   // Lists of active shift, reduce actions.
   std::vector<ParseStep> PendingShift, PendingReduce;
   auto AddSteps = [&](const GSS::Node *Head, SymbolID NextTok) {
-    for (const auto &Action : Params.Table.getActions(Head->State, NextTok)) {
+    for (const auto &Action : Params.Lang.Table.getActions(Head->State, NextTok)) {
       switch (Action.kind()) {
       case LRTable::Action::Shift:
         PendingShift.push_back({Head, Action});
         break;
       case LRTable::Action::Reduce:
         PendingReduce.push_back({Head, Action});
         break;
       default:
         llvm_unreachable("unexpected action kind!");
       }
     }
   };
-  StateID StartState = Params.Table.getStartState(StartSymbol);
+  StateID StartState = Params.Lang.Table.getStartState(StartSymbol);
   std::vector<const GSS::Node *> NewHeads = {
       GSS.addNode(/*State=*/StartState,
                   /*ForestNode=*/nullptr, {})};
   auto MaybeGC = [&, Roots(std::vector<const GSS::Node *>{}), I(0u)]() mutable {
     assert(PendingShift.empty() && PendingReduce.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 = NewHeads;
     GSS.gc(std::move(Roots));
   };
   for (const ForestNode &Terminal : Terminals) {
     LLVM_DEBUG(llvm::dbgs() << llvm::formatv("Next token {0} (id={1})\n",
                                              G.symbolName(Terminal.symbol()),
                                              Terminal.symbol()));
     for (const auto *Head : NewHeads)
       AddSteps(Head, Terminal.symbol());
     NewHeads.clear();
-    glrReduce(PendingReduce, Params,
+    glrReduce(PendingReduce, Params, Tokens,
               [&](const GSS::Node * NewHead) {
                 // A reduce will enable more steps.
                 AddSteps(NewHead, Terminal.symbol());
               });
 
     glrShift(PendingShift, Terminal, Params,
              [&](const GSS::Node *NewHead) { NewHeads.push_back(NewHead); });
     MaybeGC();
   }
   LLVM_DEBUG(llvm::dbgs() << llvm::formatv("Next is eof\n"));
   for (const auto *Heads : NewHeads)
     AddSteps(Heads, tokenSymbol(tok::eof));
 
-  StateID AcceptState = Params.Table.getGoToState(StartState, StartSymbol);
+  StateID AcceptState = Params.Lang.Table.getGoToState(StartState, StartSymbol);
   // Collect new heads created from the final reduce.
   std::vector<const GSS::Node*> Heads;
-  glrReduce(PendingReduce, Params, [&](const GSS::Node *NewHead) {
+  glrReduce(PendingReduce, Params, Tokens, [&](const GSS::Node *NewHead) {
     Heads.push_back(NewHead);
     // A reduce will enable more steps.
     AddSteps(NewHead, tokenSymbol(tok::eof));
   });
 
   const ForestNode *Result = nullptr;
   for (const auto *Head : Heads) {
     if (Head->State == AcceptState) {
void glrShift(std::vector<ParseStep> &PendingShift, const ForestNode &NewTok,
               const ParseParams &Params, NewHeadCallback NewHeadCB) {
   assert(NewTok.kind() == ForestNode::Terminal);
   assert(llvm::all_of(PendingShift,
                       [](const ParseStep &Step) {
                         return Step.Action.kind() == LRTable::Action::Shift;
                       }) &&
          "Pending shift actions must be shift actions");
   LLVM_DEBUG(llvm::dbgs() << llvm::formatv("  Shift {0} ({1} active heads):\n",
-                                           Params.G.symbolName(NewTok.symbol()),
+                                           Params.Lang.G.symbolName(NewTok.symbol()),
                                            PendingShift.size()));
 
   // We group pending shifts by their target state so we can merge them.
   llvm::stable_sort(PendingShift, [](const ParseStep &L, const ParseStep &R) {
     return L.Action.getShiftState() < R.Action.getShiftState();
   });
   auto Rest = llvm::makeArrayRef(PendingShift);
   llvm::SmallVector<const GSS::Node *> Parents;

 //
 //   Before (joining due to same goto state, the same base):
 //     0--1(class-name)--3(STAR)
 //     └--2(enum-name)--4(STAR)
 //   After reducing 3 by `pointer := class-name STAR` and
 //                  2 by`enum-name := class-name STAR`:
 //     0--5(pointer)       // 5 is goto(0, pointer)
 void glrReduce(std::vector<ParseStep> &PendingReduce, const ParseParams &Params,
+               const TokenStream& Tokens,
                NewHeadCallback NewHeadCB) {
   // 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
void glrReduce(std::vector<ParseStep> &PendingReduce, const ParseParams &Params,
   struct PushSpec {
     // A base node is the head after popping the GSS nodes we are reducing.
     const GSS::Node* Base = nullptr;
     Sequence Seq;
   };
   KeyedQueue<Family, PushSpec> Sequences;
 
   Sequence TempSequence;
   // 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.
   auto Pop = [&](const GSS::Node *Head, RuleID RID) {
-    LLVM_DEBUG(llvm::dbgs() << "  Pop " << Params.G.dumpRule(RID) << "\n");
-    const auto &Rule = Params.G.lookupRule(RID);
+    LLVM_DEBUG(llvm::dbgs() << "  Pop " << Params.Lang.G.dumpRule(RID) << "\n");
+    const auto &Rule = Params.Lang.G.lookupRule(RID);
     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) {
       if (I == Rule.Size) {
+        if (Rule.Guard) {
+          auto It = Params.Lang.Guards.find(Rule.Guard);
+          assert(It != Params.Lang.Guards.end() && "missing guard!");
+          if (!It->getSecond()(TempSequence, Tokens))
+            return;
+        }
         F.Start = TempSequence.front()->startTokenIndex();
         LLVM_DEBUG(llvm::dbgs() << "    --> base at S" << N->State << "\n");
         Sequences.emplace(F, PushSpec{N, TempSequence});
         return;
       }
       TempSequence[Rule.Size - 1 - I] = N->Payload;
       for (const GSS::Node *Parent : N->parents())
         DFS(Parent, I + 1, DFS);
void glrReduce(std::vector<ParseStep> &PendingReduce, const ParseParams &Params,
   // Main reduction loop:
   //  - pop as much as we can
   //  - process one family at a time, forming a forest node
   //  - produces new GSS heads which may enable more pops
   PopPending();
   while (!Sequences.empty()) {
     Family F = Sequences.top().first;
 
-    LLVM_DEBUG(llvm::dbgs() << "  Push " << Params.G.symbolName(F.Symbol)
+    LLVM_DEBUG(llvm::dbgs() << "  Push " << Params.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 {
       FamilySequences.emplace_back(Sequences.top().first.Rule,
                                    Sequences.top().second.Seq);
       FamilyBases.emplace_back(
-          Params.Table.getGoToState(Sequences.top().second.Base->State,
+          Params.Lang.Table.getGoToState(Sequences.top().second.Base->State,
                                     F.Symbol),
           Sequences.top().second.Base);
 
       Sequences.pop();
     } while (!Sequences.empty() && Sequences.top().first == F);
     // Build a forest node for each unique sequence.
     sortAndUnique(FamilySequences);
     auto &SequenceNodes = TempForestNodes;
     SequenceNodes.clear();
     for (const auto &SequenceSpec : FamilySequences)
       SequenceNodes.push_back(&Params.Forest.createSequence(
           F.Symbol, SequenceSpec.first, SequenceSpec.second));
     // 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(Params.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;
       auto &Parents = TempGSSNodes;

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/Language.h"
+#include "clang-pseudo/cxx/CXX.h"
+#include "clang-pseudo/grammar/LRTable.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/ErrorOr.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include <utility>
+
+static llvm::cl::opt<std::string>
+    Grammar("grammar",
+            llvm::cl::desc(
+                "Specify a BNF grammar file path, or builtin language (cxx)."),
+            llvm::cl::init("cxx"));
+
+namespace clang {
+namespace pseudo {
+
+static bool alwaysAccept(llvm::ArrayRef<const ForestNode *> RHS,
+                         const TokenStream &) {
+  return true;
+}
+
+namespace cli {
+const ParseLang &getLanguage() {
+  if (::Grammar == "cxx")
+    return cxx::getLanguage();
+
+  static ParseLang *PL = [&]() {
+    // Read from a bnf grammar file.
+    llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> GrammarText =
+        llvm::MemoryBuffer::getFile(::Grammar);
+    if (std::error_code EC = GrammarText.getError()) {
+      llvm::errs() << "Error: can't read grammar file '" << ::Grammar
+                   << "': " << EC.message() << "\n";
+      std::exit(1);
+    }
+    std::vector<std::string> Diags;
+    auto G = Grammar::parseBNF(GrammarText->get()->getBuffer(), Diags);
+    if (!Diags.empty()) {
+      for (const auto &Diag : Diags)
+        llvm::errs() << Diag << "\n";
+      std::exit(1);
+    }
+
+    LRTable *Table = new LRTable(LRTable::buildSLR(*G));
+    llvm::DenseMap<ExtensionID, Guard> *Guards =
+        new llvm::DenseMap<ExtensionID, Guard>();
+    for (ExtensionID ID = 1; ID < G->table().AttributeValues.size(); ++ID)
+      Guards->insert(std::make_pair(ID, alwaysAccept));
+    return new ParseLang{*G.release(), *Table, *Guards};
+  }();
+  return *PL;
+}
+} // namespace cli
+
+} // namespace pseudo
+} // namespace clang

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

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

clang-tools-extra/pseudo/lib/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/lib/cxx/CMakeLists.txt

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

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"
     ;
-
 const Grammar &getGrammar() {
   static std::vector<std::string> Diags;
   static Grammar *G = Grammar::parseBNF(CXXBNF, Diags).release();
   assert(Diags.empty());
   return *G;
 }
 
 const LRTable &getLRTable() {
   static LRTable *Table = new LRTable(LRTable::buildSLR(getGrammar()));
   return *Table;
 }
 
+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";
+}
+} // namespace
+
+const ParseLang &getLanguage() {
+  static llvm::DenseMap<ExtensionID, Guard> *Guards =
+      new llvm::DenseMap<ExtensionID, Guard>(
+          {{(ExtensionID)Extension::Override, guardOverride},
+           {(ExtensionID)Extension::Final, guardFinal}});
+  static ParseLang *L = new ParseLang{getGrammar(), getLRTable(), *Guards};
+  return *L;
+}
+
 } // namespace cxx
 } // namespace pseudo
 } // namespace clang

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]
+};
 No newline at end of file

clang-tools-extra/pseudo/tool/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS support)
 
 add_clang_tool(clang-pseudo
   ClangPseudo.cpp
   )
 
 clang_target_link_libraries(clang-pseudo
   PRIVATE
   clangBasic
   )
 
 target_link_libraries(clang-pseudo
   PRIVATE
   clangPseudo
   clangPseudoGrammar
+  clangPseudoCLI
   )
 

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

 //===-- ClangPseudo.cpp - Clang pseudoparser tool -------------------------===//
 //
 // 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/Bracket.h"
 #include "clang-pseudo/DirectiveTree.h"
 #include "clang-pseudo/GLR.h"
 #include "clang-pseudo/Token.h"
+#include "clang-pseudo/cli/CLI.h"
 #include "clang-pseudo/grammar/Grammar.h"
 #include "clang-pseudo/grammar/LRGraph.h"
 #include "clang-pseudo/grammar/LRTable.h"
 #include "clang/Basic/LangOptions.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Signals.h"
 
-using clang::pseudo::Grammar;
 using clang::pseudo::TokenStream;
 using llvm::cl::desc;
 using llvm::cl::init;
 using llvm::cl::opt;
 
-static opt<std::string>
-    Grammar("grammar", desc("Parse and check a BNF grammar file."), init(""));
 static opt<bool> PrintGrammar("print-grammar", desc("Print the grammar."));
 static opt<bool> PrintGraph("print-graph",
                             desc("Print the LR graph for the grammar"));
 static opt<bool> PrintTable("print-table",
                             desc("Print the LR table for the grammar"));
 static opt<std::string> Source("source", desc("Source file"));
 static opt<bool> PrintSource("print-source", desc("Print token stream"));
 static opt<bool> PrintTokens("print-tokens", desc("Print detailed token info"));
if (PrintTokens)
       llvm::outs() << *Stream;
     if (PrintDirectiveTree)
       llvm::outs() << DirectiveStructure;
 
     ParseableStream = clang::pseudo::stripComments(cook(*Stream, LangOpts));
     pairBrackets(*ParseableStream);
   }
 
-  if (Grammar.getNumOccurrences()) {
-    std::string Text = readOrDie(Grammar);
-    std::vector<std::string> Diags;
-    auto G = Grammar::parseBNF(Text, Diags);
-
-    if (!Diags.empty()) {
-      llvm::errs() << llvm::join(Diags, "\n");
-      return 2;
-    }
-    llvm::outs() << llvm::formatv("grammar file {0} is parsed successfully\n",
-                                  Grammar);
+  if (true) {
+    const auto &Lang = clang::pseudo::cli::getLanguage();
     if (PrintGrammar)
-      llvm::outs() << G->dump();
+      llvm::outs() << Lang.G.dump();
     if (PrintGraph)
-      llvm::outs() << clang::pseudo::LRGraph::buildLR0(*G).dumpForTests(*G);
-    auto LRTable = clang::pseudo::LRTable::buildSLR(*G);
+      llvm::outs() << clang::pseudo::LRGraph::buildLR0(Lang.G).dumpForTests(
+          Lang.G);
+
     if (PrintTable)
-      llvm::outs() << LRTable.dumpForTests(*G);
+      llvm::outs() << Lang.Table.dumpForTests(Lang.G);
     if (PrintStatistics)
-      llvm::outs() << LRTable.dumpStatistics();
+      llvm::outs() << Lang.Table.dumpStatistics();
 
     if (ParseableStream) {
       clang::pseudo::ForestArena Arena;
       clang::pseudo::GSS GSS;
       llvm::Optional<clang::pseudo::SymbolID> StartSymID =
-          G->findNonterminal(StartSymbol);
+          Lang.G.findNonterminal(StartSymbol);
       if (!StartSymID) {
         llvm::errs() << llvm::formatv(
-            "The start symbol {0} doesn't exit in the grammar!\n", Grammar);
+            "The start symbol {0} doesn't exit in the grammar!\n", StartSymbol);
         return 2;
       }
-      auto &Root = glrParse(*ParseableStream,
-                            clang::pseudo::ParseParams{*G, LRTable, Arena, GSS},
-                            *StartSymID);
+      auto &Root =
+          glrParse(*ParseableStream,
+                   clang::pseudo::ParseParams{Lang, Arena, GSS}, *StartSymID);
       if (PrintForest)
-        llvm::outs() << Root.dumpRecursive(*G, /*Abbreviated=*/true);
+        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";
       }
     }
   }
 
   return 0;
 }

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

 }
 
 class GLRTest : public ::testing::Test {
 public:
   void build(llvm::StringRef GrammarBNF) {
     std::vector<std::string> Diags;
     G = Grammar::parseBNF(GrammarBNF, Diags);
   }
-
+  // FIXME: move to TokenStream class.
+  TokenStream emptyTokenStream() {
+    TokenStream Empty;
+    Empty.finalize();
+    return Empty;
+  }
+  ParseLang getTestLang() {
+    return {*G, Table, Guards};
+  }
   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 (G->table().Terminals[I] == Name)
         return tokenSymbol(static_cast<tok::TokenKind>(I));
     for (SymbolID ID = 0; ID < G->table().Nonterminals.size(); ++ID)
       if (G->table().Nonterminals[ID].Name == Name)
         return ID;
     ADD_FAILURE() << "No such symbol found: " << Name;
     return 0;
   }
-
+  ExtensionID extensionID(llvm::StringRef AttrValueName) const {
+    for (unsigned I = 0; I < G->table().AttributeValues.size(); ++I)
+      if (G->table().AttributeValues[I] == AttrValueName)
+        return static_cast<ExtensionID>(I);
+    ADD_FAILURE() << "No such attribute value found: " << AttrValueName;
+    return 0;
+  }
   RuleID ruleFor(llvm::StringRef NonterminalName) const {
     auto RuleRange = G->table().Nonterminals[id(NonterminalName)].RuleRange;
     if (RuleRange.End - RuleRange.Start == 1)
       return G->table().Nonterminals[id(NonterminalName)].RuleRange.Start;
     ADD_FAILURE() << "Expected a single rule for " << NonterminalName
                   << ", but it has " << RuleRange.End - RuleRange.Start
                   << " rule!\n";
     return 0;
   }
 
   NewHeadCallback captureNewHeads() {
     return [this](const GSS::Node *NewHead) {
       NewHeadResults.push_back(NewHead);
     };
   };
 
 protected:
   std::unique_ptr<Grammar> G;
+  LRTable Table;
+  llvm::DenseMap<ExtensionID, Guard> Guards;
   ForestArena Arena;
   GSS GSStack;
   std::vector<const GSS::Node*> NewHeadResults;
 };
 
 TEST_F(GLRTest, ShiftMergingHeads) {
   // Given a test case where we have two heads 1, 2, 3 in the GSS, the heads 1,
   // 2 have shift actions to reach state 4, and the head 3 has a shift action to
TEST_F(GLRTest, ShiftMergingHeads) {
   auto *GSSNode1 = GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr,
                                    /*Parents=*/{GSSNode0});
   auto *GSSNode2 = GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr,
                                    /*Parents=*/{GSSNode0});
   auto *GSSNode3 = GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr,
                                    /*Parents=*/{GSSNode0});
 
   buildGrammar({}, {}); // Create a fake empty grammar.
-  LRTable T = LRTable::buildForTests(G->table(), /*Entries=*/{});
+  Table = LRTable::buildForTests(G->table(), /*Entries=*/{});
 
   ForestNode &SemiTerminal = Arena.createTerminal(tok::semi, 0);
   std::vector<ParseStep> PendingShift = {
       {GSSNode1, Action::shift(4)},
       {GSSNode3, Action::shift(5)},
       {GSSNode2, Action::shift(4)},
   };
-  glrShift(PendingShift, SemiTerminal, {*G, T, Arena, GSStack},
+  glrShift(PendingShift, SemiTerminal,  {getTestLang(), Arena, GSStack},
            captureNewHeads());
 
   EXPECT_THAT(NewHeadResults, testing::UnorderedElementsAre(
                                   AllOf(state(4), parsedSymbol(&SemiTerminal),
                                         parents({GSSNode1, GSSNode2})),
                                   AllOf(state(5), parsedSymbol(&SemiTerminal),
                                         parents({GSSNode3}))))
       << NewHeadResults;
 }
 
 TEST_F(GLRTest, ReduceConflictsSplitting) {
   //  Before (splitting due to R/R conflict):
   //    0--1(IDENTIFIER)
   //  After reducing 1 by `class-name := IDENTIFIER` and
   //                      `enum-name := IDENTIFIER`:
   //    0--2(class-name)    // 2 is goto(0, class-name)
   //    └--3(enum-name)     // 3 is goto(0, enum-name)
   buildGrammar({"class-name", "enum-name"},
                {"class-name := IDENTIFIER", "enum-name := IDENTIFIER"});
 
-  LRTable Table = LRTable::buildForTests(
+  Table = LRTable::buildForTests(
       G->table(), {{/*State=*/0, id("class-name"), Action::goTo(2)},
                    {/*State=*/0, id("enum-name"), Action::goTo(3)}});
 
   const auto *GSSNode0 =
       GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr, /*Parents=*/{});
   const auto *GSSNode1 =
       GSStack.addNode(3, &Arena.createTerminal(tok::identifier, 0), {GSSNode0});
 
   std::vector<ParseStep> PendingReduce = {
       {GSSNode1, Action::reduce(ruleFor("class-name"))},
       {GSSNode1, Action::reduce(ruleFor("enum-name"))}};
-  glrReduce(PendingReduce, {*G, Table, Arena, GSStack},
+  glrReduce(PendingReduce, {getTestLang(), Arena, GSStack}, emptyTokenStream(),
             captureNewHeads());
   EXPECT_THAT(NewHeadResults,
               testing::UnorderedElementsAre(
                   AllOf(state(2), parsedSymbolID(id("class-name")),
                         parents({GSSNode0})),
                   AllOf(state(3), parsedSymbolID(id("enum-name")),
                         parents({GSSNode0})))) << NewHeadResults;
 }
TEST_F(GLRTest, ReduceSplittingDueToMultipleBases) {
   const auto *GSSNode2 =
       GSStack.addNode(/*State=*/2, /*ForestNode=*/ClassNameNode, /*Parents=*/{});
   const auto *GSSNode3 =
       GSStack.addNode(/*State=*/3, /*ForestNode=*/EnumNameNode, /*Parents=*/{});
   const auto *GSSNode4 = GSStack.addNode(
       /*State=*/4, &Arena.createTerminal(tok::star, /*TokenIndex=*/1),
       /*Parents=*/{GSSNode2, GSSNode3});
 
-  LRTable Table = LRTable::buildForTests(
+  Table = LRTable::buildForTests(
       G->table(),
       {{/*State=*/2, id("ptr-operator"), Action::goTo(/*NextState=*/5)},
        {/*State=*/3, id("ptr-operator"), Action::goTo(/*NextState=*/6)}});
   std::vector<ParseStep> PendingReduce = {
       {GSSNode4, Action::reduce(ruleFor("ptr-operator"))}};
-  glrReduce(PendingReduce, {*G, Table, Arena, GSStack},
+  glrReduce(PendingReduce, {getTestLang(), Arena, GSStack}, emptyTokenStream(),
             captureNewHeads());
 
   EXPECT_THAT(NewHeadResults,
               testing::UnorderedElementsAre(
                   AllOf(state(5), parsedSymbolID(id("ptr-operator")),
                         parents({GSSNode2})),
                   AllOf(state(6), parsedSymbolID(id("ptr-operator")),
                         parents({GSSNode3})))) << NewHeadResults;
const auto *GSSNode2 = GSStack.addNode(
       /*State=*/2, /*ForestNode=*/CVQualifierNode, /*Parents=*/{GSSNode0});
   const auto *GSSNode3 =
       GSStack.addNode(/*State=*/3, /*ForestNode=*/ClassNameNode,
                       /*Parents=*/{GSSNode1});
   const auto *GSSNode4 =
       GSStack.addNode(/*State=*/4, /*ForestNode=*/EnumNameNode,
                       /*Parents=*/{GSSNode2});
 
-  LRTable Table = LRTable::buildForTests(
+  Table = LRTable::buildForTests(
       G->table(),
       {{/*State=*/1, id("type-name"), Action::goTo(/*NextState=*/5)},
        {/*State=*/2, id("type-name"), Action::goTo(/*NextState=*/5)}});
   // FIXME: figure out a way to get rid of the hard-coded reduce RuleID!
   std::vector<ParseStep> PendingReduce = {
       {
           GSSNode3, Action::reduce(/*RuleID=*/0) // type-name := class-name
       },
       {
           GSSNode4, Action::reduce(/*RuleID=*/1) // type-name := enum-name
       }};
-  glrReduce(PendingReduce, {*G, Table, Arena, GSStack},
+  glrReduce(PendingReduce, {getTestLang(), Arena, GSStack}, emptyTokenStream(),
             captureNewHeads());
 
   // Verify that the stack heads are joint at state 5 after reduces.
   EXPECT_THAT(NewHeadResults, testing::UnorderedElementsAre(AllOf(
                                   state(5), parsedSymbolID(id("type-name")),
                                   parents({GSSNode1, GSSNode2}))))
       << NewHeadResults;
   // Verify that we create an ambiguous ForestNode of two parses of `type-name`.
const auto *GSSNode2 =
                       /*Parents=*/{GSSNode0});
   const auto *GSSNode3 =
       GSStack.addNode(/*State=*/3, /*ForestNode=*/StartTerminal,
                       /*Parents=*/{GSSNode1});
   const auto *GSSNode4 =
       GSStack.addNode(/*State=*/4, /*ForestNode=*/StartTerminal,
                       /*Parents=*/{GSSNode2});
 
-  LRTable Table = LRTable::buildForTests(
+  Table = LRTable::buildForTests(
       G->table(), {{/*State=*/0, id("pointer"), Action::goTo(5)}});
   // FIXME: figure out a way to get rid of the hard-coded reduce RuleID!
   std::vector<ParseStep> PendingReduce = {
       {
           GSSNode3, Action::reduce(/*RuleID=*/0) // pointer := class-name *
       },
       {
           GSSNode4, Action::reduce(/*RuleID=*/1) // pointer := enum-name *
       }};
-  glrReduce(PendingReduce, {*G, Table, Arena, GSStack},
+  glrReduce(PendingReduce,{getTestLang(), Arena, GSStack}, emptyTokenStream(),
             captureNewHeads());
 
   EXPECT_THAT(NewHeadResults, testing::UnorderedElementsAre(
                                   AllOf(state(5), parsedSymbolID(id("pointer")),
                                         parents({GSSNode0}))))
       << NewHeadResults;
   EXPECT_EQ(NewHeadResults.front()->Payload->dumpRecursive(*G),
             "[  0, end) pointer := <ambiguous>\n"
build(R"bnf(
     _ := test
 
     test := { expr
     test := { IDENTIFIER
     test := left-paren expr
     left-paren := {
     expr := IDENTIFIER
   )bnf");
+  Table = LRTable::buildSLR(*G);
   clang::LangOptions LOptions;
   const TokenStream &Tokens = cook(lex("{ abc", LOptions), LOptions);
-  auto LRTable = LRTable::buildSLR(*G);
 
   const ForestNode &Parsed =
-      glrParse(Tokens, {*G, LRTable, Arena, GSStack}, id("test"));
+      glrParse(Tokens, {getTestLang(), Arena, GSStack}, id("test"));
   // 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(*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
 
     test := IDENTIFIER
     test := foo
     foo := IDENTIFIER
   )bnf");
   clang::LangOptions LOptions;
   const TokenStream &Tokens = cook(lex("IDENTIFIER", LOptions), LOptions);
-  auto LRTable = LRTable::buildSLR(*G);
+  Table = LRTable::buildSLR(*G);
 
   const ForestNode &Parsed =
-      glrParse(Tokens, {*G, LRTable, Arena, GSStack}, id("test"));
+      glrParse(Tokens, {getTestLang(), Arena, GSStack}, id("test"));
   EXPECT_EQ(Parsed.dumpRecursive(*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);
-  auto LRTable = LRTable::buildSLR(*G);
+  Table = LRTable::buildSLR(*G);
 
   const ForestNode &Parsed =
-      glrParse(Tokens, {*G, LRTable, Arena, GSStack}, id("test"));
+      glrParse(Tokens, {getTestLang(), Arena, GSStack}, id("test"));
   EXPECT_EQ(Parsed.dumpRecursive(*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");
+  Guards.insert(std::make_pair(
+      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;
+  Table = LRTable::buildSLR(*G);
+
+  std::string Input = "test";
+  const TokenStream &Succeeded = cook(lex(Input, LOptions), LOptions);
+  EXPECT_EQ(glrParse(Succeeded, {getTestLang(), Arena, GSStack}, id("start"))
+                .dumpRecursive(*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, {getTestLang(), Arena, GSStack}, id("start"))
+                .dumpRecursive(*G),
+            "[  0, end) start := <opaque>\n");
+}
+
 TEST(GSSTest, GC) {
   //      ┌-A-┬-AB
   //      ├-B-┘
   // Root-+-C
   //      ├-D
   //      └-E
   GSS GSStack;
   auto *Root = GSStack.addNode(0, nullptr, {});