[pseudo] Add first and follow set computation in Grammar.

[hokein]

Summary

These will be used when building parsing table for LR parsers.

Separate from https://reviews.llvm.org/D118196.

[hokein]

update

[sammccall]

clang/include/clang/Tooling/Syntax/Pseudo/Grammar.h

148

AFAICS, firstSets are iterated over in followSets, and followSets are iterated over when building SLR.

Seems like exposing vector<vector<SymbolID>> would be enough. Up to you.
(Or the Epochs<SymbolID> data structure from the prototype - there must be a name for that data structure)

clang/lib/Tooling/Syntax/Pseudo/Grammar.cpp

142

nit: X := ... Y Z

(no confusion that the ... is associated with Y or that YZ is one symbol)

156

X := ... Z

166

Seems more natural to catch this problem in the constructor?
Then we'd stash the SymbolID in a member variable and just return it here.

clang/unittests/Tooling/Syntax/Pseudo/GrammarTest.cpp

25

whoops, I missed these in the previous review, these should really be targetID and sequence as they're functions.

108

nit: ToPairs, plural

[hokein]

address comments.

[hokein]

clang/include/clang/Tooling/Syntax/Pseudo/Grammar.h

148

that's right, vector<vector<...>> is enough, but it adds an extra step in the implementation (we need the set anyway for deduplication, and then convert to a vector), and it introduces some complexity in the followSet computation, we can't use a unified ExpandFollowSet (as the input could be a vector or llvm::Denseset) sigh.

clang/unittests/Tooling/Syntax/Pseudo/GrammarTest.cpp

25

they're public member variables :)

[sammccall]

clang/unittests/Tooling/Syntax/Pseudo/GrammarTest.cpp

25

MATCHER_P(TargetID) produces a template function named TargetID. It should be named targetID per the style rules.

clang/include/clang/Tooling/Syntax/Pseudo/Grammar.h

 //    declaration-seq := declaration
 //    declaration-seq := declaration-seq declaration
 //
 //  A grammar formally describes a language, and it is constructed by a set of
 //  production rules. A rule is of BNF form (AAA := BBB CCC). A symbol is either
 //  non-terminal or terminal, identified by a SymbolID.
 //
 //  Notions about the BNF grammar:
-//  - "_" is the augmented symbol, formed by start symbols.
+//  - "_" is the start symbol of the augmented grammar;
 //  - single-line comment is supported, starting with a #
 //  - A rule describes how a nonterminal (left side of :=) is constructed, and
 //    it is *per line* in the grammar file
 //  - Terminals (also called tokens) correspond to the clang::TokenKind; they
 //    are written in the grammar like "IDENTIFIER", "USING", "+"
 //  - Nonterminals are specified with "lower-case" names in the grammar; they
 //    shouldn't be nullable (has an empty sequence)
 //  - optional symbols are supported (specified with a _opt suffix), and they
 //    will be eliminated during the grammar parsing stage
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLING_SYNTAX_GRAMMAR_H
 #define LLVM_CLANG_TOOLING_SYNTAX_GRAMMAR_H
 
 #include "clang/Basic/TokenKinds.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/StringRef.h"
 #include <cstdint>
 #include <vector>
 
 namespace clang {
 namespace syntax {
 namespace pseudo {
 // A SymbolID uniquely identifies a terminal/non-terminal symbol in a grammar.

 
 struct GrammarTable;
 
 // Grammar that describes a programming language, e.g. C++. It represents the
 // contents of the specified grammar.
 // It is a building block for constructing a table-based parser.
 class Grammar {
 public:
-  explicit Grammar(std::unique_ptr<GrammarTable> T) : T(std::move(T)) {}
+  explicit Grammar(std::unique_ptr<GrammarTable>);
 
   // Parses grammar from a BNF file.
   // Diagnostics emitted during parsing are stored in Diags.
   static std::unique_ptr<Grammar> parseBNF(llvm::StringRef BNF,
                                            std::vector<std::string> &Diags);
 
+  // Returns the SymbolID of the start symbol '_'.
+  SymbolID startSymbol() const { return StartSymbol; };
+
   // Returns all rules of the given non-terminal symbol.
   llvm::ArrayRef<Rule> rulesFor(SymbolID SID) const;
   const Rule &lookupRule(RuleID RID) const;
 
   // Gets symbol (terminal or non-terminal) name.
   // Terminals have names like "," (kw_comma) or "OPERATOR" (kw_operator).
   llvm::StringRef symbolName(SymbolID) const;
 
   // Dumps the whole grammar.
   std::string dump() const;
   // Dumps a particular rule.
   std::string dumpRule(RuleID) const;
   // Dumps all rules of the given nonterminal symbol.
   std::string dumpRules(SymbolID) const;
 
   const GrammarTable &table() const { return *T; }
 
 private:
   std::unique_ptr<GrammarTable> T;
+  // The start symbol '_' of the augmented grammar.
+  SymbolID StartSymbol;
 };
+// For each nonterminal X, computes the set of terminals that begin strings
+// derived from X. (Known as FIRST sets in grammar-based parsers).
+std::vector<llvm::DenseSet<SymbolID>> firstSets(const Grammar &);
+// For each nonterminal X, computes the set of terminals that could immediately
+// follow X. (Known as FOLLOW sets in grammar-based parsers).
+std::vector<llvm::DenseSet<SymbolID>> followSets(const Grammar &);
 
 // Storage for the underlying data of the Grammar.
 // It can be constructed dynamically (from compiling BNF file) or statically
 // (a compiled data-source).
 struct GrammarTable {
   struct Nonterminal {
     std::string Name;
     // Corresponding rules that construct the non-terminal, it is a [start, end)

clang/lib/Tooling/Syntax/Pseudo/Grammar.cpp

 //===--- Grammar.cpp - Grammar for clang pseudo parser  ----------*- C++-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Tooling/Syntax/Pseudo/Grammar.h"
+#include "clang/Basic/TokenKinds.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/raw_ostream.h"
 
 namespace clang {
 namespace syntax {
 namespace pseudo {
 
 Rule::Rule(SymbolID Target, llvm::ArrayRef<SymbolID> Sequence)
     : Target(Target), Size(static_cast<uint8_t>(Sequence.size())) {
   assert(Sequence.size() <= Rule::MaxElements);
   llvm::copy(Sequence, this->Sequence);
 }
 
+Grammar::Grammar(std::unique_ptr<GrammarTable> Table) : T(std::move(Table)) {
+  // start symbol is named _, binary search it.
+  auto It = llvm::partition_point(
+      T->Nonterminals,
+      [](const GrammarTable::Nonterminal &X) { return X.Name < "_"; });
+  assert(It != T->Nonterminals.end() && It->Name == "_" &&
+         "symbol _ must exist in the grammar!");
+  StartSymbol = It - T->Nonterminals.begin();
+}
+
 llvm::ArrayRef<Rule> Grammar::rulesFor(SymbolID SID) const {
   assert(isNonterminal(SID));
   const auto &R = T->Nonterminals[SID].RuleRange;
   assert(R.end <= T->Rules.size());
   return llvm::makeArrayRef(&T->Rules[R.start], R.end - R.start);
 }
 
 const Rule &Grammar::lookupRule(RuleID RID) const {
std::string Grammar::dump() const {
   for (SymbolID SID = 0; SID < T->Nonterminals.size(); ++SID)
     OS << llvm::formatv("  {0} {1}\n", SID, symbolName(SID));
   OS << "Rules:\n";
   for (RuleID RID = 0; RID < T->Rules.size(); ++RID)
     OS << llvm::formatv("  {0} {1}\n", RID, dumpRule(RID));
   return OS.str();
 }
 
+std::vector<llvm::DenseSet<SymbolID>> firstSets(const Grammar &G) {
+  std::vector<llvm::DenseSet<SymbolID>> FirstSets(
+      G.table().Nonterminals.size());
+  auto ExpandFirstSet = [&FirstSets](SymbolID Target, SymbolID First) {
+    assert(isNonterminal(Target));
+    if (isToken(First))
+      return FirstSets[Target].insert(First).second;
+    bool Changed = false;
+    for (SymbolID SID : FirstSets[First])
+      Changed |= FirstSets[Target].insert(SID).second;
+    return Changed;
+  };
+
+  // A rule S := T ... implies elements in FIRST(S):
+  //  - if T is a terminal, FIRST(S) contains T
+  //  - if T is a nonterminal, FIRST(S) contains FIRST(T)
+  // Since FIRST(T) may not have been fully computed yet, FIRST(S) itself may
+  // end up being incomplete.
+  // We iterate until we hit a fixed point.
+  // (This isn't particularly efficient, but table building isn't on the
+  // critical path).
+  bool Changed = true;
+  while (Changed) {
+    Changed = false;
+    for (const auto &R : G.table().Rules)
+      // We only need to consider the first element because symbols are
+      // non-nullable.
+      Changed |= ExpandFirstSet(R.Target, R.seq().front());
+  }
+  return FirstSets;
+}
+
+std::vector<llvm::DenseSet<SymbolID>> followSets(const Grammar &G) {
+  auto FirstSets = firstSets(G);
+  std::vector<llvm::DenseSet<SymbolID>> FollowSets(
+      G.table().Nonterminals.size());
+  // Expand the follow set of a non-terminal symbol Y by adding all from the
+  // given symbol set.
+  auto ExpandFollowSet = [&FollowSets](SymbolID Y,
+                                       const llvm::DenseSet<SymbolID> &ToAdd) {
+    assert(isNonterminal(Y));
+    bool Changed = false;
+    for (SymbolID F : ToAdd)
+      Changed |= FollowSets[Y].insert(F).second;
+    return Changed;
+  };
+  // Follow sets is computed based on the following 3 rules, the computation
+  // is completed at a fixed point where there is no more new symbols can be
+  // added to any of the follow sets.
+  //
+  // Rule 1: add endmarker to the FOLLOW(S), where S is the start symbol.
+  FollowSets[G.startSymbol()].insert(tokenSymbol(tok::eof));
+  bool Changed = true;
+  while (Changed) {
+    Changed = false;
+    for (const auto &R : G.table().Rules) {
+      // Rule 2: for a rule X := ... Y Z, we add all symbols from FIRST(Z) to
+      // FOLLOW(Y).
+      for (size_t i = 0; i + 1 < R.seq().size(); ++i) {
+        if (isToken(R.seq()[i]))
+          continue;
+        // We only need to consider the next symbol because symbols are
+        // non-nullable.
+        SymbolID Next = R.seq()[i + 1];
+        if (isToken(Next))
+          // First set for a terminal is itself.
+          Changed |= ExpandFollowSet(R.seq()[i], {Next});
+        else
+          Changed |= ExpandFollowSet(R.seq()[i], FirstSets[Next]);
+      }
+      // Rule 3: for a rule X := ... Z, we add all symbols from FOLLOW(X) to
+      // FOLLOW(Z).
+      SymbolID Z = R.seq().back();
+      if (isNonterminal(Z))
+        Changed |= ExpandFollowSet(Z, FollowSets[R.Target]);
+    }
+  }
+  return FollowSets;
+}
+
 } // namespace pseudo
 } // namespace syntax
 } // namespace clang

clang/unittests/Tooling/Syntax/Pseudo/GrammarTest.cpp

 namespace clang {
 namespace syntax {
 namespace pseudo {
 namespace {
 
 using testing::AllOf;
 using testing::ElementsAre;
 using testing::IsEmpty;
+using testing::Pair;
 using testing::UnorderedElementsAre;
 
 MATCHER_P(TargetID, SID, "") { return arg.Target == SID; }
 template <typename... T> testing::Matcher<const Rule &> Sequence(T... IDs) {
   return testing::Property(&Rule::seq, ElementsAre(IDs...));
 }
 
 class GrammarTest : public ::testing::Test {
 public:
   void build(llvm::StringRef BNF) {
     Diags.clear();
     G = Grammar::parseBNF(BNF, Diags);
   }
 
-  SymbolID lookup(llvm::StringRef Name) const {
+  SymbolID id(llvm::StringRef Name) const {
     for (unsigned I = 0; I < NumTerminals; ++I)
       if (G->table().Terminals[I] == Name)
         return tokenSymbol(static_cast<tok::TokenKind>(I));
     for (SymbolID ID = 0; ID < G->table().Nonterminals.size(); ++ID)
       if (G->table().Nonterminals[ID].Name == Name)
         return ID;
     ADD_FAILURE() << "No such symbol found: " << Name;
     return 0;
   }
 
 protected:
   std::unique_ptr<Grammar> G;
   std::vector<std::string> Diags;
 };
 
 TEST_F(GrammarTest, Basic) {
-  build("expression := IDENTIFIER + expression # comment");
+  build("_ := IDENTIFIER + _ # comment");
   EXPECT_THAT(Diags, IsEmpty());
 
   auto ExpectedRule =
-      AllOf(TargetID(lookup("expression")),
-            Sequence(lookup("IDENTIFIER"), lookup("+"), lookup("expression")));
-  auto ExpressionID = lookup("expression");
-  EXPECT_EQ(G->symbolName(ExpressionID), "expression");
-  EXPECT_THAT(G->rulesFor(ExpressionID), UnorderedElementsAre(ExpectedRule));
+      AllOf(TargetID(id("_")), Sequence(id("IDENTIFIER"), id("+"), id("_")));
+  EXPECT_EQ(G->symbolName(id("_")), "_");
+  EXPECT_THAT(G->rulesFor(id("_")), UnorderedElementsAre(ExpectedRule));
   const auto &Rule = G->lookupRule(/*RID=*/0);
   EXPECT_THAT(Rule, ExpectedRule);
   EXPECT_THAT(G->symbolName(Rule.seq()[0]), "IDENTIFIER");
   EXPECT_THAT(G->symbolName(Rule.seq()[1]), "+");
-  EXPECT_THAT(G->symbolName(Rule.seq()[2]), "expression");
+  EXPECT_THAT(G->symbolName(Rule.seq()[2]), "_");
 }
 
 TEST_F(GrammarTest, EliminatedOptional) {
   build("_ := CONST_opt INT ;_opt");
   EXPECT_THAT(Diags, IsEmpty());
   EXPECT_THAT(G->table().Rules,
-              UnorderedElementsAre(
-                  Sequence(lookup("INT")),
-                  Sequence(lookup("CONST"), lookup("INT")),
-                  Sequence(lookup("CONST"), lookup("INT"), lookup(";")),
-                  Sequence(lookup("INT"), lookup(";"))));
+              UnorderedElementsAre(Sequence(id("INT")),
+                                   Sequence(id("CONST"), id("INT")),
+                                   Sequence(id("CONST"), id("INT"), id(";")),
+                                   Sequence(id("INT"), id(";"))));
 }
 
 TEST_F(GrammarTest, Diagnostics) {
   build(R"cpp(
     _ := ,_opt
     _ := undefined-sym
     null :=
     _ := IDENFIFIE # a typo of the terminal IDENFITIER
 
     invalid
   )cpp");
 
+  EXPECT_EQ(G->startSymbol(), id("_"));
   EXPECT_THAT(Diags, UnorderedElementsAre(
                          "Rule '_ := ,_opt' has a nullable RHS",
                          "Rule 'null := ' has a nullable RHS",
                          "No rules for nonterminal: undefined-sym",
                          "Failed to parse 'invalid': no separator :=",
                          "Token-like name IDENFIFIE is used as a nonterminal",
                          "No rules for nonterminal: IDENFIFIE"));
 }
 
+TEST_F(GrammarTest, FirstAndFollowSets) {
+  build(
+      R"bnf(
+_ := expr
+expr := expr - term
+expr := term
+term := IDENTIFIER
+term := ( expr )
+)bnf");
+  ASSERT_TRUE(Diags.empty());
+  auto ToPairs = [](std::vector<llvm::DenseSet<SymbolID>> Input) {
+    std::vector<std::pair<SymbolID, llvm::DenseSet<SymbolID>>> Sets;
+    for (SymbolID ID = 0; ID < Input.size(); ++ID)
+      Sets.emplace_back(ID, std::move(Input[ID]));
+    return Sets;
+  };
+
+  EXPECT_THAT(
+      ToPairs(firstSets(*G)),
+      UnorderedElementsAre(
+          Pair(id("_"), UnorderedElementsAre(id("IDENTIFIER"), id("("))),
+          Pair(id("expr"), UnorderedElementsAre(id("IDENTIFIER"), id("("))),
+          Pair(id("term"), UnorderedElementsAre(id("IDENTIFIER"), id("(")))));
+  EXPECT_THAT(
+      ToPairs(followSets(*G)),
+      UnorderedElementsAre(
+          Pair(id("_"), UnorderedElementsAre(id("EOF"))),
+          Pair(id("expr"), UnorderedElementsAre(id("-"), id("EOF"), id(")"))),
+          Pair(id("term"), UnorderedElementsAre(id("-"), id("EOF"), id(")")))));
+
+  build(R"bnf(
+# A simplfied C++ decl-specifier-seq.
+_ := decl-specifier-seq
+decl-specifier-seq := decl-specifier decl-specifier-seq
+decl-specifier-seq := decl-specifier
+decl-specifier := simple-type-specifier
+decl-specifier := INLINE
+simple-type-specifier := INT
+   )bnf");
+  ASSERT_TRUE(Diags.empty());
+  EXPECT_THAT(
+      ToPairs(firstSets(*G)),
+      UnorderedElementsAre(
+          Pair(id("_"), UnorderedElementsAre(id("INLINE"), id("INT"))),
+          Pair(id("decl-specifier-seq"),
+               UnorderedElementsAre(id("INLINE"), id("INT"))),
+          Pair(id("simple-type-specifier"), UnorderedElementsAre(id("INT"))),
+          Pair(id("decl-specifier"),
+               UnorderedElementsAre(id("INLINE"), id("INT")))));
+  EXPECT_THAT(
+      ToPairs(followSets(*G)),
+      UnorderedElementsAre(
+          Pair(id("_"), UnorderedElementsAre(id("EOF"))),
+          Pair(id("decl-specifier-seq"), UnorderedElementsAre(id("EOF"))),
+          Pair(id("decl-specifier"),
+               UnorderedElementsAre(id("INLINE"), id("INT"), id("EOF"))),
+          Pair(id("simple-type-specifier"),
+               UnorderedElementsAre(id("INLINE"), id("INT"), id("EOF")))));
+}
+
 } // namespace
 } // namespace pseudo
 } // namespace syntax
 } // namespace clang