[pseudo] Remove the explicit Accept actions.

[hokein]

Summary

As pointed out in the previous review section, having a dedicated accept
action doesn't seem to be necessary. This patch implements the the same behavior
without accept acction, which will save some code complexity.

[sammccall]

This is a great simplification, thanks!

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

117–119

rather than mingling this with the glrReduce, I'd suggest collecting the set of final heads first and then analyzing them afterwards.

This means looping a second time, but I think the logic around recognizing patterns that look like accept might grow (e.g. if we want to incorporate some error tolerance)

[hokein]

pull out the logic of detecting acceptable state out of glrReduce callback.

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

117–119

that sounds reasonable, but it requires some additional changes (to identify inactive heads in the callback of glrReduce):

• AddSteps now returns true/false whether there is any actions in LRTable[NewHead->state][nextTok];
• no available action in the acceptable state on the eof token in LRTable (see the change in lr-build-basic.test);

[sammccall]

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

117–119

Hmm, I'm not sure whether the conditional or unconditional version is better, and we're really borrowing problems from the future here.

Let's go back to this simplest version, and update the opaque forest node comment below to a FIXME.
(We will need to invoke our generic error-recovery handlers when we reach EOF without reaching accept state, and simulating shifting an eof token may be the best way to reuse the code)

118

this line introduces a requirement that the start symbol be a nonterminal - if this is new, can we doc it?

[hokein]

switch to the previous simple version

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

118

this is not a new requirement, it is rather implicit previously (we use G.findNonterminal to pass the start-symbol argument of the glrParse). I added an assertion in the glrParse.

It would be nice to diagnose it in the bnf grammar parsing time (will add a followup patch).

[sammccall]

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

118

FWIW I think an assertion (and possibly a comment) is the right tradeoff here, maintaining diagnostics for all this stuff seems like overkill

[hokein]

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

118

Fair enough. I underestimated the effort of doing this stuff (we need to adjust a few existing tests in GrammarTests as well).

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

 //  The LRTable can be described as a matrix where the rows represent
 //  the states of the LR graph, the columns represent the symbols of the
 //  grammar, and each entry of the matrix (called action) represents a
 //  state transition in the graph.
 //
 //  Typically, based on the category of the grammar symbol, the LRTable is
 //  broken into two logically separate tables:
 //    - ACTION table with terminals as columns -- e.g. ACTION[S, a] specifies
-//      next action (shift/reduce/accept/error) on state S under a lookahead
-//      terminal a
+//      next action (shift/reduce) on state S under a lookahead terminal a
 //    - GOTO table with nonterminals as columns -- e.g. GOTO[S, X] specifies
 //      the state which we transist to from the state S with the nonterminal X
 //
 //  LRTable is *performance-critial* as it is consulted frequently during a
 //  parse. In general, LRTable is very sparse (most of the entries are empty).
 //  For example, for the C++ language, the SLR table has ~1500 states and 650
 //  symbols which results in a matrix having 975K entries, ~90% of entries are
 //  empty.
enum Kind : uint8_t {
 
       // Shift to state n: move forward with the lookahead, and push state n
       // onto the state stack.
       // A shift is a forward transition, and the value n is the next state that
       // the parser is to enter.
       Shift,
       // Reduce by a rule: pop the state stack.
       Reduce,
-      // Signals that we have parsed the input successfully.
-      Accept,
+
+      // NOTE: there are no typical accept actions in the LRtable, accept
+      // actions are handled specifically in the parser -- if the parser
+      // reaches to a target state (which is goto(StartState, StartSymbol)) at
+      // the EOF token after a reduce, this indicates the input has been parsed
+      // as the StartSymbol successfully.
 
       // Nonterminal actions, corresponding to entry of GOTO table.
 
       // Go to state n: push state n onto the state stack.
       // Similar to Shift, but it is a nonterminal forward transition.
       GoTo,
     };
 
-    static Action accept(RuleID RID) { return Action(Accept, RID); }
     static Action goTo(StateID S) { return Action(GoTo, S); }
     static Action shift(StateID S) { return Action(Shift, S); }
     static Action reduce(RuleID RID) { return Action(Reduce, RID); }
     static Action sentinel() { return Action(Sentinel, 0); }
 
     StateID getShiftState() const {
       assert(kind() == Shift);
       return Value;

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

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,
                            SymbolID StartSymbol) {
+  assert(isNonterminal(StartSymbol) && "Start symbol must be a nonterminal");
   llvm::ArrayRef<ForestNode> Terminals = Params.Forest.createTerminals(Tokens);
   auto &G = Params.G;
   (void)G;
   auto &GSS = Params.GSStack;
 
-  // Lists of active shift, reduce, accept actions.
-  std::vector<ParseStep> PendingShift, PendingReduce, PendingAccept;
+  // 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)) {
       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!");
       }
     }
   };
+  StateID StartState = Params.Table.getStartState(StartSymbol);
   std::vector<const GSS::Node *> NewHeads = {
-      GSS.addNode(/*State=*/Params.Table.getStartState(StartSymbol),
+      GSS.addNode(/*State=*/StartState,
                   /*ForestNode=*/nullptr, {})};
   auto MaybeGC = [&, Roots(std::vector<const GSS::Node *>{}), I(0u)]() mutable {
     assert(PendingShift.empty() && PendingReduce.empty() &&
-           PendingAccept.empty() && "Running GC at the wrong time!");
+           "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) {
 
     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));
-  glrReduce(PendingReduce, Params,
-            [&](const GSS::Node * NewHead) {
-              // A reduce will enable more steps.
-              AddSteps(NewHead, tokenSymbol(tok::eof));
-            });
+
+  StateID AcceptState = Params.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) {
+    Heads.push_back(NewHead);
 
-  if (!PendingAccept.empty()) {
-    LLVM_DEBUG({
-      llvm::dbgs() << llvm::formatv("Accept: {0} accepted result:\n",
-                                             PendingAccept.size());
-      for (const auto &Accept : PendingAccept)
-        llvm::dbgs() << "  - " << G.symbolName(Accept.Head->Payload->symbol())
-                     << "\n";
-    });
-    assert(PendingAccept.size() == 1);
-    return *PendingAccept.front().Head->Payload;
+  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);
 }
 
 // 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

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

 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const LRTable::Action &A) {
   switch (A.kind()) {
   case LRTable::Action::Shift:
     return OS << llvm::formatv("shift state {0}", A.getShiftState());
   case LRTable::Action::Reduce:
     return OS << llvm::formatv("reduce by rule {0}", A.getReduceRule());
   case LRTable::Action::GoTo:
     return OS << llvm::formatv("go to state {0}", A.getGoToState());
-  case LRTable::Action::Accept:
-    return OS << "acc";
   case LRTable::Action::Sentinel:
     llvm_unreachable("unexpected Sentinel action kind!");
   }
   llvm_unreachable("unexpected action kind!");
 }
 
 std::string LRTable::dumpStatistics() const {
   return llvm::formatv(R"(
for (uint16_t Terminal = 0; Terminal < NumTerminals; ++Terminal) {
       for (auto A : find(S, TokID)) {
         if (A.kind() == LRTable::Action::Shift)
           OS.indent(4) << llvm::formatv("'{0}': shift state {1}\n",
                                         G.symbolName(TokID), A.getShiftState());
         else if (A.kind() == LRTable::Action::Reduce)
           OS.indent(4) << llvm::formatv("'{0}': reduce by rule {1} '{2}'\n",
                                         G.symbolName(TokID), A.getReduceRule(),
                                         G.dumpRule(A.getReduceRule()));
-        else if (A.kind() == LRTable::Action::Accept)
-          OS.indent(4) << llvm::formatv("'{0}': accept\n", G.symbolName(TokID));
       }
     }
     for (SymbolID NontermID = 0; NontermID < G.table().Nonterminals.size();
          ++NontermID) {
       if (find(S, NontermID).empty())
         continue;
       OS.indent(4) << llvm::formatv("'{0}': go to state {1}\n",
                                     G.symbolName(NontermID),

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

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.underscore() && !I.hasNext()) {
-        Build.insert({SID, tokenSymbol(tok::eof), Action::accept(I.rule())});
+      // If we've just parsed the start symbol, this means we successfully parse
+      // the input. We don't add the reduce action of `_ := start_symbol` in the
+      // LRTable (the GLR parser handles it specifically).
+      if (G.lookupRule(I.rule()).Target == G.underscore() && !I.hasNext())
         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));
           Build.insert({SID, Follow, Action::reduce(I.rule())});
         }
       }
     }
   }
   return std::move(Build).build(G.table(), Graph.states().size());
 }
 
 } // namespace pseudo
 } // namespace clang

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

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

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

 # GRAPH-NEXT: 4 ->[-] 3
 
 # RUN: clang-pseudo -grammar %s -print-table | FileCheck %s --check-prefix=TABLE
 #      TABLE: LRTable:
 # TABLE-NEXT: State 0
 # TABLE-NEXT:     'IDENTIFIER': shift state 2
 # TABLE-NEXT:     'expr': go to state 1
 # TABLE-NEXT: State 1
-# TABLE-NEXT:     'EOF': accept
 # TABLE-NEXT:     '-': shift state 3
 # TABLE-NEXT: State 2
 # TABLE-NEXT:     'EOF': reduce by rule 1 'expr := IDENTIFIER'
 # TABLE-NEXT:     '-': reduce by rule 1 'expr := IDENTIFIER'
 # TABLE-NEXT: State 3
 # TABLE-NEXT:     'IDENTIFIER': shift state 2
 # TABLE-NEXT:     'expr': go to state 4
 # TABLE-NEXT: State 4
 # TABLE-NEXT:     'EOF': reduce by rule 0 'expr := expr - expr'
 # TABLE-NEXT:     '-': shift state 3
 # TABLE-NEXT:     '-': reduce by rule 0 'expr := expr - expr'

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

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);
+
+  const ForestNode &Parsed =
+      glrParse(Tokens, {*G, LRTable, 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(GSSTest, GC) {
   //      ┌-A-┬-AB
   //      ├-B-┘
   // Root-+-C
   //      ├-D
   //      └-E
   GSS GSStack;
   auto *Root = GSStack.addNode(0, nullptr, {});

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

TEST(LRTable, Builder) {
   // +-------+----+-------+---
   // |state0 |    | s0,r0 |...
   // |state1 | acc|       |...
   // |state2 |    |  r1   |...
   // +-------+----+-------+---
   std::vector<LRTable::Entry> Entries = {
       {/* State */ 0, tokenSymbol(tok::semi), Action::shift(0)},
       {/* State */ 0, tokenSymbol(tok::semi), Action::reduce(0)},
-      {/* State */ 1, tokenSymbol(tok::eof), Action::accept(2)},
+      {/* State */ 1, tokenSymbol(tok::eof), Action::reduce(2)},
       {/* State */ 2, tokenSymbol(tok::semi), Action::reduce(1)}};
   GrammarTable GT;
   LRTable T = LRTable::buildForTests(GT, Entries);
   EXPECT_THAT(T.find(0, tokenSymbol(tok::eof)), IsEmpty());
   EXPECT_THAT(T.find(0, tokenSymbol(tok::semi)),
               UnorderedElementsAre(Action::shift(0), Action::reduce(0)));
   EXPECT_THAT(T.find(1, tokenSymbol(tok::eof)),
-              UnorderedElementsAre(Action::accept(2)));
+              UnorderedElementsAre(Action::reduce(2)));
   EXPECT_THAT(T.find(1, tokenSymbol(tok::semi)), IsEmpty());
   EXPECT_THAT(T.find(2, tokenSymbol(tok::semi)),
               UnorderedElementsAre(Action::reduce(1)));
   // Verify the behaivor for other non-available-actions terminals.
   EXPECT_THAT(T.find(2, tokenSymbol(tok::kw_int)), IsEmpty());
 }
 
 } // namespace
 } // namespace pseudo
 } // namespace clang