diff --git a/clang-tools-extra/pseudo/include/clang-pseudo/LRTable.h b/clang-tools-extra/pseudo/include/clang-pseudo/LRTable.h
--- a/clang-tools-extra/pseudo/include/clang-pseudo/LRTable.h
+++ b/clang-tools-extra/pseudo/include/clang-pseudo/LRTable.h
@@ -19,8 +19,7 @@
// 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
//
@@ -76,8 +75,12 @@
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.
@@ -86,7 +89,6 @@
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); }
diff --git a/clang-tools-extra/pseudo/lib/GLR.cpp b/clang-tools-extra/pseudo/lib/GLR.cpp
--- a/clang-tools-extra/pseudo/lib/GLR.cpp
+++ b/clang-tools-extra/pseudo/lib/GLR.cpp
@@ -44,9 +44,11 @@
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) {
+ std::vector<ParseStep> PendingShift, PendingReduce;
+ auto AddSteps = [&](const GSS::Node *Head, SymbolID NextTok) -> bool {
+ bool Active = false;
for (const auto &Action : Params.Table.getActions(Head->State, NextTok)) {
+ Active =true;
switch (Action.kind()) {
case LRTable::Action::Shift:
PendingShift.push_back({Head, Action});
@@ -54,16 +56,15 @@
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!");
}
}
+ return Active;
};
+ 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, {})};
for (const ForestNode &Terminal : Terminals) {
LLVM_DEBUG(llvm::dbgs() << llvm::formatv("Next token {0} (id={1})\n",
@@ -84,23 +85,26 @@
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));
- });
- 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;
+ std::vector<const GSS::Node*> InactiveHeads;
+ StateID AcceptState = Params.Table.getGoToState(StartState, StartSymbol);
+ glrReduce(PendingReduce, Params, [&](const GSS::Node *NewHead) {
+ // A reduce will enable more steps.
+ if (!AddSteps(NewHead, tokenSymbol(tok::eof)))
+ InactiveHeads.push_back(NewHead);
+ });
+
+ const ForestNode *Result = nullptr;
+ for (const auto *Head : InactiveHeads) {
+ 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.
return Params.Forest.createOpaque(StartSymbol, /*Token::Index=*/0);
}
diff --git a/clang-tools-extra/pseudo/lib/grammar/LRTable.cpp b/clang-tools-extra/pseudo/lib/grammar/LRTable.cpp
--- a/clang-tools-extra/pseudo/lib/grammar/LRTable.cpp
+++ b/clang-tools-extra/pseudo/lib/grammar/LRTable.cpp
@@ -25,8 +25,6 @@
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!");
}
@@ -66,8 +64,6 @@
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();
diff --git a/clang-tools-extra/pseudo/lib/grammar/LRTableBuild.cpp b/clang-tools-extra/pseudo/lib/grammar/LRTableBuild.cpp
--- a/clang-tools-extra/pseudo/lib/grammar/LRTableBuild.cpp
+++ b/clang-tools-extra/pseudo/lib/grammar/LRTableBuild.cpp
@@ -124,11 +124,11 @@
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.
diff --git a/clang-tools-extra/pseudo/test/lr-build-basic.test b/clang-tools-extra/pseudo/test/lr-build-basic.test
--- a/clang-tools-extra/pseudo/test/lr-build-basic.test
+++ b/clang-tools-extra/pseudo/test/lr-build-basic.test
@@ -22,7 +22,6 @@
# 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
diff --git a/clang-tools-extra/pseudo/test/lr-build-conflicts.test b/clang-tools-extra/pseudo/test/lr-build-conflicts.test
--- a/clang-tools-extra/pseudo/test/lr-build-conflicts.test
+++ b/clang-tools-extra/pseudo/test/lr-build-conflicts.test
@@ -33,7 +33,6 @@
# 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'
diff --git a/clang-tools-extra/pseudo/unittests/GLRTest.cpp b/clang-tools-extra/pseudo/unittests/GLRTest.cpp
--- a/clang-tools-extra/pseudo/unittests/GLRTest.cpp
+++ b/clang-tools-extra/pseudo/unittests/GLRTest.cpp
@@ -393,6 +393,29 @@
"[ 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");
+}
+
} // namespace
} // namespace pseudo
} // namespace clang
diff --git a/clang-tools-extra/pseudo/unittests/LRTableTest.cpp b/clang-tools-extra/pseudo/unittests/LRTableTest.cpp
--- a/clang-tools-extra/pseudo/unittests/LRTableTest.cpp
+++ b/clang-tools-extra/pseudo/unittests/LRTableTest.cpp
@@ -33,7 +33,7 @@
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);
@@ -41,7 +41,7 @@
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)));