[pseudo] Support parsing variant target symbols.

[hokein]

Summary

With this patch, we're able to parse smaller chunks of C++ code (statement,
declaration), rather than translation-unit.

The target symbol is listed in the grammar in a form of `_ :=
statement`, each target symbol has a dedicated state (_ := • statement).
We create and track all these separate states in the LRTable. When we
start parsing, we lookup the corresponding state to start the parser.

LR pasing table changes with this patch:

• number of states: 1467 -> 1471
• number of actions: 82891 -> 83578
• size of the table (bytes): 334248 -> 336996

[sammccall]

Very nice!
And change to compiled grammar size is small.
Would including *every* nonterminal as a start symbol would blow the size up a bit?
This would eliminate some complexity in the interface.

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

125

From the caller's perspective, is "target symbol" really a clearer name than "start symbol"? The latter seems like more common terminology.

126

// A rule _ := Target must exist for the chosen target symbol.

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

163

might be clearer just to make this a member of the builder, and add a addStartState(SymbolID, StateID) method?

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

43

nit: since we're ultimately copying this array to call the constructor, maybe just take ArrayRef here?

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

29–31

Maybe "_ lists all the start-symbols which we support parsing".

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

46

-start-symbol might be more common

62

nit: just findNonterminal()? rather than echoing the type

[hokein]

• adress comments
• rename TargetSymbol -> StartSymbol
• don't use StartSymbol for "_", rename and update a few occurrences
• move findNonterminal to Grammar.h since it is used in various places

[hokein]

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

125

I'd like to call it start symbol as well, it is clearer.

The only downside is that we're diverging from the standard LR literature (_ is the start symbol of the augmented grammar). We need a name for the symbol _, I rename the Grammar::startSymbol to Grammar::underscore (or even _?), please take a look on this patch again.

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

192

it is unfortunate that we put this function in the Grammar.h. This could be avoided when we have the generated enum grammar type, but we are not there yet...

[hokein]

add a comment in cxx.bnf explaining why not making all nonterminals as start symbol by default.

[hokein]

Would including *every* nonterminal as a start symbol would blow the size up a bit?
This would eliminate some complexity in the interface.

This does increase the size, some datapoints:

• ~240 start symbols
• number of states: 1.4K -> 2K
• number of actions: 83K -> 96K
• size of table(bytes): 334K -> 388K

As discussed, the benefit is not obvious, let's leave it out now and revisit it when needed (added a comment in the cxx.bnf).

[sammccall]

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

192

This doesn't seem so bad to me, but I'd prefer it to be a method on Grammar I think - callers like the ones in the benchmark shouldn't have to worry about the GrammarTable object.

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

118

this means if you pass --start-symbol=typo we'll hit an assertion

I think findNonterminal should probably return Optional instead?

[hokein]

move the findNonterminal to Grammar.

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

State.SetBytesProcessed(static_cast<uint64_t>(State.iterations()) *
                           SourceText->size());
 }
 BENCHMARK(runPreprocessTokens);
 
 static void runGLRParse(benchmark::State &State) {
   clang::LangOptions LangOpts = genericLangOpts();
   LRTable Table = clang::pseudo::LRTable::buildSLR(*G);
   TokenStream ParseableStream = parseableTokenStream();
+  SymbolID StartSymbol = *G->findNonterminal("translation-unit");
   for (auto _ : State) {
     pseudo::ForestArena Forest;
     pseudo::GSS GSS;
-    glrParse(ParseableStream, ParseParams{*G, Table, Forest, GSS});
+    glrParse(ParseableStream, ParseParams{*G, Table, Forest, GSS}, StartSymbol);
   }
   State.SetBytesProcessed(static_cast<uint64_t>(State.iterations()) *
                           SourceText->size());
 }
 BENCHMARK(runGLRParse);
 
 static void runParseOverall(benchmark::State &State) {
   clang::LangOptions LangOpts = genericLangOpts();
   LRTable Table = clang::pseudo::LRTable::buildSLR(*G);
+  SymbolID StartSymbol = *G->findNonterminal("translation-unit");
   for (auto _ : State) {
     pseudo::ForestArena Forest;
     pseudo::GSS GSS;
-    glrParse(parseableTokenStream(), ParseParams{*G, Table, Forest, GSS});
+    glrParse(parseableTokenStream(), ParseParams{*G, Table, Forest, GSS},
+             StartSymbol);
   }
   State.SetBytesProcessed(static_cast<uint64_t>(State.iterations()) *
                           SourceText->size());
 }
 BENCHMARK(runParseOverall);
 
 } // namespace
 } // namespace pseudo

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

void operator()(llvm::StringRef Code) {
     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});
+    auto &Root =
+        glrParse(ParseableStream, clang::pseudo::ParseParams{*G, T, Arena, GSS},
+                 *G->findNonterminal("translation-unit"));
     if (Print)
       llvm::outs() << Root.dumpRecursive(*G);
   }
 };
 
 Fuzzer *Fuzz = nullptr;
 
 } // namespace

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

struct ParseParams {
   // The LR table which GLR uses to parse the input, should correspond to the
   // Grammar G.
   const LRTable &Table;
 
   // Arena for data structure used by the GLR algorithm.
   ForestArena &Forest;  // Storage for the output forest.
   GSS &GSStack;         // Storage for parsing stacks.
 };
-// Parse the given token stream with the GLR algorithm, and return a forest node
-// of the start symbol.
+// Parses the given token stream as the start symbol with the GLR algorithm,
+// and returns a forest node of the start symbol.
 //
-// If the parsing fails, we model it as an opaque node in the forest.
+// A rule `_ := StartSymbol` must exit for the chosen start symbol.
 //
-// FIXME: add support for variant start symbols.
-const ForestNode &glrParse(const TokenStream &Code, const ParseParams &Params);
+// 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);
 
 // An active stack head can have multiple available actions (reduce/reduce
 // actions, reduce/shift actions).
 // A step is any one action applied to any one stack head.
 struct ParseStep {
   // A specific stack head.
   const GSS::Node *Head = nullptr;
   // An action associated with the head.

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

 //===----------------------------------------------------------------------===//
 
 #ifndef CLANG_PSEUDO_GRAMMAR_H
 #define CLANG_PSEUDO_GRAMMAR_H
 
 #include "clang/Basic/TokenKinds.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/Optional.h"
 #include "llvm/ADT/StringRef.h"
 #include <cstdint>
 #include <vector>
 
 namespace clang {
 namespace pseudo {
 // A SymbolID uniquely identifies a terminal/nonterminal symbol in a grammar.
 // nonterminal IDs are indexes into a table of nonterminal symbols.

 public:
   explicit Grammar(std::unique_ptr<GrammarTable>);
 
   // Parses grammar from a BNF file.
   // Diagnostics emitted during parsing are stored in Diags.
   static std::unique_ptr<Grammar> parseBNF(llvm::StringRef BNF,
                                            std::vector<std::string> &Diags);
 
-  // Returns the SymbolID of the start symbol '_'.
-  SymbolID startSymbol() const { return StartSymbol; };
+  // Returns the SymbolID of the symbol '_'.
+  SymbolID underscore() const { return Underscore; };
 
   // Returns all rules of the given nonterminal symbol.
   llvm::ArrayRef<Rule> rulesFor(SymbolID SID) const;
   const Rule &lookupRule(RuleID RID) const;
 
   // Gets symbol (terminal or nonterminal) name.
   // Terminals have names like "," (kw_comma) or "OPERATOR" (kw_operator).
   llvm::StringRef symbolName(SymbolID) const;
 
+  // Lookup the SymbolID of the nonterminal symbol by Name.
+  llvm::Optional<SymbolID> findNonterminal(llvm::StringRef Name) const;
+
   // Dumps the whole grammar.
   std::string dump() const;
   // Dumps a particular rule.
   std::string dumpRule(RuleID) const;
   // Dumps all rules of the given nonterminal symbol.
   std::string dumpRules(SymbolID) const;
 
   const GrammarTable &table() const { return *T; }
 
 private:
   std::unique_ptr<GrammarTable> T;
-  // The start symbol '_' of the augmented grammar.
-  SymbolID StartSymbol;
+  // The symbol ID of '_'. (In the LR literature, this is the start symbol of
+  // the augmented grammar.)
+  SymbolID Underscore;
 };
 // For each nonterminal X, computes the set of terminals that begin strings
 // derived from X. (Known as FIRST sets in grammar-based parsers).
 std::vector<llvm::DenseSet<SymbolID>> firstSets(const Grammar &);
 // For each nonterminal X, computes the set of terminals that could immediately
 // follow X. (Known as FOLLOW sets in grammar-based parsers).
 std::vector<llvm::DenseSet<SymbolID>> followSets(const Grammar &);
 
struct GrammarTable {
   // clang::tok::TokenKind is the index of the table.
   llvm::ArrayRef<std::string> Terminals;
   // A table of nonterminals, sorted by name.
   // SymbolID is the index of the table.
   std::vector<Nonterminal> Nonterminals;
 };
 
 } // namespace pseudo
 } // namespace clang
 
 #endif // CLANG_PSEUDO_GRAMMAR_H

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

public:
   // transits to state Dst.
   struct Edge {
     StateID Src, Dst;
     SymbolID Label;
   };
 
   llvm::ArrayRef<State> states() const { return States; }
   llvm::ArrayRef<Edge> edges() const { return Edges; }
+  llvm::ArrayRef<std::pair<SymbolID, StateID>> startStates() const {
+    return StartStates;
+  }
 
   std::string dumpForTests(const Grammar &) const;
 
 private:
-  LRGraph(std::vector<State> States, std::vector<Edge> Edges)
-      : States(std::move(States)), Edges(std::move(Edges)) {}
+  LRGraph(std::vector<State> States, std::vector<Edge> Edges,
+          std::vector<std::pair<SymbolID, StateID>> StartStates)
+      : States(std::move(States)), Edges(std::move(Edges)),
+        StartStates(std::move(StartStates)) {}
 
   std::vector<State> States;
   std::vector<Edge> Edges;
+  std::vector<std::pair<SymbolID, StateID>> StartStates;
 };
 
 } // namespace pseudo
 } // namespace clang
 
 namespace llvm {
 // Support clang::pseudo::Item as DenseMap keys.
 template <> struct DenseMapInfo<clang::pseudo::Item> {

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

public:
   // Returns the state after we reduce a nonterminal.
   // Expected to be called by LR parsers.
   StateID getGoToState(StateID State, SymbolID Nonterminal) const;
 
   // Looks up available actions.
   // Returns empty if no available actions in the table.
   llvm::ArrayRef<Action> find(StateID State, SymbolID Symbol) const;
 
+  // Returns the state from which the LR parser should start to parse the input
+  // tokens as the given StartSymbol.
+  //
+  // In LR parsing, the start state of `translation-unit` corresponds to
+  // `_ := • translation-unit`.
+  //
+  // Each start state responds to **a** single grammar rule like `_ := start`.
+  // REQUIRE: The given StartSymbol must exist in the grammar (in a form of
+  //          `_ := start`).
+  StateID getStartState(SymbolID StartSymbol) const;
+
   size_t bytes() const {
     return sizeof(*this) + Actions.capacity() * sizeof(Action) +
            States.capacity() * sizeof(StateID) +
            NontermOffset.capacity() * sizeof(uint32_t) +
            TerminalOffset.capacity() * sizeof(uint32_t);
   }
 
   std::string dumpStatistics() const;
private:
   std::vector<uint32_t> NontermOffset;
   // Similar to NontermOffset, but for terminals, index is tok::TokenKind.
   std::vector<uint32_t> TerminalOffset;
   // Parallel to Actions, the value is State (rows of the matrix).
   // Grouped by the SymbolID, and only subranges are sorted.
   std::vector<StateID> States;
   // A flat list of available actions, sorted by (SymbolID, State).
   std::vector<Action> Actions;
+  // A sorted table, storing the start state for each target parsing symbol.
+  std::vector<std::pair<SymbolID, StateID>> StartStates;
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const LRTable::Action &);
 
 } // namespace pseudo
 } // namespace clang
 
 #endif // CLANG_PSEUDO_LRTABLE_H

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

llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const GSS::Node &N) {
   std::vector<std::string> ParentStates;
   for (const auto *Parent : N.parents())
     ParentStates.push_back(llvm::formatv("{0}", Parent->State));
   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) {
+const ForestNode &glrParse(const TokenStream &Tokens, const ParseParams &Params,
+                           SymbolID StartSymbol) {
   llvm::ArrayRef<ForestNode> Terminals = Params.Forest.createTerminals(Tokens);
   auto &G = Params.G;
   auto &GSS = Params.GSStack;
 
   // Lists of active shift, reduce, accept actions.
   std::vector<ParseStep> PendingShift, PendingReduce, PendingAccept;
   auto AddSteps = [&](const GSS::Node *Head, SymbolID NextTok) {
     for (const auto &Action : Params.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;
       case LRTable::Action::Accept:
         PendingAccept.push_back({Head, Action});
         break;
       default:
         llvm_unreachable("unexpected action kind!");
       }
     }
   };
-
   std::vector<const GSS::Node *> NewHeads = {
-      GSS.addNode(/*State=*/0, /*ForestNode*/ nullptr, {})};
+      GSS.addNode(/*State=*/Params.Table.getStartState(StartSymbol),
+                  /*ForestNode=*/nullptr, {})};
   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,
LLVM_DEBUG({
       for (const auto &Accept : PendingAccept)
         llvm::dbgs() << "  - " << G.symbolName(Accept.Head->Payload->symbol())
                      << "\n";
     });
     assert(PendingAccept.size() == 1);
     return *PendingAccept.front().Head->Payload;
   }
   // We failed to parse the input, returning an opaque forest node for recovery.
-  auto RulesForStart = G.rulesFor(G.startSymbol());
-  // FIXME: support multiple start symbols.
-  assert(RulesForStart.size() == 1 && RulesForStart.front().Size == 1 &&
-         "start symbol _ must have exactly one rule");
-  return Params.Forest.createOpaque(RulesForStart.front().Sequence[0], 0);
+  return Params.Forest.createOpaque(StartSymbol, /*Token::Index=*/0);
 }
 
 // Apply all pending shift actions.
 // In theory, LR parsing doesn't have shift/shift conflicts on a single head.
 // But we may have multiple active heads, and each head has a shift action.
 //
 // We merge the stack -- if multiple heads will reach the same state after
 // shifting a token, we shift only once by combining these heads.

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

 
 Rule::Rule(SymbolID Target, llvm::ArrayRef<SymbolID> Sequence)
     : Target(Target), Size(static_cast<uint8_t>(Sequence.size())) {
   assert(Sequence.size() <= Rule::MaxElements);
   llvm::copy(Sequence, this->Sequence);
 }
 
 Grammar::Grammar(std::unique_ptr<GrammarTable> Table) : T(std::move(Table)) {
-  // start symbol is named _, binary search it.
-  auto It = llvm::partition_point(
-      T->Nonterminals,
-      [](const GrammarTable::Nonterminal &X) { return X.Name < "_"; });
-  assert(It != T->Nonterminals.end() && It->Name == "_" &&
-         "symbol _ must exist in the grammar!");
-  StartSymbol = It - T->Nonterminals.begin();
+  Underscore = *findNonterminal("_");
 }
 
 llvm::ArrayRef<Rule> Grammar::rulesFor(SymbolID SID) const {
   assert(isNonterminal(SID));
   const auto &R = T->Nonterminals[SID].RuleRange;
   assert(R.End <= T->Rules.size());
   return llvm::makeArrayRef(&T->Rules[R.Start], R.End - R.Start);
 }
 
 const Rule &Grammar::lookupRule(RuleID RID) const {
   assert(RID < T->Rules.size());
   return T->Rules[RID];
 }
 
 llvm::StringRef Grammar::symbolName(SymbolID SID) const {
   if (isToken(SID))
     return T->Terminals[symbolToToken(SID)];
   return T->Nonterminals[SID].Name;
 }
 
+llvm::Optional<SymbolID> Grammar::findNonterminal(llvm::StringRef Name) const {
+  auto It = llvm::partition_point(
+      T->Nonterminals,
+      [&](const GrammarTable::Nonterminal &X) { return X.Name < Name; });
+  if (It != T->Nonterminals.end() && It->Name == Name)
+    return It - T->Nonterminals.begin();
+  return llvm::None;
+}
+
 std::string Grammar::dumpRule(RuleID RID) const {
   std::string Result;
   llvm::raw_string_ostream OS(Result);
   const Rule &R = T->Rules[RID];
   OS << symbolName(R.Target) << " :=";
   for (SymbolID SID : R.seq())
     OS << " " << symbolName(SID);
   return Result;
auto ExpandFollowSet = [&FollowSets](SymbolID Y,
     for (SymbolID F : ToAdd)
       Changed |= FollowSets[Y].insert(F).second;
     return Changed;
   };
   // Follow sets is computed based on the following 3 rules, the computation
   // is completed at a fixed point where there is no more new symbols can be
   // added to any of the follow sets.
   //
-  // Rule 1: add endmarker to the FOLLOW(S), where S is the start symbol.
-  FollowSets[G.startSymbol()].insert(tokenSymbol(tok::eof));
+  // Rule 1: add endmarker to the FOLLOW(S), where S is the start symbol of the
+  // augmented grammar, in our case it is '_'.
+  FollowSets[G.underscore()].insert(tokenSymbol(tok::eof));
   bool Changed = true;
   while (Changed) {
     Changed = false;
     for (const auto &R : G.table().Rules) {
       // Rule 2: for a rule X := ... Y Z, we add all symbols from FIRST(Z) to
       // FOLLOW(Y).
       for (size_t I = 0; I + 1 < R.seq().size(); ++I) {
         if (isToken(R.seq()[I]))

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

std::string LRGraph::dumpForTests(const Grammar &G) const {
   for (const auto &E : Edges) {
     OS << llvm::formatv("{0} ->[{1}] {2}\n", E.Src, G.symbolName(E.Label),
                         E.Dst);
   }
   return OS.str();
 }
 
 LRGraph LRGraph::buildLR0(const Grammar &G) {
   class Builder {
   public:
     Builder(const Grammar &G) : G(G) {}
 
     // Adds a given state if not existed.
     std::pair<StateID, /*inserted*/ bool> insert(ItemSet KernelItems) {
       assert(llvm::is_sorted(KernelItems) &&
              "Item must be sorted before inserting to a hash map!");
       auto It = StatesIndex.find(KernelItems);
public:
     }
 
     // Returns a state with the given id.
     const State &find(StateID ID) const {
       assert(ID < States.size());
       return States[ID];
     }
 
+    void addStartState(SymbolID Sym, StateID State) {
+      StartStates.push_back({Sym, State});
+    }
+
     LRGraph build() && {
       States.shrink_to_fit();
       Edges.shrink_to_fit();
-      return LRGraph(std::move(States), std::move(Edges));
+      llvm::sort(StartStates);
+      StartStates.shrink_to_fit();
+      return LRGraph(std::move(States), std::move(Edges),
+                     std::move(StartStates));
     }
 
   private:
     // Key is the **kernel** item sets.
     llvm::DenseMap<ItemSet, /*index of States*/ size_t> StatesIndex;
     std::vector<State> States;
     std::vector<Edge> Edges;
     const Grammar &G;
+    std::vector<std::pair<SymbolID, StateID>> StartStates;
   } Builder(G);
 
   std::vector<StateID> PendingStates;
   // Initialize states with the start symbol.
-  auto RRange = G.table().Nonterminals[G.startSymbol()].RuleRange;
+  auto RRange = G.table().Nonterminals[G.underscore()].RuleRange;
   for (RuleID RID = RRange.Start; RID < RRange.End; ++RID) {
     auto StartState = std::vector<Item>{Item::start(RID, G)};
     auto Result = Builder.insert(std::move(StartState));
     assert(Result.second && "State must be new");
     PendingStates.push_back(Result.first);
+
+    const Rule &StartRule = G.lookupRule(RID);
+    assert(StartRule.Size == 1 &&
+           "Start rule must have exactly one symbol in its body!");
+    Builder.addStartState(StartRule.seq().front(), Result.first);
   }
 
   while (!PendingStates.empty()) {
     auto CurrentStateID = PendingStates.back();
     PendingStates.pop_back();
     for (auto Next :
          nextAvailableKernelItems(Builder.find(CurrentStateID), G)) {
       auto Insert = Builder.insert(Next.second);

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

if (Start == TargetedStates.end())
     return {};
   const LRTable::StateID *End = Start;
   while (End != TargetedStates.end() && *End == Src)
     ++End;
   return llvm::makeArrayRef(&Actions[Start - States.data()],
                             /*length=*/End - Start);
 }
 
+LRTable::StateID LRTable::getStartState(SymbolID Target) const {
+  assert(llvm::is_sorted(StartStates) && "StartStates must be sorted!");
+  auto It = llvm::partition_point(
+      StartStates, [Target](const std::pair<SymbolID, StateID> &X) {
+        return X.first < Target;
+      });
+  assert(It != StartStates.end() && It->first == Target &&
+         "target symbol doesn't have a start state!");
+  return It->second;
+}
+
 } // namespace pseudo
 } // namespace clang

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

 };
 } // namespace llvm
 
 namespace clang {
 namespace pseudo {
 
 class LRTable::Builder {
 public:
+  Builder(llvm::ArrayRef<std::pair<SymbolID, StateID>> StartStates)
+      : StartStates(StartStates) {}
+
   bool insert(Entry E) { return Entries.insert(std::move(E)).second; }
   LRTable build(const GrammarTable &GT) && {
     // E.g. given the following parsing table with 3 states and 3 terminals:
     //
     //            a    b     c
     // +-------+----+-------+-+
     // |state0 |    | s0,r0 | |
     // |state1 | acc|       | |
LRTable build(const GrammarTable &GT) && {
     for (size_t Terminal = 0; Terminal < Table.TerminalOffset.size();
          ++Terminal) {
       Table.TerminalOffset[Terminal] = SortedIndex;
       while (SortedIndex < Sorted.size() &&
              Sorted[SortedIndex].Symbol ==
                  tokenSymbol(static_cast<tok::TokenKind>(Terminal)))
         ++SortedIndex;
     }
+    Table.StartStates = std::move(StartStates);
     return Table;
   }
 
 private:
   llvm::DenseSet<Entry> Entries;
+  std::vector<std::pair<SymbolID, StateID>> StartStates;
 };
 
 LRTable LRTable::buildForTests(const GrammarTable &GT,
                                llvm::ArrayRef<Entry> Entries) {
-  Builder Build;
+  Builder Build({});
   for (const Entry &E : Entries)
     Build.insert(E);
   return std::move(Build).build(GT);
 }
 
 LRTable LRTable::buildSLR(const Grammar &G) {
-  Builder Build;
   auto Graph = LRGraph::buildLR0(G);
+  Builder Build(Graph.startStates());
   for (const auto &T : Graph.edges()) {
     Action Act = isToken(T.Label) ? Action::shift(T.Dst) : Action::goTo(T.Dst);
     Build.insert({T.Src, T.Label, Act});
   }
   assert(Graph.states().size() <= (1 << StateBits) &&
          "Graph states execceds the maximum limit!");
   auto FollowSets = followSets(G);
   for (StateID SID = 0; SID < Graph.states().size(); ++SID) {
     for (const Item &I : Graph.states()[SID].Items) {
       // If we've just parsed the start symbol, we can accept the input.
-      if (G.lookupRule(I.rule()).Target == G.startSymbol() && !I.hasNext()) {
+      if (G.lookupRule(I.rule()).Target == G.underscore() && !I.hasNext()) {
         Build.insert({SID, tokenSymbol(tok::eof), Action::accept(I.rule())});
         continue;
       }
       if (!I.hasNext()) {
         // If we've reached the end of a rule A := ..., then we can reduce if
         // the next token is in the follow set of A.
         for (SymbolID Follow : FollowSets[G.lookupRule(I.rule()).Target]) {
           assert(isToken(Follow));

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

 #    and right shift operator;
 #
 # Guidelines:
 #   - nonterminals are lower_case; terminals (aka tokens) correspond to
 #     clang::TokenKind, written as "IDENTIFIER", "USING", "::" etc;
 #   - optional symbols are supported, with a _opt suffix;
 #
 # [1] https://isocpp.org/files/papers/N4860.pdf
+
+# _ lists all the start-symbols which we support parsing.
 #
-#
-# _ serves as a "fake" start symbol, coming with real grammar symbols.
+# We list important nonterminals as start symbols, rather than doing it for all
+# nonterminals by default, this reduces the number of states by 30% and LRTable
+# actions by 16%.
 _ := translation-unit
+_ := statement-seq
+_ := declaration-seq
 
 # gram.key
 typedef-name := IDENTIFIER
 typedef-name := simple-template-id
 namespace-name := IDENTIFIER
 namespace-name := namespace-alias
 namespace-alias := IDENTIFIER
 class-name := IDENTIFIER

clang-tools-extra/pseudo/test/glr-variant-start.cpp

+// RUN: clang-pseudo -grammar=%cxx-bnf-file -source=%s --start-symbol=statement-seq --print-forest | FileCheck %s
+
+a + a;
+// CHECK:      statement-seq~expression-statement := expression ;
+// CHECK-NEXT: ├─expression~additive-expression := additive-expression + multiplicative-expression
+// CHECK-NEXT: │ ├─additive-expression~IDENTIFIER :=
+// CHECK-NEXT: │ ├─+ :=
+// CHECK-NEXT: │ └─multiplicative-expression~IDENTIFIER :=
+// CHECK-NEXT: └─; :=

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

 static opt<bool>
     PrintDirectiveTree("print-directive-tree",
                       desc("Print directive structure of source code"));
 static opt<bool>
     StripDirectives("strip-directives",
                     desc("Strip directives and select conditional sections"));
 static opt<bool> PrintStatistics("print-statistics", desc("Print GLR parser statistics"));
 static opt<bool> PrintForest("print-forest", desc("Print parse forest"));
+static opt<std::string> StartSymbol("start-symbol",
+                                    desc("specify the start symbol to parse"),
+                                    init("translation-unit"));
 
 static std::string readOrDie(llvm::StringRef Path) {
   llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Text =
       llvm::MemoryBuffer::getFile(Path);
   if (std::error_code EC = Text.getError()) {
     llvm::errs() << "Error: can't read grammar file '" << Path
                  << "': " << EC.message() << "\n";
     ::exit(1);
   }
   return Text.get()->getBuffer().str();
 }
 
 int main(int argc, char *argv[]) {
   llvm::cl::ParseCommandLineOptions(argc, argv, "");
   llvm::sys::PrintStackTraceOnErrorSignal(argv[0]);
 
   clang::LangOptions LangOpts = clang::pseudo::genericLangOpts();
   std::string SourceText;
   llvm::Optional<clang::pseudo::TokenStream> RawStream;
   llvm::Optional<TokenStream> PreprocessedStream;
   llvm::Optional<clang::pseudo::TokenStream> ParseableStream;
   if (Source.getNumOccurrences()) {
if (PrintGraph)
       llvm::outs() << clang::pseudo::LRGraph::buildLR0(*G).dumpForTests(*G);
     auto LRTable = clang::pseudo::LRTable::buildSLR(*G);
     if (PrintTable)
       llvm::outs() << LRTable.dumpForTests(*G);
 
     if (ParseableStream) {
       clang::pseudo::ForestArena Arena;
       clang::pseudo::GSS GSS;
-      auto &Root =
-          glrParse(*ParseableStream,
-                   clang::pseudo::ParseParams{*G, LRTable, Arena, GSS});
+      llvm::Optional<clang::pseudo::SymbolID> StartSymID =
+          G->findNonterminal(StartSymbol);
+      if (!StartSymID) {
+        llvm::errs() << llvm::formatv(
+            "The start symbol {0} doesn't exit in the grammar!\n", Grammar);
+        return 2;
+      }
+      auto &Root = glrParse(*ParseableStream,
+                            clang::pseudo::ParseParams{*G, LRTable, Arena, GSS},
+                            *StartSymID);
       if (PrintForest)
         llvm::outs() << Root.dumpRecursive(*G, /*Abbreviated=*/true);
 
       if (PrintStatistics) {
         llvm::outs() << "Forest bytes: " << Arena.bytes()
                      << " nodes: " << Arena.nodeCount() << "\n";
         llvm::outs() << "GSS bytes: " << GSS.bytes()
                      << " nodes: " << GSS.nodeCount() << "\n";
       }
     }
   }
 
   return 0;
 }

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

build(R"bnf(
     test := left-paren expr
     left-paren := {
     expr := IDENTIFIER
   )bnf");
   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});
+  const ForestNode &Parsed =
+      glrParse(Tokens, {*G, LRTable, 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 := IDENTIFIER
     test := foo
     foo := IDENTIFIER
   )bnf");
   clang::LangOptions LOptions;
   const TokenStream &Tokens = cook(lex("IDENTIFIER", LOptions), LOptions);
   auto LRTable = LRTable::buildSLR(*G);
 
-  const ForestNode &Parsed = glrParse(Tokens, {*G, LRTable, Arena, GSStack});
+  const ForestNode &Parsed =
+      glrParse(Tokens, {*G, LRTable, 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");
 }
 
 } // namespace
 } // namespace pseudo
 } // namespace clang

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

build(R"cpp(
     _ := IDENFIFIE # a typo of the terminal IDENFITIER
 
     invalid
     # cycle
     a := b
     b := a
   )cpp");
 
-  EXPECT_EQ(G->startSymbol(), id("_"));
+  EXPECT_EQ(G->underscore(), id("_"));
   EXPECT_THAT(Diags, UnorderedElementsAre(
                          "Rule '_ := ,_opt' has a nullable RHS",
                          "Rule 'null := ' has a nullable RHS",
                          "No rules for nonterminal: undefined-sym",
                          "Failed to parse 'invalid': no separator :=",
                          "Token-like name IDENFIFIE is used as a nonterminal",
                          "No rules for nonterminal: IDENFIFIE",
                          "The grammar contains a cycle involving symbol a"));