Regular, Recursive, Restricted Jun 4, 2024

submited by

Style Pass

2024-06-05 04:30:07

It is definitely declarative and obvious. But it is ambiguous — it doesn ’t tell whether * or + binds tighter, and their associativity. You can express those properties directly in the grammar:

But at this point we lose decorativeness. The way my brain parses the above grammar is by pattern matching it as a grammar for infix expressions and folding it back to the initial compressed form, not by reading the grammar rules as written.

This captures precedence mostly declaratively: we first match Sum, and, failing that, match Product. But the clarity of semantics is lost — PEGs are never ambiguous by virtue of always picking the first alternative, so it ’s too easy to introduce an unintended ambiguity.

Let me present a formalism that, I think, ticks both boxes for the toy example and pose a question of whether it generalizes.

As a grammar for strings, it is ambiguous. There are two parse trees for 1 + 2 + 3 — the “correct ” one (1 + 2) + 3, and the alternative: 1 + (2 + 3).