《编译原理》期末复习资料汇总1826.docx

编译原理期末复习资料【题 1】1. （a|b）*（aa|bb）（aa|b）*画出状态态转换图。IaIb 1,2,32,3,442,3,55 2,3,42,3,44,6,77,82,3,55 2,3,52,3,442,3,5,6,7,8 2,3,4,6,7,82,3,44,6,77,82,3,55,7,88 2,3,5,6,7,82,3,44,7,882,3,55,6,77,8 2,3,5,7,82,3,44,7,882,3,55,6,77,8 2,3,4,7,82,3,44,6,77,82,3,55,7,88IaIb123243325446575675746 新新的状态转转换图如下下： （1）A=1,22,3，BB=4,5,6,7 Aa=2,4 ×（2）A=1,33，B=2，CC=4,5,6,7 Aa=2B，AAb=33,5 ×（3）A=1，BB=2，C=3,DD=4,5,6,7（单单元素可以以不用看，必必有，古先先看D） Da=4,7D，Dbb=5,6D，AAa=22B，AAb=33C，BBa=44D，BBb=33C，CCa=22B，CCb=55C，则则有ab ABC BDCCBDDDD2. （a*|bb*）b（bba）*的的状态转换换图。IaIb 1,2,3,42,43,4,55,6,88 2,42,45,6,88 3,4,5,6,8-3,4,55,6,77,8 5,6,8-7 3,4,5,6,7,86,83,4,55,6,77,8 76,8- 6,8-7IaIb1232243-54-657567-7-6新的状态转转换图如下下：化简：（用用终结状态态与非终结结状态，然然后输出状状态一致分分一类）。（1）A=1,22,6，BB=3,4,5,7 Aa=2 ××（2）A=1,22，B=6，CC=3,4,7，D=5 Cb=5,6 ×（只要有有一个不属属于任何一一个集合，就就不行）（3）A=1,22，B=6，CC=3，D=4,7，E=5 Ab=3,4 ×（4） AA=1，B=2，CC=6，D=3，EE=4,7，FF=5 Aaa=2B，Abb=3D，Baa=2B，Bbb=4E，Caa=7E，Dbb=5F，Ebb=6C，Faa=7E，Fbb=5Fab ABD BBECE-D-FE-CFEF注意事项项：知识要点点：u 正则表达式式：；是最左边一一个字母一一定是，其其余字母为为的任意组组合，不包包括。a和若干干个a（包包括0的情情形）后跟跟一个b构构成的符号号串集合a和a后后跟若干个个（包括00的情形）bb构成的符符号串集合合u 状态转换图图（有穷状状态自动机机）： 【题 2】1.求如下下简单算术术表达式文文法中语法法变量的FFOLLOOW集。解答：（1）求求表达式文文法的语法法符号的FFIRSTT集：FIRSTT(F)=（, idFIRSTT(T)=FIRSST(F)=（, id FIRSTT(E)=FIRSST(T)=（, id FIRSTT(E')=+，FIRSTT(T')=*, FIRSTT(+)=+, FIRRST(*)=*FIRSTT(（)=（FIRSTT(）)=）FIRSTT(id)=idd（2）求表表达式文法法的语法变变量的 FFOLLOOW集：FOLLOOW(E) = #, ) FOLLOOW(E'')= FFOLLOOW( EE ) = #, ) FOLLOOW(T) = FIRSST(E'')-FOLLLOW(EE)FOLLLOW(EE')= +,),#FOLLOOW(T'')= FFOLLOOW(T)= +,),#FOLLOOW(F) = FFIRSTT(T)FOLLLOW(TT)FOLLLOW(TT') =*,+,),# 6知识点Firstt集合的求求法： FFirstt集合最终终是对产生生式右部的的字符串而而言的，但但其关键是是求出非终终结符的FFirstt集合，由由于终结符符的Firrst集合合就是它自自己，所以以求出非终终结符的FFirstt集合后，就就可很直观观地得到每每个字符串串的Firrst集合合1. 直直接收取：对形如UU->a的产生式式（其中aa是终结符符），把aa收入到FFirstt(U)中中2. 反反复传送：对形入UU->P11P2P33Pn的的产生式（其其中P是非非终结符），应应先把Fiirst(P1)中中的全部内内容传送到到Firsst(U)中,如果果P1中有有，把FFirstt(P2)中的内容容传送到FFirstt(U)中中,类推直直到Pi中中无。Folloow集合的的求法： FFolloow集合是是针对非终终结符而言言的，Foolloww(U)所所表达的是是句型中非非终结符UU所有可能能的后随终终结符号的的集合，特特别地，“$”是识别别符号的后后随符,先先直接加入入到S中。1. 直接接收取：注注意产生式式右部的每每一个形如如“Uaa”的组组合，把aa直接收入入到Folllow(U)中。2. 直接接收取：对对形如“UP”(P是非终终结符)的的组合，把把Firsst(P)中非收收入到Foolloww(U)中中。3. 反复复传送：对对形如U>aP的的产生式（其其中P是非非终结符）或或U->aaPQ(PP,Q为非非终结符且且Q中含)，应把把Folllow(UU)中的全全部内容传传送到Foolloww(P)中中。例 文文法：SABc Aaa| Bb|Firstt集合求法法:能由非非终结符号号推出的所所有的开头头符号或可可能的，但但要求这个个开头符号号是终结符符号。如此此题A可以以推导出aa和，所所以FIRRST（AA）=aa，；同理 FFIRSTT（B）=b,;S可可以推导出出aBc，还还可以推导导出bc，还还可以推导导出c，所所以FIRRST(SS）=aa，b，ccFolloow集合的的求法:紧紧跟随其后后面的终结结符号或。但文法法的识别符符号包含，在求的的时候还要要考虑到。 具体体做法是把把所有包含含你要求的的符号的产产生式都找找出来，再再看哪个有有用。 FFolloow（S）=如如求A的，产产生式：SSABcc Aaa| ，但但只有SABc 有用。跟跟随在A后后面的终结结符号是FFIRSTT（B）=b，当FFIRSTT（B）的的元素为时，跟随随在A后的的符号就是是c，所以以 Folllow（AA）=bb，c同同理Folllow（BB）=cc2.对下面面的文法 G ： (1)计算这个文法的每个非终结符的 FIRST 集和 FOLLOW 集。(2) 证明这个方法是 LL(1) 的。(3) 构造它的预测分析表。解：（1）计计算这个文文法的每个个非终结符符的FIRRST集和和FOLLLOW集。 FIRSTT集合有： FIRSTT(E)=FIRSST(T)=FIRRST(FF)=FIIRST(P)=(,a,b,; FIRSTT(E')=+, FIRSTT(T)=FIRSST(F)=FIRRST(PP)=(,a,bb,; FIRSTT(T')=FIRRST(TT)=(,aa,b,; FIRSTT(F)=FIRSST(P)=(,a,b,; FIRSTT(F')=FIRRST(PP)=*,; FIRSTT(P)=(,aa,b,; FOLLOOW集合有有： FOLLOOW(E)=),#; FOLLOOW(E'')=FOOLLOWW(E)=),#; FOLLOOW(T)=FIRRST(EE')FOLLLOW(EE)=+,),#;/不包含 FOLLOOW(T'')=FOOLLOWW(T)=FIRSST(E'')FOLLLOW(EE)=+,),#; FOLLOOW(F)=FIRRST(TT')FOLLLOW(TT)=(,a,bb,+,),#;/不包含 FOLLOOW(F'')=FOOLLOWW(F)=FIRSST(T'')FOLLLOW(TT)=(,a,bb,+,),#; FOLLOOW(P)=FIRRST(FF')FOLLLOW(FF)=*,(,aa,b,+,),#;/不包包含 (2)证明明这个方法法是LL(1)的。 各产生式的的SELEECT集合合有： SELECCT(E->TE'')=FIIRST(T)=(,a,b,; SELECCT(E''->+EE)=+; SELECCT(E''->)=FOLLLOW(E/)=),# SELECCT(T->FT'')=FIIRST(F)=(,a,b,; SELECCT(T''->T)=FIRRST(TT)=(,a,bb,; SELECCT(T''->)=FOLLLOW(T/)=+,),#; SELECCT(F->PF'')=FIIRST(P)=(,a,b,; SELECCT(F''->*FF')=*; SELECCT(F''->)=FOLLLOW(F')=(,aa,b,+,),#; SELECCT(P->(E)=( SELECCT(P->a)=a SELECCT(P->b)=b SELECCT(P->)= 可见，相同同左部产生生式的SEELECTT集的交集集均为空，所所以文法GGE是是LL(11)文法。 (3)构造造它的预测测分析表。 文法GEE的预测测分析表如如下： 【题 3】考虑下面的的文法：（1） 求出所有语法变量的FIRSTOP集合和LASTOP集合。（2） 构造文法的算符优先关系表，并判断是否为算符优先文法。（3） 计算文法的算符优先函数。（4） 给出表达式和id*(id+id)的算符优先分析过程。解答：（1） 所有语法变变量的FIIRSTOOP集合和和LASTTOP集合合如下：（2）文法法的算符优优先关系表表算符关 系算 符+-*/()id+-*/（）id因为文法中中任意两个个终结符之之间只存在在一种关系系，因此该该文法为算算符优先文文法。（3） 文法的算符符优先函数数优先函数算符+-*/（）id#（栈内优先先函数）22440440（栈外优先先函数）11335050（4） 表达式的算算符优先分分析过程步骤栈输入串优先关系动作1#+#2#+#移进3#F+#用归约4#F+#移进+5#F+#移进6#F+F#+#用归约7#E#+#用归约表达式idd*(idd+id)的算符优优先分析过过程步骤栈S优先关系当前输入字字符R输入字符串串0#id*(id+id)#1#id*(id+iid)#2#N*(id+iid)#3#N*（id+idd)#4#N*(id+id)#5#N*(iid+id)#6#N*(NN+id)#7#N*(NN+id)#8#N*(NN+id)#9#N*(NN+N)#10#N*(NN)#11#N*(NN)#12#N*N#13#N停止#2.已知文文法 GS 为为： S->a|(TT) T-> TT,S|SS (1) 计计算 GS 的的 FIRRSTVTT 和 LLASTVVT 。 (2) 构构造 GS 的的算符优先先关系表并并说明 GGS 是否为算符优先先文法。 (3) 计计算 GS 的的优先函数数。 (4) 给给出输入串串 (a,a)# 的算符优优先分析过过程。解：（1）各各符号的FFIRSTTVT和LLASTVVT：（2）算符符优先关系系表： 因为文法中中任意两个个终结符之之间只存在在一种关系系，因此该该文法为算算符优先文文法。（3）对应应的算符优优先函数为为： （4）句子子(a,aa)#分析析过程如下下： 知识点 FIRSTTVT 及及 LASSTVT 求法 构造集合 FIRSSTVT （ P ）的两条条规则。 （i）若有有产生式 Pa ，或 PQa ，则 a FIRRSTVTT （ PP ）。 （ii）若若 a FIRRSTVTT （ PP ），且且有产生式式 PQ ，则 a FIRRSTVTT （ PP ）。 构造集合 FIRSSTVT （ P ）的两条条规则 （i）有产产生式Pa，或或PaQ，则则aLASTTVT（PP）。（ii）若若 a LASSTVT （ Q ），且有有产生式 PQ ，则 a FIRRSTVTT （ PP ）。【题 4】1. 令文法G：S BB B aB B b 判判断该文法法是否LRR（1）文文法，若是是构造LRR（1）分分析表。解1）将文文法G拓广广为G：（0）SSS （11）SBB （2）BBAb （3）BBb 2)求出GG的非终终结符的FFOLLOOW和FIIRST集集AFOLLOOW(A)FIRSTT(A)S#a,bS#a,bBa,b,#a,b3）构造个个G的LLR(1)的项目集集族及GOO函数I5:SBB.,#I2:SB.B,# B.Ab,# B.b,#I1:SS.,# BBI7:Bb.,#I6:Ba.B,# B.Ab,# B.b,# S B aa bI0:S.S,# S.BB,# B.aB,a|b B.b,a|bI9:BaB.,# BI3:Ba.B,a|b B.aB,a|b B.b,a|b a a aI8:BaB.,a|b B bI4:Bb.,a|b b3)判断文文法是否为为LR（11）文法。 该该文法构出出的CI0, I1, I2, I3, I4, I5, I6, I7, I8, I9中，每每个状态集集均无冲突突，所以该该文法是LLR（1）文文法。4）构造LLR(1)分析表状态ACTIOONGOTOab#SB0S3S4121acc2S6S753S3S484r3r35r16S6S77r38r2r29r2填空题1.消除左左递归（PP124）文法左递归归问题:一一个文法是是含有左递递归的，如如果存在非非终结符PP。u 直接消除见见诸于产生生式中的左左递归： 假假定关于非非终结符PP的规则为为PPa | b,其中b不以P开开头。那么么，我们可可以把P的的规则等价价地改写为为如下的非非直接左递递归形式：PbP¢¢P¢aPP¢|e 一一般而言，假假定关于PP的全部产产生式是PPPa1 | Pa2 | | PPam | b1 | b2|bn,其中中，每个aa都不等于于e，而每个个b都不以PP开头,那那么，消除除P的直接接左递归性性就是把这这些规则改改写成： Pb1PP¢ | b2P¢ | | bnP¢P¢a11P¢ | a2P¢ | | amP¢ | e例 文文法 EEET | T TTT*F | F F(E) | i 经经消去直接接左递归后后变成： ETTE¢ E¢+TE¢ | e TFFT¢ T¢*FT¢ | e F(E) | i 例例如文法SQc|cQRb|bRSa|a 虽虽没有直接接左递归，但但S、Q、RR都是左递递归的 SÞQcÞRbcÞSabccu 一个文法消消除左递归归的条件：1) 不含以e为为右部的产产生式（无无空产生式式）；2) 不含回路。u 消除左递归归的算法：1. 把文文法G的所所有非终结结符按任一一种顺序排排列成P11，P2，Pn；按此顺序执行；2. FOOR ii:=1 TO n DO BEEGIN FFOR j:=11 TOO i-1 DDO 把把形如PiiPjg的规则改改写成 PPid1g|d2g|dkg ; (其中Pjjd1|d2|dk是关于于Pj的所所有规则) 消除除关于Pii规则的直直接左递归归性 ENND3. 化简简由2所得得的文法。即即去除那些些从开始符符号出发永永远无法到到达的非终终结符的产产生规则。例 考考虑文法GG(S)SQc|cQRb|bRSa|a令它的非终终结符的排排序为R、QQ、S。对对于R，不不存在直接接左递归。把R代入到到Q的有关关候选后，把把Q的规则则变为QSab | abb | bb，现在的的Q不含直直接左递归归。把Q代入到到S的有关关候选后，SS变成SSabcc | aabc | bc | c，由由于SSabcc | aabc | bc | c存存在直接左左递归，消消除S的直直接左递归归后：SabcSS¢ | bbcS¢ | ccS¢S¢¢abcSS¢ | eQSab |ab | bRSa|aa关于Q和RR的规则已已是多余的的，化简为为： SSabcSS¢ | bbcS¢ | ccS¢ SS¢abcSS¢ | e注意：由于于对非终结结符排序的的不同，最最后所得的的文法在形形式上可能能不一样。但但不难证明明，它们都都是等价的的。同样：例例 考虑虑文法G(S)SQc|cQRb|bRSa|a非终结符排排序选为SS、Q、RR，那么， R Qca|ca|aa R Rbcaa|bcaa|ca|a最后所得的的无左递归归文法是： SQc | c QRb | b RbcaRR¢ | ccaR¢ |a R¢ R¢¢ bcaa R¢ | e不同排序所所得的文法法的等价性性是显然的的。2. 文法的分类类(Choomskyy体系)（PP41）（1）短语语结构文法法（PSGG）如果G满足足文法定义义的要求，则则是型型文法（短短语结构文文法PSGG: Phhrasee Strructuure GGrammmar ）。L(G)为为PSL。（1）上下下文有关文文法(CSSG)如果对于，均均有|成立(除外)，则称为型文文法。即：上下文有有关文法（CCSG） L(G)为为1型/上上下文有关关/敏感语语言(CSSL)。其其他定义方方法：设文文法GSS，若PP中任一产产生式的形式式为 ,其中,(VT）*,AA V。（2） 上下文无关关文法(CCFG)如果对于，均均有|，并且且V成立立，则称GG为型文文法。即：上下文无无关文法(CFG:)L(G)为为2型/上上下文无关关语言（CCFL），CCFG能描描述程序设设计语言的的多数语法法成分。（3）正规规（则）文文法(RGG)设,，wT+或为为，如果对对于,均具有如如下形式：右线性(RRightt Linnear)文法：或或左线性(LLeft Lineear)文文法：或都是型文文法(正规规文法RGG)，L(G)为33型/正规规集/正则则集/正则则语言（RRL），能能描述程序序设计语言言的多数单单词。左、右右线性文法法不可混用用。例正规规文法（RRG）：G1：S®®0 | 1 | 00 | 11 G3：S®®0 | 1 | 0A | 1B，AA ®0，B ®1G5：S®®0 | 0SG8：A®®aS | bS | cSS | aa | bb | cc上下文无关关文法（CCFG）：G2：S®®A | B | AA | BB, A ®®0，B ®1 G4：S®®A | B | BB, A ®0，B ®1 G14：SS®0 | 1 | 2 | 3 | 0S0 | 1SS1 | 2S2 | 3SS3上下文有关关文法（CCSG）：G：SCDDCaCCACACCaCaDdaDdAcdecl = (，T，)是是一个文法法, P*G是00型文法，LL(G)是是0型语言言；-其能力相相当于图灵灵机*|:G是是1型文法法，L(GG)是1型型语言(除除);-其识识别系统是是线性界限限自动机*N : G是2型型文法，LL(G)是是2型语言言;-其识别系系统是不确确定的下推推自动机*AaaB或Aa: GG是右线性性文法，LL(G)是是3型语言言ABaa或A: GG是左线性性文法，LL(G)是是3型语言言-其其识别系统统是有穷自自动机3.逆波兰兰表示法逆波兰表达达式又叫做做后缀表达达式。在通通常的表达达式中，二二元运算符符总是置于于与之相关关的两个运运算对象之之间，所以以，这种表表示法也称称为中缀表表示。波兰兰逻辑学家家J.Luukasiiewiccz于19929年提提出了另一一种表示表表达式的方方法。按此此方法，每每一运算符符都置于其其运算对象象之后，故故称为后缀缀表示。将一个普通通的中序表表达式转换换为逆波兰兰表达式的的一般算法法是： (1) 首先构造一一个运算符符栈，此运运算符在栈栈内遵循越越往栈顶优优先级越高高的原则。 (2) 读入一个用用中缀表示示的简单算算术表达式式，为方便便起见,设设该简单算算术表达式式的右端多多加上了优优先级最低低的特殊符符号“#”。 (3) 从左至右扫扫描该算术术表达式，从从第一个字字符开始判判断，如果果该字符是是数字，则则分析到该该数字串的的结束并将将该数字串串直接输出出。 (4) 如果不是数数字，该字字符则是运运算符，此此时需比较较优先关系系。做法如如下：将该该字符与运运算符栈顶顶的运算符符的优先关关系相比较较。如果，该该字符优先先关系高于于此运算符符栈顶的运运算符，则则将该运算算符入栈。倘倘若不是的的话，则将将栈顶的运运算符从栈栈中弹出，直直到栈顶运运算符的优优先级低于于当前运算算符，将该该字符入栈栈。 (5)重重复上述操操作(3)-(4)直至扫描描完整个简简单算术表表达式，确确定所有字字符都得到到正确处理理，我们便便可以将中中缀式表示示的简单算算术表达式式转化为逆逆波兰表示示的简单算算术表达式式。逆波兰表达达式，它的的语法规定定，表达式式必须以逆逆波兰表达达式的方式式给出。逆逆波兰表达达式又叫做做后缀表达达式。这个个知识点在在数据结构构和编译原原理这两门门课程中都都有介绍，下下面是一些些例子： 正常的表达达式 逆波波兰表达式式 a+b -> a,b,+ a+(b-c) -> a,b,c,-,+ a+(b-c)*dd -> a,b,c,-,d,*,+ a+d*(b-c)->>a,d,b,c,-,*,+ a=1+33 -> a=1,3 + http=(smttp+htttp+ttelneet)/11024 ->>httpp=smttp,htttp,ttelneet,+,+,10024,/4. 三地址码的的几种表示示（）四元元式 （op，aarg1，aarg2，rresullt）例：x:=y opp z 的的四元式(op，yy，z，xx)例：a:=b * -c + b* -c(，c，_，T1)(*，b，TT1，T2)(，c，_，T3)(*，b，TT3，T4)(+，T22，T4，T5)(:=，TT5，_，aa)（）三元元式 为了避免把把临时变量量填入符号号表，用中中间代码地地址（指针针）代表运运算对象。（op，aarg1，aarg2）例：a:=b * -c + b * -c(0)(，c，_ )(1)(*，b，(0)(2)(，c，_ )(3)(*，b，(2)(4)(+，(1)，(3)(5)(:=，a，(4)例：xii:= y(0)(= ，xx，i)(1)(:=，y,（0）)用用两条三元元式表示索索引赋值。例：x:=yi(0)( =，yy，i) (1)(:=，x，(0)例9 将下下列语句翻翻译为逆波波兰表示(后缀式)、三元式式和四元表表示： a:=(b+c)*ee+(b+c)/ff【解】解题题思路把中缀式式转换为后后缀式的简简单方法：按中缀式式中各运算算符的优先先规则，从从最先执行行的部分开开始写，一一层层套。如如ab+cada+be，先把把b+c写写为bc+；然后把把a套上去，成成为abcc+；再把aad表示示为ad；然后把把套上去，成成为abcc+ad，依此类类推。四元式由由4个部分分组成：算算符op、第第1和第22运算量aarg1和和arg22，以及运运算结果rresullt。运算算量和运算算结果有时时指用户自自定义的变变量，有时时指编译程程序引进的的临时变量量。如果oop是一个个算术或逻逻辑算符，则则resuult总是是一个新引引进的临时时变量，用用于存放运运算结果。三元式只只需3个域域：op、aarg1和和arg22。与四元元式相比，三三元式避免免了临时变变量的填入入，而是通通过计算这这个临时变变量的语句句的位置来来引用这个个临时变量量。我们很很容易把一一个算术表表达式或一一个赋值句句表示为四四元式序列列或三元式式序列。解答逆逆波兰表示示为：bcc+e*bbc+f/+:=三元式序序列为：(1)(+，b，cc)(2)(* ，(1) ，ee)(3)(+ ，bb，c)(4)(/ ，(3) ，ff)(5)(+ ，(2) ，(4)(6)(:= ，aa，(5)四元式序序列为：(1)(+ ，bb，c，TT1)(2)(* ，TT1，e，TT2)(3)(+ ，bb，c，TT3)(4)(/ ，TT3，f，TT4)(5)(+ ，TT2，T44，T5)(6)(:= ，TT5，-，aa)练习给给出下列表表达式的逆逆波兰表示示、四元式式和三元式式形式。（）（）（） 句柄设有CFGG G=(V,T,P,S),G的句句型的最左左直接短语语称为句柄柄。附：定义22.27 设有CFFG G=(V，TT，P，SS)，(VT)*，SS，A，则称是句型的相相对于变量量A的短语语(phrrase)；如果此此时有A，则称是句型的相相对于变量量A的直接接短语。在在无意义冲冲突时，简简称为句型型的直接短短语,直接接短语也叫叫做简单短短语。例 对对于文法的的句型来说说，它的短短语有：，。其中直直接短语有有：，。而就是句句型的句柄柄。6. 综合属性和和继承属性性如果节点的的属性值是是通过分析析树中该节节点或其子子节点的属属性值计算算出来的，则则称其为综综合属性；如果节点点的属性值值是由该节节点、该节节点的兄弟弟节点或父父节点的属属性值计算算出来的，则则称其为继继承属性。例1 文法符号号的属性有有综合属性性和继承属性性两种。例2 S属性文法法中的每个个文法符号号，只含有有综合属性。例3 终结符只只有综合属性，它它们有词法法分析器提提供。7. 语法制导定定义（0） s'->sspriintf（“0”）；（1） s->BBB prrintff（“1”）； （2） B->aBB pprinttf（“2”）； (3)BB->b priintf（“3”）； 输入#bab# 输出结果是33210