消除Epsilon生成以消除左递归 [英] Eliminating Epsilon Production for Left Recursion Elimination

问题描述

我遵循的是从语法中消除左递归的算法，它说如果有的话去除ε

Im following the algorithm for left recursion elimination from a grammar.It says remove the epsilon production if there is any

我有以下语法

S-->Aa/b

A-->Ac/Sd/∈

我可以看到去除ε产生后语法变得

I can see after removing the epsilon productions the grammer becomes

  1) S-->Aa/a/b

  2)A-->Ac/Sd/c/d

我很困惑a / b出现在哪里1）和c / d出现在哪里2）
有人可以解释一下吗？

Im confused where the a/b comes in 1) and c/d comes in 2) Can someone explain this?

推荐答案

让我们看看规则 S-> Aa A->∈，然后 S->∈a仅给出 S->。 a ，因此与先前的规则一起，我们得到 S-> Aa | a | b

lets look at the rule S->Aa, if A->∈ then S->∈a giving just S->a, so together with the previous rules we get S->Aa|a|b

现在让我们检查规则 A-> Ac 和 A->∈c A-> c 。

now lets check the rule A->Ac and A->∈c which gives us A->c.

A-&Sd ？我没有看到您通常如何获得 A-> d 。如果这是规则，则此语法接受字符串 da（ S-> Aa& A-> d-> da ），但请尝试使用原始语法构造此字符串-如果您以 S 开头，并且字符串以 a 结尾，这意味着您必须使用 S-> Aa ，但是要拥有 d 使用 A-&Sd ，这迫使我们再有一个 a 或 b ，这意味着我们无法构造此字符串，并且规则 A-> d 不正确。

what about A->Sd? I dont see how you got A->d as a rule. if that is a rule, then the string "da" is accepted by this grammar (S->Aa & A->d --> "da"), but try to construct this string with the original grammar - if you start with S and the string finishes with a, it means you must use S->Aa, but then in order to have a "d" you must use A->Sd, which forces us to have another "a" or "b", meaning we cannot construct this string, and the rule A->d is not correct.

这篇关于消除Epsilon生成以消除左递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！