从语法中删除左递归

Question

从以下语法中删除左递归：

问1

S -> SXY | a
X -> xY | xX
Y -> Yy | epsilon

问2

P ->  P H 4 U | p
H -> h
U -> u | u P

我知道删除左递归的规则，但我很困惑。因此，如果有人请发布此语法的答案，那将很有帮助。

---

从评论更新：

我知道这 2 个是左递归语法：

S -> SXY | a
P -> P H 4 U | p 

我知道如何从这些语法中删除左递归，但是其他语法呢？

P -> P ... This is left recursive. 
P -> p ... Is this is also left recursive ?

Answer 1

首先，让我们把术语弄明白：你评论中的四行（我添加到问题中）是语法规则，而不是语法。 每个只处理一个扩展;它们都没有提供从起始符号 S 到终端符号字符串的路径。

左递归规则是指 LHS（非终端符号（大写字母））的扩展可能导致以相同符号开头的较长字符串。 因此，P -> P 不是左递归的，因为该规则毫无意义。 P -> p 不是左递归的，因为它将非终端符号 P 扩展到终端符号 p（小写）。

您是正确的，前两个规则是左递归的。

这会让你动起来吗？ 我相信它回答了你所有悬而未决的具体问题。