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) && {
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     //  - TerminalOffset: [a] = 0, [b] = 1, [c] = 4, [d] = 4 (d is a sentinel)
59     //  -  States:     [ 1,    0,  0,  2]
60     //    Actions:     [ acc, s0, r0, r1]
61     //                   ~~~ corresponding range for terminal a
62     //                        ~~~~~~~~~~ corresponding range for terminal b
63     // First step, we sort all entries by (Symbol, State, Action).
64     std::vector<Entry> Sorted(Entries.begin(), Entries.end());
65     llvm::sort(Sorted, [](const Entry &L, const Entry &R) {
66       return std::forward_as_tuple(L.Symbol, L.State, L.Act.opaque()) <
67              std::forward_as_tuple(R.Symbol, R.State, R.Act.opaque());
68     });
69 
70     LRTable Table;
71     Table.Actions.reserve(Sorted.size());
72     Table.States.reserve(Sorted.size());
73     // We are good to finalize the States and Actions.
74     for (const auto &E : Sorted) {
75       Table.Actions.push_back(E.Act);
76       Table.States.push_back(E.State);
77     }
78     // Initialize the terminal and nonterminal offset, all ranges are empty by
79     // default.
80     Table.TerminalOffset = std::vector<uint32_t>(GT.Terminals.size() + 1, 0);
81     Table.NontermOffset = std::vector<uint32_t>(GT.Nonterminals.size() + 1, 0);
82     size_t SortedIndex = 0;
83     for (SymbolID NonterminalID = 0; NonterminalID < Table.NontermOffset.size();
84          ++NonterminalID) {
85       Table.NontermOffset[NonterminalID] = SortedIndex;
86       while (SortedIndex < Sorted.size() &&
87              Sorted[SortedIndex].Symbol == NonterminalID)
88         ++SortedIndex;
89     }
90     for (size_t Terminal = 0; Terminal < Table.TerminalOffset.size();
91          ++Terminal) {
92       Table.TerminalOffset[Terminal] = SortedIndex;
93       while (SortedIndex < Sorted.size() &&
94              Sorted[SortedIndex].Symbol ==
95                  tokenSymbol(static_cast<tok::TokenKind>(Terminal)))
96         ++SortedIndex;
97     }
98     Table.StartStates = std::move(StartStates);
99     return Table;
100   }
101 
102 private:
103   llvm::DenseSet<Entry> Entries;
104   std::vector<std::pair<SymbolID, StateID>> StartStates;
105 };
106 
107 LRTable LRTable::buildForTests(const GrammarTable &GT,
108                                llvm::ArrayRef<Entry> Entries) {
109   Builder Build({});
110   for (const Entry &E : Entries)
111     Build.insert(E);
112   return std::move(Build).build(GT);
113 }
114 
115 LRTable LRTable::buildSLR(const Grammar &G) {
116   auto Graph = LRGraph::buildLR0(G);
117   Builder Build(Graph.startStates());
118   for (const auto &T : Graph.edges()) {
119     Action Act = isToken(T.Label) ? Action::shift(T.Dst) : Action::goTo(T.Dst);
120     Build.insert({T.Src, T.Label, Act});
121   }
122   assert(Graph.states().size() <= (1 << StateBits) &&
123          "Graph states execceds the maximum limit!");
124   auto FollowSets = followSets(G);
125   for (StateID SID = 0; SID < Graph.states().size(); ++SID) {
126     for (const Item &I : Graph.states()[SID].Items) {
127       // If we've just parsed the start symbol, we can accept the input.
128       if (G.lookupRule(I.rule()).Target == G.underscore() && !I.hasNext()) {
129         Build.insert({SID, tokenSymbol(tok::eof), Action::accept(I.rule())});
130         continue;
131       }
132       if (!I.hasNext()) {
133         // If we've reached the end of a rule A := ..., then we can reduce if
134         // the next token is in the follow set of A.
135         for (SymbolID Follow : FollowSets[G.lookupRule(I.rule()).Target]) {
136           assert(isToken(Follow));
137           Build.insert({SID, Follow, Action::reduce(I.rule())});
138         }
139       }
140     }
141   }
142   return std::move(Build).build(G.table());
143 }
144 
145 } // namespace pseudo
146 } // namespace clang
147