gpt4 book ai didi

recursion - 从 CFG 中删除左递归

转载 作者:行者123 更新时间:2023-12-05 01:18:10 24 4
gpt4 key购买 nike

以下文法有左递归:

T -> Tx | TYx | YX | x
X -> xx
Y -> Yy | Yx | y

你如何去除左递归。我阅读了维基百科的解释,但我对 CFG 还很陌生,所以它没有多大意义。任何帮助表示赞赏?一个简单的英文解释会更受欢迎。

最佳答案

在此示例中,您可以关注 Robert C. Moore 的 general algorithm将具有左递归的规则转换为具有右递归的规则:

A -> A a1 | A a2 | ... | b1 | b2 | ...
# converts to
A -> b1 A' | b2 A' | ...
A' -> e | a1 A' | a2 A' | ... # where e = epsilon

在我们的第一个案例中: A=T, a1=x, a2=Yx, b1=y, b2=x ...(类似 Y)
T  -> YXT' | xT'
T' -> e | xT' | YxT'
X -> xx
Y -> yY'
Y' -> e | yY' | xY'

关于recursion - 从 CFG 中删除左递归,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13151021/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com