C++20 grammar

1 files changed, 1933 insertions, 0 deletions

diff --git a/cppbnf.cpp b/cppbnf.cpp
new file mode 100755
index 0000000..5266fa0
--- /dev/null
+++ b/cppbnf.cpp
@@ -0,0 +1,1933 @@
+#include "bnf.h"
+
+#include <algorithm>
+#include <unordered_set>
+#include <unordered_map>
+#include <utility>
+
+#include <boost/algorithm/string/predicate.hpp>
+
+#include <gtest/gtest.h>
+#include <gmock/gmock.h>
+
+using namespace std::string_literals;
+
+namespace {
+
+ // "..." -> {".", ".", "."}
+ std::vector<std::string> vectorize(std::string s) {
+  std::vector<std::string> result;
+  std::for_each(s.begin(), s.end(), [&](const char c) {result.push_back(std::string( 1, c )); });
+  return result;
+ }
+
+ std::unordered_map<std::string, std::unordered_set<std::string>> reverseBNF(const T_BNF& bnf)
+ {
+  std::unordered_map<std::string, std::unordered_set<std::string>> result;
+  for (const auto& [symbol, lists] : bnf) {
+   for (const auto& list : lists) {
+    for (const auto& i : list) {
+     auto it = result.find(i);
+     if (it == result.end())
+      result.emplace(i, std::unordered_set<std::string>{symbol});
+     else
+      it->second.insert(symbol);
+    }
+   }
+  }
+
+  return result;
+ }
+
+ bool isTerminal(const std::string& symbol, const T_BNF& bnf)
+ {
+  return bnf.find(symbol) == bnf.end();
+ }
+
+ size_t numberOfStartSymbols(const T_BNF& bnf)
+ {
+  // exactly 1 start symbol
+  std::vector<std::string> startSymbols;
+
+  auto reverse{ reverseBNF(bnf) };
+
+  for (const auto& [symbol, lists] : bnf) {
+   if (reverse.find(symbol) == reverse.end())
+    startSymbols.push_back(symbol);
+  }
+
+  if (startSymbols.size() > 1) {
+   std::cout << "Start symbols:" << std::endl;
+   for (const auto& i : startSymbols)
+    std::cout << " " << i << std::endl;
+  }
+  return startSymbols.size();
+ }
+
+ bool symbolsValid(const T_BNF& bnf)
+ {
+  for (const auto& [symbol, lists] : bnf) {
+   if (boost::contains(symbol, " ")) {
+    std::cerr << "Warning: Symbol " << symbol << " contains space." << std::endl;
+    return false;
+   }
+
+   for (const auto& list : lists) {
+    for (const auto& i : list) {
+     if (i.size() == 1 && !isTerminal(i, bnf)) {
+      std::cerr << "Warning: Non-Terminal symbol " << i << " in " << symbol << " is too long." << std::endl;
+      return false;
+     }
+
+     if (boost::contains(i, " ")) {
+      std::cerr << "Warning: Symbol " << i << " in " << symbol << " contains space." << std::endl;
+      return false;
+     }
+    }
+   }
+  }
+
+  return true;
+ }
+
+ // returns 1 if exactly one start symbol and
+ // all nodes size > 1, except terminal symbols
+ bool valid(const T_BNF& bnf) {
+  return numberOfStartSymbols(bnf) == 1 && symbolsValid(bnf);
+ }
+
+ bool validLex(const T_BNF& bnf) {
+  // all terminal symbols exactly one character
+
+  for (const auto& [symbol, lists] : bnf) {
+   for (const auto& list : lists) {
+    for (const auto& i : list) {
+     if (i.size() != 1 && isTerminal(i, bnf)) {
+      std::cerr << "Warning: Terminal symbol in " << symbol << " is too long: "s << i << std::endl;
+      return false;
+     }
+    }
+   }
+  }
+
+  return true;
+ }
+
+ const std::string optionalMarker{"OPTIONAL:"};
+
+ std::string optional(const std::string& s)
+ {
+  return optionalMarker + s;
+ }
+
+ std::vector<std::string> all_except(const std::vector<std::string>& blacklist)
+ {
+  std::vector<std::string> result;
+
+  for (char c = 0x20; c <= 0x7e; c++) {
+   std::string s{1, c};
+   if (std::find(blacklist.begin(), blacklist.end(), s) == blacklist.end())
+    result.push_back(s);
+  }
+
+  return result;
+ }
+
+ bool containsOptional(const std::vector<std::string>& list)
+ {
+  return std::any_of(list.begin(), list.end(), [](const std::string& s) {return boost::starts_with(s, optionalMarker); });
+ }
+
+ std::vector<std::vector<std::string>> resolveOptional(const std::vector<std::string>& list)
+ {
+  std::vector<std::vector<std::string>> result{1, list};
+
+  while (std::find_if(result[0].begin(), result[0].end(), [](const std::string& s) {return boost::starts_with(s, optionalMarker); }) != result[0].end())
+  {
+   size_t size = result.size();
+
+   // remove from all entries (all have same OPTIONAL property) the OPTIONAL and append a version without this entry
+   for (size_t i = 0; i < size; i++) {
+    std::vector<std::string> newList = result[i];
+
+    size_t index = std::find_if(result[i].begin(), result[i].end(), [](const std::string& s) {return boost::starts_with(s, optionalMarker); }) - result[i].begin();
+    auto& oldString = result[i][index];
+    oldString = oldString.substr(optionalMarker.size()); // Remove OPTIONAL marker inside old list
+
+    newList.erase(newList.begin() + index); // Add removed version of list
+    result.push_back(newList);
+   }
+  }
+  
+  return result;
+ }
+
+ void resolveOptional(std::vector<std::vector<std::string>>& lists)
+ {
+  for (int i = 0; i < lists.size(); i++) {
+   if (containsOptional(lists[i])) {
+    auto insertList = resolveOptional(lists[i]);
+    // replace element i with new list
+    lists.erase(lists.begin() + i);
+    lists.insert(lists.begin() + i, insertList.begin(), insertList.end());
+   }
+  }
+ }
+
+ T_BNF& normalizeBNF(T_BNF& bnf)
+ {
+  // resolve OPTIONAL symbols
+  for (auto& [symbol, lists] : bnf) {
+   resolveOptional(lists);
+  }
+
+  return bnf;
+ }
+
+ T_BNF& normalizeLexBNF(T_BNF& bnf)
+ {
+  normalizeBNF(bnf);
+
+  // vectorize terminal symbols
+  for (auto& [symbol, lists] : bnf) {
+   for (auto& list : lists) {
+    for (int i = 0; i < list.size(); i++) {
+     if (list[i].size() > 1 && isTerminal(list[i], bnf)) {
+      auto newList = vectorize(list[i]);
+      list.erase(list.begin() + i);
+      list.insert(list.begin() + i, newList.begin(), newList.end());
+     }
+    }
+   }
+  }
+
+  return bnf;
+ }
+
+} // namespace
+
+T_BNF GetCppBNFLex()
+{
+ T_BNF bnf{
+  // [gram.lex]
+
+  {"hex-quad", {{"hexadecimal-digit", "hexadecimal-digit", "hexadecimal-digit", "hexadecimal-digit"}}},
+
+  {"universal-character-name", {
+   {"\\", "u", "hex-quad"},
+   {"\\", "U", "hex-quad", "hex-quad"}
+  }},
+
+  {"preprocessing-token", {
+   {"header-name"},
+   {"import-keyword"},
+   {"identifier"},
+   {"pp-number"},
+   {"character-literal"},
+   {"user-defined-character-literal"},
+   {"string-literal"},
+   {"user-defined-string-literal"},
+   {"preprocessing-op-or-punc"},
+   // + other non-whitespace: TODO
+  }},
+
+  {"token", { // lex -> gram
+   {"identifier"},
+   {"keyword"},
+   {"literal"},
+   {"OPERATOR"}, // conflict with keyword "operator"
+   {"punctuator"},
+  }},
+
+  {"header-name", {
+   {"<", "h-char-sequence", ">"},
+   {"\"", "q-char-sequence", "\""},
+  }},
+
+  {"h-char-sequence", {{"h-char"}, {"h-char-sequence", "h-char"}}},
+  {"h-char", {all_except({"\n", ">"})}},
+  {"q-char-sequence", {{"q-char"}, {"q-char-sequence", "q-char"}}},
+  {"q-char", {all_except({"\n", "\""})}},
+
+  {"pp-number", {
+   {"digit"},
+   {".", "digit"},
+   {"pp-number", "digit"},
+   {"pp-number", "identifier-nondigit"},
+   {"pp-number", "'", "digit"},
+   {"pp-number", "'", "nondigit"},
+   {"pp-number", "e", "sign"},
+   {"pp-number", "E", "sign"},
+   {"pp-number", "p", "sign"},
+   {"pp-number", "P", "sign"},
+   {"pp-number", "."},
+  }},
+
+  {"identifier", {
+   {"identifier-nondigit"},
+   {"identifier", "identifier-nondigit"},
+   {"identifier", "digit"},
+  }},
+
+  {"identifier-nondigit", {
+   {"nondigit"},
+   {"universal-character-name"},
+  }},
+
+  {"nondigit", {
+   {"a"}, {"b"}, {"c"}, {"d"}, {"e"}, {"f"}, {"g"}, {"h"}, {"i"}, {"j"}, {"k"}, {"l"}, {"m"},
+   {"n"}, {"o"}, {"p"}, {"q"}, {"r"}, {"s"}, {"t"}, {"u"}, {"v"}, {"w"}, {"x"}, {"y"}, {"z"},
+   {"A"}, {"B"}, {"C"}, {"D"}, {"E"}, {"F"}, {"G"}, {"H"}, {"I"}, {"J"}, {"K"}, {"L"}, {"M"},
+   {"N"}, {"O"}, {"P"}, {"Q"}, {"R"}, {"S"}, {"T"}, {"U"}, {"V"}, {"W"}, {"X"}, {"Y"}, {"Z"}, {"_"}
+  }},
+
+  {"digit", {{"0"},{"1"},{"2"},{"3"},{"4"},{"5"},{"6"},{"7"},{"8"},{"9"}}},
+
+  {"preprocessing-op-or-punc", {
+   {"{"}, {"}"}, {"["}, {"]"}, {"#"}, {"#", "#"}, {"("}, {")"},
+   {"<:"}, {":>"}, {"<%"}, {"%>"}, {"%:"}, {"%:%:"}, {";"}, {":"}, {"..."},
+   {"new"}, {"delete"}, {"?"}, {"::"}, {"."}, {".*"}, {"->"}, {"->*"}, {"~"},
+   {"!"}, {"+"}, {"-"}, {"*"}, {"/"}, {"%"}, {"^"}, {"&"}, {"|"},
+   {"="}, {"+="}, {"-="}, {"*="}, {"/="}, {"%="}, {"^="}, {"&="}, {"|="},
+   {"=="}, {"!="}, {"<"}, {">"}, {"<="}, {">="}, {"<=>"}, {"&&"}, {"||"},
+   {"<<"}, {">>"}, {"<<="}, {">>="}, {"++"}, {"--"}, {","},
+   {"and"}, {"or"}, {"xor"}, {"not"}, {"bitand"}, {"bitor"}, {"compl"},
+   {"and_eq"}, {"or_eq"}, {"xor_eq"}, {"not_eq"}
+  }},
+
+  {"literal", {
+   {"integer-literal"},
+   {"character-literal"},
+   {"floating-point-literal"},
+   {"string-literal"},
+   {"boolean-literal"},
+   {"pointer-literal"},
+   {"user-defined-literal"},
+  }},
+
+  {"integer-literal", {
+   {"binary-literal", optional("integer-suffix")},
+   {"octal-literal", optional("integer-suffix")},
+   {"decimal-literal", optional("integer-suffix")},
+   {"hexadecimal-literal", optional("integer-suffix")},
+  }},
+
+  { "binary-literal", {
+   {"0b", "binary-digit"},
+   {"0B", "binary-digit"},
+   {"binary-literal", optional("'"), "binary-digit"},
+  }},
+
+  { "octal-literal", {
+   {"0"},
+   {"octal-literal", optional("'"), "octal-digit"}
+  } },
+
+  { "decimal-literal", {
+   {"nonzero-digit"},
+   {"decimal-literal", optional("'"), "digit"},
+  } },
+
+  { "hexadecimal-literal", {
+   {"hexadecimal-prefix", "hexadecimal-digit-sequence"},
+  } },
+
+  { "binary-digit", {{"0"}, {"1"}} },
+
+  { "octal-digit", {{"0"},{"1"},{"2"},{"3"},{"4"},{"5"},{"6"},{"7"}} },
+
+  { "nonzero-digit", {{"1"},{"2"},{"3"},{"4"},{"5"},{"6"},{"7"},{"8"},{"9"}} },
+
+  { "hexadecimal-prefix", {{"0x"}, {"0X"}} },
+
+  { "hexadecimal-digit-sequence", {
+   {"hexadecimal-digit"},
+   {"hexadecimal-digit-sequence", optional("'"), "dexadecimal-digit"},
+  } },
+
+  { "hexadecimal-digit", {
+   {"0"},{"1"},{"2"},{"3"},{"4"},{"5"},{"6"},{"7"},{"8"},{"9"},
+   {"a"},{"b"},{"c"},{"d"},{"e"},{"f"},
+   {"A"},{"B"},{"C"},{"D"},{"E"},{"F"}
+  } },
+
+  { "integer-suffix", {
+   {"unsigned-suffix", optional("long-suffix")},
+   {"unsigned-suffix", optional("long-long-suffix")},
+   {"long-suffix", optional("unsigned-suffix")},
+   {"long-long-suffix", optional("unsigned-suffix")},
+  } },
+
+  { "unsigned-suffix", {{"u"}, {"U"}} },
+
+  { "long-suffix", {{"l"}, {"L"}} },
+
+  { "long-long-suffix", {{"ll"}, {"LL"}} },
+
+  { "character-literal", {{optional("encoding-prefix"), "'", "c-char-sequence", "'"}} },
+
+  { "encoding-prefix", {{"u8"}, {"u"}, {"U"}, {"L"}} },
+
+  { "c-char-sequence", {
+   {"c-char"},
+   {"c-char-sequence", "c-char"},
+  } },
+
+  { "c-char", {
+   all_except({"'", "\\", "\n"}),
+   {"escape-sequence"},
+   {"universal-character-name"},
+  } },
+
+  { "escape-sequence", {
+   {"simple-escape-sequence"},
+   {"octal-escape-sequence"},
+   {"hexadecimal-escape-sequence"},
+  } },
+
+  { "simple-escape-sequence", {{"\\'"},{"\\\""},{"\\?"},{"\\\\"},{"\\a"},{"\\b"},{"\\f"},{"\\n"},{"\\r"},{"\\t"},{"\\v"},} },
+
+  { "octal-escape-sequence", {
+   {"\\", "octal-digit"},
+   {"\\", "octal-digit", "octal-digit"},
+   {"\\", "octal-digit", "octal-digit", "octal-digit"},
+  } },
+
+  { "hexadecimal-escape-sequence", {
+   {"\\x", "hexadecimal-digit"},
+   {"hexadecimal-escape-sequence", "hexadecimal-digit"}
+  } },
+
+  { "floating-point-literal", {
+   {"decimal-floating-point-literal"},
+   {"hexadecimal-floating-point-literal"}
+  } },
+
+  { "decimal-floating-point-literal", {
+   {"fractional-constant", optional("exponent-part"), optional("floating-point-suffix")},
+   {"digit-sequence", "exponent-part", optional("floating-point-suffix")},
+  } },
+
+  { "hexadecimal-floating-point-literal", {
+   {"hexadecimal-prefix", "hexadecimal-fractional-constant", "binary-exponent-part", optional("floating-point-suffix")},
+   {"hexadecimal-prefix", "hexadecimal-digit-sequence", "binary-exponent-part", optional("floating-point-suffix")},
+  } },
+
+  { "fractional-constant", {
+   {optional("digit-sequence"), ".", "digit-sequence"},
+   {"digit-sequence", "."},
+  } },
+
+  { "hexadecimal-fractional-constant", {
+   {optional("hexadecimal-digit-sequence"),".","hexadecimal-digit-sequence"},
+   {"hexadecimal-digit-sequence", "."},
+  } },
+
+  { "exponent-part", {
+   {"e", optional("sign"), "digit-sequence"},
+   {"E", optional("sign"), "digit-sequence"}
+  } },
+
+  { "binary-exponent-part", {
+   {"p", optional("sign"), "digit-sequence"},
+   {"P", optional("sign"), "digit-sequence"}
+  } },
+
+  { "sign", {{"+"}, {"-"}} },
+
+  { "digit-sequence", {
+   {"digit"},
+   {"digit-sequence", optional("'"), "digit"},
+  } },
+
+  { "floating-point-suffix", {{"f"},{"l"},{"F"},{"L"}} },
+
+  { "string-literal", {
+   {optional("encoding-prefix"), "\"" , optional("s-char-sequence"), "\"" },
+   {optional("encoding-prefix"), "R", "raw-string"},
+  } },
+
+  { "s-char-sequence", {
+   {"s-char"},
+   {"s-char-sequence", "s-char"}
+  } },
+
+  { "s-char", {
+   all_except({"\"", "\\", "\n"}),
+   {"escape-sequence"},
+   {"universal-character-name"},
+  } },
+
+  { "raw-string", {
+   {"\"", optional("d-char-sequence"), "(", optional("r-char-sequence"), ")", optional("d-char-sequence"), "\"" },
+  } },
+
+  { "r-char-sequence", {
+   {"r-char"},
+   {"r-char-sequence", "r-char"}
+  } },
+
+  { "r-char", {
+   all_except({")"}), // TODO: actually: non-match from "raw-string" above: ")", optional("d-char-sequence"), "\""
+  } },
+
+  { "d-char-sequence", {
+   {"d-char"},
+   {"d-char-sequence", "d-char"}
+  } },
+
+  { "d-char", {
+   all_except({" ", "(", ")", "\\", "\t", "\v", "\f", "\n"}),
+  } },
+
+  { "boolean-literal", {{"true"}, {"false"}} },
+
+  { "pointer-literal", {{"nullptr"}} },
+
+  { "user-defined-literal", {
+   {"user-defined-integer-literal"},
+   {"user-defined-floating-point-literal"},
+   {"user-defined-string-literal"},
+   {"user-defined-character-literal"},
+  } },
+
+  { "user-defined-integer-literal", {
+   {"decimal-literal", "ud-suffix"},
+   {"octal-literal", "ud-suffix"},
+   {"hexadecimal-literal", "ud-suffix"},
+   {"binary-literal", "ud-suffix"},
+  } },
+
+  { "user-defined-floating-point-literal", {
+   {"fractional-constant", optional("exponent-part"), "ud-suffix"},
+   {"digit-sequence", "exponent-part", "ud-suffix"},
+   {"hexadecimal-prefix", "hexadecimal-fractional-constant", "binary-exponent-part", "ud-suffix"},
+   {"hexadecimal-prefix", "hexadecimal-digit-sequence", "binary-exponent-part", "ud-suffix"},
+  } },
+
+  { "user-defined-string-literal", {
+   {"string-literal", "ud-suffix"},
+  } },
+
+  { "user-defined-character-literal", {
+   {"character-literal", "ud-suffix"},
+  } },
+
+  { "ud-suffix", {{"identifier"}} },
+
+ };
+
+ return normalizeLexBNF(bnf);
+}
+
+T_BNF GetCppBNFGram()
+{
+ T_BNF bnf{
+  // [gram.key]
+
+  {"typedef-name", {{"identifier"}, {"simple-template-id"}}},
+  {"namespace-name", {{"identifier"}, {"namespace-alias"}}},
+  {"namespace-alias", {{"identifier"}}},
+  {"class-name", {{"identifier"}, {"simple-template-id"}}},
+  {"enum-name", {{"identifier"}}},
+  {"template-name", {{"identifier"}}},
+
+  // [gram.basic]
+
+  {"translation-unit", {
+   {optional("top-level-declaration-seq")},
+   {optional("global-module-fragment"), "module-declaration", optional("top-level-declaration-seq"), optional("private-module-fragment")},
+  }},
+ 
+  {"top-level-declaration-seq", {
+   {"top-level-declaration"},
+   {"top-level-declaration-seq", "top-level-declaration"},
+  }},
+ 
+  {"top-level-declaration", {
+   {"module-import-declaration"},
+   {"declaration"},
+  }},
+ 
+  // [gram.expr]
+ 
+  {"primary-expression", {
+   {"literal"},
+   {"this"},
+   {"(", "expression", ")"},
+   {"id-expression"},
+   {"lambda-expression"},
+   {"fold-expression"},
+   {"requires-expression"},
+  }},
+ 
+  {"id-expression", {
+   {"unqualified-id"},
+   {"qualified-id"},
+  }},
+ 
+  {"unqualified-id", {
+   {"identifier"},
+   {"operator-function-id"},
+   {"conversion-function-id"},
+   {"literal-operator-id"},
+   {"~", "type-specified"},
+   {"~", "decltype-specifier"},
+   {"template-id"},
+  }},
+ 
+  {"qualified-id", {{"nested-name-specifier", optional("template"), "unqualified-id"}}},
+ 
+  {"nested-name-specifier", {
+   {"::"},
+   {"type-name", "::"},
+   {"namespace-name", "::"},
+   {"decltype-specifier", "::"},
+   {"nested-name-specifier", "identifier", "::"},
+   {"nested-name-specifier", optional("template"), "simple-template-id", "::"},
+  }},
+ 
+  {"lambda-expression", {
+   {"lambda-introducer", optional("lambda-declarator"), "compound-statement"},
+   {"lambda-introducer", "<", "template-parameter-list", ">", optional("requires-clause"), optional("lambda-declarator"), "compound-statement"},
+  }},
+ 
+  {"lambda-introducer", {{"[", optional("lambda-capture"), "]"}}},
+ 
+  {"lambda-capture", {
+   {"capture-default"},
+   {"capture-list"},
+   {"capture-default", ",", "capture-list"},
+  }},
+ 
+  {"capture-default", {{"&"}, {"="}}},
+ 
+  {"capture-list", {
+   {"capture"},
+   {"capture-list", ",", "capture"}
+  }},
+ 
+  {"capture", {
+   {"simple-capture", optional("...")},
+   {optional("..."), "init-capture"},
+  }},
+ 
+  {"simple-capture", {
+   {"identifier"},
+   {"&", "identifier"},
+   {"this"},
+   {"*", "this"},
+  }},
+ 
+  {"init-capture", {
+   {"identifier", "initializer"},
+   {"&", "identifier", "initializer"},
+  }},
+ 
+  {"fold-expression", {
+   {"(", "cast-expression", "fold-operator", ")"},
+   {"(", "...", "fold-operator", "cast-expression", ")"},
+   {"(", "cast-expression", "fold-operator", "...", "fold-operator", "cast-expression", ")"},
+  }},
+ 
+  {"fold-operator", {
+   {"+"}, {"-"}, {"*"}, {"/"}, {"%"}, {"^"}, {"&"}, {"|"}, {"<<"}, {">>"},
+   {"+="}, {"-="}, {"*="}, {"/="}, {"%="}, {"^="}, {"&="}, {"|="}, {"<<="}, {">>="},
+   {"=="}, {"!="}, {"<"}, {">"}, {"<="}, {">="}, {"&&"}, {"||"}, {","}, {".*"}, {"->*"},
+  }},
+ 
+  {"requires-expression", {
+   {"requires", optional("requirement-parameter-list"), "requirement-body"}
+  }},
+ 
+  {"requirement-parameter-list", {
+   {"(", optional("parameter-declaration-clause"), ")"}
+  }},
+ 
+  {"requirement-body", {
+   {"{", "requirement-seq", "}",}
+  }},
+ 
+  { "requirement-seq", {
+   {"requirement"},
+   {"requirement-seq", "requirement"},
+  }},
+ 
+  { "requirement", {
+   {"simple-requirement"},
+   {"type-requirement"},
+   {"compound-requirement"},
+   {"nested-requirement"},
+  } },
+ 
+  { "simple-requirement", {{"expression", ";"}} },
+ 
+  { "type-requirement", {{"typename", optional("nested-name-specifier"), "type-name", ";"}} },
+ 
+  { "compound-requirement", {{"{", "expression", "}", optional("noexcept"), optional("return-type-requirement"), ";"}} },
+ 
+  { "return-type-requirement", {{"->", "type-constraint"}} },
+ 
+  { "nested-requirement", {{"requires", "constraint-expression", ";"}} },
+ 
+  { "postfix-expression", {
+   {"primary-expression"},
+   {"postfix-expression", "[", "expr-or-braced-init-list", "]"},
+   {"postfix-expression", "(", optional("expression-list"), ")"},
+   {"simple-type-specifier", "(", optional("expression-list"), ")"},
+   {"typename-specifier", "(", optional("expression-list"), ")"},
+   {"simple-type-specifier", "braced-init-list"},
+   {"typename-specifier", "braced-init-list"},
+   {"postfix-expression", ".", optional("template"), "id-expression"},
+   {"postfix-expression", "->", optional("template"), "id-expression"},
+   {"postfix-expression", "++"},
+   {"postfix-expression", "--"},
+   {"dynamic_cast", "<", "type-id", ">", "(", "expression", ")"},
+   {"static-cast", "<", "type-id", ">", "(", "expression", ")"},
+   {"reinterpret-cast", "<", "type-id", ">", "(", "expression", ")"},
+   {"const_cast", "<", "type-id", ">", "(", "expression", ")"},
+   {"typeid", "(", "expression", ")"},
+   {"typeid", "(", "type-id", ")"},
+  } },
+ 
+  { "expression-list", {{"initializer-list"}} },
+ 
+  { "unary-expression", {
+   {"postfix-expression"},
+   {"unary-operator", "cast-expression"},
+   {"++", "cast-expression"},
+   {"--", "cast-expression"},
+   {"await-expression"},
+   {"sizeof", "unary-expression"},
+   {"sizeof", "(", "type-id", ")"},
+   {"sizeof", "...", "(", "identifier", ")"},
+   {"alignof", "(", "type-id", ")"},
+   {"noexcept-expression"},
+   {"new-expression"},
+   {"delete-expression"},
+  } },
+ 
+  { "unary-operator", {{"*"}, {"&"}, {"+"}, {"-"}, {"!"}, {"~"} } },
+ 
+  { "await-expression", {{"co_await", "cast-expression"}} },
+ 
+  { "noexcept-expression", {{"noexcept", "(", "expression", ")"}} },
+ 
+  { "new-expression", {
+   {optional("::"), "new", optional("new-placement"), "new-type-id", optional("new-initializer")},
+   {optional("::"), "new", optional("new-placement"), "(", "type-id", ")", optional("new-initializer")},
+  } },
+ 
+  { "new-placement", {{"(", "expression-list", ")"}} },
+ 
+  { "new-type-id", {{"type-specifier-seq", optional("new-declarator")}} },
+ 
+  { "new-declarator", {
+   {"ptr-operator", optional("new-declarator")},
+   {"noptr-new-declarator"},
+  } },
+ 
+  { "noptr-new-declarator", {
+   {"[", optional("expression"), "]", optional("attribute-specifier-seq")},
+   {"noptr-new-declarator", "[", "constant-expression", "]" , optional("attribute-specifier-seq")},
+  } },
+ 
+  { "new-initializer", {
+   {"(", optional("expression-list"), ")"},
+   {"braced-init-list"},
+  } },
+ 
+  { "delete-expression", {
+   {optional("::"), "delete", "cast-expression"},
+   {optional("::"), "delete", "[", "]", "cast-expression"},
+  } },
+ 
+  { "cast-expression", {
+   {"unary-expression"},
+   {"(", "type-id", ")", "cast-expression"},
+  } },
+ 
+  { "pm-expression", {
+   {"cast-expression"},
+   {"pm-expression", ".*", "cast-expression"},
+   {"pm-expression", "->*", "cast-expression"},
+  } },
+ 
+  { "multiplicative-expression", {
+   {"pm-expression"},
+   {"multiplicative-expression", "*", "pm-expression"},
+   {"multiplicative-expression", "/", "pm-expression"},
+   {"multiplicative-expression", "%", "pm-expression"},
+  } },
+ 
+  { "additive-expression", {
+   {"multiplicative-expression"},
+   {"additive-expression", "+", "multiplicative-expression"},
+   {"additive-expression", "-", "multiplicative-expression"},
+  } },
+ 
+  { "shift-expression", {
+   {"additive-expression"},
+   {"shift-expression", "<<", "additive-expression"},
+   {"shift-expression", ">>", "additive-expression"},
+  } },
+ 
+  { "compare-expression", {
+   {"shift-expression"},
+   {"compare-expression", "<=>", "shift-expression"}
+  } },
+ 
+  { "relational-expression", {
+   {"compare-expression"},
+   {"relational-expression", "<",  "compare-expression"},
+   {"relational-expression", ">",  "compare-expression"},
+   {"relational-expression", "<=", "compare-expression"},
+   {"relational-expression", ">=", "compare-expression"},
+  } },
+ 
+  { "equality-expression", {
+   {"relational-expression"},
+   {"equality-expression", "==", "relational-expression"},
+   {"equality-expression", "!=", "relational-expression"},
+  } },
+ 
+  { "and-expression", {
+   {"equality-expression"},
+   {"and-expression", "&", "equality-expression"},
+  } },
+ 
+  { "exclusive-or-expression", {
+   {"and-expression"},
+   {"exclusive-or-expression", "^", "and-expression"},
+  } },
+ 
+  { "inclusive-or-expression", {
+   {"exclusive-or-expression"},
+   {"inclusive-or-expression", "|", "exclusive-or-expression"},
+  } },
+ 
+  { "logical-and-expression", {
+   {"inclusive-or-expression"},
+   {"logical-and-expression", "&&", "inclusive-or-expression"}
+  } },
+ 
+  { "logical-or-expression", {
+   {"logical-and-expression"},
+   {"logical-or-expression", "||", "logical-and-expression"},
+  } },
+ 
+  { "conditional-expression", {
+   {"logical-or-expression"},
+   {"logical-or-expression", "?", "expression", ":", "assignment-expression"},
+  } },
+ 
+  { "yield-expression", {
+   {"co_yield", "assignment-expression"},
+   {"co_yield", "braced-init-list"}
+  } },
+ 
+  { "throw-expression", {{"throw", optional("assignment-expression")}} },
+ 
+  { "assignment-expression", {
+   {"conditional-expression"},
+   {"yield-expression"},
+   {"throw-expression"},
+   {"logical-or-expression", "assignment-operator", "initializer-clause"},
+  } },
+ 
+  { "assignment-operator", {{"="}, {"*="}, {"/="}, {"%="}, {"+="}, {"-="}, {">>="}, {"<<="}, {"&="}, {"^="}, {"|="}} },
+ 
+  { "expression", {
+   {"assignment-expression"},
+   {"expression", ",", "assignment-expression"},
+  } },
+ 
+  { "constant-expression", {{"conditional-expression"}} },
+ 
+  // [gram.stmt]
+ 
+  { "statement", {
+   {"labeled-statement"},
+   {optional("attribute-specifier-seq"), "expression-statement"},
+   {optional("attribute-specifier-seq"), "compound-statement"},
+   {optional("attribute-specifier-seq"), "selection-statement"},
+   {optional("attribute-specifier-seq"), "iteration-statement"},
+   {optional("attribute-specifier-seq"), "jump-statement"},
+   {"declaration-statement"},
+   {optional("attribute-specifier-seq"), "try-block"},
+  } },
+ 
+  { "init-statement", {
+   {"expression-statement"},
+   {"simple-declaration"},
+  } },
+ 
+  { "condition", {
+   {"expression"},
+   {optional("attribute-specifier-seq"), "decl-specifier-seq", "declarator", "brace-or-equal-initializer"},
+  } },
+ 
+  { "labeled-statement", {
+   {optional("attribute-specifier-seq"), "identifier", ":", "statement"},
+   {optional("attribute-specifier-seq"), "case", "constant-expression", ":", "statement"},
+   {optional("attribute-specifier-seq"), "default", ":", "statement"},
+  } },
+ 
+  { "expression-statement", {
+   {optional("expression"), ";"}
+  } },
+ 
+  { "compound-statement", {
+   {"{", optional("statement-seq"), "}"}
+  } },
+ 
+  { "statement-seq", {
+   {"statement"},
+   {"statement-seq statement"},
+  } },
+ 
+  { "selection-statement", {
+   {"if", optional("constexpr"), "(", optional("init-statement"), "condition", ")", "statement"},
+   {"if", optional("constexpr"), "(", optional("init-statement"), "condition", ")", "statement", "else", "statement"},
+   {"switch", "(", optional("init-statement"), "condition", ")", "statement"},
+  } },
+ 
+  { "iteration-statement", {
+   {"while", "(", "condition", ")", "statement"},
+   {"do", "statement", "while", "(", "expression", ")", ";"},
+   {"for", "(", "init-statement", optional("condition"), ";", optional("expression"), ")", "statement"},
+   {"for", "(", optional("init-statement"), "for-range-declaration", ":", "for-range-initializer", ")", "statement"},
+  } },
+
+  { "for-range-declaration", {
+   {optional("attribute-specifier-seq"), "decl-specifier-seq", "declarator"},
+   {optional("attribute-specifier-seq"), "decl-specifier-seq", optional("ref-qualifier"), "[", "identifier-list", "]"},
+  } },
+
+  { "for-range-initializer", {
+   {"expr-or-braced-init-list"},
+  } },
+
+  { "jump-statement", {
+   {"break", ";"},
+   {"continue", ";"},
+   {"return", optional("expr-or-braced-init-list"), ";"},
+   {"coroutine-return-statement"},
+   {"goto", "identifier", ";"},
+  } },
+
+  { "coroutine-return-statement", {
+   {"co_return", optional("expr-or-braced-init-list"), ";"},
+  } },
+
+  { "declaration-statement", { {"block-declaration"} } },
+
+  // [gram.dcl]
+
+  { "declaration-seq", {
+   {"declaration"},
+   {"declaration-seq declaration"},
+  } },
+
+  {"declaration", {
+   {"block-declaration"},
+   {"nodeclspec-function-declaration"},
+   {"function-definition"},
+   {"template-declaration"},
+   {"deduction-guide"},
+   {"explicit-instantiation"},
+   {"explicit-specialization"},
+   {"export-declaration"},
+   {"linkage-specification"},
+   {"namespace-definition"},
+   {"empty-declaration"},
+   {"attribute-declaration"},
+  }},
+
+  { "block-declaration", {
+   {"simple-declaration"},
+   {"asm-declaration"},
+   {"namespace-alias-definition"},
+   {"using-declaration"},
+   {"using-enum-declaration"},
+   {"using-directive"},
+   {"static_assert-declaration"},
+   {"alias-declaration"},
+   {"opaque-enum-declaration"},
+  } },
+
+  { "nodeclspec-function-declaration", {
+   {optional("attribute-specifier-seq"), "declarator", ";"},
+  } },
+
+  { "alias-declaration", {
+   {"using", "identifier", optional("attribute-specifier-seq"), "=", "defining-type-id", ";"},
+  } },
+
+  { "simple-declaration", {
+   {"decl-specifier-seq", optional("init-declarator-list"), ";"},
+   {"attribute-specifier-seq", "decl-specifier-seq", "init-declarator-list", ";"},
+   {optional("attribute-specifier-seq"), "decl-specifier-seq", optional("ref-qualifier"), "[", "identifier-list", "]", "initializer", ";"},
+  } },
+
+  { "static_assert-declaration", {
+   {"static_assert", "(", "constant-expression", ")", ";"},
+   {"static_assert", "(", "constant-expression", ",", "string-literal", ")", ";"},
+  } },
+
+  { "empty-declaration", {
+   {";"},
+  } },
+
+  { "attribute-declaration", {
+   {"attribute-specifier-seq", ";"},
+  } },
+
+  { "decl-specifier", {
+   {"storage-class-specifier"},
+   {"defining-type-specifier"},
+   {"function-specifier"},
+   {"friend"},
+   {"typedef"},
+   {"constexpr"},
+   {"consteval"},
+   {"constinit"},
+   {"inline"},
+  } },
+
+  { "decl-specifier-seq", {
+   {"decl-specifier", optional("attribute-specifier-seq")},
+   {"decl-specifier", "decl-specifier-seq"},
+  } },
+
+  { "storage-class-specifier", {
+   {"static"},
+   {"thread_local"},
+   {"extern"},
+   {"mutable"},
+  } },
+
+  { "function-specifier", {
+   {"virtual"},
+   {"explicit-specifier"},
+  } },
+
+  { "explicit-specifier", {
+   {"explicit", "(", "constant-expression", ")"},
+   {"explicit"},
+  } },
+
+  { "typedef-name", {
+   {"identifier"},
+   {"simple-template-id"},
+  } },
+
+  { "type-specifier", {
+   {"simple-type-specifier"},
+   {"elaborated-type-specifier"},
+   {"typename-specifier"},
+   {"cv-qualifier"},
+  } },
+
+  { "type-specifier-seq", {
+   {"type-specifier", optional("attribute-specifier-seq")},
+   {"type-specifier", "type-specifier-seq"},
+  } },
+
+  { "defining-type-specifier", {
+   {"type-specifier"},
+   {"class-specifier"},
+   {"enum-specifier"},
+  } },
+
+  { "defining-type-specifier-seq", {
+   {"defining-type-specifier", optional("attribute-specifier-seq")},
+   {"defining-type-specifier", "defining-type-specifier-seq"},
+  } },
+
+  { "simple-type-specifier", {
+   {optional("nested-name-specifier"), "type-name"},
+   {"nested-name-specifier", "template", "simple-template-id"},
+   {"decltype-specifier"},
+   {"placeholder-type-specifier"},
+   {optional("nested-name-specifier"), "template-name"},
+   {"char"},
+   {"char8_t"},
+   {"char16_t"},
+   {"char32_t"},
+   {"wchar_t"},
+   {"bool"},
+   {"short"},
+   {"int"},
+   {"long"},
+   {"signed"},
+   {"unsigned"},
+   {"float"},
+   {"double"},
+   {"void"},
+  } },
+
+  { "type-name", {
+   {"class-name"},
+   {"enum-name"},
+   {"typedef-name"},
+  } },
+
+  { "elaborated-type-specifier", {
+   {"class-key", optional("attribute-specifier-seq"), optional("nested-name-specifier"), "identifier"},
+   {"class-key", "simple-template-id"},
+   {"class-key", "nested-name-specifier", optional("template"), "simple-template-id"},
+   {"elaborated-enum-specifier"},
+  } },
+
+  { "elaborated-enum-specifier", {
+   {"enum", optional("nested-name-specifier"), "identifier"},
+  } },
+
+  { "decltype-specifier", {
+   {"decltype", "(", "expression", ")"},
+  } },
+
+  { "placeholder-type-specifier", {
+   {optional("type-constraint"), "auto"},
+   {optional("type-constraint"), "decltype", "(", "auto", ")"},
+  } },
+
+  { "init-declarator-list", {
+   {"init-declarator"},
+   {"init-declarator-list", ",", "init-declarator"},
+  } },
+
+  { "init-declarator", {
+   {"declarator", optional("initializer")},
+   {"declarator", "requires-clause"},
+  } },
+
+  { "declarator", {
+   {"ptr-declarator"},
+   {"noptr-declarator", "parameters-and-qualifiers", "trailing-return-type"},
+  } },
+
+  { "ptr-declarator", {
+   {"noptr-declarator"},
+   {"ptr-operator", "ptr-declarator"},
+  } },
+
+  { "noptr-declarator", {
+   {"declarator-id", optional("attribute-specifier-seq")},
+   {"noptr-declarator", "parameters-and-qualifiers"},
+   {"noptr-declarator", "[", optional("constant-expression"), "]", optional("attribute-specifier-seq")},
+   {"(", "ptr-declarator", ")"},
+  } },
+
+  { "parameters-and-qualifiers", {
+   {"(", "parameter-declaration-clause", ")", optional("cv-qualifier-seq"),
+    optional("ref-qualifier"), optional("noexcept-specifier"), optional("attribute-specifier-seq")},
+  } },
+
+  { "trailing-return-type", {
+   {"->", "type-id"},
+  } },
+
+  { "ptr-operator", {
+   {"*", optional("attribute-specifier-seq"), optional("cv-qualifier-seq")},
+   {"&", optional("attribute-specifier-seq")},
+   {"&&", optional("attribute-specifier-seq")},
+   {"nested-name-specifier", "*", optional("attribute-specifier-seq"), optional("cv-qualifier-seq")},
+  } },
+
+  { "cv-qualifier-seq", {
+   {"cv-qualifier", optional("cv-qualifier-seq")},
+  } },
+
+  { "cv-qualifier", {
+   {"const"},
+   {"volatile"},
+  } },
+
+  { "ref-qualifier", {
+   {"&"}, {"&&"},
+  } },
+
+  { "declarator-id", {
+   {optional("..."), "id-expression"},
+  } },
+
+  { "type-id", {
+   {"type-specifier-seq", optional("abstract-declarator")},
+  } },
+
+  { "defining-type-id", {
+   {"defining-type-specifier-seq", optional("abstract-declarator")},
+  } },
+
+  { "abstract-declarator", {
+   {"ptr-abstract-declarator"},
+   {optional("noptr-abstract-declarator"), "parameters-and-qualifiers", "trailing-return-type"},
+   {"abstract-pack-declarator"},
+  } },
+
+  { "ptr-abstract-declarator", {
+   {"noptr-abstract-declarator"},
+   {"ptr-operator", optional("ptr-abstract-declarator")},
+  } },
+
+  { "noptr-abstract-declarator", {
+   {optional("noptr-abstract-declarator"), "parameters-and-qualifiers"},
+   {optional("noptr-abstract-declarator"), "[", optional("constant-expression"), "]", optional("attribute-specifier-seq")},
+   {"(", "ptr-abstract-declarator", ")"},
+  } },
+
+  { "abstract-pack-declarator", {
+   {"noptr-abstract-pack-declarator"},
+   {"ptr-operator", "abstract-pack-declarator"},
+  } },
+
+  { "noptr-abstract-pack-declarator", {
+   {"noptr-abstract-pack-declarator", "parameters-and-qualifiers"},
+   {"noptr-abstract-pack-declarator", "[", optional("constant-expression"), "]", optional("attribute-specifier-seq")},
+   {"..."},
+  } },
+
+  { "parameter-declaration-clause", {
+   {optional("parameter-declaration-list"), optional("...")},
+   {"parameter-declaration-list", ",", "..."},
+  } },
+
+  { "parameter-declaration-list", {
+   {"parameter-declaration"},
+   {"parameter-declaration-list", ",", "parameter-declaration"},
+  } },
+
+  { "parameter-declaration", {
+   {optional("attribute-specifier-seq"), "decl-specifier-seq", "declarator"},
+   {optional("attribute-specifier-seq"), "decl-specifier-seq", "declarator", "initializer-clause"},
+   {optional("attribute-specifier-seq"), "decl-specifier-seq", optional("abstract-declarator")},
+   {optional("attribute-specifier-seq"), "decl-specifier-seq", optional("abstract-declarator"), "=", "initializer-clause"},
+  } },
+
+  { "initializer", {
+   {"brace-or-equal-initializer"},
+   {"(", "expression-list", ")"},
+  } },
+
+  { "brace-or-equal-initializer", {
+   {"=", "initializer-clause"},
+   {"braced-init-list"},
+  } },
+
+  { "initializer-clause", {
+   {"assignment-expression"},
+   {"braced-init-list"},
+  } },
+
+  { "braced-init-list", {
+   {"{", "initializer-list", optional(","), "}"},
+   {"{", "designated-initializer-list", optional(","), "}"},
+   {"{", "}"},
+  } },
+
+  { "initializer-list", {
+   {"initializer-clause", optional("...")},
+   {"initializer-list", ",", "initializer-clause", optional("...")},
+  } },
+
+  { "designated-initializer-list", {
+   {"designated-initializer-clause"},
+   {"designated-initializer-list", ",", "designated-initializer-clause"},
+  } },
+
+  { "designated-initializer-clause", {
+   {"designator", "brace-or-equal-initializer"},
+  } },
+
+  { "designator", {
+   {".", "identifier"},
+  } },
+
+  { "expr-or-braced-init-list", {
+   {"expression"},
+   {"braced-init-list"},
+  } },
+
+  { "function-definition", {
+   {optional("attribute-specifier-seq"), optional("decl-specifier-seq"), "declarator", optional("virt-specifier-seq"), "function-body"},
+   {optional("attribute-specifier-seq"), optional("decl-specifier-seq"), "declarator", "requires-clause", "function-body"},
+  } },
+
+  { "function-body", {
+   {optional("ctor-initializer"), "compound-statement"},
+   {"function-try-block"},
+   {"=", "default", ";"},
+   {"=", "delete", ";"},
+  } },
+
+  { "enum-name", {
+   {"identifier"},
+  } },
+
+  { "enum-specifier", {
+   {"enum-head", "{", optional("enumerator-list"), "}"},
+   {"enum-head", "{", "enumerator-list", ",", "}"},
+  } },
+
+  { "enum-head", {
+   {"enum-key", optional("attribute-specifier-seq"), optional("enum-head-name"), optional("enum-base")},
+  } },
+
+  { "enum-head-name", {
+   {optional("nested-name-specifier"), "identifier"},
+  } },
+
+  { "opaque-enum-declaration", {
+   {"enum-key", optional("attribute-specifier-seq"), "enum-head-name", optional("enum-base"), ";"},
+  } },
+
+  { "enum-key", {
+   {"enum"},
+   {"enum", "class"},
+   {"enum", "struct"},
+  } },
+  
+  { "enum-base", {
+   {":", "type-specifier-seq"},
+  } },
+
+  { "enumerator-list", {
+   {"enumerator-definition"},
+   {"enumerator-list", ",", "enumerator-definition"},
+  }},
+
+  { "enumerator-definition", {
+   {"enumerator"},
+   {"enumerator", "=", "constant-expression"},
+  } },
+
+  { "enumerator", {
+   {"identifier", optional("attribute-specifier-seq")},
+  } },
+
+  { "using-enum-declaration", {
+   {"using", "elaborated-enum-specifier", ";"},
+  } },
+
+  { "namespace-name", {
+   {"identifier"},
+   {"namespace-alias"},
+  } },
+
+  { "namespace-definition", {
+   {"named-namespace-definition"},
+   {"unnamed-namespace-definition"},
+   {"nested-namespace-definition"},
+  }},
+
+  { "named-namespace-definition", {
+   {optional("inline"), "namespace", optional("attribute-specifier-seq"), "identifier", "{", "namespace-body", "}"},
+  } },
+
+  { "unnamed-namespace-definition", {
+   {optional("inline"), "namespace", optional("attribute-specifier-seq"), "{", "namespace-body", "}"},
+  } },
+
+  { "nested-namespace-definition", {
+   {"namespace", "enclosing-namespace-specifier", "::", optional("inline"), "identifier", "{", "namespace-body", "}"},
+  } },
+
+  { "enclosing-namespace-specifier", {
+   {"identifier"},
+   {"enclosing-namespace-specifier", "::", optional("inline"), "identifier"},
+  } },
+
+  { "namespace-body", {
+   {optional("declaration-seq")},
+  } },
+
+  { "namespace-alias", {
+   {"identifier"},
+  } },
+
+  { "namespace-alias-definition", {
+   {"namespace", "identifier", "=", "qualified-namespace-specifier", ";"},
+  } },
+
+  { "qualified-namespace-specifier", {
+   {optional("nested-name-specifier"), "namespace-name"},
+  } },
+
+  { "using-directive", {
+   {optional("attribute-specifier-seq"), "using", "namespace", optional("nested-name-specifier"), "namespace-name", ";"},
+  } },
+
+  { "using-declaration", {
+   {"using", "using-declarator-list", ";"},
+  } },
+
+  { "using-declarator-list", {
+   {"using-declarator", optional("...")},
+   {"using-declarator-list", ",", "using-declarator", optional("...")},
+  } },
+
+  { "using-declarator", {
+   {optional("typename"), "nested-name-specifier", "unqualified-id"},
+  } },
+
+  { "asm-declaration", {
+   {optional("attribute-specifier-seq"), "asm", "(", "string-literal", ")", ";"},
+  } },
+
+  { "linkage-specification", {
+   {"extern", "string-literal", "{", optional("declaration-seq"), "}"},
+   {"extern", "string-literal", "declaration"},
+  } },
+
+  { "attribute-specifier-seq", {
+   {optional("attribute-specifier-seq"), "attribute-specifier"},
+  } },
+
+  { "attribute-specifier", {
+   {"[", "[", optional("attribute-using-prefix"), "attribute-list", "]", "]"},
+   {"alignment-specifier"},
+  } },
+
+  { "alignment-specifier", {
+   {"alignas", "(", "type-id", optional("..."), ")"},
+   {"alignas", "(", "constant-expression", optional("..."), ")"},
+  } },
+
+  { "attribute-using-prefix", {
+   {"using", "attribute-namespace", ":"},
+  } },
+
+  { "attribute-list", {
+   {optional("attribute")},
+   {"attribute-list", ",", optional("attribute")},
+   {"attribute", "..."},
+   {"attribute-list", ",", "attribute", "..."},
+  } },
+
+  { "attribute", {
+   {"attribute-token", optional("attribute-argument-clause")},
+  } },
+
+  { "attribute-token", {
+   {"identifier"},
+   {"attribute-scoped-token"},
+  } },
+
+  { "attribute-scoped-token", {
+   {"attribute-namespace", "::", "identifier"},
+  } },
+
+  { "attribute-namespace", {
+   {"identifier"},
+  } },
+
+  { "attribute-argument-clause", {
+   {"(", optional("balanced-token-seq"), ")"},
+  } },
+
+  { "balanced-token-seq", {
+   {"balanced-token"},
+   {"balanced-token-seq", "balanced-token"},
+  } },
+
+  { "balanced-token", {
+   {"(", optional("balanced-token-seq"), ")"},
+   {"[", optional("balanced-token-seq"), "]"},
+   {"{", optional("balanced-token-seq"), "}"},
+   all_except({"(", ")", "[", "]", "{", "}",}),
+  }},
+
+  // [gram.module]
+
+  { "module-declaration", {
+   {optional("export"), "module", "module-name", optional("module-partition"), optional("attribute-specifier-seq"), ";"},
+  } },
+
+  { "module-name", {
+   {optional("module-name-qualifier"), "identifier"},
+  } },
+
+  { "module-partition", {
+   {":", optional("module-name-qualifier"), "identifier"},
+  } },
+
+  { "module-name-qualifier", {
+   {"identifier", "."},
+   {"module-name-qualifier", "identifier", "."},
+  } },
+
+  { "export-declaration", {
+   {"export", "declaration"},
+   {"export", "{", optional("declaration-seq"), "}"},
+  } },
+
+  { "module-import-declaration", {
+   {optional("export"), "import-keyword", "module-name",      optional("attribute-specifier-seq"), ";"},
+   {optional("export"), "import-keyword", "module-partition", optional("attribute-specifier-seq"), ";"},
+   {optional("export"), "import-keyword", "header-name",      optional("attribute-specifier-seq"), ";"},
+  } },
+
+  { "global-module-fragment", {
+   {"module", ";", optional("top-level-declaration-seq")},
+  } },
+
+  { "private-module-fragment", {
+   {"module", ":", "private", ";", optional("top-level-declaration-seq")},
+  } },
+
+  // [gram.class]
+
+  { "class-name", {
+   {"identifier"},
+   {"simple-template-id"},
+  } },
+
+  { "class-specifier", {
+   {"class-head", "{", optional("member-specification"), "}"},
+  } },
+
+  { "class-head", {
+   {"class-key", optional("attribute-specifier-seq"), "class-head-name", optional("class-virt-specifier"), optional("base-clause")},
+   {"class-key", optional("attribute-specifier-seq"), optional("base-clause")},
+  } },
+
+  { "class-head-name", {
+   {optional("nested-name-specifier"), "class-name"},
+  } },
+
+  { "class-virt-specifier", {
+   {"final"},
+  } },
+
+  { "class-key", {
+   {"class"},
+   {"struct"},
+   {"union"},
+  } },
+
+
+  { "member-specification", {
+   {"member-declaration", optional("member-specification")},
+   {"access-specifier", ":", optional("member-specification")},
+  } },
+
+  { "member-declaration", {
+   {optional("attribute-specifier-seq"), optional("decl-specifier-seq"), optional("member-declarator-list"), ";"},
+   {"function-definition"},
+   {"using-declaration"},
+   {"using-enum-declaration"},
+   {"static_assert-declaration"},
+   {"template-declaration"},
+   {"deduction-guide"},
+   {"alias-declaration"},
+   {"opaque-enum-declaration"},
+   {"empty-declaration"},
+  } },
+
+  { "member-declarator-list", {
+   {"member-declarator"},
+   {"member-declarator-list", ",", "member-declarator"},
+  } },
+
+  { "member-declarator", {
+   {"declarator", optional("virt-specifier-seq"), optional("pure-specifier")},
+   {"declarator", "requires-clause"},
+   {"declarator", optional("brace-or-equal-initializer")},
+   {optional("identifier"), optional("attribute-specifier-seq"), ":", "constant-expression", optional("brace-or-equal-initializer")},
+  } },
+
+  { "virt-specifier-seq", {
+   {"virt-specifier"},
+   {"virt-specifier-seq", "virt-specifier"},
+  } },
+
+  { "virt-specifier", {
+   {"override"},
+   {"final"},
+  } },
+
+  { "pure-specifier", {
+   {"=", "0"},
+  } },
+
+  { "conversion-function-id", {
+   {"operator", "conversion-type-id"},
+  } },
+
+  { "conversion-type-id", {
+   {"type-specifier-seq", optional("conversion-declarator")},
+  } },
+
+  { "conversion-declarator", {
+   {"ptr-operator", optional("conversion-declarator")},
+  } },
+
+  { "base-clause", {
+   {":", "base-specfier-list"},
+  } },
+
+  { "base-specfier-list", {
+   {"base-specifier", optional("...")},
+   {"base-specifier-list", ",", "base-specifier", optional("...")},
+  } },
+
+  { "base-specifier", {
+   {optional("attribute-specifier-seq"), "class-or-decltype"},
+   {optional("attribute-specifier-seq"), "virtual", optional("access-specifier"), "class-or-decltype"},
+   {optional("attribute-specifier-seq"), "access-specifier", optional("virtual"), "class-or-decltype"},
+  } },
+
+  { "class-or-decltype", {
+   {optional("nested-name-specifier"), "type-name"},
+   {"nested-name-specifier", "template", "simple-template-id"},
+   {"decltype-specifier"},
+  } },
+
+  { "access-specifier", {
+   {"private"},
+   {"protected"},
+   {"public"},
+  } },
+
+  { "ctor-initializer", {
+   {":", "mem-initializer-list"},
+  } },
+
+  { "mem-initializer-list", {
+   {"mem-initializer", optional("...")},
+   {"mem-initializer-list", ",", "mem-initializer", optional("...")},
+  } },
+
+  { "mem-initializer", {
+   {"mem-initializer-id", "(", optional("expression-list"), ")"},
+   {"mem-initializer-id", "braced-init-list"},
+  } },
+
+  { "mem-initializer-id", {
+   {"class-or-decltype"},
+   {"identifier"},
+  } },
+
+  // [gram.over]
+
+  { "operator-function-id", {
+   {"operator", "OPERATOR"},
+  } },
+
+  { "OPERATOR", {
+   {"new"}, {"delete"}, {"new[]"}, {"delete[]"}, {"co_await()[]"}, {"->"}, {"->*"},
+   {"~"}, {"!"}, {"+"}, {"-"}, {"*"}, {"/"}, {"%"}, {"^"}, {"&"},
+   {"|"}, {"="}, {"+="}, {"-="}, {"*="}, {"/="}, {"%="}, {"^="}, {"&="},
+   {"|="}, {"=="}, {"!="}, {"<"}, {">"}, {"<="}, {">="}, {"<=>"}, {"&&"},
+   {"||"}, {"<<"}, {">>"}, {"<<="}, {">>="}, {"++"}, {"--"}, {","},
+  } },
+
+  { "literal-operator-id", {
+   {"operator", "string-literal", "identifier"},
+   {"operator", "user-defined-string-literal"},
+  } },
+
+  // [gram.temp]
+
+  { "template-declaration", {
+   {"template-head", "declaration"},
+   {"template-head", "concept-definition"},
+  } },
+
+  { "template-head", {
+   {"template", "<", "template-parameter-list", ">", optional("requires-clause")},
+  } },
+
+  { "template-parameter-list", {
+   {"template-parameter"},
+   {"template-parameter-list", ",", "template-parameter"},
+  } },
+
+  { "requires-clause", {
+   {"requires", "constraint-logical-or-expression"},
+  } },
+
+  { "constraint-logical-or-expression", {
+   {"constraint-logical-and-expression"},
+   {"constraint-logical-or-expression", "||", "constraint-logical-and-expression"},
+  } },
+
+  { "constraint-logical-and-expression", {
+   {"primary-expression"},
+   {"constraint-logical-and-expression", "&&", "primary-expression"},
+  } },
+
+  { "template-parameter", {
+   {"type-parameter"},
+   {"parameter-declaration"},
+  } },
+
+  { "type-parameter", {
+   {"type-parameter-key", optional("..."), optional("identifier")},
+   {"type-parameter-key", optional("identifier"), "=", "type-id"},
+   {"type-constraint", optional("...") ,optional("identifier")},
+   {"type-constraint", optional("identifier"), "=", "type-id"},
+   {"template-head type-parameter-key", optional("..."), optional("identifier")},
+   {"template-head type-parameter-key", optional("identifier"), "=", "id-expression"},
+  } },
+
+  { "type-parameter-key", {
+   {"class"},
+   {"typename"},
+  } },
+
+  { "type-constraint", {
+   {optional("nested-name-specifier"), "concept-name"},
+   {optional("nested-name-specifier"), "concept-name", "<", optional("template-argument-list"), ">"},
+  } },
+
+  { "simple-template-id", {
+   {"template-name", "<", optional("template-argument-list"), ">"},
+  } },
+
+  { "template-id", {
+   {"simple-template-id"},
+   {"operator-function-id", "<", optional("template-argument-list"), ">"},
+   {"literal-operator-id" , "<", optional("template-argument-list"), ">"},
+  } },
+
+  { "template-name", {
+   {"identifier"},
+  } },
+
+  { "template-argument-list", {
+   {"template-argument", optional("...")},
+   {"template-argument-list", ",", "template-argument", optional("...")},
+  } },
+
+  { "template-argument", {
+   {"constant-expression"},
+   {"type-id"},
+   {"id-expression"},
+  } },
+
+  { "constraint-expression", {
+   {"logical-or-expression"},
+  } },
+
+  { "deduction-guide", {
+   {optional("explicit-specifier"), "template-name", "(", "parameter-declaration-clause", ")", "->", "simple-template-id", ";"},
+  } },
+
+  { "concept-definition", {
+   {"concept", "concept-name", "=", "constraint-expression", ";"},
+  } },
+
+  { "concept-name", {
+   {"identifier"},
+  } },
+
+  { "typename-specifier", {
+   {"typename", "nested-name-specifier", "identifier"},
+   {"typename", "nested-name-specifier", optional("template"), "simple-template-id"},
+  } },
+
+  { "explicit-instantiation", {
+   {optional("extern"), "template", "declaration"},
+  } },
+
+  { "explicit-specialization", {
+   {"template", "<", ">", "declaration"},
+  } },
+
+  // [gram.except]
+
+  { "try-block", {
+   {"try", "compound-statement", "handler-seq"},
+  } },
+
+  { "function-try-block", {
+   {"try", optional("ctor-initializer"), "compound-statement", "handler-seq"},
+  } },
+
+  { "handler-seq", {
+   {"handler", optional("handler-seq")},
+  } },
+
+  { "handler", {
+   {"catch", "(", "exception-declaration", ")", "compound-statement"},
+  } },
+
+  { "exception-declaration", {
+   {optional("attribute-specifier-seq"), "type-specifier-seq", "declarator"},
+   {optional("attribute-specifier-seq"), "type-specifier-seq", optional("abstract-declarator")},
+   {"..."},
+  } },
+
+  { "noexcept-specifier", {
+   {"noexcept", "(", "constant-expression", ")"},
+   {"noexcept"},
+  } },
+
+  // [gram.cpp]
+
+  { "preprocessing-file", {
+   {optional("group")},
+  } },
+
+  { "group", {
+   {"group-part"},
+   {"group", "group-part"},
+  } },
+
+  { "group-part", {
+   {"control-line"},
+   {"if-section"},
+   {"text-line"},
+   {"#", "conditionally-supported-directive"},
+  } },
+
+  { "control-line", {
+   {"#", "include", "pp-tokens", "new-line"},
+   {optional("export"), "import", "pp-tokens", "new-line"},
+   {"#", "define", "identifier", "replacement-list", "new-line"},
+   {"#", "define", "identifier", "lparen", optional("identifier-list"), ")", "replacement-list", "new-line"},
+   {"#", "define", "identifier", "lparen", "...", ")", "replacement-list", "new-line"},
+   {"#", "define", "identifier", "lparen", "identifier-list", ",", "...", ")", "replacement-list", "new-line"},
+   {"#", "undef",  "identifier", "new-line"},
+   {"#", "line", "pp-tokens", "new-line"},
+   {"#", "error",  optional("pp-tokens"), "new-line"},
+   {"#", "pragma", optional("pp-tokens"), "new-line"},
+   {"#", "new-line"},
+  } },
+
+  { "if-section", {
+   {"if-group", optional("elif-groups"), optional("else-group"), "endif-line"},
+  } },
+
+  { "if-group", {
+   {"#", "if",     "constant-expression", "new-line", optional("group")},
+   {"#", "ifdef",  "identifier", "new-line", optional("group")},
+   {"#", "ifndef", "identifier", "new-line", optional("group")},
+  } },
+
+  { "elif-groups", {
+   {"elif-group"},
+   {"elif-groups", "elif-group"},
+  } },
+
+  { "elif-group", {
+   {"#", "elif", "constant-expression", "new-line", optional("group")},
+  } },
+
+  { "else-group", {
+   {"#", "else", "new-line", optional("group")},
+  } },
+
+  { "endif-line", {
+   {"#", "endif", "new-line"},
+  } },
+
+  { "text-line", {
+   {optional("pp-tokens"), "new-line"},
+  } },
+
+  { "conditionally-supported-directive", {
+   {"pp-tokens", "new-line"},
+  } },
+
+  { "lparen", {
+   {"("}, // TODO: NOT immediately preceded by white-space!
+  } },
+
+  { "identifier-list", {
+   {"identifier"},
+   {"identifier-list", "identifier"},
+  } },
+
+  { "replacement-list", {
+   {optional("pp-tokens")},
+  } },
+
+  { "pp-tokens", {
+   {"preprocessing-token"},
+   {"pp-tokens", "preprocessing-token"},
+  } },
+
+  { "new-line", {
+   {"\n"},
+  } },
+
+  { "defined-macro-expression", {
+   {"defined", "identifier"},
+   {"defined", "(", "identifier", ")"},
+  } },
+
+  { "h-preprocessing-token", {
+   {"preprocessing-token"}, // TODO: except ">"
+  } },
+
+  { "h-pp-tokens", {
+   {"h-preprocessing-token"},
+   {"h-pp-tokens", "h-preprocessing-token"},
+  } },
+
+  { "header-name-tokens", {
+   {"string-literal"},
+   {"<", "h-pp-tokens", ">"},
+  } },
+
+  { "has-include-expression", {
+   {"__has_include", "(", "header-name", ")"},
+   {"__has_include", "(", "header-name-tokens", ")"},
+  } },
+
+  { "has-attribute-expression", {
+   {"__has_cpp_attribute", "(", "pp-tokens", ")"},
+  } },
+
+  { "pp-import", {
+   {optional("export"), "import", "header-name",        optional("pp-tokens"), ";", "new-line"},
+   {optional("export"), "import", "header-name-tokens", optional("pp-tokens"), ";", "new-line"},
+   {optional("export"), "import",                                "pp-tokens",  ";", "new-line"},
+  } },
+
+  { "pp-global-module-fragment", {
+   {"module", ";", "pp-balanced-token-seq", "module"},
+  } },
+
+  { "pp-balanced-token-seq", {
+   {"pp-balanced-token"},
+   {"pp-balanced-token-seq", "pp-balanced-token"},
+  } },
+
+  { "pp-balanced-token", {
+   {"pp-ldelim", optional("pp-balanced-token-seq"), "pp-rdelim"},
+   // TODO: + any preprocessing-token except pp-ldelim and pp-rdelim
+  } },
+
+  { "pp-ldelim", {
+   {"(", "[", "{", "<:", "<%"},
+  } },
+
+  { "pp-rdelim", {
+   {")", "]", "}", ":>", "%>"},
+  } },
+
+  { "va-opt-replacement", {
+   {"__VA_OPT__", "(", optional("pp-tokens"), ")"},
+  } },
+ };
+
+ return normalizeBNF(bnf);
+}
+
+TEST(Lex, Test2) {
+ auto bnf = GetCppBNFLex();
+
+ EXPECT_TRUE(valid(bnf));
+ EXPECT_TRUE(validLex(bnf));
+}
+
+TEST(Gram, Test3) {
+ auto bnf = GetCppBNFGram();
+
+ EXPECT_TRUE(valid(bnf));
+}