有没有可能，一个文法的最左推导生成的语法树？

xdshting

有没有可能，对一个文法的表达式进行最左推导生成的语法树，和最右推导生成的语法树不一样？

为什么？

谢谢

prolj

看文法，文法严密的话不会。

kns1024wh

看起来很困难，不容易实现

cjaizss

可能的,比如:
s->s + s  (其他省略)
就会导致不一样,因为它并没有隐含加是左结合还是右结合
但
s->s + r
r->a
r->b
...
这样则不会

freearth

这不就是二义性文法的直观定义吗？
这种东西一定是存在的，而且存在固有二义性语言。

原帖由 xdshting 于 2008-12-18 20:38 发表
有没有可能，对一个文法的表达式进行最左推导生成的语法树，和最右推导生成的语法树不一样？

为什么？

谢谢

cjaizss

固有二义性语言（Inherently ambiguous languages）有个挺经典的例子：
{a{n}b{n}c{m}d{m}|n>0,m>0}并{{a{n}b{m}c{m}d{n}|n>0,m>0}
这是两个2类语言的并，所以也是二类语言，属于固有二义，不可消除，
{a{n}b{n}c{n}d{n}|n>0}总会有两个生成

cjaizss

原帖由 cjaizss 于 2008-12-19 22:32 发表
固有二义性语言（Inherently ambiguous languages）有个挺经典的例子：
{a{n}b{n}c{m}d{m}|n>0,m>0}并{{a{n}b{m}c{m}d{n}|n>0,m>0}
这是两个2类语言的并，所以也是二类语言，属于固有二义，不可消除，
{a{n} ...

第一个为：
S->XY
X->ab
X->aXb
Y->cd
Y->cYd
第二个为：
S->Y
Y->aXd
Y->aYd
X->bc
X->bXc
所以为2类语言

cjaizss

固有二义性文法存在，并且不存在一个算法（有限自动机）可以判定任何一个文法的固有二义性