免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12345
最近访问板块 发新帖
楼主: liuzq71

下面的"产生式"如何"消除左递归"?谢谢 [复制链接]

论坛徽章:
0
发表于 2009-04-30 10:36 |显示全部楼层
原帖由 liuzq71 于 2009-2-5 08:01 发表
(其中大写的是终结符,小写的是非终结符),

i -> i  i  ANB ;
i -> i  i  ORB ;
i -> i  vi ;
i -> LD  ID  |  LDI  ID ;
vi -> OR ID | ORI ID | vo ;
vo -> AND  ID | ANI  ID ;

这些产生式是否 ...



这个文法对于LR分析器倒是没问题,但是这个文法有问题。
我先简化一下我对这个的理解吧:

i -> i  i  ANB ;
i -> i  i  ORB ;
i -> i  s | s ;
s -> LD  ID  |  LDI  ID | OR ID | ORI ID | AND ID | ANI ID;


如果我没理解错误的话就是i是1 ->n个指令序列,产生式i同时还需要识别两个i后是否跟随一个后缀ANB 或者ORB,这里的问题是,你后续的所有产生式都会一个一个的规约成一个s的序列(这里你就算用top-down方式分析同样会遇到相同的问题,不论你怎么消除左递归都会遇到当识别出最顶层的i的时候,后续应该和i并列的下一个块i成为了i的子节点)

例如: 1.jpg

如果如你23楼的图示,那么指令ANB和ORB所针对的就不是两个单一的指令序列,而是两个指令块,所以除非你能定义什么才构成一个指令块,你所说的文法才能够写出来。比如说如你所说,可以确定以LD或LDI开头,跟随
0->n个非LD|LDI|ANB|ORB的指令,最后每个操纵双指令块的指令都以ANB和ORB结尾,例如:
block -> LD  ID  ops |  LDI  ID ops | block block sfx;
sfx -> ANB | ORB;
ops -> ops op | .; /*注意,我的分析器中默认.为epsilon,所以这里代表epsilon*/
op -> OR ID | ORI ID | AND  ID | ANI  ID;

这样,在输入为:
LD x0
AND x1

LD x2
OR x3
AND x4

ANB


LD x5
OR x6

LD x7
AND x8
AND x9

ORB

ANB
上,生成的分析树为:

2.jpg


但是看你的问题来说之所识别的代码又仅仅是顺序执行的去操纵寄存器或者stack等等,这里是不是有必要识别成递归嵌套的结构还是个问题,而且我不认为你的需求仅仅如你所说的识别ld ldi开头,针对双语句块的指令anb orb结尾生成新指令块的这么一种语言,而且我认为有些错误未必需要在语法识别阶段去分析出来,所以你最好把详细的语法规范贴出来。

[ 本帖最后由 Solidus 于 2009-4-30 10:53 编辑 ]

论坛徽章:
0
发表于 2009-04-30 11:04 |显示全部楼层
恩,不好意思,看错了,

i -> i  i  ANB ;
i -> i  i  ORB ;
i -> i  vi ;
i -> LD  ID  |  LDI  ID ;
vi -> OR ID | ORI ID | AND  ID | ANI  ID;

你那个用LR(不论是SLR(1),LR(1),LALR(1))没问题的可以识别出来,没问题的,我上面那个帖子没看仔细:

3.jpg


这个文法消除左递归和左因子后应该是这样的:
i -> LD ID i1 |  LDI ID i1;
i1 -> i  i2 i1| vi i1 | .;/*.==epsilon*/
i2 -> ANB | ORB;
vi -> OR ID | ORI ID | AND  ID | ANI  ID;

其first:
<i1>  : LDI  AND  ORI  OR  ANI  %EPSILON  LD  
<i2>  : ORB  ANB  
<i>  : LDI  LD  
<vi>  : AND  ORI  ANI  OR  
ID  : ID  
LD  : LD  
OR  : OR  
error  : error  
AND  : AND  
ORI  : ORI  
ANB  : ANB  
LDI  : LDI  
ORB  : ORB  
ANI  : ANI  
<%Start>  : LDI  LD  

下面是follow:
---------------------------------------------------------------------
<i1>  : ORB  %EOI  ANB  
<i2>  : LDI  AND  ORB  ORI  ANI  OR  LD  %EOI  ANB  
<i>  : ORB  %EOI  ANB  
<vi>  : LDI  AND  ORB  ORI  ANI  OR  LD  %EOI  ANB  
<%Start>  : %EOI  

---------------------------------------------------------------------


下面是这个文法的生成的具体语法树:
4.jpg

[ 本帖最后由 Solidus 于 2009-4-30 12:06 编辑 ]

论坛徽章:
0
发表于 2009-05-05 22:11 |显示全部楼层

回复 #42 Solidus 的帖子

请问楼主,你这是个什么工具,看起来很不错,google搜不到,能不能简介一下,谢谢

论坛徽章:
0
发表于 2009-05-06 12:32 |显示全部楼层
原帖由 lyl19 于 2009-5-5 22:11 发表
请问楼主,你这是个什么工具,看起来很不错,google搜不到,能不能简介一下,谢谢



俺自己写的,http://code.google.com/p/grammardesigner/

不过不是很好用的,一方面是我不太会写UI,另一方面是当初UI部分引用的是我那库的早期版本,后来接口改了UI部分一直没重写,所以现在上面这个版本不是很好用。

论坛徽章:
0
发表于 2009-05-09 12:39 |显示全部楼层

回复 #44 Solidus 的帖子

佩服,先下下来感受一下
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP