diff --git a/clang-tools-extra/pseudo/benchmarks/Benchmark.cpp b/clang-tools-extra/pseudo/benchmarks/Benchmark.cpp --- a/clang-tools-extra/pseudo/benchmarks/Benchmark.cpp +++ b/clang-tools-extra/pseudo/benchmarks/Benchmark.cpp @@ -142,6 +142,20 @@ } BENCHMARK(glrParse); +static void glrParseLR0(benchmark::State &State) { + LRTable Table = clang::pseudo::LRTable::buildLR0(*G); + SymbolID StartSymbol = *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); + } + State.SetBytesProcessed(static_cast(State.iterations()) * + SourceText->size()); +} +BENCHMARK(glrParseLR0); + static void full(benchmark::State &State) { LRTable Table = clang::pseudo::LRTable::buildSLR(*G); SymbolID StartSymbol = *G->findNonterminal("translation-unit"); 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 @@ -154,6 +154,7 @@ // Build a SLR(1) parsing table. static LRTable buildSLR(const Grammar &G); + static LRTable buildLR0(const Grammar &G); class Builder; // Represents an entry in the table, used for building the LRTable. 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 @@ -62,6 +62,22 @@ llvm_unreachable("unexpected action kind!"); } } + for (const auto &Action : + Params.Table.getActions(Head->State, tokenSymbol(tok::eod))) { + 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 NewHeads = { GSS.addNode(/*State=*/Params.Table.getStartState(StartSymbol), 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 @@ -135,5 +135,31 @@ return std::move(Build).build(G.table(), Graph.states().size()); } +LRTable LRTable::buildLR0(const Grammar &G) { + 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.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. + Build.insert({SID, tokenSymbol(tok::eod), Action::reduce(I.rule())}); + } + } + } + return std::move(Build).build(G.table(), Graph.states().size()); +} + } // namespace pseudo } // namespace clang 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 @@ -24,6 +24,6 @@ # TABLE-NEXT: State 1 # TABLE-NEXT: 'EOF': accept # TABLE-NEXT: State 2 -# TABLE-NEXT: 'EOF': reduce by rule 1 'expr := id' +# TABLE-NEXT: 'EOD': reduce by rule 1 'expr := id' # TABLE-NEXT: State 3 -# TABLE-NEXT: 'EOF': reduce by rule 0 'id := IDENTIFIER' +# TABLE-NEXT: 'EOD': reduce by rule 0 'id := IDENTIFIER' 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 @@ -36,12 +36,10 @@ # 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: 'EOD': 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: 'EOD': reduce by rule 0 'expr := expr - expr' # TABLE-NEXT: '-': shift state 3 -# TABLE-NEXT: '-': reduce by rule 0 'expr := expr - expr' diff --git a/clang-tools-extra/pseudo/tool/ClangPseudo.cpp b/clang-tools-extra/pseudo/tool/ClangPseudo.cpp --- a/clang-tools-extra/pseudo/tool/ClangPseudo.cpp +++ b/clang-tools-extra/pseudo/tool/ClangPseudo.cpp @@ -108,7 +108,7 @@ llvm::outs() << G->dump(); if (PrintGraph) llvm::outs() << clang::pseudo::LRGraph::buildLR0(*G).dumpForTests(*G); - auto LRTable = clang::pseudo::LRTable::buildSLR(*G); + auto LRTable = clang::pseudo::LRTable::buildLR0(*G); if (PrintTable) llvm::outs() << LRTable.dumpForTests(*G); if (PrintStatistics)