1 //===--- Grammar.cpp - Grammar for clang pseudoparser -----------*- 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/Basic/TokenKinds.h"
11 #include "llvm/ADT/ArrayRef.h"
12 #include "llvm/ADT/STLExtras.h"
13 #include "llvm/ADT/StringRef.h"
14 #include "llvm/Support/FormatVariadic.h"
15 #include "llvm/Support/raw_ostream.h"
16
17 namespace clang {
18 namespace pseudo {
19
Rule(SymbolID Target,llvm::ArrayRef<SymbolID> Sequence)20 Rule::Rule(SymbolID Target, llvm::ArrayRef<SymbolID> Sequence)
21 : Target(Target), Size(static_cast<uint8_t>(Sequence.size())) {
22 assert(Sequence.size() <= Rule::MaxElements);
23 llvm::copy(Sequence, this->Sequence);
24 }
25
Grammar(std::unique_ptr<GrammarTable> Table)26 Grammar::Grammar(std::unique_ptr<GrammarTable> Table) : T(std::move(Table)) {
27 Underscore = *findNonterminal("_");
28 }
29
rulesFor(SymbolID SID) const30 llvm::ArrayRef<Rule> Grammar::rulesFor(SymbolID SID) const {
31 assert(isNonterminal(SID));
32 const auto &R = T->Nonterminals[SID].RuleRange;
33 assert(R.End <= T->Rules.size());
34 return llvm::makeArrayRef(&T->Rules[R.Start], R.End - R.Start);
35 }
36
lookupRule(RuleID RID) const37 const Rule &Grammar::lookupRule(RuleID RID) const {
38 assert(RID < T->Rules.size());
39 return T->Rules[RID];
40 }
41
symbolName(SymbolID SID) const42 llvm::StringRef Grammar::symbolName(SymbolID SID) const {
43 if (isToken(SID))
44 return T->Terminals[symbolToToken(SID)];
45 return T->Nonterminals[SID].Name;
46 }
47
mangleSymbol(SymbolID SID) const48 std::string Grammar::mangleSymbol(SymbolID SID) const {
49 static const char *const TokNames[] = {
50 #define TOK(X) #X,
51 #define KEYWORD(X, Y) #X,
52 #include "clang/Basic/TokenKinds.def"
53 nullptr};
54 if (clang::pseudo::isToken(SID))
55 return TokNames[clang::pseudo::symbolToToken(SID)];
56 std::string Name = symbolName(SID).str();
57 // translation-unit -> translation_unit
58 std::replace(Name.begin(), Name.end(), '-', '_');
59 return Name;
60 }
61
mangleRule(RuleID RID) const62 std::string Grammar::mangleRule(RuleID RID) const {
63 const auto &R = lookupRule(RID);
64 std::string MangleName = mangleSymbol(R.Target);
65 for (size_t I = 0; I < R.seq().size(); ++I)
66 MangleName += llvm::formatv("_{0}{1}", I, mangleSymbol(R.seq()[I]));
67 return MangleName;
68 }
69
findNonterminal(llvm::StringRef Name) const70 llvm::Optional<SymbolID> Grammar::findNonterminal(llvm::StringRef Name) const {
71 auto It = llvm::partition_point(
72 T->Nonterminals,
73 [&](const GrammarTable::Nonterminal &X) { return X.Name < Name; });
74 if (It != T->Nonterminals.end() && It->Name == Name)
75 return It - T->Nonterminals.begin();
76 return llvm::None;
77 }
78
dumpRule(RuleID RID) const79 std::string Grammar::dumpRule(RuleID RID) const {
80 std::string Result;
81 llvm::raw_string_ostream OS(Result);
82 const Rule &R = T->Rules[RID];
83 OS << symbolName(R.Target) << " :=";
84 for (unsigned I = 0; I < R.Size; ++I) {
85 OS << " " << symbolName(R.Sequence[I]);
86 if (R.RecoveryIndex == I)
87 OS << " [recover=" << T->AttributeValues[R.Recovery] << "]";
88 }
89 if (R.Guarded)
90 OS << " [guard]";
91 return Result;
92 }
93
dumpRules(SymbolID SID) const94 std::string Grammar::dumpRules(SymbolID SID) const {
95 assert(isNonterminal(SID));
96 std::string Result;
97 const auto &Range = T->Nonterminals[SID].RuleRange;
98 for (RuleID RID = Range.Start; RID < Range.End; ++RID)
99 Result.append(dumpRule(RID)).push_back('\n');
100 return Result;
101 }
102
dump() const103 std::string Grammar::dump() const {
104 std::string Result;
105 llvm::raw_string_ostream OS(Result);
106 OS << "Nonterminals:\n";
107 for (SymbolID SID = 0; SID < T->Nonterminals.size(); ++SID)
108 OS << llvm::formatv(" {0} {1}\n", SID, symbolName(SID));
109 OS << "Rules:\n";
110 for (RuleID RID = 0; RID < T->Rules.size(); ++RID)
111 OS << llvm::formatv(" {0} {1}\n", RID, dumpRule(RID));
112 return OS.str();
113 }
114
firstSets(const Grammar & G)115 std::vector<llvm::DenseSet<SymbolID>> firstSets(const Grammar &G) {
116 std::vector<llvm::DenseSet<SymbolID>> FirstSets(
117 G.table().Nonterminals.size());
118 auto ExpandFirstSet = [&FirstSets](SymbolID Target, SymbolID First) {
119 assert(isNonterminal(Target));
120 if (isToken(First))
121 return FirstSets[Target].insert(First).second;
122 bool Changed = false;
123 for (SymbolID SID : FirstSets[First])
124 Changed |= FirstSets[Target].insert(SID).second;
125 return Changed;
126 };
127
128 // A rule S := T ... implies elements in FIRST(S):
129 // - if T is a terminal, FIRST(S) contains T
130 // - if T is a nonterminal, FIRST(S) contains FIRST(T)
131 // Since FIRST(T) may not have been fully computed yet, FIRST(S) itself may
132 // end up being incomplete.
133 // We iterate until we hit a fixed point.
134 // (This isn't particularly efficient, but table building isn't on the
135 // critical path).
136 bool Changed = true;
137 while (Changed) {
138 Changed = false;
139 for (const auto &R : G.table().Rules)
140 // We only need to consider the first element because symbols are
141 // non-nullable.
142 Changed |= ExpandFirstSet(R.Target, R.seq().front());
143 }
144 return FirstSets;
145 }
146
followSets(const Grammar & G)147 std::vector<llvm::DenseSet<SymbolID>> followSets(const Grammar &G) {
148 auto FirstSets = firstSets(G);
149 std::vector<llvm::DenseSet<SymbolID>> FollowSets(
150 G.table().Nonterminals.size());
151 // Expand the follow set of a nonterminal symbol Y by adding all from the
152 // given symbol set.
153 auto ExpandFollowSet = [&FollowSets](SymbolID Y,
154 const llvm::DenseSet<SymbolID> &ToAdd) {
155 assert(isNonterminal(Y));
156 bool Changed = false;
157 for (SymbolID F : ToAdd)
158 Changed |= FollowSets[Y].insert(F).second;
159 return Changed;
160 };
161 // Follow sets is computed based on the following 3 rules, the computation
162 // is completed at a fixed point where there is no more new symbols can be
163 // added to any of the follow sets.
164 //
165 // Rule 1: add endmarker to the FOLLOW(S), where S is the start symbol of the
166 // augmented grammar, in our case it is '_'.
167 FollowSets[G.underscore()].insert(tokenSymbol(tok::eof));
168 bool Changed = true;
169 while (Changed) {
170 Changed = false;
171 for (const auto &R : G.table().Rules) {
172 // Rule 2: for a rule X := ... Y Z, we add all symbols from FIRST(Z) to
173 // FOLLOW(Y).
174 for (size_t I = 0; I + 1 < R.seq().size(); ++I) {
175 if (isToken(R.seq()[I]))
176 continue;
177 // We only need to consider the next symbol because symbols are
178 // non-nullable.
179 SymbolID Next = R.seq()[I + 1];
180 if (isToken(Next))
181 // First set for a terminal is itself.
182 Changed |= ExpandFollowSet(R.seq()[I], {Next});
183 else
184 Changed |= ExpandFollowSet(R.seq()[I], FirstSets[Next]);
185 }
186 // Rule 3: for a rule X := ... Z, we add all symbols from FOLLOW(X) to
187 // FOLLOW(Z).
188 SymbolID Z = R.seq().back();
189 if (isNonterminal(Z))
190 Changed |= ExpandFollowSet(Z, FollowSets[R.Target]);
191 }
192 }
193 return FollowSets;
194 }
195
getTerminalNames()196 static llvm::ArrayRef<std::string> getTerminalNames() {
197 static const auto &TerminalNames = []() {
198 auto TerminalNames = new std::string[NumTerminals];
199 #define PUNCTUATOR(Tok, Spelling) TerminalNames[tok::Tok] = Spelling;
200 #define KEYWORD(Keyword, Condition) \
201 TerminalNames[tok::kw_##Keyword] = llvm::StringRef(#Keyword).upper();
202 #define TOK(Tok) TerminalNames[tok::Tok] = llvm::StringRef(#Tok).upper();
203 #include "clang/Basic/TokenKinds.def"
204 return llvm::makeArrayRef(TerminalNames, NumTerminals);
205 }();
206 return TerminalNames;
207 }
GrammarTable()208 GrammarTable::GrammarTable() : Terminals(getTerminalNames()) {}
209
210 } // namespace pseudo
211 } // namespace clang
212