compiler-construction - 使语法明确？

Question

我有以下问题。这个语法是模棱两可的：

stmt -> 如果 expr 则 stmt stmt' | 一个

stmt'-> 否则 stmt | 爱普生

表达式 -> b

我试图修改它，我的结果是：

stmt -> 如果 expr 则 stmt'' | 一个

stmt'' -> stmt | stmt'</p>

stmt' -> B 否则 stmt

表达式 -> b

但这不会生成相同的语言。

有人可以帮我修改模棱两可的语法，使其明确并接受相同的语言吗？

Answer 1

使用给定的语法，字符串有两个最左边的推导，if b then if b then a else a如下所示。

推导1：

if expr then stmt stmt'
if b then stmt stmt'
if b then if expr then stmt stmt' stmt'
if b then if b then stmt stmt' stmt'
if b then if b then a stmt' stmt'
if b then if b then a stmt'
if b then if b then a else stmt
if b then if b then a else a

推导2：

if expr then stmt stmt'
if b then stmt stmt'
if b then if expr then stmt stmt' stmt'
if b then if b then stmt stmt' stmt'
if b then if b then a stmt' stmt'
if b then if b then a else stmt stmt'
if b then if b then a else a stmt'
if b then if b then a else a

解析树在大多数情况下保持不变。但是在推导之后if b then if b then a stmt' stmt'，节点的顺序发生了变化，从而影响了树的结构。因此，给定的语法是模棱两可的。