编译器:改变模棱两可的语法

Question

我做这个练习有一个小问题。

给定这个语法:

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

a)表示它与字符串

有二义性

b)说明什么语言捕获了语法

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

解决方案:

a) I显示了字符串'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

可以描述为"X的一个实例被相等数量的a s和b s包围"。这里的X是递归的基。

正如您所建立的，目标语言的每个字母的数量相等，或者多一个字母。那么我们可能会问:"X的简单定义是什么?"