1 //===--- GrammarBNF.cpp - build grammar from BNF files  ----------*- 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/DenseSet.h"
12 #include "llvm/ADT/STLExtras.h"
13 #include "llvm/ADT/StringExtras.h"
14 #include "llvm/Support/FormatVariadic.h"
15 #include <memory>
16 #include <utility>
17 
18 namespace clang {
19 namespace pseudo {
20 
21 namespace {
22 static const llvm::StringRef OptSuffix = "_opt";
23 static const llvm::StringRef StartSymbol = "_";
24 
25 // Builds grammar from BNF files.
26 class GrammarBuilder {
27 public:
28   GrammarBuilder(std::vector<std::string> &Diagnostics)
29       : Diagnostics(Diagnostics) {}
30 
31   Grammar build(llvm::StringRef BNF) {
32     auto Specs = eliminateOptional(parse(BNF));
33 
34     assert(llvm::all_of(Specs,
35                         [](const RuleSpec &R) {
36                           if (R.Target.endswith(OptSuffix))
37                             return false;
38                           return llvm::all_of(
39                               R.Sequence, [](const RuleSpec::Element &E) {
40                                 return !E.Symbol.endswith(OptSuffix);
41                               });
42                         }) &&
43            "Optional symbols should be eliminated!");
44 
45     auto T = std::make_unique<GrammarTable>();
46 
47     // Assemble the name->ID and ID->nonterminal name maps.
48     llvm::DenseSet<llvm::StringRef> UniqueNonterminals;
49     llvm::DenseMap<llvm::StringRef, SymbolID> SymbolIds;
50 
51     llvm::DenseSet<llvm::StringRef> UniqueAttributeValues;
52 
53     for (uint16_t I = 0; I < NumTerminals; ++I)
54       SymbolIds.try_emplace(T->Terminals[I], tokenSymbol(tok::TokenKind(I)));
55     auto Consider = [&](llvm::StringRef Name) {
56       if (!SymbolIds.count(Name))
57         UniqueNonterminals.insert(Name);
58     };
59     for (const auto &Spec : Specs) {
60       Consider(Spec.Target);
61       for (const RuleSpec::Element &Elt : Spec.Sequence) {
62         Consider(Elt.Symbol);
63         for (const auto& KV : Elt.Attributes)
64            UniqueAttributeValues.insert(KV.second);
65       }
66     }
67     llvm::for_each(UniqueNonterminals, [&T](llvm::StringRef Name) {
68       T->Nonterminals.emplace_back();
69       T->Nonterminals.back().Name = Name.str();
70     });
71     assert(T->Nonterminals.size() < (1 << (SymbolBits - 1)) &&
72            "Too many nonterminals to fit in SymbolID bits!");
73     llvm::sort(T->Nonterminals, [](const GrammarTable::Nonterminal &L,
74                                    const GrammarTable::Nonterminal &R) {
75       return L.Name < R.Name;
76     });
77     // Add an empty string for the corresponding sentinel unset attribute.
78     T->AttributeValues.push_back("");
79     llvm::for_each(UniqueAttributeValues, [&T](llvm::StringRef Name) {
80       T->AttributeValues.emplace_back();
81       T->AttributeValues.back() = Name.str();
82     });
83     llvm::sort(T->AttributeValues);
84     assert(T->AttributeValues.front() == "");
85 
86     // Build name -> ID maps for nonterminals.
87     for (SymbolID SID = 0; SID < T->Nonterminals.size(); ++SID)
88       SymbolIds.try_emplace(T->Nonterminals[SID].Name, SID);
89 
90     // Convert the rules.
91     T->Rules.reserve(Specs.size());
92     std::vector<SymbolID> Symbols;
93     auto Lookup = [SymbolIds](llvm::StringRef Name) {
94       auto It = SymbolIds.find(Name);
95       assert(It != SymbolIds.end() && "Didn't find the symbol in SymbolIds!");
96       return It->second;
97     };
98     for (const auto &Spec : Specs) {
99       assert(Spec.Sequence.size() <= Rule::MaxElements);
100       Symbols.clear();
101       for (const RuleSpec::Element &Elt : Spec.Sequence)
102         Symbols.push_back(Lookup(Elt.Symbol));
103       T->Rules.push_back(Rule(Lookup(Spec.Target), Symbols));
104       applyAttributes(Spec, *T, T->Rules.back());
105     }
106 
107     assert(T->Rules.size() < (1 << RuleBits) &&
108            "Too many rules to fit in RuleID bits!");
109     const auto &SymbolOrder = getTopologicalOrder(T.get());
110     llvm::stable_sort(
111         T->Rules, [&SymbolOrder](const Rule &Left, const Rule &Right) {
112           // Sorted by the topological order of the nonterminal Target.
113           return SymbolOrder[Left.Target] < SymbolOrder[Right.Target];
114         });
115     for (SymbolID SID = 0; SID < T->Nonterminals.size(); ++SID) {
116       auto StartIt = llvm::partition_point(T->Rules, [&](const Rule &R) {
117         return SymbolOrder[R.Target] < SymbolOrder[SID];
118       });
119       RuleID Start = StartIt - T->Rules.begin();
120       RuleID End = Start;
121       while (End < T->Rules.size() && T->Rules[End].Target == SID)
122         ++End;
123       T->Nonterminals[SID].RuleRange = {Start, End};
124     }
125     Grammar G(std::move(T));
126     diagnoseGrammar(G);
127     return G;
128   }
129 
130   // Gets topological order for nonterminal symbols.
131   //
132   // The topological order is defined as: if a *single* nonterminal A produces
133   // (or transitively) a nonterminal B (that said, there is a production rule
134   // B := A), then A is less than B.
135   //
136   // It returns the sort key for each symbol, the array is indexed by SymbolID.
137   std::vector<unsigned> getTopologicalOrder(GrammarTable *T) {
138     std::vector<std::pair<SymbolID, SymbolID>> Dependencies;
139     for (const auto &Rule : T->Rules) {
140       // if A := B, A depends on B.
141       if (Rule.Size == 1 && pseudo::isNonterminal(Rule.Sequence[0]))
142         Dependencies.push_back({Rule.Target, Rule.Sequence[0]});
143     }
144     llvm::sort(Dependencies);
145     std::vector<SymbolID> Order;
146     // Each nonterminal state flows: NotVisited -> Visiting -> Visited.
147     enum State {
148       NotVisited,
149       Visiting,
150       Visited,
151     };
152     std::vector<State> VisitStates(T->Nonterminals.size(), NotVisited);
153     std::function<void(SymbolID)> DFS = [&](SymbolID SID) -> void {
154       if (VisitStates[SID] == Visited)
155         return;
156       if (VisitStates[SID] == Visiting) {
157         Diagnostics.push_back(
158             llvm::formatv("The grammar contains a cycle involving symbol {0}",
159                           T->Nonterminals[SID].Name));
160         return;
161       }
162       VisitStates[SID] = Visiting;
163       for (auto It = llvm::lower_bound(Dependencies,
164                                        std::pair<SymbolID, SymbolID>{SID, 0});
165            It != Dependencies.end() && It->first == SID; ++It)
166         DFS(It->second);
167       VisitStates[SID] = Visited;
168       Order.push_back(SID);
169     };
170     for (SymbolID ID = 0; ID != T->Nonterminals.size(); ++ID)
171       DFS(ID);
172     std::vector<unsigned> Result(T->Nonterminals.size(), 0);
173     for (size_t I = 0; I < Order.size(); ++I)
174       Result[Order[I]] = I;
175     return Result;
176   }
177 
178 private:
179   // Text representation of a BNF grammar rule.
180   struct RuleSpec {
181     llvm::StringRef Target;
182     struct Element {
183       llvm::StringRef Symbol; // Name of the symbol
184       // Attributes that are associated to the sequence symbol or rule.
185       std::vector<std::pair<llvm::StringRef/*Key*/, llvm::StringRef/*Value*/>>
186           Attributes;
187     };
188     std::vector<Element> Sequence;
189 
190     std::string toString() const {
191       std::vector<llvm::StringRef> Body;
192       for (const auto &E : Sequence)
193         Body.push_back(E.Symbol);
194       return llvm::formatv("{0} := {1}", Target, llvm::join(Body, " "));
195     }
196   };
197 
198   std::vector<RuleSpec> parse(llvm::StringRef Lines) {
199     std::vector<RuleSpec> Specs;
200     for (llvm::StringRef Line : llvm::split(Lines, '\n')) {
201       Line = Line.trim();
202       // Strip anything coming after the '#' (comment).
203       Line = Line.take_while([](char C) { return C != '#'; });
204       if (Line.empty())
205         continue;
206       RuleSpec Rule;
207       if (parseLine(Line, Rule))
208         Specs.push_back(std::move(Rule));
209     }
210     return Specs;
211   }
212 
213   bool parseLine(llvm::StringRef Line, RuleSpec &Out) {
214     auto Parts = Line.split(":=");
215     if (Parts.first == Line) { // no separator in Line
216       Diagnostics.push_back(
217           llvm::formatv("Failed to parse '{0}': no separator :=", Line).str());
218       return false;
219     }
220 
221     Out.Target = Parts.first.trim();
222     Out.Sequence.clear();
223     for (llvm::StringRef Chunk : llvm::split(Parts.second, ' ')) {
224       Chunk = Chunk.trim();
225       if (Chunk.empty())
226         continue; // skip empty
227       if (Chunk.startswith("[") && Chunk.endswith("]")) {
228         if (Out.Sequence.empty())
229           continue;
230 
231         parseAttributes(Chunk, Out.Sequence.back().Attributes);
232         continue;
233       }
234 
235       Out.Sequence.push_back({Chunk, /*Attributes=*/{}});
236     }
237     return true;
238   }
239 
240   bool parseAttributes(
241       llvm::StringRef Content,
242       std::vector<std::pair<llvm::StringRef, llvm::StringRef>> &Out) {
243     assert(Content.startswith("[") && Content.endswith("]"));
244     auto KV = Content.drop_front().drop_back().split('=');
245     Out.push_back({KV.first, KV.second.trim()});
246 
247     return true;
248   }
249   // Apply the parsed extensions (stored in RuleSpec) to the grammar Rule.
250   void applyAttributes(const RuleSpec& Spec, const GrammarTable& T, Rule& R) {
251     auto LookupExtensionID = [&T](llvm::StringRef Name) {
252       const auto It = llvm::partition_point(
253           T.AttributeValues, [&](llvm::StringRef X) { return X < Name; });
254       assert(It != T.AttributeValues.end() && *It == Name &&
255              "Didn't find the attribute in AttrValues!");
256       return It - T.AttributeValues.begin();
257     };
258     for (unsigned I = 0; I < Spec.Sequence.size(); ++I) {
259       for (const auto &KV : Spec.Sequence[I].Attributes) {
260         if (KV.first == "guard") {
261           R.Guard = LookupExtensionID(KV.second);
262         } else if (KV.first == "recover") {
263           R.Recovery = LookupExtensionID(KV.second);
264           R.RecoveryIndex = I;
265         } else {
266           Diagnostics.push_back(
267               llvm::formatv("Unknown attribute '{0}'", KV.first).str());
268         }
269       }
270     }
271   }
272 
273   // Inlines all _opt symbols.
274   // For example, a rule E := id +_opt id, after elimination, we have two
275   // equivalent rules:
276   //   1) E := id + id
277   //   2) E := id id
278   std::vector<RuleSpec> eliminateOptional(llvm::ArrayRef<RuleSpec> Input) {
279     std::vector<RuleSpec> Results;
280     std::vector<RuleSpec::Element> Storage;
281     for (const auto &R : Input) {
282       eliminateOptionalTail(
283           R.Sequence, Storage, [&Results, &Storage, &R, this]() {
284             if (Storage.empty()) {
285               Diagnostics.push_back(
286                   llvm::formatv("Rule '{0}' has a nullable RHS", R.toString()));
287               return;
288             }
289             Results.push_back({R.Target, Storage});
290           });
291       assert(Storage.empty());
292     }
293     return Results;
294   }
295   void eliminateOptionalTail(llvm::ArrayRef<RuleSpec::Element> Elements,
296                              std::vector<RuleSpec::Element> &Result,
297                              llvm::function_ref<void()> CB) {
298     if (Elements.empty())
299       return CB();
300     auto Front = Elements.front();
301     if (!Front.Symbol.endswith(OptSuffix)) {
302       Result.push_back(std::move(Front));
303       eliminateOptionalTail(Elements.drop_front(1), Result, CB);
304       Result.pop_back();
305       return;
306     }
307     // Enumerate two options: skip the opt symbol, or inline the symbol.
308     eliminateOptionalTail(Elements.drop_front(1), Result, CB); // skip
309     Front.Symbol = Front.Symbol.drop_back(OptSuffix.size());   // drop "_opt"
310     Result.push_back(std::move(Front));
311     eliminateOptionalTail(Elements.drop_front(1), Result, CB);
312     Result.pop_back();
313   }
314 
315   // Diagnoses the grammar and emit warnings if any.
316   void diagnoseGrammar(const Grammar &G) {
317     const auto &T = G.table();
318     for (SymbolID SID = 0; SID < T.Nonterminals.size(); ++SID) {
319       auto Range = T.Nonterminals[SID].RuleRange;
320       if (Range.Start == Range.End)
321         Diagnostics.push_back(
322             llvm::formatv("No rules for nonterminal: {0}", G.symbolName(SID)));
323       llvm::StringRef NameRef = T.Nonterminals[SID].Name;
324       if (llvm::all_of(NameRef, llvm::isAlpha) && NameRef.upper() == NameRef) {
325         Diagnostics.push_back(llvm::formatv(
326             "Token-like name {0} is used as a nonterminal", G.symbolName(SID)));
327       }
328     }
329     for (RuleID RID = 0; RID + 1u < T.Rules.size(); ++RID) {
330       if (T.Rules[RID] == T.Rules[RID + 1])
331         Diagnostics.push_back(
332             llvm::formatv("Duplicate rule: `{0}`", G.dumpRule(RID)));
333     }
334     // symbol-id -> used counts
335     std::vector<unsigned> UseCounts(T.Nonterminals.size(), 0);
336     for (const Rule &R : T.Rules)
337       for (SymbolID SID : R.seq())
338         if (isNonterminal(SID))
339           ++UseCounts[SID];
340     for (SymbolID SID = 0; SID < UseCounts.size(); ++SID)
341       if (UseCounts[SID] == 0 && T.Nonterminals[SID].Name != StartSymbol)
342         Diagnostics.push_back(
343             llvm::formatv("Nonterminal never used: {0}", G.symbolName(SID)));
344   }
345   std::vector<std::string> &Diagnostics;
346 };
347 } // namespace
348 
349 Grammar Grammar::parseBNF(llvm::StringRef BNF,
350                           std::vector<std::string> &Diagnostics) {
351   Diagnostics.clear();
352   return GrammarBuilder(Diagnostics).build(BNF);
353 }
354 
355 } // namespace pseudo
356 } // namespace clang
357