讲稿第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答疑地点：工科楼答疑地点：工科楼E11102复习习题课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正规语言、正规文法、正规式、自动机正规语言、正规文法、正规式、自动机的互换的互换u有限自动机的

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

4、 | 10正规式1(0|1)*1013.写出其识别的正规集(即对应的正规语言)以1开头，以101结尾的二进制数11语法分析自顶向下分析l 递归子程序法l LL(1)分析法（预测分析）自底向上分析（移进归约分析）l 简单优先分析l 算符优先分析l LR分析：LR(0)、SLR(1)、LR(1)、LALR(1)12语法分析自顶向下分析l 递归子程序法l LL(1)分析法（预测分析）自底向上分析（移进归约分析）l 简单优先分析l 算符优先分析l LR分析：LR(0)、SLR(1)、LR(1)、LALR(1)13自顶向下分析消除左递归、提取左因子计算FIRST集、FOLLOW集、 SELECT集递归子

5、程序法(了解)l 判断是不是LL(1)文法l 设计子程序LL(1) 分析法（预测分析法）l 填写预测分析表l 分析某个符号串是否为句子14自顶向下分析常见题型u 消除左递归（直接、间接）u 消除左因子(提左公因子)u 求 FIRST 集u 求 FOLLOW 集u 求 SELECT 集u 编制递归子程序（了解）u 计算预测分析表(LL(1)分析表)u 跟踪预测分析过程15LL分析的概念根据当前输入符号，唯一地确定采用哪个产生式进行推导l LL(1) 文法l 何时改写文法l 适用范围l 左递归、左因子、FIRST、FOLLOW集和SELECT 集的概念16二、LL(1)文法1、计算该文法的每个非终

6、结符的FIRST集和FOLLOW集；2、求每个产生式的SELECT集；3、构造LL(1)分析表(终结符排列顺序为：adbe# )，并判断GS是否为LL(1)文法；4、若GS是LL(1)文法，则分析符号串aaabd#是否为文法的句子，并给出分析过程。分析时包含以下4列： 步骤分析栈输入串使用产生式GS：S aH H aMd | d M Ab | A aM | e171、计算该文法的每个非终结符的FIRST集和FOLLOW集；GS：S aH H aMd | d M Ab | A aM | eSa#Ha, d#Ma, e, d, bAa, eb2、求每个产生式的SELECT集；S aHaH aMd

7、aH d dM Aba, eM d, bA aMaA ee183、构造LL(1)分析表(终结符排列顺序为：adbe# )，并判断GS是否为LL(1)文法；SaHHaMdDMAbAbAaMeS aHaH aMd aH d dM Aba, eM d, bA aMaA ee194、若GS是LL(1)文法，则分析符号串aaabd#是否为文法的句子，并给出分析过程。分析时包含以下4列： 1#Saaabd# S aH2#Haaaabd# a匹配3#Haabd# H aMd 4#dMaaabd# a匹配5#dMabd# M Ab6#dbAabd# A aM7#dbMaabd# a匹配8#dbMbd# M 9

8、#dbbd# b匹配10#dd# d匹配11# 接受SaHHaMdDMAbAbAaMe分析成功，所以符号串aaabd#是文法的句子。 20移近归约分析概念l 移进、归约、句柄、规范归约l 移近归约冲突、归约归约冲突核心l 如何寻找和确定句型中的句柄l 各种方法的区别21简单优先分析（了解）简单优先分析的基本思想简单优先关系分析过程22算符优先分析u 算符文法(OG)的定义u 算符优先关系的定义u 算符优先文法(OPG)的定义u FIRSTVT、LASTVT的定义及计算u 素短语、最左素短语的概念及寻找u 算符优先关系表的计算u 算符优先分析过程23三、算符优先方法1、计算每个非终结符的FIRS

9、TVT和LASTVT； 2、构造算符优先关系表(终结符排列顺序为b(a)，并判断GS是否为算符优先文法；3、计算GS的优先函数。4、给出输入串b(aa)a)b#的算符优先分析过程GS：S bMb M (L | a L Ma)241、计算每个非终结符的FIRSTVT和LASTVT；和GS：S bMb M (L | a L Ma)SbbM(, aa, )L(, a)2、构造算符优先关系表(终结符排列顺序为b(a)#，并判断GS是否为算符优先文法；a b ()#任意两个终结符间至多存在一种算符优先关系，所以GS是算符优先文法253、计算GS的优先函数。a b ()#01*#f12211g31311a

10、b()#f22231g22331ab()#f32341g32441ab()#f42341g42451ab()#f52351g42451264、给出输入串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

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

12、和 FOLLOW 集的计算u LR(0) 分析表的构造u SLR(1) 分析表的构造u 分析过程30LALR(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 | 321、判断GS是否为LR(0)、S

13、LR(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, #331、判断GS是否为LR(0)、SLR(1)、LALR(1)、LR(1)文法，并说明理由； 构造G的LR(0)项目集规范族I0:S SS AdDS A aAdA I1:S S I2:S AdDI3:A aAdA aAdA I4:S AdDD DdAD bD SAadI6:S AdDD DdADI7:D bbI5:

14、A aAdAaI9:D DdAA aAdA dAI10:D DdAaI8:A aAddI0、I3、I4、I6、I9、I10中存在移近-归约冲突I0中存在归约-归约冲突因此文法不是LR(0)文法FOLLOW(S)FOLLOW(A)= #d, # = #，不为空因此文法不是SLR(1)文法341、判断GS是否为LR(0)、SLR(1)、LALR(1)、LR(1)文法，并说明理由； 构造G的LR(1)项目集规范族检查所有LR(1)项目集都无冲突，所以GS是LR(1)文法。I0:SS, #SAdD, #S, #AaAd, dA, dI1:SS, #I2:SAdD, #I3:AaAd, dAaAd, d

15、A, dI4:SAdD, #DDdA, d/#Db, d/#D, d/#SAadI6:SAdD, d/#DDdA, d/#DI7:Db, d/#bI5:AaAd, dAaI9:DDdA, d/#AaAd, d/#A, d/#dAI10:DDdA, d/#I8:AaAd, ddI11:AaAd, d/#AaAd, dA, daaI12:AaAd, d/#AI13:AaAd, d/#d351、判断GS是否为LR(0)、SLR(1)、LALR(1)、LR(1)文法，并说明理由； 由于I3和I11、 I5和I12 、 I8和I13分别为同心集，合并后无归约-归约冲突，所以GS也是LALR(1)文法I0

16、:SS, #SAdD, #S, #AaAd, dA, dI1:SS, #I2:SAdD, #I3:AaAd, dAaAd, dA, dI4:SAdD, #DDdA, d/#Db, d/#D, d/#SAadI6:SAdD, d/#DDdA, d/#DI7:Db, d/#bI5, 8:AaAd, d/#AaI9:DDdA, d/#AaAd, d/#A, d/#dAI10:DDdA, d/#I8,1 3:AaAd, d/#dI11:AaAd, d/#AaAd, dA, daaAd362、从上述可采用的无冲突的分析方法中，选择一种最简单的方法构造LR分析表(构造时终结符排列顺序为 abd# )；选择

17、构造LALR(1)分析表如下：状态ACTIONGOTOabd#SAD0S3r4r2121acc2S43S3r454S7r7r765S86S9r17r6r68r3r39S3r4r41010r5r5373、用构造出的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#是文法的句子。 状态ACTIO

18、NGOTOabd#SAD0S3r4r2121acc2S43S3r454S7r7r765S86S9r17r6r68r39S3r4r41010r5r538属性文法语法制导定义和翻译方案 l 区别 l 用途 概念l 综合属性l 继承属性l 计算顺序39中间代码的生成l 逆波兰式l 三元式l 树l 四元式语法制导翻译方法l 翻译要求l 翻译过程40常见题型u 属性文法的理解u 语义子程序的编制u 表达式的翻译（逆波兰式、三元式、四元式等）41五、语法制导翻译有文法 GS：SS0|S1|0|1请按照语法制导翻译的方法，给出每个产生式相应的语义规则(或者说配上语义动作子程序)，它输出由S生成的二进制的数值。例如，对于输入101，输出5。解：拓展文法，加入新开始符号S和产生式SS。用 S.val 表示二进制值。语义规则如下：(0) SS print(S.val)(1) SS1 0S.val= 2*S1.val(2) SS1 1S.val= 2*S1.val+1(3) S