context-free-grammar - 编译器：改变模棱两可的语法

Question

我对这个练习有一点小问题。

鉴于此语法：

S -> aX | X
X -> aXb | b | eps

a) 表明它与字符串不明确

b）说出什么语言捕捉了语法

c) 更改语法并构建后代解析器

我的解决方案：

a）我用字符串' ab '显示模棱两可：

- S -> aX -> ab
- S -> X -> aXb -> ab

b) 语法捕捉这种语言：

L = {a^n b^n: n >= 0} U {a^n b^m: n=m+1, n,m >= 0} U {a^n b^m: m=n+1, n,m >= 0} 

c）我的问题是更改语法以构建解析器。我尝试了不同的语法，但它们也模棱两可。例如这个：

 - G -> X$
   X -> aX' | b | eps
   X' -> XB | eps 

你能帮我找到练习的正确语法或给我一个输入吗？

Answer 1

如你所知，语言

S -> X | a S b

a可以被描述为“被相同数量的s 和s包围的 X 的一个实例b”。X这是递归的基础。

正如您已经确定的那样，目标语言的每个字母数量相同，或者一个字母中的一个以上。所以我们可能会问，“什么简单的定义X可以产生这种语言？”