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/STLExtras.h"
14 #include "llvm/ADT/SmallSet.h"
15 #include <cstdint>
16
17 namespace clang {
18 namespace pseudo {
19
build()20 LRTable LRTable::Builder::build() && {
21 assert(NumNonterminals != 0 && "Set NumNonterminals or init with grammar");
22 LRTable Table;
23
24 // Count number of states: every state has to be reachable somehow.
25 StateID MaxState = 0;
26 for (const auto &Entry : StartStates)
27 MaxState = std::max(MaxState, Entry.second);
28 for (const auto &Entry : Transition)
29 MaxState = std::max(MaxState, Entry.second);
30 unsigned NumStates = MaxState + 1;
31
32 Table.StartStates = std::move(StartStates);
33
34 // Compile the goto and shift actions into transition tables.
35 llvm::DenseMap<unsigned, SymbolID> Gotos;
36 llvm::DenseMap<unsigned, SymbolID> Shifts;
37 for (const auto &E : Transition) {
38 if (isToken(E.first.second))
39 Shifts.try_emplace(shiftIndex(E.first.first, E.first.second, NumStates),
40 E.second);
41 else
42 Gotos.try_emplace(gotoIndex(E.first.first, E.first.second, NumStates),
43 E.second);
44 }
45 Table.Shifts = TransitionTable(Shifts, NumStates * NumTerminals);
46 Table.Gotos = TransitionTable(Gotos, NumStates * NumNonterminals);
47
48 // Compile the follow sets into a bitmap.
49 Table.FollowSets.resize(tok::NUM_TOKENS * FollowSets.size());
50 for (SymbolID NT = 0; NT < FollowSets.size(); ++NT)
51 for (SymbolID Follow : FollowSets[NT])
52 Table.FollowSets.set(NT * tok::NUM_TOKENS + symbolToToken(Follow));
53
54 // Store the reduce actions in a vector partitioned by state.
55 Table.ReduceOffset.reserve(NumStates + 1);
56 std::vector<RuleID> StateRules;
57 for (StateID S = 0; S < NumStates; ++S) {
58 Table.ReduceOffset.push_back(Table.Reduces.size());
59 auto It = Reduce.find(S);
60 if (It == Reduce.end())
61 continue;
62 Table.Reduces.insert(Table.Reduces.end(), It->second.begin(),
63 It->second.end());
64 llvm::sort(Table.Reduces.begin() + Table.ReduceOffset.back(),
65 Table.Reduces.end());
66 }
67 Table.ReduceOffset.push_back(Table.Reduces.size());
68
69 // Error recovery entries: sort (no dups already), and build offset lookup.
70 llvm::sort(Recoveries, [&](const auto &L, const auto &R) {
71 return std::tie(L.first, L.second.Result, L.second.Strategy) <
72 std::tie(R.first, R.second.Result, R.second.Strategy);
73 });
74 Table.Recoveries.reserve(Recoveries.size());
75 for (const auto &R : Recoveries)
76 Table.Recoveries.push_back({R.second.Strategy, R.second.Result});
77 Table.RecoveryOffset = std::vector<uint32_t>(NumStates + 1, 0);
78 unsigned SortedIndex = 0;
79 for (StateID State = 0; State < NumStates; ++State) {
80 Table.RecoveryOffset[State] = SortedIndex;
81 while (SortedIndex < Recoveries.size() &&
82 Recoveries[SortedIndex].first == State)
83 SortedIndex++;
84 }
85 Table.RecoveryOffset[NumStates] = SortedIndex;
86 assert(SortedIndex == Recoveries.size());
87
88 return Table;
89 }
90
buildSLR(const Grammar & G)91 LRTable LRTable::buildSLR(const Grammar &G) {
92 auto Graph = LRGraph::buildLR0(G);
93 Builder Build(G);
94 Build.StartStates = Graph.startStates();
95 for (const auto &T : Graph.edges())
96 Build.Transition.try_emplace({T.Src, T.Label}, T.Dst);
97 for (const auto &Entry : Graph.recoveries())
98 Build.Recoveries.push_back(
99 {Entry.Src, Recovery{Entry.Strategy, Entry.Result}});
100 Build.FollowSets = followSets(G);
101 assert(Graph.states().size() <= (1 << StateBits) &&
102 "Graph states execceds the maximum limit!");
103 // Add reduce actions.
104 for (StateID SID = 0; SID < Graph.states().size(); ++SID) {
105 for (const Item &I : Graph.states()[SID].Items) {
106 // If we've just parsed the start symbol, this means we successfully parse
107 // the input. We don't add the reduce action of `_ := start_symbol` in the
108 // LRTable (the GLR parser handles it specifically).
109 if (G.lookupRule(I.rule()).Target == G.underscore() && !I.hasNext())
110 continue;
111 if (!I.hasNext())
112 // If we've reached the end of a rule A := ..., then we can reduce if
113 // the next token is in the follow set of A.
114 Build.Reduce[SID].insert(I.rule());
115 }
116 }
117 return std::move(Build).build();
118 }
119
120 } // namespace pseudo
121 } // namespace clang
122