这两个语法是否相等？

Question

我有以下不明确的语法，当然不是 slr1:

E -> E+A+A | E+A-A | E-A+A | E-A-A | T
T -> T+A | T-A | A
A -> A*B | A/B | B
B -> (E) | x

我使用的转换规则是：

E -> E + T  ----->  E -> TE'
                    E' -> +TE' | ε

所以第一个语法转换为：

E -> T E' .
E' -> + A + A E' .
E' -> + A - A E' .
E' -> - A + A E' .
E' -> - A - A E' .
E' -> .
T -> A T' .
T' -> + A T' .
T' -> - A T' .
T' -> .
A -> B A' .
A' -> * B A' .
A' -> / B A' .
A' -> .
B -> ( E ) .
B -> x .

这解决了歧义，但它仍然不是 slr1。转换是正确的。之后，我擦除 T 规则并将它们安装到 E'。所以 slr1 的最终语法如下：

E -> A E' .
E' -> + A + A E' .
E' -> + A - A E' .
E' -> - A + A E' .
E' -> - A - A E' .
E' -> + A .
E' -> - A .
E' -> .
A -> B A' .
A' -> * B A' .
A' -> / B A' .
A' -> .
B -> ( E ) .
B -> x .

现在我有两个问题。

2个最终语法相等??我通过说这两个语法必须接受相同的句子来定义相等性。看起来他们确实如此。
我擦除T规则的事实正确吗？？我的练习要求我将第一个更改为 slr1，而我想出的只是最后一个。提前致谢，对不起我的英语。

Answer 1

我希望你的作业被提供良好反馈的人标记。我愿意相信高等教育在某些地方仍然有效，但显然这是一种幻想。

总之。您最终得到的语法是您提出的问题的有效解决方案，但该解决方案是基于误解和错误，巧合地相互抵消以产生有效结果。

首先，误解：左递归与歧义不同，因此左因式分解和消除左递归并不能消除歧义。特别是，您声称 "This is solving the ambiguity but it continues not being SLR(1)" 是错误的。转换并没有消除歧义；语法仍然不是 SLR(1)，因为它仍然不明确。

E                   E
T E'                T E'
A T' E'             A T' E'
B A' T' E'          B A' T' E'
x A' T' E'          x A' T' E'
x T' E'             x T' E'
x + A T' E'         x E'
x + B A' T' E'      x + A + A E'
x + x A' T' E'      x + B A' + A E'
x + x T' E'         x + x A' + A E'
x + x + A T' E'     x + x + A E'
x + x + B A' T' E'  x + x + B A' E'
x + x + x A' T' E'  x + x + x A' E'
x + x + x T' E'     x + x + x E'
x + x + x E'        x + x + x
x + x + x

错误是删除了T规则。您从

开始

E -> T E' .
T -> A T' .
T' -> + A T' .
T' -> - A T' .
T' -> .

由此，您可以轻松擦除 T，因为它只用在一个地方：

E -> A T' E'.
T' -> + A T' .
T' -> - A T' .
T' -> .

擦除 T' 并不是那么简单，因为它是递归的。而且，无论如何，E' 没有任何使用 T' 的产生式，因此向 E' 添加新的产生式并不是对 T'.[=23= 的机械消除]

但是，您选择添加到 E' 的作品实际上消除了歧义。从这个意义上说，做得很好。但请注意，您可以在没有左递归消除的情况下完成此操作：

E -> E + A + A .
E -> E + A - A .
E -> E - A + A .
E -> E - A - A .
E -> A + A .
E -> A - A .
E -> A .
A -> A * B .
A -> A / B .
A -> B .
B -> ( E ) .
B -> x .

那个语法是明确的，出于同样的原因你的是：+ 和 - 运算符被分解为一系列三元运算，前面可能有一个二元运算（如果加法运算符序列包含奇数个运算符）。但它不是 SLR(1)。实际上，对于任何 k，它都不是 LR(k)，因为在我们知道运算符的数量是偶数还是奇数之前，不可能知道操作序列应该以三元运算还是二元运算开始。

但我们可以通过使加法运算符右结合来解决该问题（实际上，与您的语法相同）：

E -> A + A + E .
E -> A + A - E .
E -> A - A + E .
E -> A - A - E .
# Rest of the grammar is the same

这个文法当然不是LL(1)；它不是左因数。但是原题不需要LL(1)文法，上面就是SLR(1).

但是，这只是对原始歧义语法的一种可能解释，而且很可能不是最自然的解释，因为右结合性通常不是自然解释。除非问题指定了所需的关联性，否则无法知道所需的是什么。

这两个语法是否相等？

Is these 2 grammars equal?

compiler-construction

grammar

parsing

context-free-grammar

lr