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