1 //===--- LRTable.cpp - Parsing table for LR parsers --------------*- 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/LRTable.h"
10 #include "clang-pseudo/Grammar.h"
11 #include "llvm/ADT/ArrayRef.h"
12 #include "llvm/ADT/STLExtras.h"
13 #include "llvm/Support/ErrorHandling.h"
14 #include "llvm/Support/FormatVariadic.h"
15 #include "llvm/Support/raw_ostream.h"
16 
17 namespace clang {
18 namespace pseudo {
19 
20 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const LRTable::Action &A) {
21   switch (A.kind()) {
22   case LRTable::Action::Shift:
23     return OS << llvm::formatv("shift state {0}", A.getShiftState());
24   case LRTable::Action::Reduce:
25     return OS << llvm::formatv("reduce by rule {0}", A.getReduceRule());
26   case LRTable::Action::GoTo:
27     return OS << llvm::formatv("go to state {0}", A.getGoToState());
28   case LRTable::Action::Accept:
29     return OS << "acc";
30   case LRTable::Action::Sentinel:
31     llvm_unreachable("unexpected Sentinel action kind!");
32   }
33   llvm_unreachable("unexpected action kind!");
34 }
35 
36 std::string LRTable::dumpStatistics() const {
37   StateID NumOfStates = 0;
38   for (StateID It : States)
39     NumOfStates = std::max(It, NumOfStates);
40   return llvm::formatv(R"(
41 Statistics of the LR parsing table:
42     number of states: {0}
43     number of actions: {1}
44     size of the table (bytes): {2}
45 )",
46                        NumOfStates, Actions.size(), bytes())
47       .str();
48 }
49 
50 std::string LRTable::dumpForTests(const Grammar &G) const {
51   std::string Result;
52   llvm::raw_string_ostream OS(Result);
53   StateID MaxState = 0;
54   for (StateID It : States)
55     MaxState = std::max(MaxState, It);
56   OS << "LRTable:\n";
57   for (StateID S = 0; S <= MaxState; ++S) {
58     OS << llvm::formatv("State {0}\n", S);
59     for (uint16_t Terminal = 0; Terminal < NumTerminals; ++Terminal) {
60       SymbolID TokID = tokenSymbol(static_cast<tok::TokenKind>(Terminal));
61       for (auto A : find(S, TokID)) {
62         if (A.kind() == LRTable::Action::Shift)
63           OS.indent(4) << llvm::formatv("'{0}': shift state {1}\n",
64                                         G.symbolName(TokID), A.getShiftState());
65         else if (A.kind() == LRTable::Action::Reduce)
66           OS.indent(4) << llvm::formatv("'{0}': reduce by rule {1} '{2}'\n",
67                                         G.symbolName(TokID), A.getReduceRule(),
68                                         G.dumpRule(A.getReduceRule()));
69         else if (A.kind() == LRTable::Action::Accept)
70           OS.indent(4) << llvm::formatv("'{0}': accept\n", G.symbolName(TokID));
71       }
72     }
73     for (SymbolID NontermID = 0; NontermID < G.table().Nonterminals.size();
74          ++NontermID) {
75       if (find(S, NontermID).empty())
76         continue;
77       OS.indent(4) << llvm::formatv("'{0}': go to state {1}\n",
78                                     G.symbolName(NontermID),
79                                     getGoToState(S, NontermID));
80     }
81   }
82   return OS.str();
83 }
84 
85 llvm::ArrayRef<LRTable::Action> LRTable::getActions(StateID State,
86                                                     SymbolID Terminal) const {
87   assert(pseudo::isToken(Terminal) && "expect terminal symbol!");
88   return find(State, Terminal);
89 }
90 
91 LRTable::StateID LRTable::getGoToState(StateID State,
92                                        SymbolID Nonterminal) const {
93   assert(pseudo::isNonterminal(Nonterminal) && "expected nonterminal symbol!");
94   auto Result = find(State, Nonterminal);
95   assert(Result.size() == 1 && Result.front().kind() == Action::GoTo);
96   return Result.front().getGoToState();
97 }
98 
99 llvm::ArrayRef<LRTable::Action> LRTable::find(StateID Src, SymbolID ID) const {
100   size_t Idx = isToken(ID) ? static_cast<size_t>(symbolToToken(ID)) : ID;
101   assert(isToken(ID) ? Idx + 1 < TerminalOffset.size()
102                      : Idx + 1 < NontermOffset.size());
103   std::pair<size_t, size_t> TargetStateRange =
104       isToken(ID) ? std::make_pair(TerminalOffset[Idx], TerminalOffset[Idx + 1])
105                   : std::make_pair(NontermOffset[Idx], NontermOffset[Idx + 1]);
106   auto TargetedStates =
107       llvm::makeArrayRef(States.data() + TargetStateRange.first,
108                          States.data() + TargetStateRange.second);
109 
110   assert(llvm::is_sorted(TargetedStates) &&
111          "subrange of the StateIdx should be sorted!");
112   const LRTable::StateID *Start = llvm::partition_point(
113       TargetedStates, [&Src](LRTable::StateID S) { return S < Src; });
114   if (Start == TargetedStates.end())
115     return {};
116   const LRTable::StateID *End = Start;
117   while (End != TargetedStates.end() && *End == Src)
118     ++End;
119   return llvm::makeArrayRef(&Actions[Start - States.data()],
120                             /*length=*/End - Start);
121 }
122 
123 LRTable::StateID LRTable::getStartState(SymbolID Target) const {
124   assert(llvm::is_sorted(StartStates) && "StartStates must be sorted!");
125   auto It = llvm::partition_point(
126       StartStates, [Target](const std::pair<SymbolID, StateID> &X) {
127         return X.first < Target;
128       });
129   assert(It != StartStates.end() && It->first == Target &&
130          "target symbol doesn't have a start state!");
131   return It->second;
132 }
133 
134 } // namespace pseudo
135 } // namespace clang
136