I call this "(a=aa)(a=a)" test

[u/hopeless__programmer]

Many years ago while trying to make my own programming language I faced an issue. In short, parsers didn't parse specific inputs as expected, due to some implicit rules.

For instance, let's consider EBNF grammar for a sequence of expressions a=aaaa, where a on the right can repeat arbitrary number of times. This will look something like this:

symbol = "a"
params = symbol params | symbol
Line   = symbol "=" params
lines  = Line lines | Line

I designed it without + and * notation on purpose, to narrow down the root cause to the most basic rules: terminals, and and or expressions, and recursion.

Using this grammar I expect the text a=aaa=a to be parsed as (a=aa)(a=a): as two separate Line. But typically parser generators will not produce parser that can handle such case. Instead, the parser will (typically) fail.

The root cause is of course the nature of such parsers: they don't scan for all possible combinations. Instead, in case of collisions (like in this case a at the end of a=aa and a at the beginning of next a=a) it is expected that user will insert negation or something to "fail" a specific route fast, eliminating the collision.

But doesn't this challenge the whole purpose of grammars as "simple" description of language rules? It might get very difficult to predict all possible such collisions for a large grammar, like for Python or C++. Are there any generators that don't have such limitation and can pass (a=aa)(a=a) test?

[u/EggplantExtra4946]

typically parser generators will not produce parser that can handle such case.

"parser generator" doesn't mean anything. They can implement different algorithms, typically LL parsing algorithms or LR parsing algorithms. Each one will have different limitations and ambiguities. You need to know and understand the parsing algorithm in order to reason about the grammar you specified, to make sure that it is not ambiguous. Basically, you likely didn't think it through. Expressions not separated by anything is often ambiguous, unless the parser is LL and your construct unambiguously starts with a keyword, for example: if EXPR EXPR. Keywords, operators, punctuations, balanced constructs (parentheses, backets, curly braces, etc..) are good ways to make a syntactic construct unambiguous.

The root cause is of course the nature of such parsers: they don't scan for all possible combinations.

Some parsing algorithms do but you wouldn't want to use them for a programming language because they will be hard to reason about, for the implementer but even more so for the users.

But doesn't this challenge the whole purpose of grammars as "simple" description of language rules?

There is nothing wrong with grammars, the issue is the parsing algorithm and the ambiguities that can arise because of it and because of how you designed your syntax.

[u/evincarofautumn]

Typically these choices are made in the interest of efficiency. If you use a fixed-length lookahead, and match greedily without backtracking, your parsing state is simpler, and you can consume input optimistically and fail immediately when no rule applies, except where the user has explicitly indicated where they want some non-default behavior, like try to opt into backtracking in Megaparsec/Parsec, or the nongreedy *? and atomic *+ quantifiers in Perl regex.

There are “Generalized LR” (GLR) parser generators, typically based on Tomita’s algorithm. Bison and Happy both support writing grammars in this mode. If there’s a local ambiguity (here a shift/reduce conflict), the parser just continues along both paths. The result is a parse forest of the derivations that succeeded, which can be none, one, or many, that is, no parse, unambiguous, or an ambiguity, which is either an error or in need of disambiguation by some other rule.

One problem I’ve encountered with this is that tolerating ambiguities earlier in the pipeline can make good error reporting more difficult. Say you have some input that initially looks like it could parse as either of two productions, A or B, and A is what the user intended, but that parser happens to fail first. If you report an error about B because it’s the last possible interpretation to fail, you misidentify what the user wanted, and give a confusing message.

[u/cscottnet → u/evincarofautumn]

Not only that, but you now have introduced the possibility of invisible performance issues in your parser. Depending on the exact input and how you've structured your grammar, your parser can backtrack though an incredible amount of bad parses before finally reaching the right one. You're still getting the right answer, so your test suites won't fail, but your performance has fallen off a cliff.

In my experience these sorts of performance bugs are really annoying, because they largely sneak through modern testing infrastructure and CI pipelines.

I strongly prefer parsers with predictable time guarantees.

[u/evincarofautumn → u/cscottnet]

The nice thing about GLR and general CFG parsing algorithms is that they’re not backtracking. Nested backtracking can be exponential, but Tomita and CYK are cubic, and Valiant is subcubic. For non-pathological grammars & programs it surprisingly doesn’t come up much.

I test for these things by setting perf budgets on heap size and wallclock time. They can be fairly generous, the point is just to catch obviously wrong cases of blowup, like “If this hello-world takes 1 MiB to parse we’re probably doing something terribly wrong”.

[u/cscottnet → u/evincarofautumn]

We've been using a packrat parser for wikitext, and in my experience it is very easy to make it blow up either in space or in time. PEG parsers have explicit backtracking, and IMO it's a bad idea. :)

[u/pthierry]

One solution is called backtracking: Recursive Descent: The Next Iteration

[u/bl4nkSl8]

You have to choose to support either ambiguity and backtracking, or simplicity and early termination.

Typically separators(comma, full stop, semicolon) and surrounding parens/braces/curlies are used to make backtracking unnecessary (as there's a pparser erformance cost to it) but peg / packrat parsers can do pretty well using caching and backtracking to provide good error messages with decent performance.

Choose your poison

My preference is early exit and many small files so that the cache at the file level can stay hot and the parse errors can get fixed without guessing a reasonable fix

[u/hopeless__programmer → u/bl4nkSl8]

Is my example grammar ambiguous? Does a | b notation allows/implies ambiguity? Up to this point I considered a | b strictly ordered: b can be scanned only if a fails. But after reading original paper on PEG I think mb I should use a / b instead.

[u/bl4nkSl8 → u/hopeless__programmer]

Not technically, but you do need context to interpret it. Without that context it becomes ambiguous, which is why backtracking is needed

[u/Significant_Neat6476]

Parser tokenisation for token generation is generally greedy (especially if used with regex like engines) - i.e. your params rule will consume all aaaa in your example and spit it out as single token.