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