#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 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 BNF& bnf)
 {
  return bnf.find(symbol) == bnf.end();
 }

 size_t numberOfStartSymbols(const 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 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 (!isTerminal(i, bnf)) {
      // every non-terminal symbol must be longer that 1 char
      if (i.size() == 1) {
       std::cerr << "Warning: Non-Terminal symbol " << i << " in " << symbol << " is too short." << std::endl;
       return false;
      }

      // non-terminal symbols must not contain space
      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 BNF& bnf) {
  return numberOfStartSymbols(bnf) == 1 && symbolsValid(bnf);
 }

 bool validLex(const 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());
   }
  }
 }

 BNF& normalizeBNF(BNF& bnf)
 {
  // resolve OPTIONAL symbols
  for (auto& [symbol, lists] : bnf) {
   resolveOptional(lists);
  }

  return bnf;
 }

 BNF& normalizeLexBNF(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

BNF GetCppBNFLex()
{
 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);
}

BNF GetCppBNFGram()
{
 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(CppBnf, LexicalBnf) {
 auto bnf = SubBNF(GetCppBNFLex(), "preprocessing-token");

 EXPECT_TRUE(valid(bnf));
 EXPECT_TRUE(validLex(bnf));
}

TEST(CppBnf, GrammarBnf) {
 auto bnf = SubBNF(GetCppBNFGram(), "translation-unit");

 EXPECT_TRUE(valid(bnf));
}