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/grammar/LRTable.h"
10 #include "clang-pseudo/grammar/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::Sentinel:
29     llvm_unreachable("unexpected Sentinel action kind!");
30   }
31   llvm_unreachable("unexpected action kind!");
32 }
33 
34 std::string LRTable::dumpStatistics() const {
35   return llvm::formatv(R"(
36 Statistics of the LR parsing table:
37     number of states: {0}
38     number of actions: {1}
39     size of the table (bytes): {2}
40 )",
41                        StateOffset.size() - 1, Actions.size(), bytes())
42       .str();
43 }
44 
45 std::string LRTable::dumpForTests(const Grammar &G) const {
46   std::string Result;
47   llvm::raw_string_ostream OS(Result);
48   OS << "LRTable:\n";
49   for (StateID S = 0; S < StateOffset.size() - 1; ++S) {
50     OS << llvm::formatv("State {0}\n", S);
51     for (uint16_t Terminal = 0; Terminal < NumTerminals; ++Terminal) {
52       SymbolID TokID = tokenSymbol(static_cast<tok::TokenKind>(Terminal));
53       for (auto A : find(S, TokID)) {
54         if (A.kind() == LRTable::Action::Shift)
55           OS.indent(4) << llvm::formatv("'{0}': shift state {1}\n",
56                                         G.symbolName(TokID), A.getShiftState());
57         else if (A.kind() == LRTable::Action::Reduce)
58           OS.indent(4) << llvm::formatv("'{0}': reduce by rule {1} '{2}'\n",
59                                         G.symbolName(TokID), A.getReduceRule(),
60                                         G.dumpRule(A.getReduceRule()));
61       }
62     }
63     for (SymbolID NontermID = 0; NontermID < G.table().Nonterminals.size();
64          ++NontermID) {
65       if (find(S, NontermID).empty())
66         continue;
67       OS.indent(4) << llvm::formatv("'{0}': go to state {1}\n",
68                                     G.symbolName(NontermID),
69                                     getGoToState(S, NontermID));
70     }
71   }
72   return OS.str();
73 }
74 
75 llvm::ArrayRef<LRTable::Action> LRTable::getActions(StateID State,
76                                                     SymbolID Terminal) const {
77   assert(pseudo::isToken(Terminal) && "expect terminal symbol!");
78   return find(State, Terminal);
79 }
80 
81 LRTable::StateID LRTable::getGoToState(StateID State,
82                                        SymbolID Nonterminal) const {
83   assert(pseudo::isNonterminal(Nonterminal) && "expected nonterminal symbol!");
84   auto Result = find(State, Nonterminal);
85   assert(Result.size() == 1 && Result.front().kind() == Action::GoTo);
86   return Result.front().getGoToState();
87 }
88 
89 llvm::ArrayRef<LRTable::Action> LRTable::find(StateID Src, SymbolID ID) const {
90   assert(Src + 1u < StateOffset.size());
91   std::pair<size_t, size_t> Range =
92       std::make_pair(StateOffset[Src], StateOffset[Src + 1]);
93   auto SymbolRange = llvm::makeArrayRef(Symbols.data() + Range.first,
94                                         Symbols.data() + Range.second);
95 
96   assert(llvm::is_sorted(SymbolRange) &&
97          "subrange of the Symbols should be sorted!");
98   const LRTable::StateID *Start =
99       llvm::partition_point(SymbolRange, [&ID](SymbolID S) { return S < ID; });
100   if (Start == SymbolRange.end())
101     return {};
102   const LRTable::StateID *End = Start;
103   while (End != SymbolRange.end() && *End == ID)
104     ++End;
105   return llvm::makeArrayRef(&Actions[Start - Symbols.data()],
106                             /*length=*/End - Start);
107 }
108 
109 LRTable::StateID LRTable::getStartState(SymbolID Target) const {
110   assert(llvm::is_sorted(StartStates) && "StartStates must be sorted!");
111   auto It = llvm::partition_point(
112       StartStates, [Target](const std::pair<SymbolID, StateID> &X) {
113         return X.first < Target;
114       });
115   assert(It != StartStates.end() && It->first == Target &&
116          "target symbol doesn't have a start state!");
117   return It->second;
118 }
119 
120 } // namespace pseudo
121 } // namespace clang
122