[syntax][pseudo] Implement LR parsing table.

[hokein]

Summary

This patch introduces a dense implementation of the LR parsing table, which is
used by LR parsers. We implement a SLR(1) parsing table from an LR(0) automaton.

Statistics of the LR parsing table on the C++ spec grammar:

number of states: 1449
number of actions: 83069
number of index entries: 72612
size of the table (bytes): 334928

[hokein]

Polish the LRTable implementation, using two flat vectors

memory-size (bytes): 1380908 => 664600

[sammccall]

A few initial comments just on the "easy parts" - changes to grammar and the first/follow set computation.

I need to study the rest. Generally I have a feeling some of the impl is very inefficient but efficiency may not matter much in this context, and it's unclear how much better it can be made without adding lots of complexity. Going to look more closely :-)

clang/include/clang/Tooling/Syntax/Pseudo/Grammar.h

128

This function seems like a bit of an attractive nuisance: it could be a cheap accessor, but isn't. There are just two callers - both are calling it in a loop and both seem dubious to be iterating over all symbols at all. I wonder if we can avoid it entirely.

130

this "augmented symbol" name doesn't seem widely used. (search for lr "augmented symbol" produces few results, mostly unrelated). It's also a confusing name, because it's IIUC it's not the symbol that's augmented, but rather the grammar has been augmented with the symbol...

I'd suggest just calling it the start symbol, unless the distinction is critical (I don't yet understand why it's important - I added it in the prototype just to avoid having the language-specific name "translation-unit" hardcoded).

Otherwise it's hard to suggest a good name without understanding what it's for, but it should be descriptive...

133

In about the same number of words you could explain what this actually is :-)

// Computes the set of terminals that could appear at the start of each non-terminal.

133

is there some reason these functions need to be part of the grammar class?

They seem like part of the LR building to me, it could be local to LRBuilder.cpp, or exposed from LRTable.h or so for testing

clang/include/clang/Tooling/Syntax/Pseudo/LRAutomaton.h

66

why is std::set used here? (generally a data structure to avoid)

75

I have a feeling we've discussed this before but...

I find this alias/abstraction unhelpful when reading the code, because operations on states are e.g. state.insert or state.contains, which don't match the abstraction.

I'd probably prefer just using ItemSet, but alternatively struct State { ItemSet Items; } seems like it would work well: State.Items.contains(...) reads very naturally.

clang/lib/Tooling/Syntax/Pseudo/Grammar.cpp

39

this function could use some comments.

A rule S := T ... implies elements in first(S):
 - if T is a terminal, first(S) contains T
 - if T is a nonterminal, first(S) contains first(T)
Since first(T) may not have been fully computed yet,
first(S) itself may end up being incomplete.
We iterate until a fixed point.
(This isn't particularly efficient, but table building performance isn't critical).

51

bool Changed = true; while(Changed) {? or maybe for (bool Changed = true; Changed;) {?

(do-while is rare enough that it always takes me a bit to grasp the control flow)

56

comment that we only need to consider the first element because symbols are non-nullable

88

nit: ... Y Z, with consistent spaces/capitalization
Unless case is meant to imply something here?

95

copying the set here seems gratuitous, especially since we're doing this in a loop where !changed is the usual thing.

I think inlining ExpandFollowSet for each case would make sense here. It turns into 1 line for the NT case plus two lines for the T case, so it's actually shorter overall

101

I think if (isNonterminal(Z)) ...expand... would be clearer here, since the condition is really part of rule 3 (but in a not-totally obvious way, it's nice to see them side-by-side)

clang/lib/Tooling/Syntax/Pseudo/LRBuilder.cpp

80

nit: please be consistent about spacing & capitalization for rules

I think trying to use a convention of uppercase/lowercase for term/nonterm is difficult because there's no clear way to indicate that a symbol could be either, which is common.

80

I can't really understand this description, it'd be helpful if it didn't reuse the name "advance" (particularly as a noun)

153

this loop looks like it's iterating over every possible symbol that might appear next, rather than just the ones that do (and creating a temporary array of 1000 items each outer iteration to do it).

Seems like we could do better by instead advancing every rule, and spitting out a list of {symbol, ItemSet} pairs?

157

Hmm, and advance() is computing closures from scratch every time, probably just to find "oh, the state already existed". Seems like we could save work by using the kernel set to represent the full set until we actually need to iterate over its items.

I'd like to think about this some more.

[sammccall]

OK, a bunch of random notes but I'm getting a higher level picture.

I'm not sure about the split between LRAutomaton and LRTable. I suppose doing it in two stages simplifies the implementation, but I don't think the first stage particularly needs to be public.
Also I think the names are confusing: Automaton vs Table isn't a clear contrast as one describes behavior and one a data structure. And the "LRTable" seems more automaton-like to me!

I think my suggestion would be:

• call the final structure LRAutomaton
• call the LRAutomaton::build()::Builder structure LRGraph or something
• I'm not sure the LRAutomaton structure needs to exist exactly, seems like the current LRTable::build() could operate on LRGraph directly

but I'm going to ponder this more.

clang/include/clang/Tooling/Syntax/Pseudo/LRAutomaton.h

32

accepting the grammar as a parameter rather than the rule length would let us ensure the length is correct locally rather than relying on the caller.
Essentially all the callers need to do a lookup anyway.

45

nit: redundant pseudo::qualifier

47

nit: unsigned.

just dot()?
and similarly ruleID()->rule()?
Not sure these would really be unclear

79

Hmm, isn't the point of GLR that it's a nondeterministic automaton?

We've done the LR-style NFA->DFA conversion, but it's not complete (when we hit a conflict we continue rather than giving up)

clang/lib/Tooling/Syntax/Pseudo/LRBuilder.cpp

144

nit: too many braces - please spell out some of the types
(and Auto should probably be State here?)

215

These comments are echoing the code - saying what, not why.

"If we've just parsed the start symbol, we can accept the input".

220

Seems like we should maybe have the accepted symbol as a payload on the Accept action?

Actually why do we need an Accept action, as opposed to just a reduce action and recognize it because it's the symbol we want and the stack is empty?

224

"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"

[sammccall]

OK, I think I understand it now! Sorry for so many comments, happy to chat offline about which ones to address/where to start.

clang/include/clang/Tooling/Syntax/Pseudo/LRTable.h

39

API polish: this class is a mix of accessors and direct member state - it can be hard to know how to best interact with such a thing.

I'd suggest:

• public factories static Action Action::reduce(RuleID) etc, private data & constructor
• expose Kind kind(), but not the individual is() methods: they don't buy much and this pattern encourages switch where appropriate
• make Kind enum rather than enum class - Action::Shift is sufficiently scoped already
• shift() & goTo() -> targetState() which asserts either condition. Apart from anything else, this makes naming easier: "shift" is a verb so shift() is a confusing name.

39

mention that this combines the Action and Go-to tables from LR literature?

41

I think it's worth documenting what each of these actions means.

Referring to enum values as "action table" and "goto table" seems confusing - they're part of the same table! The main reference point when reading the code needs to be the code, rather than the textbook.

67

if you make the data members private the union could just be a uint16 and save yourself some trouble here :-) Up to you

84

This action struct can be squeezed to 16 bits.

Kind only needs 3 bits (I suspect it can be 2: Error and Accept aren't heavily used).
RuleID is 12 bits, StateID would fit within 11 and 12 should be safe.

Combined with the optimization suggested below, this should get the whole table down to 335KB.

102

nit: please be consistent with Nonterminal (and "nonterminal") vs NonTerminal (and "non-terminal"). I think Nonterminal is used elsewhere in the code.

105

Why is this assertion valid? Is it a precondition of the function that some item in From can advance over NonTerminal?

121

I think there's an even more compact representation:
Basically sort the index keys as symbol-major, but then don't store the actual symbol there but rather store the range for the symbol in an external array:

// index is lookahead tok::TokenKind. Values are indices into Index: the range for tok is StateIdx[TokenIdx[tok]...TokenIdx[tok+1]]
vector<unsigned> TokenIdx;

// index is nonterminal SymbolID. Values are  indices into Index: the range for sym is StateIdx[NontermIdx[sym]...NontermIdx[sym+1]].
vector<unsigned> NontermIdx;

// parallel to actions, value is the from state. Only subranges are sorted.
vector<StateID> StateIdx;

vector<Action> Actions;

This should be 4 * (392 + 245) + (2 + 4) * 83k ~= 500k. And the one extra indirection should save 5-10 steps of binary search.

This is equivalent to 2 * vector<unsigned> + vector<pair<StateID, Action>> but keeping the searched index compact is probably a good thing.

clang/lib/Tooling/Syntax/Pseudo/LRBuilder.cpp

74

As far as I can tell, this is the only place where we need to deduplicate/check for membership in the set.

WDYT about using a local DenseSet<Item> in closure() itself for this, and making the representation of ItemSet a (small)vector?

(IIUC the reason for std::set over DenseMap is determinism. Using vector should preserve that: if you really want sorting you can sort after computing closure, but if we just want a well-defined order to ensure stable state numbers then insertion order should work fine)

109

using hashcode instead of the key itself should be explained.
(If it's just an issue with hash of std::set, I think using std::vector fixes it)

157

Yeah, I think this should work. Builder would maintain a map from (sorted kernel items) => stateID, and Builder.insert() would call closure() only if actually inserting.

clang/tools/clang-pseudo/ClangPseudo.cpp

46

I think that we should also have flags to:

• dump the grammar
• dump the LR table

[hokein]

clang/include/clang/Tooling/Syntax/Pseudo/Grammar.h

130

yeah, it is about augmented grammar. Strictly speaking, it is a start symbol of augmented symbol. Maybe we should not speak augmented stuff in the code, it is not a well-known term, and causes confusion. rename it to start symbol instead.

It looks like using augmented grammar is a "standard" LR technique, it introduces a converged start state and accepting state in the LR graph, which makes it easier for the implementation. And it is a good fit for support multiple start symbols.

133

as discussed, made them as free functions in Grammar.h. Separate the first and follow set changes to https://reviews.llvm.org/D118990, comments around them should be addressed there.

clang/lib/Tooling/Syntax/Pseudo/Grammar.cpp

88

Y was for nonterminal while z was for nonterminal or terminals. They are not super important, changed all to Uppercase.

[hokein]

comments around LRAutomaton should be addressed in the separate patch, https://reviews.llvm.org/D119172.

clang/include/clang/Tooling/Syntax/Pseudo/LRAutomaton.h

32

right, but we still need this one, for constructing an empty/Tombstone items for DenseMapInfo.

66

the main reason to we want a deterministic order for computing the hash value. Changed to a sorted vector.

79

yes and no. There are a few conceptually difference here.

GLR is indeed a nondeterministic parser, but I think the term deterministic/nondeterministic in parser is different than the ones used in automaton context.
A deterministic parser (typical LR) has a property that there will always be only one possible action to choose from, thus it is fast (linear), and it produces only one syntax tree;
A deterministic automaton is described here.

We've done the LR-style NFA->DFA conversion, but it's not complete (when we hit a conflict we continue rather than giving up)

Not exactly, there is no NFA->DFA conversion here. What this patch does:

1. we constructs a deterministic LR(0) automaton (DFA) directly, this is what LRAutomaton represents;
2. based on the DFA, we construct an LR table (called Action and GoTo Table in standard LR). In particular, we use the FollowSet to determine reduce actions, it is called SLR(1) table which is powerful the the LR(0) table.

A conflict in the LRTable doesn't imply an incomplete DFA. For an arbitrary grammar (no matter it is ambiguous or not), we can always construct a DFA. For example, based on the same LR(0) automaton, we could build a SLR(1) table (without conflicts) or LR(0) table (with conflicts).
The real problem lies in the interpretation of states of the automaton, considering a node in the automaton with state 0

E := T. + E
E := T.

and the node as a "+" outer edge, if the next symbol is +, we have two options "reduce E := T" or shift +. SLR can tell reduction is not available + is not in the FOLLOW(E) (thus no conflict) while LR(0) will accept both (thus conflicts).

I added some bits in the file comment of the LRGraph.h, hope it can clarify these concepts.

clang/lib/Tooling/Syntax/Pseudo/LRBuilder.cpp

109

using the ItemSet as key seems heavy (for cxx.grammar, 65KB for llvm::DenseMap<itemset, ..> vs 32KB for llvm::DenseMap<hash_code>) and unnecessary (we don't need to access the Itemset).

Added comments.

144

too many braces - please spell out some of the types

this is one of cons of using inlay-hints :(

[hokein]

• rebase, rescope the patch to LRTable
• refine the Action class interfaces, and nameing;
• use a more compact Index, reduce LRTable from 660KB => 335KB;
• address review comments;

[hokein]

clang/include/clang/Tooling/Syntax/Pseudo/LRTable.h

84

squeezed to 16 bits (3 bits for Kind, and 13 bits for the Value).

105

This is guaranteed by a DFA (a node can not have two out edges with a same label), the same reason why we don't have shift/shift conflicts.

121

This looks like a nice improvement, though the implementation is a little tricky -- we reduced the binary-search space from 2 dimension (State, Symbol) to 1 dimension Symbol.

[sammccall]

This is really nice, mostly nits.

clang/include/clang/Tooling/Syntax/Pseudo/Grammar.h

175

why is this exposed/required rather than being initialized by the GrammarTable constructor?
Since this is essentially static (must always correspond to tok::TokenKind) it seems that GrammarTable could just have an ArrayRef and it could be initialized by a lazy-init singleton:

// in Grammar.cpp
static ArrayRef<std::string> getTerminalNames() {
  static std::vector<std::string> *TerminalNames = []{

  };
  return *TerminalNames;
}

(I know eventually we'd like GrammarTable to be generated and have very minimal dynamic init, but there are lots of other details needed e.g. we can't statically initialize vector<Rule> either, so we should cross that bridge when we come to it)

clang/include/clang/Tooling/Syntax/Pseudo/LRTable.h

29

space -> sparse

59

Maybe mention relation to GLR: GLR can execute these in parallel?

68

nit: I think you want this to be a comment on the section rather than on Error, leave a blank line?

69

Error seems like an action we'd dynamically handle, rather than an unreachable sentinel.

I'd prefer to call this sentinel and llvm_unreachable() on it in the relevant places. Even if we do plan dynamic error actions, we have enough spare bits to keep these two cases separate.

81

again blank line between "nonterminal actions" and "go to state n"

81

pust -> push?

I thought goto replaces the top of the stack rather than being pushed onto it.

e.g.
stack is { stmt := . expr ; }, lookahead is IDENT, action is shift "expr := IDENT ."
stack is { stmt := . expr ; | expr := IDENT . }, lookahead is semi, action is reduce
stack is { stmt := . expr ; }, reduced symbol is expr, goto is state "stmt := expr . ;"
stack is { stmt := expr . ;}, lookahead is semi...

Line 3=>4 doesn't seem like a push

107

maybe value()=>opaque() or asInteger()?

Partly to give a hint a bit more at the purpose, partly to avoid confusion of Value != value()

115

static assert RuleBits <= ValueBits, and I think we want a StateBits above plus some assertions on the number of states when building

115

FWIW I've mostly seen just unsigned as the field type for bitfields. It seems a little confusing to explicitly specify the size both as 16 and 13 bits.

Up to you, but if you change this one also consider the Kind enum.

137

This is quite a lot of surface (together with the DenseMapInfo stuff) to expose.
Currently it looks like it needs to be in the header so that the LRTableTest can construct a table directly rather than going through LRGraph.

I think you could expose a narrower interface:

struct Entry { ;... };
// Specify exact table contents for testing.
static LRTable buildForTests(ArrayRef<Entry>);

Then the builder/densemapinfo can be moved to the cpp file, and both buildForTests and buildSLR can use the builder internally. WDYT?

155

maybe "value is the offset into States/Actions where the entries for this symbol begin".

164

Reading the building/lookup code, "index" and "idx" are used so often they're hard to follow.

I think calling this "States", parallel to "Actions", would be clearer.

Similarly maybe the NontermIdx -> NontermOffset (Offset into States/Actions arrays where we find entries for this nonterminal).
Then we can just use the word "index" for actual subscripts.

166

concepetually -> conceptually.

I think mixing this comment in with the concrete data is confusing.
Maybe lift it to the top of the private section like:

// Conceptually this is a multimap from (State, SymbolID) => action.
// In the literature this is often a table (and multiple entries, i.e. conflicts are forbidden).
// Our physical representation is quite different for compactness.

clang/lib/Tooling/Syntax/Pseudo/LRTable.cpp

26

as things currently stand this should be unreachable - these values should never escape the DenseMap. assert or llvm_unreachable?

98

(moving the comment thread to the new code location)

The DFA input guarantees Result.size() <= 1, but why can't it be zero?
If this is a requirement on the caller, mention it in the header?

163

nit: "assign" seems clearer than "resize"

166

We end up with holes because we're looping over the values rather than the keys. This also feels quite indirect.

Seems clear enough to reverse this, something like:

unsigned Pos = 0;
for (unsigned NT = 0; TK < GT.Nonterminals.size(); ++I) {
  NontermIdx[NT] = Pos;
  while (Pos < Sorted.size() && Sorted[Pos].Action == NT)
    ++Pos;
}
NontermIdx.back() = Pos;
// and the same for terminals

clang/lib/Tooling/Syntax/Pseudo/LRTableBuild.cpp

19 ↗

(On Diff #407862)

(I think it would be worth moving this into LRTable in order to hide the Builder type from the header...)

31 ↗

(On Diff #407862)

(rephrasing a comment that got lost earlier in the review)

I'm not totally clear on the scope/purpose of the accept action:

• if it's meant to be sufficient to know whether the parse succeeded, I think it needs the symbol we accepted as a payload. The grammar will accept them all, but the caller will place restrictions.
• if we're OK inspecting the stack and seeing our last reduction was a Decl or so, why doens't the parser just do that at the end of the stream and do away with Accept altogether? (This would avoid the need to splice eof tokens into token streams to parse subranges of them).

clang/unittests/Tooling/Syntax/Pseudo/LRGraphTest.cpp

20 ↗

(On Diff #407862)

Seems sensible to combine the table-building tests in here, but it does make the organization of the tests hard.
(Particularly since LRTableTests.cpp exists but the most important tests are in this file instead).

Since these cross module boundaries, and they are exactly "bundle of text in, bundle of text out"...
how do you feel about making them lit tests instead?

# RUN: clang-pseudo -grammar %s -print-graph | FileCheck --check-prefix=GRAPH
# RUN: clang-pseudo -grammar %s -print-table | FileCheck --check-prefix=TABLE
_ := expr
...
#      GRAPH: States:
# GRAPH-NEXT: ...
#      TABLE: LRTable:
# TABLE-NEXT: ...

[hokein]

• address comments
• more api polishments
• LRGraph unittest => lit tests
• hide LRTable::Builder, move to LRTableBuild.cpp

[hokein]

update

clang/include/clang/Tooling/Syntax/Pseudo/Grammar.h

175

fair enough, let's hide it in a GrammarTable contructor.

clang/include/clang/Tooling/Syntax/Pseudo/LRTable.h

69

changed to Sentinel, and remove Error action for now.

81

yeah, this is mostly right -- stack in step 2 has two frames, rather than a combined one.

The truth is:

1. stack is [{ _ := . stmt | stmt := . expr ; }], lookahead is IDENT, action is shift "expr := IDENT ." (push a new state to the stack)
2. stack is [{ _ := . stmt | stmt := . expr ; }, { expr := IDENT . }], lookahead is semi, action is reduce
3. stack is [{ _ := . stmt | stmt := . expr ; }], reduced symbol is expr, goto is state "stmt := expr . ;"
4. stack is [{ _ := . stmt | stmt := . expr ;}, { stmt := expr . ;}], lookahead is semi, action is shift "stmt := expr ; ."
5. stack is [{ _ := . stmt | stmt := . expr ;}, { stmt := expr . ;}, { stmt := expr ; .}], lookahead is eof, action is reduce "stmt := expr ;"
6. stack is [{ _ := . stmt | stmt := . expr ;}], reduced symbol is stmt, goto state is "_ := stmt ."
7. stack is [{ _ := . stmt | stmt := . expr ;}, { _ := stmt .}], lookahead is eof, action is accept, the parsing is done

Step 3 => 4 is a push.

107

renamed to opaque.

137

Yeah, I exposed the Builder mainly for testing purposes. The new interface looks good to me.

clang/lib/Tooling/Syntax/Pseudo/LRTable.cpp

98

yeah, getGoToState and getActions are expected to be called by the GLR parser, the parser itself should guarantee it during parsing. Added comments.

166

yeah, this is much better!

clang/lib/Tooling/Syntax/Pseudo/LRTableBuild.cpp

19 ↗

(On Diff #407862)

I tend to move all build bits (Builder, BuildSLRTable, BuildFor tests) to this file rather than LRTable.cpp.

31 ↗

(On Diff #407862)

The accept action is following what is described in the standard LR literature.

Yeah, the main purpose of the accept action is to tell us whether a parse succeeded.
We could add a ruleID as a payload for accept action, but I'm not sure whether it would be useful, the associated rule is about _ (e.g. _ := translation_unit) -- we are interested in translation_unit, this can be retrieved from the forest.

I think the both options are mostly equivalent (the 1st option is a standard LR implementation, the 2rd one seems more add-hoc)-- we can treat accept action as a "special" reduce action of the rule "_ := translation_unit" except that we don't do the reduce, we just stop parsing.

I think we probably will revisit later -- things become tricker, if we start supporting snippets (the start symbol _ will have multiple rules), e.g. for the follow grammar,

_ := stmt
_ := expr
stmt := expr
expr := ID

the input "ID" can be parsed as a "stmt" or an "expr", if we use a unified state { _ := . stmt | _ := . expr } to start, we will have a new-type conflict (accept/reduce). I don't think we want to handle this kind of new conflicts. There are some options:

• careful manage the _ rules, to make sure no such conflicts happened;
• introduce a new augmented grammar __ := _ (the accept/reduce would become reduce/reduce conflict);
• use separate start state per _ rule, and callers need to pass a targeting non-terminal to the parser;

Since there are some uncertain bits here, I'd prefer not doing further changes in this patch (but happy to add a ruleID payload for accept action). WDYT?

clang/unittests/Tooling/Syntax/Pseudo/LRGraphTest.cpp

20 ↗

(On Diff #407862)

I don't have strong opinion about these, both of them work. I think having options in the clang-pseudo tool to dump graph/table is a helpful feature for debugging as well, using lit tests might make more sense.

[sammccall]

Thanks, I really like the way the tests look now!

clang/include/clang/Tooling/Syntax/Pseudo/LRTable.h

79

// Pops

81

parsd -> parsed

clang/lib/Tooling/Syntax/Pseudo/LRTable.cpp

29

nit: goTo -> go to, like dumpForTests?

[hokein]

address comments

[aaron.ballman]

Hi, this commit is causing runtime failures on Windows in debug builds. Can you please correct or revert? Thanks!

clang/lib/Tooling/Syntax/Pseudo/LRTable.cpp

120

This is causing an assertion with debug builds on Windows because Actions[End] is out of bounds (so the MSVC STL debug assertions catch the issue) for the test cases in this patch.

[hokein]

In D118196#3341110, @aaron.ballman wrote:

Hi, this commit is causing runtime failures on Windows in debug builds. Can you please correct or revert? Thanks!

sorry for the trouble. I'm mostly running out of time today, I will revert this patch, and fix it tomorrow.

[aaron.ballman]

In D118196#3341159, @hokein wrote:

In D118196#3341110, @aaron.ballman wrote:

Hi, this commit is causing runtime failures on Windows in debug builds. Can you please correct or revert? Thanks!

sorry for the trouble. I'm mostly running out of time today, I will revert this patch, and fix it tomorrow.

Thanks!

[hokein]

clang/lib/Tooling/Syntax/Pseudo/LRTable.cpp

120

this should be llvm::makeArrayRef(&Actions[Start], End - Start). Fixed in 302ca279cb83043ef7d60115eb5ba58f12064a4a.

[aaron.ballman]

clang/lib/Tooling/Syntax/Pseudo/LRTable.cpp

120

I can confirm that the issue is now fixed for me, thank you!

clang/include/clang/Tooling/Syntax/Pseudo/Grammar.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLING_SYNTAX_GRAMMAR_H
 #define LLVM_CLANG_TOOLING_SYNTAX_GRAMMAR_H
 
 #include "clang/Basic/TokenKinds.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/StringRef.h"
 #include <cstdint>
 #include <vector>
 
 namespace clang {
 namespace syntax {
 namespace pseudo {
 // A SymbolID uniquely identifies a terminal/non-terminal symbol in a grammar.
public:
   // Diagnostics emitted during parsing are stored in Diags.
   static std::unique_ptr<Grammar> parseBNF(llvm::StringRef BNF,
                                            std::vector<std::string> &Diags);
 
   // Return all rules of the given non-terminal symbol.
   llvm::ArrayRef<Rule> lookupRules(SymbolID SID) const;
   const Rule &lookupRule(RuleID RID) const;
 
+  // Returns all symbols.
+  std::vector<SymbolID> symbols() const;
+
+  // Returns the SymbolID of the augmented symbol '_'
+  SymbolID augmentedSymbol() const { return 0; }
+
+  // Computes the FIRST(X) for all non-terminal symbol X.
+  std::vector<llvm::DenseSet<SymbolID>> firstSets() const;
+  // Computes the FOLLOW(X) for all non-terminal symbol X.
+  std::vector<llvm::DenseSet<SymbolID>> followSets() const;
+
   // Get symbol (terminal or non-terminal) name.
   // Terminals have names like "," (kw_comma) or "OPERATOR" (kw_operator).
   llvm::StringRef symbolName(SymbolID) const;
 
   // Dump the whole grammar.
   std::string dump() const;
   // Dump a particular rule.
   std::string dumpRule(RuleID) const;
struct Nonterminal {
     std::string Name;
     // A [start, end) index range for the non-terminal.
     struct { RuleID start; RuleID end; } RuleRange;
   };
 
   // The rules are sorted (and thus grouped) by target symbol.
   // RuleID is the index of the vector.
   std::vector<Rule> Rules;
-  // A table of terminals (aka tokens). It correspond to the clang::Token.
+  // A table of terminals (aka tokens). It corresponds to the clang::Token.
   // clang::tok::TokenKind is the index of the table.
   std::vector<std::string> Terminals;
   // A table of nonterminals, sorted by name.
   // SymbolID is the index of the table.
   std::vector<Nonterminal> Nonterminals;
 };
 
 } // namespace pseudo
 } // namespace syntax
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLING_SYNTAX_GRAMMAR_H

clang/include/clang/Tooling/Syntax/Pseudo/LRAutomaton.h

+//===--- LRAutomaton.h - Build an LR automaton  ------------------*- 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 LLVM_CLANG_TOOLING_SYNTAX_PSEUDO_LRAUTOMATON_H
+#define LLVM_CLANG_TOOLING_SYNTAX_PSEUDO_LRAUTOMATON_H
+
+#include "clang/Tooling/Syntax/Pseudo/Grammar.h"
+#include "clang/Tooling/Syntax/Pseudo/LRTable.h"
+#include "llvm/ADT/Hashing.h"
+#include <set>
+
+namespace clang {
+namespace syntax {
+namespace pseudo {
+
+// An LR item -- a grammar rule with a dot at some position of the body.
+// e.g. a production rule A := xy yields 3 items:
+//   A := .xy
+//   A := x.y
+//   A := xy.
+// An item indicates how much of a production rule has been recognized at a
+// position (described by dot), for example, A := x.y indicates that we have
+// recognized the x part from the input, and we hope next to see the input
+// derivable from y.
+class Item {
+public:
+  Item(RuleID ID, uint8_t RuleLength, uint8_t DotPos)
+      : RID(ID), RuleLength(RuleLength), DotPos(DotPos) {}
+
+  bool hasNext() const { return DotPos < RuleLength; }
+  SymbolID next(const Grammar &G) const {
+    assert(hasNext());
+    return rule(G).Sequence[DotPos];
+  }
+
+  Item advance() const {
+    assert(hasNext());
+    return Item(RID, RuleLength, DotPos + 1);
+  }
+  const pseudo::Rule &rule(const Grammar &G) const { return G.lookupRule(RID); }
+  RuleID ruleID() const { return RID; }
+  int dotPos() const { return DotPos; }
+  std::string dump(const Grammar &G) const;
+
+  bool operator==(const Item &I) const {
+    return DotPos == I.DotPos && RID == I.RID;
+  }
+  bool operator<(const Item &I) const {
+    return std::tie(RID, DotPos) < std::tie(I.RID, I.DotPos);
+  }
+  friend llvm::hash_code hash_value(const Item &I) {
+    return llvm::hash_combine(I.RID, I.DotPos);
+  }
+
+private:
+  RuleID RID;
+  uint8_t RuleLength; // the length of rule body.
+  uint8_t DotPos;
+};
+
+using ItemSet = std::set<Item>;
+// A state of the LR automaton is an item set, which contains all possible rules
+// that the LR parser may be parsing in that state.
+//
+// Conceptually, If we knew in advance what we're parsing, at any point we're
+// partway through parsing a production, sitting on a stack of partially parsed
+// productions. But because we don't know, there could be *several* productions
+// we're partway through. The set of possibilities is the parser state, and we
+// precompute all the transitions between these states.
+using State = ItemSet;
+llvm::hash_code hash_code(const State &S);
+std::string dump(const State &S, const Grammar &G);
+
+// A deterministic finite state automaton for LR parsing.
+//
+// Intuitively, an LR automaton is a transition graph. The graph has a
+// collection of nodes, called States. Each state corresponds to a particular
+// item set, which represents a condition that could occur duing the process of
+// parsing a production. Edges are directed from one state to another. Each edge
+// is labeled by a grammar symbol (terminal or non-terminal).
+//
+// The LR automaton is used to construct the LR parsing table (See comments in
+// LRTable) which is used to drive the LR parser.
+class LRAutomaton {
+public:
+  // Constructs an LR(0) automaton.
+  static LRAutomaton build(const Grammar &);
+
+  // Edge represents a transition in the LR automaton.
+  // If the parser is at state From, with a lookahead symbol Input, then it
+  // transit to state To.
+  struct Edge {
+    StateID From, To;
+    SymbolID Input;
+  };
+
+  llvm::ArrayRef<State> states() const { return States; }
+  llvm::ArrayRef<Edge> edges() const { return Edges; }
+
+  std::string dumpForTests(const Grammar &) const;
+
+private:
+  LRAutomaton(std::vector<State> States, std::vector<Edge> Edges)
+      : States(std::move(States)), Edges(std::move(Edges)) {}
+
+  std::vector<State> States;
+  std::vector<Edge> Edges;
+};
+
+} // namespace pseudo
+} // namespace syntax
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLING_SYNTAX_PSEUDO_LRAUTOMATON_H

clang/include/clang/Tooling/Syntax/Pseudo/LRTable.h

+//===--- LRTable.h - Define LR Parsing Table ---------------------*- 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 LLVM_CLANG_TOOLING_SYNTAX_PSEUDO_TABLE_H
+#define LLVM_CLANG_TOOLING_SYNTAX_PSEUDO_TABLE_H
+
+#include "clang/Tooling/Syntax/Pseudo/Grammar.h"
+#include "llvm/ADT/ArrayRef.h"
+#include <vector>
+
+namespace clang {
+namespace syntax {
+namespace pseudo {
+
+using StateID = uint16_t;
+
+// A dense (thus memory-efficient) implementation of the LR parsing table.
+//
+// The LR parsing table is used to drive LR parsing. It is being consulted by LR
+// parsers to make parsing decision. Conceptually, the parsing table answers the
+// question "Given a lookahead token and current state on top of the stack, what
+// is the next step?".
+//
+// The LR parsing table is constructed from a LR automaton, and it has two
+// kinds of entries:
+//   - Action(I, a) specifies the next action (shift/reduce/accept) on state I
+//     under a terminal a.
+//   - GoTo(I, X) specifies a transition from state I under a non-terminal X.
+//
+// Unlike a typical LR parsing table, it allows conflicted actions -- an Action
+// entry can have multiple available actions.
+class LRTable {
+public:
+  struct Action {
+    enum class Kind : uint8_t {
+      // Action table
+      Error = 0,
+      Shift,
+      Reduce,
+      Accept,
+      // GoTo table
+      GoTo,
+    };
+
+    bool isReduce() const { return K == Kind::Reduce; }
+    bool isShift() const { return K == Kind::Shift; }
+    bool isGoTo() const { return K == Kind::GoTo; }
+    bool isAccept() const { return K == Kind::Accept; }
+    StateID shift() const {
+      assert(isShift());
+      return Shift;
+    }
+    StateID goTo() const {
+      assert(isGoTo());
+      return GoToState;
+    }
+    RuleID reduce() const {
+      assert(isReduce());
+      return Rule;
+    }
+
+    bool operator==(const Action &L) const {
+      if (K != L.K)
+        return false;
+      switch (K) {
+      case Kind::Accept:
+      case Kind::Error:
+        return true;
+      case Kind::Shift:
+        return Shift == L.Shift;
+      case Kind::Reduce:
+        return Rule == L.Rule;
+      case Kind::GoTo:
+        return GoToState == L.GoToState;
+      }
+      llvm_unreachable("Unhandled Action::Kind");
+    }
+
+    Kind K = Kind::Error;
+    // Value
+    union {
+      StateID Shift;     // For shift action
+      RuleID Rule;       // For reduce action
+      StateID GoToState; // For go-to
+    };
+  };
+
+  // Returns all available actions for the state From on a terminal.
+  llvm::ArrayRef<Action> actions(StateID From, SymbolID Token) const {
+    assert(pseudo::isToken(Token));
+    auto Actions = find({From, Token});
+    assert(Actions.size() > 0);
+    return Actions;
+  }
+
+  // Returns the transisted state for the state From on a nonterminal.
+  StateID goTo(StateID From, SymbolID NonTerminal) const {
+    assert(pseudo::isNonterminal(NonTerminal));
+    auto Goto = find({From, NonTerminal});
+    assert(Goto.size() == 1 && Goto.front().isGoTo());
+    return Goto.front().goTo();
+  }
+
+  size_t bytes() const {
+    return sizeof(*this) + Actions.capacity() * sizeof(Action) +
+           Index.capacity() * sizeof(IndexKey);
+  }
+
+  std::string dumpStatistics() const;
+  std::string dumpForTests(const Grammar &G) const;
+
+  // Build a SLR(1) parsing table, see the Dragron book.
+  static LRTable build(const Grammar &G);
+
+private:
+  struct IndexKey {
+    StateID From;
+    SymbolID Next;
+    friend bool operator==(const IndexKey &L, const IndexKey &R) {
+      return std::tie(L.From, L.Next) == std::tie(R.From, R.Next);
+    }
+    friend bool operator<(const IndexKey &L, const IndexKey &R) {
+      return std::tie(L.From, L.Next) < std::tie(R.From, R.Next);
+    }
+  };
+  static_assert(sizeof(IndexKey) <= 4, "expected to be <= 4 bytes");
+
+  // Looks up available actions for the given Key.
+  // Returns empty if no available actions in the table.
+  llvm::ArrayRef<Action> find(IndexKey Key) const;
+
+  // A sorted table of lookup keys, lookup results are stored in Actions.
+  std::vector<IndexKey> Index; // Sorted
+  // A flat table of available actions, in parallel with Index.
+  std::vector<Action> Actions;
+};
+
+} // namespace pseudo
+} // namespace syntax
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLING_SYNTAX_PSEUDO_TABLE_H

clang/lib/Tooling/Syntax/Pseudo/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS Support)
 
 add_clang_library(clangSyntaxPseudo
   Grammar.cpp
   GrammarBNF.cpp
+  LRTable.cpp
+  LRBuilder.cpp
   
   LINK_LIBS
   clangBasic
   clangLex
   )

clang/lib/Tooling/Syntax/Pseudo/Grammar.cpp

 //===--- Grammar.cpp - Grammar for clang pseudo parser  ----------*- 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/Tooling/Syntax/Pseudo/Grammar.h"
+#include "clang/Basic/TokenKinds.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/raw_ostream.h"
 
 namespace clang {
 namespace syntax {
llvm::ArrayRef<Rule> Grammar::lookupRules(SymbolID SID) const {
   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];
 }
 
+std::vector<llvm::DenseSet<SymbolID>> Grammar::firstSets() const {
+  std::vector<llvm::DenseSet<SymbolID>> FirstSets(T->Nonterminals.size());
+  auto ExpandFirstSet = [&FirstSets](SymbolID Target, SymbolID First) {
+    assert(isNonterminal(Target));
+    if (isToken(First))
+      return FirstSets[Target].insert(First).second;
+    bool Changed = false;
+    for (SymbolID SID : FirstSets[First])
+      Changed |= FirstSets[Target].insert(SID).second;
+    return Changed;
+  };
+
+  bool Changed = false;
+  do {
+    Changed = false;
+    for (const auto &R : T->Rules) {
+      assert(R.size() > 0);
+      Changed |= ExpandFirstSet(R.target(), R.seq().front());
+    }
+  } while (Changed);
+
+  return FirstSets;
+}
+
+std::vector<llvm::DenseSet<SymbolID>> Grammar::followSets() const {
+  auto FirstSets = firstSets();
+  std::vector<llvm::DenseSet<SymbolID>> FollowSets(T->Nonterminals.size());
+  // Expand the follow set of a non-terminal symbol Y by adding all from the
+  // given symbol set.
+  auto ExpandFollowSet = [&FollowSets](SymbolID Y,
+                                       const llvm::DenseSet<SymbolID> &ToAdd) {
+    assert(isNonterminal(Y));
+    bool Changed = false;
+    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.
+  // The algorithm doesn't consider nullable-nonterminal case, as we prohibit
+  // nullable-symbol in the grammar.
+  //
+  // Rule 1: add endmarker to the FOLLOW(S), where S is the start symbol.
+  FollowSets[augmentedSymbol()].insert(tokenSymbol(tok::eof));
+  bool Changed = false;
+  do {
+    Changed = false;
+    for (const auto &R : T->Rules) {
+      // Rule 2: for a rule X := ...Yz, 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]))
+          continue;
+        SymbolID Next = R.seq()[i + 1];
+        // First set for a non-terminal is itself.
+        auto First =
+            isToken(Next) ? llvm::DenseSet<SymbolID>{Next} : FirstSets[Next];
+        Changed |= ExpandFollowSet(R.seq()[i], First);
+      }
+      SymbolID Z = R.seq().back();
+      if (!isNonterminal(Z))
+        continue;
+      // Rule 3: for a rule X := ....Z, we add all symbols from FOLLOW(X) to
+      // FOLLOW(Z).
+      Changed |= ExpandFollowSet(Z, FollowSets[R.target()]);
+    }
+  } while (Changed);
+  return FollowSets;
+}
+
+std::vector<SymbolID> Grammar::symbols() const {
+  std::vector<SymbolID> Syms;
+  for (uint16_t Terminal = 0; Terminal < NumTerminals; ++Terminal)
+    Syms.push_back(tokenSymbol(static_cast<tok::TokenKind>(Terminal)));
+  for (SymbolID Nonterminal = 0; Nonterminal < T->Nonterminals.size();
+       ++Nonterminal)
+    Syms.push_back(Nonterminal);
+  return Syms;
+}
+
 llvm::StringRef Grammar::symbolName(SymbolID SID) const {
   if (isToken(SID))
     return T->Terminals[symbolToToken(SID)];
   return T->Nonterminals[SID].Name;
 }
 
 std::string Grammar::dumpRule(RuleID RID) const {
   std::string Result;

clang/lib/Tooling/Syntax/Pseudo/LRBuilder.cpp

+//===--- LRBuilder.cpp - Build LRAutomaton and parsing tables ----*- 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/Tooling/Syntax/Pseudo/Grammar.h"
+#include "clang/Tooling/Syntax/Pseudo/LRAutomaton.h"
+#include "clang/Tooling/Syntax/Pseudo/LRTable.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/Hashing.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/StringExtras.h"
+#include "llvm/Support/FormatVariadic.h"
+#include "llvm/Support/raw_ostream.h"
+#include <map>
+
+namespace clang {
+namespace syntax {
+namespace pseudo {
+
+std::string Item::dump(const Grammar &G) const {
+  const auto &Rule = G.lookupRule(RID);
+  auto ToNames = [&](llvm::ArrayRef<SymbolID> Syms) {
+    std::vector<llvm::StringRef> Results;
+    for (auto SID : Syms)
+      Results.push_back(G.symbolName(SID));
+    return Results;
+  };
+  return llvm::formatv("{0} := {1} • {2}\n", G.symbolName(Rule.target()),
+                       llvm::join(ToNames(Rule.seq().take_front(DotPos)), " "),
+                       llvm::join(ToNames(Rule.seq().drop_front(DotPos)), " "))
+      .str();
+}
+
+llvm::hash_code hash_code(const State &S) {
+  return llvm::hash_combine_range(S.begin(), S.end());
+}
+
+std::string dump(const State &S, const Grammar &G) {
+  std::string Result;
+  llvm::raw_string_ostream OS(Result);
+  for (const auto &Item : S)
+    OS << llvm::formatv("    {0}", Item.dump(G));
+  return OS.str();
+}
+
+// Computes a closure of the given item set S:
+//  - extends the given S to contain all options for parsing next token;
+//  - nonterminals after a dot are recursively expanded into the begin-state
+//    of all production rules that produce that nonterminal;
+//
+// Given
+//   Grammar rules = [ _ := E, E := E-T, E := T, T := n, T := (E) ]
+//   Input = [ E := .T ]
+// returns [ E := .T, T := .n, T := .(E) ]
+static State closure(ItemSet IS, const Grammar &G) {
+  std::vector<Item> ProcessingItems = {IS.begin(), IS.end()};
+  while (!ProcessingItems.empty()) {
+    auto ProcessingItem = std::move(ProcessingItems.back());
+    ProcessingItems.pop_back();
+
+    if (!ProcessingItem.hasNext())
+      continue;
+    SymbolID NextSym = ProcessingItem.next(G);
+
+    if (pseudo::isToken(NextSym))
+      continue;
+    auto RRange = G.table().Nonterminals[NextSym].RuleRange;
+    for (RuleID RID = RRange.start; RID < RRange.end; ++RID) {
+      Item NewItem(RID, G.lookupRule(RID).size(), /*dot*/ 0);
+      if (IS.insert(NewItem).second) // new
+        ProcessingItems.push_back(std::move(NewItem));
+    }
+  }
+  return IS;
+}
+// For all items A := a.Xb in S, returns a closure itemset with a dot
+// advance of X.
+static State advance(const State &S, SymbolID X, const Grammar &G) {
+  ItemSet AdvanceX;
+  for (const Item &I : S) {
+    if (I.hasNext() && I.next(G) == X)
+      AdvanceX.insert(I.advance());
+  }
+  return closure(std::move(AdvanceX), G);
+}
+
+std::string LRAutomaton::dumpForTests(const Grammar &G) const {
+  std::string Result;
+  llvm::raw_string_ostream OS(Result);
+
+  OS << "States:\n";
+  for (StateID ID = 0; ID < States.size(); ++ID) {
+    OS << llvm::formatv("State {0}\n", ID);
+    OS << dump(States[ID], G);
+  }
+  return OS.str();
+}
+
+LRAutomaton LRAutomaton::build(const Grammar &G) {
+  class Builder {
+  public:
+    // Adds a given state if not existed.
+    std::pair<StateID, /*inserted*/ bool> insert(State S) {
+      auto Hash = hash_code(S);
+      auto It = StatesIndex.find(Hash);
+      if (It != StatesIndex.end())
+        return {It->second, false}; // no insertion took place.
+      States.push_back(std::move(S));
+      StatesIndex.insert({Hash, States.size() - 1});
+      return {States.size() - 1, true};
+    }
+    void insertEdge(StateID From, StateID To, SymbolID Input) {
+      Edges.push_back({From, To, Input});
+    }
+    // Returns a state with the given id.
+    const State &find(StateID ID) const {
+      assert(ID < States.size());
+      return States[ID];
+    }
+
+    LRAutomaton build() && {
+      States.resize(States.size());
+      Edges.resize(Edges.size());
+      return LRAutomaton(std::move(States), std::move(Edges));
+    }
+
+  private:
+    llvm::DenseMap<llvm::hash_code, size_t> StatesIndex;
+    std::vector<State> States;
+    std::vector<Edge> Edges;
+  } Builder;
+
+  std::vector<StateID> PendingStates;
+  // Initialize with the augmented symbol states.
+  auto RRange = G.table().Nonterminals[G.augmentedSymbol()].RuleRange;
+  for (RuleID RID = RRange.start; RID < RRange.end; ++RID) {
+    const auto &Rule = G.lookupRule(RID);
+    assert(Rule.size() == 1 &&
+           "augmented symbol rule must be _ := start_symbol.");
+    auto StartState = closure({{{RID, Rule.size(), 0}}}, G);
+    auto Result = Builder.insert(std::move(StartState));
+    assert(Result.second && "State must be new");
+    PendingStates.push_back(Result.first);
+  }
+
+  while (!PendingStates.empty()) {
+    auto CurrentStateID = PendingStates.back();
+    PendingStates.pop_back();
+    for (SymbolID Move : G.symbols()) {
+      State NextState = advance(Builder.find(CurrentStateID), Move, G);
+      if (NextState.empty())
+        continue;
+      auto Insert = Builder.insert(NextState);
+      if (Insert.second) // new state, insert to the processing.
+        PendingStates.push_back(Insert.first);
+      Builder.insertEdge(CurrentStateID, Insert.first, Move);
+    }
+  }
+  return std::move(Builder).build();
+}
+
+LRTable LRTable::build(const Grammar &G) {
+  class Builder {
+  public:
+    void addAction(StateID From, SymbolID Next, LRTable::Action New) {
+      auto It = Index.find({From, Next});
+      if (It == Index.end()) {
+        StorageActions.push_back(New);
+        Index.insert({{From, Next}, {StorageActions.size() - 1}});
+        return;
+      }
+      // Avoid duplicated actions.
+      if (llvm::any_of(It->second, [&](size_t index) {
+            return StorageActions[index] == New;
+          }))
+        return;
+      StorageActions.push_back(New);
+      It->second.push_back(StorageActions.size() - 1);
+    }
+    LRTable build() && {
+      LRTable Table;
+      Table.Actions.reserve(StorageActions.size());
+      Table.Index.reserve(StorageActions.size());
+      for (auto It : Index) {
+        for (auto Pos : It.second) {
+          Table.Actions.push_back(StorageActions[Pos]);
+          Table.Index.push_back(It.first);
+        }
+      }
+      assert(llvm::is_sorted(Table.Index));
+      return Table;
+    }
+
+  private:
+    std::vector<LRTable::Action> StorageActions;
+    // We want the iteration to be ordered.
+    std::map<LRTable::IndexKey, std::vector<size_t>> Index;
+  } Builder;
+
+  auto Automaton = LRAutomaton::build(G);
+  for (const auto &T : Automaton.edges())
+    Builder.addAction(T.From, T.Input,
+                      LRTable::Action{isToken(T.Input)
+                                          ? LRTable::Action::Kind::Shift
+                                          : LRTable::Action::Kind::GoTo,
+                                      {T.To}});
+
+  auto FollowSets = G.followSets();
+  for (StateID SID = 0; SID < Automaton.states().size(); ++SID) {
+    for (const Item &I : Automaton.states()[SID]) {
+      // If "_ := start_symbol ." in the State, set Action[State, eof] to
+      // accept.
+      if (G.lookupRule(I.ruleID()).target() == G.augmentedSymbol() &&
+          !I.hasNext()) {
+        Builder.addAction(SID, tokenSymbol(tok::eof),
+                          LRTable::Action{LRTable::Action::Kind::Accept, {}});
+        continue;
+      }
+      if (!I.hasNext()) {
+        // If a state i has an item "A := x.", set Action[i, a] to reduce
+        // "A := x" for all a in FOLLOW(A).
+        for (SymbolID Follow : FollowSets[I.rule(G).target()]) {
+          assert(isToken(Follow));
+          Builder.addAction(
+              SID, Follow,
+              LRTable::Action{LRTable::Action::Kind::Reduce, {I.ruleID()}});
+        }
+      }
+    }
+  }
+  return std::move(Builder).build();
+}
+
+} // namespace pseudo
+} // namespace syntax
+} // namespace clang

clang/lib/Tooling/Syntax/Pseudo/LRTable.cpp

+//===--- LRTable.cpp - Parsing table for LR parsers --------------*- 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/Tooling/Syntax/Pseudo/LRTable.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/Support/FormatVariadic.h"
+#include "llvm/Support/raw_ostream.h"
+
+namespace clang {
+namespace syntax {
+namespace pseudo {
+
+std::string LRTable::dumpStatistics() const {
+  StateID NumOfStates = 0;
+  for (auto It : Index)
+    NumOfStates = std::max(It.From, NumOfStates);
+  return llvm::formatv(R"(
+Statistics of the LR parsing table:
+    number of states: {0}
+    number of actions: {1}
+    size of the table (bytes): {2}
+)",
+                       NumOfStates, Actions.size(), bytes())
+      .str();
+}
+
+std::string LRTable::dumpForTests(const Grammar &G) const {
+  std::string Result;
+  llvm::raw_string_ostream OS(Result);
+  StateID MaxState = 0;
+  for (const auto &It : Index)
+    MaxState = std::max(MaxState, It.From);
+  OS << "LRTable:\n";
+  for (StateID S = 0; S <= MaxState; ++S) {
+    OS << llvm::formatv("State {0}\n", S);
+    for (SymbolID ID : G.symbols()) {
+      for (auto A : find({S, ID})) {
+        if (A.isShift())
+          OS << llvm::formatv("    '{0}': shift, and go to state {1}\n",
+                              G.symbolName(ID), A.shift());
+        else if (A.isReduce())
+          OS << llvm::formatv("    '{0}': reduce by rule {1} '{2}'\n",
+                              G.symbolName(ID), A.reduce(),
+                              G.dumpRule(A.reduce()));
+        else if (A.isAccept())
+          OS << llvm::formatv("    '{0}': accept\n", G.symbolName(ID));
+      }
+    }
+    for (SymbolID ID = 0; ID < G.table().Nonterminals.size(); ++ID) {
+      if (find({S, ID}).empty())
+        continue;
+      OS << llvm::formatv("    '{0}': go to state {1}\n", G.symbolName(ID),
+                          goTo(S, ID));
+    }
+  }
+  return OS.str();
+}
+
+llvm::ArrayRef<LRTable::Action> LRTable::find(IndexKey Key) const {
+  assert(Index.size() == Actions.size());
+  auto It = llvm::partition_point(
+      Index, [&Key](const IndexKey &E) { return E < Key; });
+  if (It == Index.end())
+    return {};
+  size_t Start = It - Index.begin();
+  auto End = Start;
+  while (End < Index.size() && Index[End] == Key)
+    ++End;
+  return llvm::makeArrayRef(&Actions[Start], &Actions[End]);
+}
+
+} // namespace pseudo
+} // namespace syntax
+} // namespace clang

clang/tools/clang-pseudo/ClangPseudo.cpp

 //===-- ClangPseudo.cpp - Clang pseudo parser 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/Tooling/Syntax/Pseudo/Grammar.h"
+#include "clang/Tooling/Syntax/Pseudo/LRTable.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/MemoryBuffer.h"
 
 using clang::syntax::pseudo::Grammar;
 using llvm::cl::desc;
 using llvm::cl::init;
if (CheckGrammar.getNumOccurrences()) {
     std::vector<std::string> Diags;
     auto RSpecs = Grammar::parseBNF(Text.get()->getBuffer(), Diags);
 
     if (!Diags.empty()) {
       llvm::errs() << llvm::join(Diags, "\n");
       return 2;
     }
     llvm::errs() << llvm::formatv("grammar file {0} is parsed successfully\n", CheckGrammar);
+    llvm::errs()
+        << clang::syntax::pseudo::LRTable::build(*RSpecs).dumpStatistics();
     return 0;
   }
   return 0;
 }

clang/unittests/Tooling/Syntax/Pseudo/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
 add_custom_target(ClangPseudoUnitTests)
 add_unittest(ClangPseudoUnitTests ClangPseudoTests
   GrammarTests.cpp
+  LRBuilderTests.cpp
   )
 
 clang_target_link_libraries(ClangPseudoTests
   PRIVATE
   clangBasic
   clangLex
   clangSyntaxPseudo
   clangTesting
   )
 
 target_link_libraries(ClangPseudoTests
   PRIVATE
   LLVMTestingSupport
   )

clang/unittests/Tooling/Syntax/Pseudo/GrammarTests.cpp

-//===--- GrammarTests.cpp - grammar tests  ------------------------*- C++-*-===//
+//===--- GrammarTests.cpp - grammar tests  -----------------------*- 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/Tooling/Syntax/Pseudo/Grammar.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <memory>
 
 namespace clang {
 namespace syntax {
 namespace pseudo {
 namespace {
 
 using testing::AllOf;
 using testing::ElementsAre;
 using testing::IsEmpty;
+using testing::Pair;
 using testing::UnorderedElementsAre;
 
 MATCHER_P(TargetID, SID, "") { return arg.target() == SID; }
 template <typename... T>
 testing::Matcher<const Rule &> Sequence(T... IDs) {
   return testing::Property(&Rule::seq, ElementsAre(IDs...));
 }
 
 class GrammarTest : public ::testing::Test {
 public:
   void build(llvm::StringRef BNF) {
     Diags.clear();
     G = Grammar::parseBNF(BNF, Diags);
   }
 
-  SymbolID lookup(llvm::StringRef Name) const {
+  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;
     assert(false);
   }
 
 protected:
   std::unique_ptr<Grammar> G;
   std::vector<std::string> Diags;
 };
 
 TEST_F(GrammarTest, Basic) {
   build("expression := IDENTIFIER + expression # comment");
   EXPECT_THAT(Diags, IsEmpty());
 
-  auto ExpectedRule = AllOf(TargetID(lookup("expression")),
-                        Sequence(lookup("IDENTIFIER"), lookup("+"),
-                                       lookup("expression")));
-  auto ExpressionID = lookup("expression");
+  auto ExpectedRule =
+      AllOf(TargetID(id("expression")),
+            Sequence(id("IDENTIFIER"), id("+"), id("expression")));
+  auto ExpressionID = id("expression");
   // auto RuleID = 0;
   EXPECT_EQ(G->symbolName(ExpressionID), "expression");
   EXPECT_THAT(G->lookupRules(ExpressionID), UnorderedElementsAre(ExpectedRule));
   const auto& Rule = G->lookupRule(/*RID=*/0);
   EXPECT_THAT(Rule, ExpectedRule);
   EXPECT_THAT(G->symbolName(Rule.seq()[0]), "IDENTIFIER");
   EXPECT_THAT(G->symbolName(Rule.seq()[1]), "+");
   EXPECT_THAT(G->symbolName(Rule.seq()[2]), "expression");
 }
 
 TEST_F(GrammarTest, EliminatedOptional) {
   build("_ := CONST_opt INT ;_opt");
   EXPECT_THAT(Diags, IsEmpty());
   EXPECT_THAT(G->table().Rules,
-              UnorderedElementsAre(
-                  Sequence(lookup("INT")),
-                  Sequence(lookup("CONST"), lookup("INT")),
-                  Sequence(lookup("CONST"), lookup("INT"), lookup(";")),
-                  Sequence(lookup("INT"), lookup(";"))));
+              UnorderedElementsAre(Sequence(id("INT")),
+                                   Sequence(id("CONST"), id("INT")),
+                                   Sequence(id("CONST"), id("INT"), id(";")),
+                                   Sequence(id("INT"), id(";"))));
 }
 
 TEST_F(GrammarTest, Diagnostics) {
   build(R"cpp(
     _ := ,_opt
     _ := undefined-sym
     null :=
     _ := IDENFIFIE # a typo of the terminal IDENFITIER
 
     invalid
   )cpp");
 
   EXPECT_THAT(Diags, UnorderedElementsAre(
                          "Rule '_ := ,_opt' emits a nullable symbol",
                          "Rule 'null := ' emits a nullable symbol",
                          "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"));
 }
 
+TEST_F(GrammarTest, FirstAndFollow) {
+  build(
+      R"bnf(
+_ := expr
+expr := expr - term
+expr := term
+term := IDENTIFIER
+term := ( expr )
+)bnf");
+  ASSERT_TRUE(Diags.empty());
+  auto ToPair = [](std::vector<llvm::DenseSet<SymbolID>> Input) {
+    std::vector<std::pair<SymbolID, llvm::DenseSet<SymbolID>>> Sets;
+    for (SymbolID ID = 0; ID < Input.size(); ++ID)
+      Sets.emplace_back(ID, std::move(Input[ID]));
+    return Sets;
+  };
+
+  EXPECT_THAT(
+      ToPair(G->firstSets()),
+      UnorderedElementsAre(
+          Pair(id("_"), UnorderedElementsAre(id("IDENTIFIER"), id("("))),
+          Pair(id("expr"), UnorderedElementsAre(id("IDENTIFIER"), id("("))),
+          Pair(id("term"), UnorderedElementsAre(id("IDENTIFIER"), id("(")))));
+  EXPECT_THAT(
+      ToPair(G->followSets()),
+      UnorderedElementsAre(
+          Pair(id("_"), UnorderedElementsAre(id("EOF"))),
+          Pair(id("expr"), UnorderedElementsAre(id("-"), id("EOF"), id(")"))),
+          Pair(id("term"), UnorderedElementsAre(id("-"), id("EOF"), id(")")))));
+
+  build(R"bnf(
+# A simplfied C++ decl-specifier-seq.
+_ := decl-specifier-seq
+decl-specifier-seq := decl-specifier decl-specifier-seq
+decl-specifier-seq := decl-specifier
+decl-specifier := simple-type-specifier
+decl-specifier := INLINE
+simple-type-specifier := INT
+   )bnf");
+  ASSERT_TRUE(Diags.empty());
+  EXPECT_THAT(
+      ToPair(G->firstSets()),
+      UnorderedElementsAre(
+          Pair(id("_"), UnorderedElementsAre(id("INLINE"), id("INT"))),
+          Pair(id("decl-specifier-seq"),
+               UnorderedElementsAre(id("INLINE"), id("INT"))),
+          Pair(id("simple-type-specifier"), UnorderedElementsAre(id("INT"))),
+          Pair(id("decl-specifier"),
+               UnorderedElementsAre(id("INLINE"), id("INT")))));
+  EXPECT_THAT(
+      ToPair(G->followSets()),
+      UnorderedElementsAre(
+          Pair(id("_"), UnorderedElementsAre(id("EOF"))),
+          Pair(id("decl-specifier-seq"), UnorderedElementsAre(id("EOF"))),
+          Pair(id("decl-specifier"),
+               UnorderedElementsAre(id("INLINE"), id("INT"), id("EOF"))),
+          Pair(id("simple-type-specifier"),
+               UnorderedElementsAre(id("INLINE"), id("INT"), id("EOF")))));
+}
+
 } // namespace
 } // namespace pseudo
 } // namespace syntax
 } // namespace clang

clang/unittests/Tooling/Syntax/Pseudo/LRBuilderTests.cpp

+//===--- LRBuilderTests.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/Tooling/Syntax/Pseudo/LRAutomaton.h"
+#include "clang/Tooling/Syntax/Pseudo/LRTable.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include <memory>
+
+namespace clang {
+namespace syntax {
+namespace pseudo {
+namespace {
+
+TEST(TableTest, BuildLRTable) {
+  struct TestCase {
+    llvm::StringRef BNF;
+    llvm::StringRef ExpectedStates;
+    llvm::StringRef ExpectedTable;
+  };
+
+  TestCase Cases[] = {
+      {
+          R"bnf(
+_ := expr
+expr := IDENTIFIER
+      )bnf",
+          R"(States:
+State 0
+    _ :=  • expr
+    expr :=  • IDENTIFIER
+State 1
+    expr := IDENTIFIER • 
+State 2
+    _ := expr • 
+)",
+          R"(LRTable:
+State 0
+    'IDENTIFIER': shift, and go to state 1
+    'expr': go to state 2
+State 1
+    'EOF': reduce by rule 1 'expr := IDENTIFIER'
+State 2
+    'EOF': accept
+)",
+      },
+      {
+          // A grammar with a S/R conflict in SLR table: (id-id)-id, or
+          // id-(id-id).
+          R"bnf(
+_ := expr
+expr := expr - expr  # S/R conflict at state 4 on '-' token
+expr := IDENTIFIER
+      )bnf",
+          R"(States:
+State 0
+    _ :=  • expr
+    expr :=  • IDENTIFIER
+    expr :=  • expr - expr
+State 1
+    expr := IDENTIFIER • 
+State 2
+    _ := expr • 
+    expr := expr • - expr
+State 3
+    expr :=  • IDENTIFIER
+    expr :=  • expr - expr
+    expr := expr - • expr
+State 4
+    expr := expr • - expr
+    expr := expr - expr • 
+)",
+          R"(LRTable:
+State 0
+    'IDENTIFIER': shift, and go to state 1
+    'expr': go to state 2
+State 1
+    'EOF': reduce by rule 1 'expr := IDENTIFIER'
+    '-': reduce by rule 1 'expr := IDENTIFIER'
+State 2
+    'EOF': accept
+    '-': shift, and go to state 3
+State 3
+    'IDENTIFIER': shift, and go to state 1
+    'expr': go to state 4
+State 4
+    'EOF': reduce by rule 2 'expr := expr - expr'
+    '-': shift, and go to state 3
+    '-': reduce by rule 2 'expr := expr - expr'
+)",
+      },
+  };
+  for (const auto &C : Cases) {
+    std::vector<std::string> Diags;
+    auto G = Grammar::parseBNF(C.BNF, Diags);
+    ASSERT_THAT(Diags, testing::IsEmpty());
+    auto Automaton = LRAutomaton::build(*G);
+    auto Table = LRTable::build(*G);
+    EXPECT_EQ(Automaton.dumpForTests(*G), C.ExpectedStates);
+    EXPECT_EQ(Table.dumpForTests(*G), C.ExpectedTable);
+  }
+}
+
+} // namespace
+} // namespace pseudo
+} // namespace syntax
+} // namespace clang