下面的"产生式"如何"消除左递归"?谢谢

ddvv

学过的都记不清了~

自动机理论 + 编译原理应该可以搞定吧~

liuzq71

to: cjaizss法师

请邦我回答一下我的#30楼的问题,多谢了!

cjaizss

原帖由 liuzq71 于 2009-2-5 11:38 发表
to:prolj (爱好者)
感谢您的建议,
只是PLC的指令表程序的编译器,我网上找了几个月了,从没看到说到点子上的,收费论文也弄了N多篇,没用,基本东插一段西插一段是抄袭的多,
我是想用编译的方法来识别分析它,做一 ...

这属于递归下降,LR(1)属于自底向上,和递归下降不是同一概念

liuzq71

原帖由 cjaizss 于 2009-2-5 21:28 发表

这属于递归下降,LR(1)属于自底向上,和递归下降不是同一概念

可是,这伪码中并无递归啊?请cjaizss版主再指点一下,好么?3Q

[ 本帖最后由 liuzq71 于 2009-2-6 09:50 编辑 ]

cjaizss

原帖由 liuzq71 于 2009-2-6 09:49 发表

可是,这伪码中并无递归啊?请cjaizss版主再指点一下,好么?3Q

递归与迭代本是一体,不要站在语言层次上看.

fineamy

不是所有的左递归文法都能转化为右递归文法的。
因此LR能处理的文法并不一定能被LL处理。

A -> A  A  b ;
A -> c | d

具体针对这个文法，显然是不能用LL实现的（因此不能用右递归文法表示，所以别指望消除做递归了）。原因是A要计数配对。
所以还是老实用LR分析吧！
YACC就能处理

更正：
对CFG有下列结论成立：
任何CFG都有等价的Chomsky normal form(CNF)和Greibach normal form(GNF).
消除左递归实际上就是求CFG的GNF。
GNF:
A -> c  | d
A -> cB | dB
B -> cb | db | cBb | dBb
B -> cbB | dbB | cBbB | dBbB

[ 本帖最后由 fineamy 于 2009-2-7 12:40 编辑 ]

fineamy

从原始问题出发，看看文法能否改造。

IkeXisa

...

路人...

路过...

wongyeam

原帖由 liuzq71 于 2009-2-2 19:55 发表
全部规则是这样的:
A -> A  A  b ;
A -> c | d

各位大侠，恕我无知，把以上的文法改成下面的文法，是不是算消除左递归了？

A->cA'
A'->AbA'|e

这文法是左递归的吗？

gta

A->cA'|dA'
A'->AbA'|epsilon

其中epsilon表示空串