Unambiguous grammar for expressions with let and addition

Question

What is an unambiguous grammar equivalent to to the following ambiguous grammar for a language of expressions with let and addition?

E ⇒ let id = E in E

E ⇒ E + E

E ⇒ num

The ambiguity should be solved so that:

• addition is left associative
• addition has higher precedence than let expressions when it appears on the right
• addition has lower precedence than let expressions when it appears on the left

Using braces to show the grouping of sub-expressions, the following illustrates how expressions should be interpreted:

num + num + num => { num + num } + num

let id = num in num + num => let id = num in { num + num }

num + let id = num in num => num + { let id = num in num }

Answer 1

Consider the expression

E1 + E2

E1 cannot have the form let ID = E3 because let ID = E3 + E2 must be parsed as let ID = (E3 + E2). This restriction is recursive: it also cannot have the form E4 + let ID = E3.

E2 can have the form let ID = E3 but it cannot have the form E3 + E4 (because E1 + E3 + E4 must be parsed as (E1 + E3) + E4). Only E1 can have the form E3 + E4.

It's straight-forward (but repetitive) to translate these restrictions to BNF:

Expr      ⇒ Sum

Sum       ⇒ SumNoLet '+' Atom
          | Atom
SumNoLet  ⇒ SumNoLet '+' AtomNoLet
          | AtomNoLet

AtomNoLet ⇒ num
          | id
          | '(' Expr ')'
Atom      ⇒ AtomNoLet
          | 'let' id '=' Expr

To make the pattern clearer, we can add the * operator:

Expr      ⇒ Sum

Sum       ⇒ SumNoLet '+' Prod
          | Prod
SumNoLet  ⇒ SumNoLet '+' ProdNoLet
          | ProdNoLet

Prod      ⇒ ProdNoLet '*' Atom
          | Atom
ProdNoLet ⇒ ProdNoLet '*' AtomNoLet
          | AtomNoLet

AtomNoLet ⇒ num
          | id
          | '(' Expr ')'
Atom      ⇒ AtomNoLet
          | 'let' id '=' Expr

It is possible to implement this in bison (or other similar parser generators) using precedence declarations. But the precedence solution is harder to reason about, and can be confusing to incorporate into more complicated grammars.