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

期末考试考试时间：2016-05-29上午9:00-11:00考试地点：东环101答疑时间：2016-05-27下午13:00-16:002016-05-28下午13:00-17:00答疑地点：工科楼E11101复习习题课2编译原理总复习形式化方法词法的描述——三型文法、正规式语法的描述——二型文法语义处理的描述——属性文法文法的概念形式定义（四元组）句子、句型、推导、分析树文法分类3编译系统结构词法分析语法分析语义分析中间代码生成代码优化目标代码生成表格管理错误处理4词法分析正规式正规文法有限自动机DFA：确定的有限自动机知识点：语言、自动机、正规式和正规文法的关系自动机和识别过程的关系5主要计算题型正规语言、正规文法、正规式、自动机的互换有限自动机的生成和DFA的构造NFA的确定化DFA的最小化6一、词法分析设有正规式1(0|1)*1011. 试构造与该正规式等价的NFA，并对其进行确定化、最小化；2. 写出与最小化以后的DFA等价的正规文法；3. 写出其识别的正规集(即对应的正规语言)。7正规式1(0|1)*101构造与该正规式等价的NFAS010,1A1B1ZCNFA确定化S010A1B1ZC10018正规式1(0|1)*101DFA最小化S010A1B1ZC1001与最小化以后的DFA等价的正规文法G[S]：S→1AA→0A|1B

B→0C|1BC→0A|1ZD→0B|1B|ε9正规式1(0|1)*1013. 写出其识别的正规集(即对应的正规语言)以1开头，以101结尾的二进制数10语法分析自顶向下分析递归子程序法LL(1)分析法（预测分析）自底向上分析（移进归约分析）简单优先分析算符优先分析LR分析：LR(0)、SLR(1)、LR(1)、LALR(1)11语法分析自顶向下分析递归子程序法LL(1)分析法（预测分析）自底向上分析（移进归约分析）简单优先分析算符优先分析LR分析：LR(0)、SLR(1)、LR(1)、LALR(1)12自顶向下分析消除左递归、提取左因子计算FIRST集、FOLLOW集、SELECT集递归子程序法(了解)判断是不是LL(1)文法设计子程序LL(1)分析法（预测分析法）填写预测分析表分析某个符号串是否为句子13自顶向下分析常见题型消除左递归（直接、间接）消除左因子(提左公因子)求FIRST集求FOLLOW集求SELECT集编制递归子程序（了解）计算预测分析表(LL(1)分析表)跟踪预测分析过程14LL分析的概念根据当前输入符号，唯一地确定采用哪个产生式进行推导LL(1)文法何时改写文法适用范围左递归、左因子、FIRST、FOLLOW集和SELECT集的概念15二、LL(1)文法1、计算该文法的每个非终结符的FIRST集和FOLLOW集；2、求每个产生式的SELECT集；3、构造LL(1)分析表(终结符排列顺序为：adbe#)，并判断G[S]是否为LL(1)文法；4、若G[S]是LL(1)文法，则分析符号串aaabd#是否为文法的句子，并给出分析过程。分析时包含以下4列：步骤

分析栈

输入串

使用产生式G[S]：S→aH

H→aMd|d

M→Ab|ε

A→aM|e161、计算该文法的每个非终结符的FIRST集和FOLLOW集；G[S]：S→aH

H→aMd|d

M→Ab|ε

A→aM|e非终结符FIRST集FOLLOW集S{a}{#}H{a,d}{#}M{a,e,ε}{d,b}A{a,e}{b}2、求每个产生式的SELECT集；产生式SELECT集S→aH{a}H→aMd

{a}H→d

{d}M→Ab{a,e}M→ε{d,b}A→aM{a}A→e{e}173、构造LL(1)分析表(终结符排列顺序为：adbe#)，并判断G[S]是否为LL(1)文法；adbe#SaHHaMdDMAbεεAbAaMe产生式SELECT集S→aH{a}H→aMd

{a}H→d

{d}M→Ab{a,e}M→ε{d,b}A→aM{a}A→e{e}184、若G[S]是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#dbbd#b匹配10#dd#d匹配11##接受adbe#SaHHaMdDMAbεεAbAaMe分析成功，所以符号串aaabd#是文法的句子。19移近归约分析概念移进、归约、句柄、规范归约移近归约冲突、归约归约冲突核心如何寻找和确定句型中的句柄各种方法的区别20简单优先分析（了解）简单优先分析的基本思想简单优先关系分析过程21算符优先分析算符文法(OG)的定义算符优先关系的定义算符优先文法(OPG)的定义FIRSTVT、LASTVT的定义及计算素短语、最左素短语的概念及寻找算符优先关系表的计算算符优先分析过程22三、算符优先方法1、计算每个非终结符的FIRSTVT和LASTVT；2、构造算符优先关系表(终结符排列顺序为b(a)，并判断G[S]是否为算符优先文法；3、计算G[S]的优先函数。4、给出输入串b((aa)a)b#的算符优先分析过程G[S]：S→bMb

M→(L|a

L→Ma)231、计算每个非终结符的FIRSTVT和LASTVT；和G[S]：S→bMb

M→(L|a

L→Ma)非终结符FIRSTVT集LASTVT集S{b}{b}M{(,a}{a,)}L{(,a}{)}2、构造算符优先关系表(终结符排列顺序为b(a)#，并判断G[S]是否为算符优先文法；ab()#a⋗⋗b⋖⋖⋗(⋖⋗⋖⋖)⋗⋗#⋖任意两个终结符间至多存在一种算符优先关系，所以G[S]是算符优先文法243、计算G[S]的优先函数。ab()#a⋗⋗b⋖⋖⋗(⋖⋗⋖⋖)⋗⋗#⋖01*##f12211g31311ab()#f22231g22331ab()#f32341g32441ab()#f42341g42451ab()#f52351g42451254、给出输入串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#a⋗a，归约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#bb，移进15#bNb#b⋗#，移进16#N#接受ab()#a⋗⋗b⋖⋖⋗(⋖⋗⋖⋖)⋗⋗#⋖分析成功，所以符号串b((aa)a)b#是文法的句子。26LR分析文法的定义分析器的结构分析表的结构分析过程27LR(0)、SLR(1)的概念LR(0)项目的定义状态的概念（闭包计算）状态转移的概念可归前缀、活前缀的概念移进项目、归约项目、接受项目、待约项目移进-归约冲突、归约-归约冲突LR(0)文法SLR(1)文法28SLR(1)分析常见题型构造拓广文法（S’-->S）计算LR(0)项目集规范族（可归前缀图的构造）FIRST和FOLLOW集的计算LR(0)分析表的构造SLR(1)分析表的构造分析过程29LALR(1)分析同心集的概念合并同心集的方法和LR(1)的区别30四、LR分析方法1、判断G[S]是否为LR(0)、SLR(1)、LALR(1)、LR(1)文法，并说明理由；2、从上述可采用的无冲突的分析方法中，选择一种最简单的方法构造LR分析表(构造时终结符排列顺序为abd#)；3、用构造出的LR分析表，分析符号串addbd#是否为该文法的句子。分析时包含以下4列：步骤

状态栈

符号栈

输入串G[S]：S→AdD|ε

A→aAd|ε

D→DdA|b|ε311、判断G[S]是否为LR(0)、SLR(1)、LALR(1)、LR(1)文法，并说明理由；将文法G[S]拓广为G’，增加产生式S’

S产生式排序为：(0)S’

S (1)SAdD (2)Sε (3)AaAd(4)A

ε (5)DDdA (6)Db (7)Dε由产生式可计算出：非终结符FIRST集FOLLOW集S’{ε,d,a}{#}S{ε,d,a}{#}A{ε,a}{d,#}D{ε,d,b}{d,#}321、判断G[S]是否为LR(0)、SLR(1)、LALR(1)、LR(1)文法，并说明理由；构造G’的LR(0)项目集规范族I0:S’

•SS•AdDS

•A

•aAdA

•I1:S’

S•I2:SA•dDI3:A

a•AdA

•aAdA

•I4:SAd•DD

•DdAD•bD

•SAadI6:SAdD•DD•dADI7:Db•bI5:A

aA•dAaI9:DDd•AA

•aAdA

•dAI10:DDdA•aI8:A

aAd•dI0、I3、I4、I6、I9、I10中存在移近-归约冲突I0中存在归约-归约冲突因此文法不是LR(0)文法FOLLOW(S)∩FOLLOW(A)={#}∩{d,#}={#}，不为空因此文法不是SLR(1)文法331、判断G[S]是否为LR(0)、SLR(1)、LALR(1)、LR(1)文法，并说明理由；构造G’的LR(1)项目集规范族检查所有LR(1)项目集都无冲突，所以G[S]是LR(1)文法。I0:S’

•S,#S•AdD,#S

•,#A

•aAd,dA

•,dI1:S’S•,#I2:SA•dD,#I3:A

a•Ad,dA

•aAd,dA

•,dI4:SAd•D,#D

•DdA,d/#D•b,d/#D

•,d/#SAadI6:SAdD•,d/#DD•dA,d/#DI7:Db•,d/#bI5:A

aA•d,dAaI9:DDd•A,d/#A

•aAd,d/#A

•,d/#dAI10:DDdA•,d/#I8:A

aAd•,ddI11:A

a•Ad,d/#A

•aAd,dA

•,daaI12:A

aA•d,d/#AI13:A

aAd•,d/#d341、判断G[S]是否为LR(0)、SLR(1)、LALR(1)、LR(1)文法，并说明理由；由于I3和I11、I5和I12、I8和I13分别为同心集，合并后无归约-归约冲突，所以G[S]也是LALR(1)文法I0:S’

•S,#S•AdD,#S

•,#A

•aAd,dA

•,dI1:S’S•,#I2:SA•dD,#I3:A

a•Ad,dA

•aAd,dA

•,dI4:SAd•D,#D

•DdA,d/#D•b,d/#D

•,d/#SAadI6:SAdD•,d/#DD•dA,d/#DI7:Db•,d/#bI5,

8:A

aA•d,d/#AaI9:DDd•A,d/#A

•aAd,d/#A

•,d/#dAI10:DDdA•,d/#I8,13:A

aAd•,d/#dI11:A

a•Ad,d/#A

•aAd,dA

•,daaAd352、从上述可采用的无冲突的分析方法中，选择一种最简单的方法构造LR分析表(构造时终结符排列顺序为abd#)；选择构造LALR(1)分析表如下：状态ACTIONGOTOabd#SAD0S3r4r2121acc2S43S3r454S7r7r765S86S9r17r6r68r3r39S3r4r41010r5r5363、用构造出的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#是文法的句子。状态ACTIONGOTOabd#SAD0S3r4r2121acc2S43S3r454S7r7r765S86S9r17r6r68r39