1 //===--- LRTableBuild.cpp - Build a LRTable from LRGraph ---------*- C++-*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "clang-pseudo/Grammar.h"
10 #include "clang-pseudo/LRGraph.h"
11 #include "clang-pseudo/LRTable.h"
12 #include "clang/Basic/TokenKinds.h"
13 #include <cstdint>
14 
15 namespace llvm {
16 template <> struct DenseMapInfo<clang::pseudo::LRTable::Entry> {
17   using Entry = clang::pseudo::LRTable::Entry;
18   static inline Entry getEmptyKey() {
19     static Entry E{static_cast<clang::pseudo::SymbolID>(-1), 0,
20                    clang::pseudo::LRTable::Action::sentinel()};
21     return E;
22   }
23   static inline Entry getTombstoneKey() {
24     static Entry E{static_cast<clang::pseudo::SymbolID>(-2), 0,
25                    clang::pseudo::LRTable::Action::sentinel()};
26     return E;
27   }
28   static unsigned getHashValue(const Entry &I) {
29     return llvm::hash_combine(I.State, I.Symbol, I.Act.opaque());
30   }
31   static bool isEqual(const Entry &LHS, const Entry &RHS) {
32     return LHS.State == RHS.State && LHS.Symbol == RHS.Symbol &&
33            LHS.Act == RHS.Act;
34   }
35 };
36 } // namespace llvm
37 
38 namespace clang {
39 namespace pseudo {
40 
41 class LRTable::Builder {
42 public:
43   Builder(llvm::ArrayRef<std::pair<SymbolID, StateID>> StartStates)
44       : StartStates(StartStates) {}
45 
46   bool insert(Entry E) { return Entries.insert(std::move(E)).second; }
47   LRTable build(const GrammarTable &GT, unsigned NumStates) && {
48     // E.g. given the following parsing table with 3 states and 3 terminals:
49     //
50     //            a    b     c
51     // +-------+----+-------+-+
52     // |state0 |    | s0,r0 | |
53     // |state1 | acc|       | |
54     // |state2 |    |  r1   | |
55     // +-------+----+-------+-+
56     //
57     // The final LRTable:
58     //  - StateOffset: [s0] = 0, [s1] = 2, [s2] = 3, [sentinel] = 4
59     //  - Symbols:     [ b,   b,   a,  b]
60     //    Actions:     [ s0, r0, acc, r1]
61     //                   ~~~~~~ range for state 0
62     //                           ~~~~ range for state 1
63     //                                ~~ range for state 2
64     // First step, we sort all entries by (State, Symbol, Action).
65     std::vector<Entry> Sorted(Entries.begin(), Entries.end());
66     llvm::sort(Sorted, [](const Entry &L, const Entry &R) {
67       return std::forward_as_tuple(L.State, L.Symbol, L.Act.opaque()) <
68              std::forward_as_tuple(R.State, R.Symbol, R.Act.opaque());
69     });
70 
71     LRTable Table;
72     Table.Actions.reserve(Sorted.size());
73     Table.Symbols.reserve(Sorted.size());
74     // We are good to finalize the States and Actions.
75     for (const auto &E : Sorted) {
76       Table.Actions.push_back(E.Act);
77       Table.Symbols.push_back(E.Symbol);
78     }
79     // Initialize the terminal and nonterminal offset, all ranges are empty by
80     // default.
81     Table.StateOffset = std::vector<uint32_t>(NumStates + 1, 0);
82     size_t SortedIndex = 0;
83     for (StateID State = 0; State < Table.StateOffset.size(); ++State) {
84       Table.StateOffset[State] = SortedIndex;
85       while (SortedIndex < Sorted.size() && Sorted[SortedIndex].State == State)
86         ++SortedIndex;
87     }
88     Table.StartStates = std::move(StartStates);
89     return Table;
90   }
91 
92 private:
93   llvm::DenseSet<Entry> Entries;
94   std::vector<std::pair<SymbolID, StateID>> StartStates;
95 };
96 
97 LRTable LRTable::buildForTests(const GrammarTable &GT,
98                                llvm::ArrayRef<Entry> Entries) {
99   StateID MaxState = 0;
100   for (const auto &Entry : Entries)
101     MaxState = std::max(MaxState, Entry.State);
102   Builder Build({});
103   for (const Entry &E : Entries)
104     Build.insert(E);
105   return std::move(Build).build(GT, /*NumStates=*/MaxState + 1);
106 }
107 
108 LRTable LRTable::buildSLR(const Grammar &G) {
109   auto Graph = LRGraph::buildLR0(G);
110   Builder Build(Graph.startStates());
111   for (const auto &T : Graph.edges()) {
112     Action Act = isToken(T.Label) ? Action::shift(T.Dst) : Action::goTo(T.Dst);
113     Build.insert({T.Src, T.Label, Act});
114   }
115   assert(Graph.states().size() <= (1 << StateBits) &&
116          "Graph states execceds the maximum limit!");
117   auto FollowSets = followSets(G);
118   for (StateID SID = 0; SID < Graph.states().size(); ++SID) {
119     for (const Item &I : Graph.states()[SID].Items) {
120       // If we've just parsed the start symbol, we can accept the input.
121       if (G.lookupRule(I.rule()).Target == G.underscore() && !I.hasNext()) {
122         Build.insert({SID, tokenSymbol(tok::eof), Action::accept(I.rule())});
123         continue;
124       }
125       if (!I.hasNext()) {
126         // If we've reached the end of a rule A := ..., then we can reduce if
127         // the next token is in the follow set of A.
128         for (SymbolID Follow : FollowSets[G.lookupRule(I.rule()).Target]) {
129           assert(isToken(Follow));
130           Build.insert({SID, Follow, Action::reduce(I.rule())});
131         }
132       }
133     }
134   }
135   return std::move(Build).build(G.table(), Graph.states().size());
136 }
137 
138 } // namespace pseudo
139 } // namespace clang
140