parsing - 带有 let 和加法的表达式的明确语法

Question

对于带有let和add的表达式语言，什么是等同于以下歧义语法的明确语法？

E ⇒ 让 id = E 在 E

E ⇒ E + E

E ⇒ 数字

应解决歧义，以便：

• 加法是左结合的
• 当出现在右边时，加法的优先级高于 let 表达式
• 当出现在左侧时，加法的优先级低于 let 表达式

使用大括号来显示子表达式的分组，以下说明了应如何解释表达式：

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

考虑表达式

E1 + E2

E1不能有形式，因为必须被解析为. 这个限制是递归的：它也不能有.let ID = E3let ID = E3 + E2let ID = (E3 + E2)E4 + let ID = E3

E2可以有形式，但不能有形式（因为必须解析为）。只能有形式。let ID = E3E3 + E4E1 + E3 + E4(E1 + E3) + E4E1E3 + E4

将这些限制转换为 BNF 很简单（但重复）：

Expr      ⇒ Sum

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

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

为了使模式更清晰，我们可以添加*操作符：

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

可以使用优先声明在野牛（或其他类似的解析器生成器）中实现这一点。但是优先解决方案更难推理，并且可能会混淆到更复杂的语法中。