讲稿第9章 编译原理习题课

1、1 期末考试期末考试 考试时间：考试时间：2016-05-29 上午上午9:00-11:00 考试地点：东环考试地点：东环101 答疑时间：答疑时间：2016-05-27 下午下午13:00-16:00 2016-05-28 下午下午13:00-17:00 答疑地点：工科楼答疑地点：工科楼E1110 2 复习习题课 3 编译原理总复习编译原理总复习 形式化方法形式化方法 l 词法的描述词法的描述三型文法、正规式三型文法、正规式 l 语法的描述语法的描述二型文法二型文法 l 语义处理的描述语义处理的描述属性文法属性文法 文法的概念文法的概念 l 形式定义（四元组）形式定义（四元组） l 句子、句

2、型、推导、分析树句子、句型、推导、分析树 l 文法分类文法分类 4 编译系统结构编译系统结构 u词法分析词法分析 u语法分析语法分析 u语义分析语义分析 u中间代码生成中间代码生成 u代码优化代码优化 u目标代码生成目标代码生成 u表格管理表格管理 u错误处理错误处理 5 词法分析词法分析 u 正规式正规式 u 正规文法正规文法 u 有限自动机有限自动机 u DFA：确定的有限自动机确定的有限自动机 知识点：知识点： u 语言、自动机、正规式和正规文法的关系语言、自动机、正规式和正规文法的关系 自动机和识别过程的关系自动机和识别过程的关系 6 主要计算题型主要计算题型 u正规语言、正规文法、正

3、规式、自动机正规语言、正规文法、正规式、自动机 的互换的互换 u有限自动机的生成和有限自动机的生成和DFA的构造的构造 uNFA的确定化的确定化 uDFA的最小化的最小化 7 一、词法分析 设有正规式1(0|1)*101 1.试构造与该正规式等价的NFA，并对其进行确定化、 最小化； 2.写出与最小化以后的DFA等价的正规文法； 3.写出其识别的正规集(即对应的正规语言)。 8 正规式1(0|1)*101 构造与该正规式等价的NFA S 01 0,1 A 1 B 1 ZC NFA确定化 S 01 0 A 1 B 1 ZC 1 0 0 1 9 正规式1(0|1)*101 DFA最小化 S 01

4、0 A 1 B 1 ZC 1 0 0 1 与最小化以后的DFA等价的正规文法 GS：S 1A A 0A | 1B B 0C | 1B C 0A | 1Z D 0B | 1B | 10 正规式1(0|1)*101 3.写出其识别的正规集(即对应的正规语言) 以1开头，以101结尾的二进制数 11 语法分析 自顶向下分析 l 递归子程序法 l LL(1)分析法（预测分析） 自底向上分析（移进归约分析） l 简单优先分析 l 算符优先分析 l LR分析：LR(0)、SLR(1)、LR(1)、 LALR(1) 12 语法分析 自顶向下分析 l 递归子程序法 l LL(1)分析法（预测分析） 自底向上分

5、析（移进归约分析） l 简单优先分析 l 算符优先分析 l LR分析：LR(0)、SLR(1)、LR(1)、LALR(1) 13 自顶向下分析 消除左递归、提取左因子 计算FIRST集、FOLLOW集、 SELECT集 递归子程序法(了解) l 判断是不是LL(1)文法 l 设计子程序 LL(1) 分析法（预测分析法） l 填写预测分析表 l 分析某个符号串是否为句子 14 自顶向下分析常见题型 u 消除左递归（直接、间接） u 消除左因子(提左公因子) u 求 FIRST 集 u 求 FOLLOW 集 u 求 SELECT 集 u 编制递归子程序（了解） u 计算预测分析表(LL(1)分析表

6、) u 跟踪预测分析过程 15 LL分析的概念 根据当前输入符号，唯一地确定采用哪 个产生式进行推导 l LL(1) 文法 l 何时改写文法 l 适用范围 l 左递归、左因子、FIRST、FOLLOW集和 SELECT 集的概念 16 二、LL(1)文法 1、计算该文法的每个非终结符的FIRST集和FOLLOW集； 2、求每个产生式的SELECT集； 3、构造LL(1)分析表(终结符排列顺序为：adbe# )，并判 断GS是否为LL(1)文法； 4、若GS是LL(1)文法，则分析符号串aaabd#是否为文 法的句子，并给出分析过程。分析时包含以下4列： 步骤分析栈输入串使用产生式 GS：S a

7、H H aMd | d M Ab | A aM | e 17 1、计算该文法的每个非终结符的FIRST集和FOLLOW集； GS：S aH H aMd | d M Ab | A aM | e Sa# Ha, d# Ma, e, d, b Aa, eb 2、求每个产生式的SELECT集； S aHa H aMd a H d d M Aba, e M d, b A aMa A ee 18 3、构造LL(1)分析表(终结符排列顺序为：adbe# )，并判 断GS是否为LL(1)文法； SaH HaMdD MAbAb AaMe S aHa H aMd a H d d M Aba, e M d, b A

8、 aMa A ee 19 4、若GS是LL(1)文法，则分析符号串aaabd#是否为文 法的句子，并给出分析过程。分析时包含以下4列： 1#Saaabd# S aH 2#Haaaabd# a匹配 3#Haabd# H aMd 4#dMaaabd# a匹配 5#dMabd# M Ab 6#dbAabd# A aM 7#dbMaabd# a匹配 8#dbMbd# M 9#dbbd# b匹配 10#dd# d匹配 11# 接受 SaH HaMdD MAbAb AaMe 分析成功，所以符号串aaabd#是文法的句子。 20 移近归约分析 概念 l 移进、归约、句柄、规范归约 l 移近归约冲突、归约归约

9、冲突 核心 l 如何寻找和确定句型中的句柄 l 各种方法的区别 21 简单优先分析（了解） 简单优先分析的基本思想 简单优先关系 分析过程 22 算符优先分析 u 算符文法(OG)的定义 u 算符优先关系的定义 u 算符优先文法(OPG)的定义 u FIRSTVT、LASTVT的定义及计算 u 素短语、最左素短语的概念及寻找 u 算符优先关系表的计算 u 算符优先分析过程 23 三、算符优先方法 1、计算每个非终结符的FIRSTVT和LASTVT； 2、构造算符优先关系表(终结符排列顺序为b(a)，并判断 GS是否为算符优先文法； 3、计算GS的优先函数。 4、给出输入串b(aa)a)b#的算

10、符优先分析过程 GS：S bMb M (L | a L Ma) 24 1、计算每个非终结符的FIRSTVT和LASTVT；和 GS：S bMb M (L | a L Ma) Sbb M(, aa, ) L(, a) 2、构造算符优先关系表(终结符排列顺序为b(a)#，并判 断GS是否为算符优先文法； a b ( ) # 任意两个终结符间至多 存在一种算符优先关系， 所以GS是算符优先文 法 25 3、计算GS的优先函数。 a b ( ) # 01*# f12211 g31311 ab()# f22231 g22331 ab()# f32341 g32441 ab()# f42341 g4245

11、1 ab()# f52351 g42451 26 4、给出输入串b(aa)a)b#的算符优先分析过程 1#b(aa)a)b# #b，移进 2#b(aa)a)b# b(，移进 3#b(aa)a)b# b(，移进 4#b(aa)a)b# (a，移进 5#b(aa)a)b# aa，归约 6#b(Na)a)b# (a，移进 7#b(Na)a)b# a )，移进 8#b(Na)a)b# )a，归约 9#b(Na)b# (a，移进 10#b(Na)b# a )，移进 11#b(Na)b# )b，归约 12#b(Nb# (b，归约 13#b(Nb# (b，归约 14#bNb# b b，移进 15#bNb#

12、b#，移进 16#N# 接受 a b ( ) # 分析成功，所以符号串 b(aa)a)b#是文法的句 子。 27 LR 分析 u 文法的定义 u 分析器的结构 u 分析表的结构 u 分析过程 28 LR(0) 、SLR(1) 的概念 u LR(0) 项目的定义 u 状态的概念（闭包计算） u 状态转移的概念 u 可归前缀、活前缀的概念 u 移进项目、归约项目、接受项目、待约项目 u 移进-归约冲突、归约-归约冲突 u LR(0) 文法 u SLR(1) 文法 29 SLR(1)分析常见题型 u 构造拓广文法（S-S） u 计算 LR(0) 项目集规范族（可归前缀图 的构造） u FIRST 和

13、 FOLLOW 集的计算 u LR(0) 分析表的构造 u SLR(1) 分析表的构造 u 分析过程 30 LALR(1)分析 u同心集的概念 u合并同心集的方法 u和LR(1)的区别 31 四、LR分析方法 1、判断GS是否为LR(0)、SLR(1)、LALR(1)、LR(1)文 法，并说明理由； 2、从上述可采用的无冲突的分析方法中，选择一种最简 单的方法构造LR分析表(构造时终结符排列顺序为 abd# )； 3、用构造出的LR分析表，分析符号串addbd#是否为该 文法的句子。分析时包含以下4列： 步骤状态栈符号栈输入串 GS：S AdD | A aAd | D DdA | b | 32

14、 1、判断GS是否为LR(0)、SLR(1)、LALR(1)、LR(1)文 法，并说明理由； 将文法GS拓广为G，增加产生式SS 产生式排序为： (0)SS(1)SAdD(2)S(3)AaAd (4)A (5)DDdA(6)Db(7)D 由产生式可计算出： S, d, a# S, d, a# A, ad, # D, d, bd, # 33 1、判断GS是否为LR(0)、SLR(1)、LALR(1)、LR(1)文 法，并说明理由； 构造G的LR(0)项目集规范族 I0: S S S AdD S A aAd A I1: S S I2: S AdD I3: A aAd A aAd A I4: S A

15、dD D DdA D b D S A a d I6: S AdD D DdA D I7: D b b I5: A aAd A a I9: D DdA A aAd A d A I10: D DdA a I8: A aAd d I0、I3、I4、I6、I9、I10中存在移近-归约冲突 I0中存在归约-归约冲突 因此文法不是LR(0)文法 FOLLOW(S)FOLLOW(A) = #d, # = #，不为空 因此文法不是SLR(1)文法 34 1、判断GS是否为LR(0)、SLR(1)、LALR(1)、LR(1)文 法，并说明理由； 构造G的LR(1)项目集规范族 检查所有LR(1)项目集都无冲突，

16、所以GS 是LR(1)文法。 I0: SS, # SAdD, # S, # AaAd, d A, d I1: SS, # I2: SAdD, # I3: AaAd, d AaAd, d A, d I4: SAdD, # DDdA, d/# Db, d/# D, d/# S A a d I6: SAdD, d/# DDdA, d/# D I7: Db, d/# b I5: AaAd, d A a I9: DDdA, d/# AaAd, d/# A, d/# d A I10: DDdA, d/# I8: AaAd, d d I11: AaAd, d/# AaAd, d A, d a a I12:

17、AaAd, d/# A I13: AaAd, d/# d 35 1、判断GS是否为LR(0)、SLR(1)、LALR(1)、LR(1)文 法，并说明理由； 由于I3和I11、 I5和I12 、 I8和I13分别为同心集，合并后无归 约-归约冲突，所以GS也是LALR(1)文法 I0: SS, # SAdD, # S, # AaAd, d A, d I1: SS, # I2: SAdD, # I3: AaAd, d AaAd, d A, d I4: SAdD, # DDdA, d/# Db, d/# D, d/# S A a d I6: SAdD, d/# DDdA, d/# D I7: Db,

18、 d/# b I5, 8: AaAd, d/# A a I9: DDdA, d/# AaAd, d/# A, d/# d A I10: DDdA, d/# I8,1 3: AaAd, d/# d I11: AaAd, d/# AaAd, d A, d a a A d 36 2、从上述可采用的无冲突的分析方法中，选择一种最简 单的方法构造LR分析表(构造时终结符排列顺序为 abd# )； 选择构造LALR(1)分析表如下： 状态 ACTIONGOTO abd#SAD 0S3r4r212 1acc 2S4 3S3r45 4S7r7r76 5S8 6S9r1 7r6r6 8r3r3 9S3r4r41

19、0 10r5r5 37 3、用构造出的LR分析表，分析符号串addbd#是否为该 文法的句子。 10#addbd# 203#addbd# 3035#aAddbd# 40358#aAddbd# 502#Adbd# 6024#Adbd# 70247#Adbd# 80246#AdDd# 902469#AdDd# 1002469(10)#AdDdA# 110246#AdD# 1201#S# 分析成功，所以符号串b(aa)a)b#是文法的句 子。 状 态 ACTIONGOTO abd#SAD 0S3r4r212 1acc 2S4 3S3r45 4S7r7r76 5S8 6S9r1 7r6r6 8r3 9S3r4r410 10r5r5 38 属性文法 语法制导定义和翻译方案 l 区别 l 用途 概念 l 综合属性 l 继承属性 l 计算顺序 39 中间代码的