形式系统

计算机专业教学
posts - 48, comments - 150, trackbacks - 0, articles - 10
  教师博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

最为精简的复习(LL(1)分析法)

Posted on 2006-07-05 22:17 形式系统 阅读(2947) 评论(15)  编辑 收藏 引用 网摘 所属分类: 编译原理

文法:
A
à (A)A | B

B à a | b | ε

说明:蓝色文字表示说明,讲解;黑色部分(除了为突出的红色文字外)为正式书面表述,即,答题时就可按黑色文字部分格式。

(1)       显然不含左递归

构造 First  Follow

 

First

Follow

A

( a b ε

# )

B

a b ε

# )

First((A)A ) Fisrt(B)=Ф

First(a ) Fisrt(b)Fisrt(ε)

B
含有 ε项的候选,由上表可知First(B)∩Follow(B)=Ф

故满足 LL(1) 文法。

 

(2)       预测分析表

            预测分析表的含义:当前状态下(即栈顶为特定非终结符,同时面临特定的输入符号(终结符)时),应该用哪条产生式去推导。将该产生式放入表中以便查阅。其求法就是利用该非终结符的产生式的候选的First集。如,若'('∈First((A)A),而当前栈顶元素为A,输入恰好为(,那么就可以认为此时采用Aà(A)A进行推导是合理的。而LL文法的条件就限定了,一个非终结符,只能属于一个候选的First的集。因而下表的每个单元格,只可能填一条产生式候选。

 

a

b

(

)

#

A

Aà B

AàB

Aà(A)A

 AàB

AàB

B

Bàa

Bàb

 

 Bàε

Bàε

 

 

 

 

 

 

 

(3)       堆栈的变化

假设输入串为((a)b)

序号

堆栈

输入

说明(答题时,本列可不写)

1

#A

( (a)b)

查表,A行, ( 列,采用Aà(A)A推导

2

#A)A(

((a)b)#

若与栈顶元素相同,则消解。下面桔黄项同理。请注意,入栈顺序是按文法由右到左的顺序。

3

#A)A

( a)b)#

Aà(A)A

4

#A)A)A(

(a)b)#

 

5

#A)A)A

a )b)#

AàB

6

#A)A)B

a )b)#

Bàa

7

#A)A)a

a )b)#

 

8

#A)A)

) b)#

 

9

#A)A

b )#

AàB

10

#A)B

b )#

Bàb

11

#A)b

b )#

 

12

#A)

) #

 

13

#A

#

#作为输入结束的界符,AàB

14

#B

#

Bàε

15

#

#

如果输入串正确,则必然会到达这个状态


       上表中,红色部分只是个例子,说明怎样查分析表,即栈顶元素指示分析表的行,输入元素指示分析表的列,从分析表中查出相应的产生式,利用其推导。

(4)       递归下降程序实现
         程序代码:http://yhspace.ys168.com
         其下的编译原理子目录,Compile01.rar,Compile02.rar.
         调试成功,用VC打开可运行。如未装VC,用文本编辑器分别打开main.cpp,compile02.cpp也可查看代码。

Feedback

# re: 最为精简的复习(LL(1)分析法)  回复  更多评论   

2006-07-07 15:10 by chenlansky
是构造FIRST集跟FOLLOW集吧…………
不是LAST集吧………………

# re: 最为精简的复习(LL(1)分析法)  回复  更多评论   

2006-07-07 23:24 by 形式系统
已更正过来了,谢谢。

# re: 最为精简的复习(LL(1)分析法)  回复  更多评论   

2006-07-08 23:29 by chen
老师你的预测分析表的分析好象和书上说的不一样也,
预测分析的FIRST在书上好象和候选首符集不一样
在上面的预测分析表的" ) "输入符下面怎么都是空的?
要不要A->

# re: 最为精简的复习(LL(1)分析法)  回复  更多评论   

2006-07-09 10:51 by 合乎
对的啊,老师你的那个预测分析表的" ) "输入符下面应该还有东西的啊,老师看看啊

# re: 最为精简的复习(LL(1)分析法)  回复  更多评论   

2006-07-09 10:51 by 形式系统
B面临)列时,还需加上B-> ε
某一列不填文法到不是问题。
如果本例第二条产生式改为B -> a| b,
则')'不可能为A,B的First。因此)列必为空。但如果有ε,则考虑其Follow集,且只有B的候选有ε ,所以分别在( #列添加B-> ε

# re: 最为精简的复习(LL(1)分析法)  回复  更多评论   

2006-07-09 11:45 by hh
是不是还少了个 A->ε 呢???

# re: 最为精简的复习(LL(1)分析法)  回复  更多评论   

2006-07-09 11:45 by hh
) 下面

# re: 最为精简的复习(LL(1)分析法)  回复  更多评论   

2006-07-09 11:55 by chen
老师 对于 ) 个符号下面的产生式
书上说若ε 属于某个FIRST()且a->FOLLOW(A),则让A与ε自动匹配
而上面的A的FIRST中也含有ε 啊
那应该在A的 ) 下面也加上A->ε

# re: 最为精简的复习(LL(1)分析法)  回复  更多评论   

2006-07-09 12:21 by chenlansky
9 #A)Ab b)# A->b
这里A->b 应该是A->B

吧…………

# re: 最为精简的复习(LL(1)分析法)  回复  更多评论   

2006-07-09 12:41 by
完全看不懂111111111111111111111111111111!!!!!!!!!!!!!!!

# re: 最为精简的复习(LL(1)分析法)  回复  更多评论   

2006-07-09 15:57 by 形式系统
少了个A->B,而不是A->ε

# re: 最为精简的复习(LL(1)分析法)  回复  更多评论   

2006-07-09 16:36 by 形式系统
chenlansky很细心,漏了一步,现在改了。

# re: 最为精简的复习(LL(1)分析法)  回复  更多评论   

2006-07-09 19:52 by 谢明秀
见鬼,大家都没有写自己的名字我好老实就写上了,不会被怪罪吧

# re: 最为精简的复习(LL(1)分析法)  回复  更多评论   

2006-07-09 23:25 by sky fancy
学士学位难 望老师能网开一面

# re: 最为精简的复习(LL(1)分析法)  回复  更多评论   

2007-10-07 07:01 by dfhdfh
http://casalinghe-erotike.mostrar-thn.cn
http://casalinga-troia-it.mostrar-thn.cn
http://ingrandimento-seno.ammucchiata-thn.cn
http://cazzo-sborranti.mostrar-thn.cn
http://annuncio-gang-bang-tutto-regione-laurax.naturali-thn.cn
http://diciottenne-nudo-maschio.mostrar-thn.cn
http://culo-mogli.mostrar-thn.cn
http://vacca-negra.play-thn.cn
http://enorme-cazzone.mostrar-thn.cn
http://bocche-rotte-sexi.naturali-thn.cn
http://ingoio-di-sborrate.vestito-thn.cn
http://filmato-amatoriali-sesso.mostrar-thn.cn
http://foto-casalinghe-gretis.naturali-thn.cn
http://chat-conoscere-ragazza-lesbica.vestito-thn.cn
http://cerco-foto-culi-over.naturali-thn.cn

只有注册用户登录后才能发表评论。