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 
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 
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