I am releasing DParserGen 0.1.0, which is a parser and lexer generator
for D. It supports LALR and GLR parsers.

The examples include grammars for D and C++. The D grammar uses LALR,
but also needs extensions like backtracking. For C++ a GLR parser is
used, so ambiguities result in special parse trees.

For more details see the repository:
https://github.com/tim-dlang/dparsergen

It can be used with dub:
https://code.dlang.org/packages/dparsergen

On Sunday, 7 May 2023 at 15:16:50 UTC, Tim wrote:

Which parts of the D grammar require backtracking?

On Sunday, 7 May 2023 at 18:38:09 UTC, max haughton wrote:

Backtracking is used to resolve some ambiguities in the grammar. The ambiguities could probably also be resolved with other solutions like lookahead.

You can find all nonterminals, which use backtracking, by searching for "@backtrack" in the grammar file: https://github.com/tim-dlang/dparsergen/blob/master/examples/d/grammard.ebnf

One example is distinguishing types and expressions in TypeidExpression, TemplateArgument and other nonterminals. The parser first tries to parse it as a type and then as an expression. The parameter of the template instance "Template!(x*[0][0])" could be a type or an expression. As a type it would be an array of an array of a pointer to "x". As an expression it would be "x" multiplied by "[0][0]", which is 0. The parser will always parse this as a type.

For statements it also first tries to parse a declaration and then an expression, so "x*y;" is always parsed as a declaration. The same ambiguity exists for IfCondition.