compiler-construction - 从语法中删除左递归

Question

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

Q.1

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

Q.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（小写），一个终结符号。

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

这会让你感动吗？我相信它可以回答您所有未解决的具体问题。