形式系统

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

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

Posted on 2006-07-03 23:57 形式系统 阅读(1090) 评论(4)  编辑 收藏 引用 网摘 所属分类: 编译原理

给出文法, G(S):       A à (A) | a

构造 SLR 分析表。


(1)建立拓广文法并编号:

         0)   S à A

         1)  A à (A)

         2)  A à a


(2)构造项目集簇和状态转换图:
A_(A).gif

(3)构造分析表
 
      若为SLR分析法,还需求FirstFollow集。

 

First

Follow

S

(     a

#

A

(      a

)  #


构造分析表如下:

 

ACTION

GOTO

a

(

)

#

S

A

0

S3

S2

 

 

 

1

1

 

 

 

Acc

 

 

2

S3

S2

 

 

 

4

3

 

 

R2

R2

 

 

4

 

 

S5

 

 

 

5

 

 

R1

R1

 

 


      请注意图中的颜色项和表中的颜色项的对应关系。
Sj表示当前输入符号和状态j入栈。
Rj表示采用第j条产生式进行归约。

(4)       堆栈的变化
假定输入串为:((a))

 

状态栈

符号栈

输入

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

1

0

#

( (a))#

查表,状态0,输入(,为S2,即将(入符号栈,2入状态栈。

2

02

#(

( a))#

( 移进

3

022

#((

a ))#

a移进

4

0223

#((a

))#

查表,状态3,面临输入),为R3,使用第3条产生式(即Aàa)规约

5

0224

#((A

) )#

)移进

6

02245

#((A)

) #

状态5面临)输入,R1,即使用Aà(A)归约。红色部分为先出栈元素,出栈后将产生式左边的符号,即A入栈,同时此时状态栈的栈顶元素是2,查SLR分析表,状态2面临输入

7

024

#(A

) #

)移进

8

0245

#(A)

#

使用Aà(A)归约

9

01

#A

#

Acc(接受项目)


Feedback

# re: 最为精简的复习  回复  更多评论   

2006-07-04 19:21 by chenlansky
老师好,这个跟书上那5.8题一样吧,,,,,,
不过好象还简单一些吧…………

# re: 最为精简的复习  回复  更多评论   

2006-07-04 22:43 by 颜春捷
这样看得就明白多了啊
希望考试的难度不要超过这道题啊!!

# re: 最为精简的复习  回复  更多评论   

2006-07-05 15:38 by 罗海华
姚老师,这种题型就考上述3方面的问题吗? 那5.8题第3问那样的类型还考不?

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

2006-07-06 00:18 by 形式系统
堆栈变化的过程当然要考。

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