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/Grammar.h" 10 #include "clang-pseudo/grammar/LRGraph.h" 11 #include "clang-pseudo/grammar/LRTable.h" 12 #include "clang/Basic/TokenKinds.h" 13 #include "llvm/ADT/SmallSet.h" 14 #include <cstdint> 15 16 namespace llvm { 17 template <> struct DenseMapInfo<clang::pseudo::LRTable::Entry> { 18 using Entry = clang::pseudo::LRTable::Entry; 19 static inline Entry getEmptyKey() { 20 static Entry E{static_cast<clang::pseudo::SymbolID>(-1), 0, 21 clang::pseudo::LRTable::Action::sentinel()}; 22 return E; 23 } 24 static inline Entry getTombstoneKey() { 25 static Entry E{static_cast<clang::pseudo::SymbolID>(-2), 0, 26 clang::pseudo::LRTable::Action::sentinel()}; 27 return E; 28 } 29 static unsigned getHashValue(const Entry &I) { 30 return llvm::hash_combine(I.State, I.Symbol, I.Act.opaque()); 31 } 32 static bool isEqual(const Entry &LHS, const Entry &RHS) { 33 return LHS.State == RHS.State && LHS.Symbol == RHS.Symbol && 34 LHS.Act == RHS.Act; 35 } 36 }; 37 } // namespace llvm 38 39 namespace clang { 40 namespace pseudo { 41 42 struct LRTable::Builder { 43 std::vector<std::pair<SymbolID, StateID>> StartStates; 44 llvm::DenseSet<Entry> Entries; 45 llvm::DenseMap<StateID, llvm::SmallSet<RuleID, 4>> Reduces; 46 std::vector<llvm::DenseSet<SymbolID>> FollowSets; 47 48 LRTable build(unsigned NumStates) && { 49 // E.g. given the following parsing table with 3 states and 3 terminals: 50 // 51 // a b c 52 // +-------+----+-------+-+ 53 // |state0 | | s0,r0 | | 54 // |state1 | acc| | | 55 // |state2 | | r1 | | 56 // +-------+----+-------+-+ 57 // 58 // The final LRTable: 59 // - StateOffset: [s0] = 0, [s1] = 2, [s2] = 3, [sentinel] = 4 60 // - Symbols: [ b, b, a, b] 61 // Actions: [ s0, r0, acc, r1] 62 // ~~~~~~ range for state 0 63 // ~~~~ range for state 1 64 // ~~ range for state 2 65 // First step, we sort all entries by (State, Symbol, Action). 66 std::vector<Entry> Sorted(Entries.begin(), Entries.end()); 67 llvm::sort(Sorted, [](const Entry &L, const Entry &R) { 68 return std::forward_as_tuple(L.State, L.Symbol, L.Act.opaque()) < 69 std::forward_as_tuple(R.State, R.Symbol, R.Act.opaque()); 70 }); 71 72 LRTable Table; 73 Table.Actions.reserve(Sorted.size()); 74 Table.Symbols.reserve(Sorted.size()); 75 // We are good to finalize the States and Actions. 76 for (const auto &E : Sorted) { 77 Table.Actions.push_back(E.Act); 78 Table.Symbols.push_back(E.Symbol); 79 } 80 // Initialize the terminal and nonterminal offset, all ranges are empty by 81 // default. 82 Table.StateOffset = std::vector<uint32_t>(NumStates + 1, 0); 83 size_t SortedIndex = 0; 84 for (StateID State = 0; State < Table.StateOffset.size(); ++State) { 85 Table.StateOffset[State] = SortedIndex; 86 while (SortedIndex < Sorted.size() && Sorted[SortedIndex].State == State) 87 ++SortedIndex; 88 } 89 Table.StartStates = std::move(StartStates); 90 91 // Compile the follow sets into a bitmap. 92 Table.FollowSets.resize(tok::NUM_TOKENS * FollowSets.size()); 93 for (SymbolID NT = 0; NT < FollowSets.size(); ++NT) 94 for (SymbolID Follow : FollowSets[NT]) 95 Table.FollowSets.set(NT * tok::NUM_TOKENS + symbolToToken(Follow)); 96 97 // Store the reduce actions in a vector partitioned by state. 98 Table.ReduceOffset.reserve(NumStates + 1); 99 std::vector<RuleID> StateRules; 100 for (StateID S = 0; S < NumStates; ++S) { 101 Table.ReduceOffset.push_back(Table.Reduces.size()); 102 auto It = Reduces.find(S); 103 if (It == Reduces.end()) 104 continue; 105 Table.Reduces.insert(Table.Reduces.end(), It->second.begin(), 106 It->second.end()); 107 std::sort(Table.Reduces.begin() + Table.ReduceOffset.back(), 108 Table.Reduces.end()); 109 } 110 Table.ReduceOffset.push_back(Table.Reduces.size()); 111 112 return Table; 113 } 114 }; 115 116 LRTable LRTable::buildForTests(const Grammar &G, llvm::ArrayRef<Entry> Entries, 117 llvm::ArrayRef<ReduceEntry> Reduces) { 118 StateID MaxState = 0; 119 for (const auto &Entry : Entries) { 120 MaxState = std::max(MaxState, Entry.State); 121 if (Entry.Act.kind() == LRTable::Action::Shift) 122 MaxState = std::max(MaxState, Entry.Act.getShiftState()); 123 if (Entry.Act.kind() == LRTable::Action::GoTo) 124 MaxState = std::max(MaxState, Entry.Act.getGoToState()); 125 } 126 Builder Build; 127 Build.Entries.insert(Entries.begin(), Entries.end()); 128 for (const ReduceEntry &E : Reduces) 129 Build.Reduces[E.State].insert(E.Rule); 130 Build.FollowSets = followSets(G); 131 return std::move(Build).build(/*NumStates=*/MaxState + 1); 132 } 133 134 LRTable LRTable::buildSLR(const Grammar &G) { 135 auto Graph = LRGraph::buildLR0(G); 136 Builder Build; 137 Build.StartStates = Graph.startStates(); 138 for (const auto &T : Graph.edges()) { 139 Action Act = isToken(T.Label) ? Action::shift(T.Dst) : Action::goTo(T.Dst); 140 Build.Entries.insert({T.Src, T.Label, Act}); 141 } 142 Build.FollowSets = followSets(G); 143 assert(Graph.states().size() <= (1 << StateBits) && 144 "Graph states execceds the maximum limit!"); 145 // Add reduce actions. 146 for (StateID SID = 0; SID < Graph.states().size(); ++SID) { 147 for (const Item &I : Graph.states()[SID].Items) { 148 // If we've just parsed the start symbol, this means we successfully parse 149 // the input. We don't add the reduce action of `_ := start_symbol` in the 150 // LRTable (the GLR parser handles it specifically). 151 if (G.lookupRule(I.rule()).Target == G.underscore() && !I.hasNext()) 152 continue; 153 if (!I.hasNext()) 154 // If we've reached the end of a rule A := ..., then we can reduce if 155 // the next token is in the follow set of A. 156 Build.Reduces[SID].insert(I.rule()); 157 } 158 } 159 return std::move(Build).build(Graph.states().size()); 160 } 161 162 } // namespace pseudo 163 } // namespace clang 164