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/ADT/StringExtras.h"
14 #include "llvm/Support/FormatVariadic.h"
15 #include "llvm/Support/raw_ostream.h"
16 
17 namespace clang {
18 namespace pseudo {
19 
20 std::string LRTable::dumpStatistics() const {
21   return llvm::formatv(R"(
22 Statistics of the LR parsing table:
23     number of states: {0}
24     number of actions: shift={1} goto={2} reduce={3}
25     size of the table (bytes): {4}
26 )",
27                        numStates(), Shifts.size(), Gotos.size(), Reduces.size(),
28                        bytes())
29       .str();
30 }
31 
32 std::string LRTable::dumpForTests(const Grammar &G) const {
33   std::string Result;
34   llvm::raw_string_ostream OS(Result);
35   OS << "LRTable:\n";
36   for (StateID S = 0; S < numStates(); ++S) {
37     OS << llvm::formatv("State {0}\n", S);
38     for (uint16_t Terminal = 0; Terminal < NumTerminals; ++Terminal) {
39       SymbolID TokID = tokenSymbol(static_cast<tok::TokenKind>(Terminal));
40       if (auto SS = getShiftState(S, TokID))
41         OS.indent(4) << llvm::formatv("{0}: shift state {1}\n",
42                                       G.symbolName(TokID), SS);
43     }
44     for (RuleID R : getReduceRules(S)) {
45       SymbolID Target = G.lookupRule(R).Target;
46       std::vector<llvm::StringRef> Terminals;
47       for (unsigned Terminal = 0; Terminal < NumTerminals; ++Terminal) {
48         SymbolID TokID = tokenSymbol(static_cast<tok::TokenKind>(Terminal));
49         if (canFollow(Target, TokID))
50           Terminals.push_back(G.symbolName(TokID));
51       }
52       OS.indent(4) << llvm::formatv("{0}: reduce by rule {1} '{2}'\n",
53                                     llvm::join(Terminals, " "), R,
54                                     G.dumpRule(R));
55     }
56     for (SymbolID NontermID = 0; NontermID < G.table().Nonterminals.size();
57          ++NontermID) {
58       if (auto GS = getGoToState(S, NontermID)) {
59         OS.indent(4) << llvm::formatv("{0}: go to state {1}\n",
60                                       G.symbolName(NontermID), *GS);
61       }
62     }
63   }
64   return OS.str();
65 }
66 
67 LRTable::StateID LRTable::getStartState(SymbolID Target) const {
68   assert(llvm::is_sorted(StartStates) && "StartStates must be sorted!");
69   auto It = llvm::partition_point(
70       StartStates, [Target](const std::pair<SymbolID, StateID> &X) {
71         return X.first < Target;
72       });
73   assert(It != StartStates.end() && It->first == Target &&
74          "target symbol doesn't have a start state!");
75   return It->second;
76 }
77 
78 } // namespace pseudo
79 } // namespace clang
80