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

编译原原理期期末复习习资料【题 11】1. （a|bb）*（aaa|bbb）（aa|b）*画出状状态转换换图。IaIb 11,2,32,3,42,3,5 22,3,42,3,4,66,7,82,3,5 22,3,52,3,42,33,5,6,77,8 22,3,4,66,7,82,3,4,66,7,82,3,5,77,8 22,3,5,66,7,82,3,4,77,82,3,5,66,7,8 22,3,5,77,82,3,4,77,82,3,5,66,7,8 22,3,4,77,82,3,4,66,7,82,3,5,77,8IaIb123243325446575675746 新的状状态转换换图如下下： （1）AA=11,2,3，BB=44,5,6,77 Aa=2,4 ×（2）AA=11,3，B=2，C=4,5,66,7 AAa=2BB，Abb=33,5 ×（3）AA=11，BB=22，CC=33,DD=44,5,6,77（单单元素可可以不用用看，必必有，古古先看DD） Da=4,7DD，Dbb=55,6D，AAa=2BB，Abb=33C，BBa=4DD，Bbb=33C，CCa=2BB，Cbb=55C，则则有ab ABC BDCCBDDDD2. （a*|b*）bb（baa）*的的状态转转换图。IaIb 11,2,3,442,43,4,5,66,8 22,42,45,6,8 33,4,5,66,8-3,4,5,66,7,8 55,6,8-7 33,4,5,66,7,86,83,4,5,66,7,8 776,8- 66,8-7IaIb1232243-54-657567-7-6新的状态态转换图图如下：化简：（用用终结状状态与非非终结状状态，然然后输出出状态一一致分一一类）。（1）AA=11,2,6，BB=33,4,5,77 Aa=2 ×（2）AA=11,2，B=6，C=3,4,77，DD=55 Cb=5,6 ×（只要要有一个个不属于于任何一一个集合合，就不不行）（3）AA=11,2，B=6，C=3，D=4,7，EE=55 Ab=3,4 ×（4） A=1，BB=22，CC=66，DD=33，EE=44,7，F=5 AAa=2BB，Abb=33D，BBa=2BB，Bbb=44E，CCa=7EE，Dbb=55F，EEb=6CC，Faa=77E，FFb=5FFab ABD BBECE-D-FE-CFEF注意事事项：知识要要点：u 正则表达达式：；是最左边边一个字字母一定定是，其其余字母母为的任任意组合合，不包包括。a和若若干个aa（包括括0的情情形）后后跟一个个b构成成的符号号串集合合a和aa后跟若若干个（包包括0的的情形）bb构成的的符号串串集合u 状态转换换图（有有穷状态态自动机机）： 【题 22】1.求如如下简单单算术表表达式文文法中语语法变量量的FOOLLOOW集。解答：（11）求表表达式文文法的语语法符号号的FIIRSTT集：FIRSST(FF)=（, idFIRSST(TT)=FFIRSST(FF)=（, id FIRSST(EE)=FFIRSST(TT)=（, id FIRSST(EE')=+，FIRSST(TT')=*, FIRSST(+)=+, FIIRSTT(*)=*FIRSST(（)=（FIRSST(）)=）FIRSST(iid)=idd（2）求求表达式式文法的的语法变变量的 FOLLLOWW集：FOLLLOW(E) = #, ) FOLLLOW(E')= FFOLLLOW( E ) = #, ) FOLLLOW(T) = FIRRST(E')-FOLLLOWW(E)FOLLLOWW(E'')= +,),#FOLLLOW(T')= FFOLLLOW(T)= +,),#FOLLLOW(F) = FFIRSST(TT)FOLLLOWW(T)FOLLLOWW(T'') =*,+,),# 6知识点点Firsst集合合的求法法： Firrst集集合最终终是对产产生式右右部的字字符串而而言的，但但其关键键是求出出非终结结符的FFirsst集合合，由于于终结符符的Fiirstt集合就就是它自自己，所所以求出出非终结结符的FFirsst集合合后，就就可很直直观地得得到每个个字符串串的Fiirstt集合1. 直接收收取：对对形如UU->aa的产产生式（其其中a是是终结符符），把把a收入入到Fiirstt(U)中2. 反复传传送：对对形入UU->PP1P22P3Pn的的产生式式（其中中P是非非终结符符），应应先把FFirsst(PP1)中中的全部部内容传传送到FFirsst(UU)中,如果PP1中有有，把把Firrst(P2)中的内内容传送送到Fiirstt(U)中,类类推直到到Pi中中无。Folllow集集合的求求法： Follloww集合是是针对非非终结符符而言的的，Foolloow(UU)所表表达的是是句型中中非终结结符U所所有可能能的后随随终结符符号的集集合，特特别地，“$”是识识别符号号的后随随符,先先直接加加入到SS中。1. 直直接收取取：注意意产生式式右部的的每一个个形如“Ua”的组组合，把把a直接接收入到到Follloww(U)中。2. 直直接收取取：对形形如“UP”(PP是非终终结符)的组合合，把FFirsst(PP)中非非收入入到Foolloow(UU)中。3. 反反复传送送：对形形如U>aPP的产生生式（其其中P是是非终结结符）或或U->>aPQQ(P,Q为非非终结符符且Q中中含)，应把把Follloww(U)中的全全部内容容传送到到Follloww(P)中。例 文法：SAABc Aa| Bb|Firsst集合合求法:能由非非终结符符号推出出的所有有的开头头符号或或可能的的，但但要求这这个开头头符号是是终结符符号。如如此题AA可以推推导出aa和，所所以FIIRSTT（A）=a，；同同理 FFIRSST（BB）=b,;SS可以推推导出aaBc，还还可以推推导出bbc，还还可以推推导出cc，所以以FIRRST(S）=a，bb，cFolllow集集合的求求法:紧紧跟随其其后面的的终结符符号或。但文文法的识识别符号号包含，在求求的时候候还要考考虑到。 具具体做法法是把所所有包含含你要求求的符号号的产生生式都找找出来，再再看哪个个有用。 Foolloow（SS）=如如求A的的，产生生式：SSABBc AAa| ，但但只有SSABBc 有有用。跟跟随在AA后面的的终结符符号是FFIRSST（BB）=b，当当FIRRST（BB）的元元素为时，跟跟随在AA后的符符号就是是c，所所以 FFolllow（AA）=b，cc同理理Follloww（B）=c2.对下下面的文文法 GG ： (1)计算这个文法的每个非终结符的 FIRST 集和 FOLLOW 集。(2) 证明这个方法是 LL(1) 的。(3) 构造它的预测分析表。解：（11）计算算这个文文法的每每个非终终结符的的FIRRST集集和FOOLLOOW集。 FIRSST集合合有： FIRSST(EE)=FFIRSST(TT)=FFIRSST(FF)=FFIRSST(PP)=(,aa,b,; FIRSST(EE')=+, FIRSST(TT)=FFIRSST(FF)=FFIRSST(PP)=(,aa,b,; FIRSST(TT')=FIRRST(T)=(,a,b,; FIRSST(FF)=FFIRSST(PP)=(,aa,b,; FIRSST(FF')=FIRRST(P)=*,; FIRSST(PP)=(,aa,b,; FOLLLOW集集合有： FOLLLOW(E)=),#; FOLLLOW(E')=FOOLLOOW(EE)=),#; FOLLLOW(T)=FIRRST(E')FOLLLOWW(E)=+,),#;/不不包含 FOLLLOW(T')=FOOLLOOW(TT)=FFIRSST(EE')FOLLLOWW(E)=+,),#; FOLLLOW(F)=FIRRST(T')FOLLLOWW(T)=(,a,b,+,),#;/不包包含 FOLLLOW(F')=FOOLLOOW(FF)=FFIRSST(TT')FOLLLOWW(T)=(,a,b,+,),#; FOLLLOW(P)=FIRRST(F')FOLLLOWW(F)=*,(,a,bb,+,),#;/不包含含 (2)证证明这个个方法是是LL(1)的的。 各产生式式的SEELECCT集合合有： SELEECT(E->>TE'')=FFIRSST(TT)=(,aa,b,; SELEECT(E'->+EE)=+; SELEECT(E'->)=FOOLLOOW(EE/)=),# SELEECT(T->>FT'')=FFIRSST(FF)=(,aa,b,; SELEECT(T'->T)=FIIRSTT(T)=(,a,b,; SELEECT(T'->)=FOOLLOOW(TT/)=+,),#; SELEECT(F->>PF'')=FFIRSST(PP)=(,aa,b,; SELEECT(F'->*FF')=*; SELEECT(F'->)=FOOLLOOW(FF')=(,a,bb,+,),#; SELEECT(P->>(E)=( SELEECT(P->>a)=a SELEECT(P->>b)=b SELEECT(P->>)= 可见，相相同左部部产生式式的SEELECCT集的的交集均均为空，所所以文法法GEE是LLL(11)文法法。 (3)构构造它的的预测分分析表。 文法GE的的预测分分析表如如下： 【题 33】考虑下面面的文法法：（1） 求出所有语法变量的FIRSTOP集合和LASTOP集合。（2） 构造文法的算符优先关系表，并判断是否为算符优先文法。（3） 计算文法的算符优先函数。（4） 给出表达式和id*(id+id)的算符优先分析过程。解答：（1） 所有语法法变量的的FIRRSTOOP集合合和LAASTOOP集合合如下：（2）文文法的算算符优先先关系表表算符关 系算 符+-*/()id+-*/（）id因为文法法中任意意两个终终结符之之间只存存在一种种关系，因因此该文文法为算算符优先先文法。（3） 文法的算算符优先先函数优先函数数算符+-*/（）id#（栈内优优先函数数）22440440（栈外优优先函数数）11335050（4） 表达式的的算符优优先分析析过程步骤栈输入串优先关系系动作1#+#2#+#移进3#F+#用归约4#F+#移进+5#F+#移进6#F+FF#+#用归约7#E#+#用归约表达式iid*(id+id)的算符符优先分分析过程程步骤栈S优先关系系当前输入入字符RR输入字符符串0#id*(idd+idd)#1#id*(id+id)#2#N*(id+id)#3#N*（id+iid)#4#N*(id+id)#5#N*(id+id)#6#N*(N+id)#7#N*(N+id)#8#N*(N+iid)#9#N*(N+NN)#10#N*(N)#11#N*(N)#12#N*NN#13#N停止#2.已知知文法 GSS 为为： S->aa|(T) T-> T,SS|S (1) 计算 GSS 的的 FIIRSTTVT 和 LLASTTVT 。 (2) 构造 GSS 的的算符优优先关系系表并说说明 GGS 是否否为算符优优先文法法。 (3) 计算 GSS 的的优先函函数。 (4) 给出输输入串 (a,a)# 的算算符优先先分析过过程。解：（11）各符符号的FFIRSSTVTT和LAASTVVT：（2）算算符优先先关系表表： 因为文法法中任意意两个终终结符之之间只存存在一种种关系，因因此该文文法为算算符优先先文法。（3）对对应的算算符优先先函数为为： （4）句句子(aa,a)#分析析过程如如下： 知识点点 FIRSSTVTT 及 LASSTVTT 求法法 构造集合合 FIIRSTTVT （ PP ）的的两条规规则。 （i）若若有产生生式 PPa ，或或 PQa ，则则 a FIIRSTTVT （ PP ）。 （ii）若若 a FIIRSTTVT （ PP ），且且有产生生式 PPQ ，则则 a FIIRSTTVT （ PP ）。 构造集合合 FIIRSTTVT （ PP ）的的两条规规则 （i）有有产生式式Pa，或或PaQ，则则aLASSTVTT（P）。（ii）若若 a LAASTVVT （ Q ），且且有产生生式 PPQ ，则则 a FIIRSTTVT （ PP ）。【题 44】1. 令文法GG：S BBB BB aBB BB b 判断该该文法是是否LRR（1）文文法，若若是构造造LR（11）分析析表。解1）将将文法GG拓广为为G：（0）SSS （1）SSBB （22）BAb （33）Bb 2)求出出G的的非终结结符的FFOLLLOW和和FIRRST集集AFOLLLOW(A)FIRSST(AA)S#a,bS#a,bBa,b,#a,b3）构造造个G的LRR(1)的项目目集族及及GO函函数I5:SBB.,#I2:SB.B,# B.Ab,# B.b,#I1:SS.,# BI7:Bb.,#I6:Ba.B,# B.Ab,# B.b,# S B a 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 aaI8:BaB.,a|b B bI4:Bb.,a|b b3)判断断文法是是否为LLR（11）文法法。 该文法法构出的的CI0, I1, I2, I3, I4, I5, I6, I7, I8, I9中，每每个状态态集均无无冲突，所所以该文文法是LLR（11）文法法。4）构造造LR(1)分分析表状态ACTIIONGOTOOab#SB0S3S4121acc2S6S753S3S484r3r35r16S6S77r38r2r29r2填空题1.消除除左递归归（P1124）文法左递递归问题题:一个个文法是是含有左左递归的的，如果果存在非非终结符符P。u 直接消除除见诸于于产生式式中的左左递归： 假定关关于非终终结符PP的规则则为PPa | b,其中中b不以PP开头。那么，我我们可以以把P的的规则等等价地改改写为如如下的非非直接左左递归形形式：PbPP¢P¢aaP¢|e 一般而而言，假假定关于于P的全全部产生生式是PPPa1 | Paa2 | | Pam | b1 | b2|bn,其其中，每每个a都不等等于e，而每每个b都不以以P开头头,那么么，消除除P的直直接左递递归性就就是把这这些规则则改写成成： Pb11P¢ | b2P¢ | | bnP¢P¢aa1P¢ | a2P¢ | | amP¢ | e例 文法 EETT | T TT*FF | F F(E) | i 经消去去直接左左递归后后变成： ETE¢ E¢¢+TEE¢ | e TFT¢ T¢¢*FTT¢ | e F(E) | i 例如文文法SQcc|cQRbb|bRSaa|a 虽没有有直接左左递归，但但S、QQ、R都都是左递递归的 SÞÞQcÞRbccÞSabbcu 一个文法法消除左左递归的的条件：1) 不含以ee为右部部的产生生式（无无空产生生式）；2) 不含回路路。u 消除左递递归的算算法：1. 把把文法GG的所有有非终结结符按任任一种顺顺序排列列成P11，P22，Pnn；按此此顺序执执行；2. FFOR i:=1 TOO nn DDO BEGGIN FFOR j:=1 TOO ii-1 DOO 把形如如PiPjg的规则则改写成成 Pid1g|d2g|dkg ; (其中中Pjd1|d2|dk是关关于Pjj的所有有规则) 消除除关于PPi规则则的直接接左递归归性 ENDD3. 化化简由22所得的的文法。即去除除那些从从开始符符号出发发永远无无法到达达的非终终结符的的产生规规则。例 考虑文文法G(S)SQcc|cQRbb|bRSaa|a令它的非非终结符符的排序序为R、Q、SS。对于于R，不不存在直直接左递递归。把R代入入到Q的的有关候候选后，把把Q的规规则变为为QSabb | ab | bb，现在在的Q不不含直接接左递归归。把Q代入入到S的的有关候候选后，SS变成SSSabbc | abbc | bcc | c，由由于SSabbc | abbc | bcc | c存在在直接左左递归，消消除S的的直接左左递归后后：SSabccS¢ | bcSS¢ | cS¢¢SS¢abccS¢ | eQQSabb |aab | bRRSa|a关于Q和和R的规规则已是是多余的的，化简简为： SabccS¢ | bcSS¢ | cS¢¢ S¢¢abccS¢ | e注意：由由于对非非终结符符排序的的不同，最最后所得得的文法法在形式式上可能能不一样样。但不不难证明明，它们们都是等等价的。同样：例 考虑文文法G(S)SQcc|cQRbb|bRSaa|a非终结符符排序选选为S、Q、RR，那么么， R Qcaa|caa|a R Rbcca|bbca|ca|a最后所得得的无左左递归文文法是： SQc | cc QRb | bb RbcaaR¢ | caRR¢ |aa R¢¢ R¢ bcca RR¢ | e不同排序序所得的的文法的的等价性性是显然然的。2. 文法的分分类(CChommskyy体系)（P441）（1）短短语结构构文法（PPSG）如果G满满足文法法定义的的要求，则则是型文法法（短语语结构文文法PSSG: Phrrasee Sttruccturre GGrammmarr ）。L(G)为PSSL。（1）上上下文有有关文法法(CSSG)如果对于于，均有有|成立立(除外外)，则则称为为型文文法。即即：上下下文有关关文法（CCSG） L(G)为1型型/上下下文有关关/敏感感语言(CSLL)。其其他定义义方法：设文法法GSS，若若P中任任一产生生式的形形式为 ,其中中,(VT）*,AA V。（2） 上下文无无关文法法(CFFG)如果对于于，均有有|，并并且V成立立，则称称G为型文法法。即：上下文文无关文文法(CCFG:)L(G)为2型型/上下下文无关关语言（CCFL），CCFG能能描述程程序设计计语言的的多数语语法成分分。（3）正正规（则则）文法法(RGG)设,，wwT+或或为，如如果对于于,均具有有如下形形式：右线性(Rigght Linnearr)文法法：或左线性(Lefft LLineear)文法：或都是型型文法(正规文文法RGG)，LL(G)为3型型/正规规集/正正则集/正则语语言（RRL），能能描述程程序设计计语言的的多数单单词。左左、右线线性文法法不可混混用。例正正规文法法（RGG）：G1：SS®0 | 1 | 000 | 111 G3：SS®0 | 1 | 00A | 1BB，A ®0，BB ®1G5：SS®0 | 0SSG8：AA®aS | bbS | cSS | a | b | cc上下文无无关文法法（CFFG）：G2：SS®A | B | AAA | BBB, AA ®0，BB ®1 G4：SS®A | B | BBB, A ®®0，BB ®1 G14：S®0 | 1 | 22 | 3 | 0SS0 | 1SS1 | 2SS2 | 3SS3上下文有有关文法法（CSSG）：G：SCCDCaaCACACaCaDDdaDDdAccdeccl = (，TT，)是一一个文法法, P*G是是0型文文法，LL(G)是0型型语言；-其能力力相当于于图灵机机*|:GG是1型型文法，LL(G)是1型型语言(除);-其识别别系统是是线性界界限自动动机*N : GG是2型型文法，LL(G)是2型型语言;-其识别别系统是是不确定定的下推推自动机机*AaB或或Aa: G是右右线性文文法，LL(G)是3型型语言ABBa或AA: G是左左线性文文法，LL(G)是3型型语言-其其识别系系统是有有穷自动动机3.逆波波兰表示示法逆波兰表表达式又又叫做后后缀表达达式。在在通常的的表达式式中，二二元运算算符总是是置于与与之相关关的两个个运算对对象之间间，所以以，这种种表示法法也称为为中缀表表示。波波兰逻辑辑学家JJ.Luukassiewwiczz于19929年年提出了了另一种种表示表表达式的的方法。按此方方法，每每一运算算符都置置于其运运算对象象之后，故故称为后后缀表示示。将一个普普通的中中序表达达式转换换为逆波波兰表达达式的一一般算法法是： (1) 首先构造造一个运运算符栈栈，此运运算符在在栈内遵遵循越往往栈顶优优先级越越高的原原则。 (2) 读入一个个用中缀缀表示的的简单算算术表达达式，为为方便起起见,设设该简单单算术表表达式的的右端多多加上了了优先级级最低的的特殊符符号“#”。 (3) 从左至右右扫描该该算术表表达式，从从第一个个字符开开始判断断，如果果该字符符是数字字，则分分析到该该数字串串的结束束并将该该数字串串直接输输出。 (4) 如果不是是数字，该该字符则则是运算算符，此此时需比比较优先先关系。做法如如下：将将该字符符与运算算符栈顶顶的运算算符的优优先关系系相比较较。如果果，该字字符优先先关系高高于此运运算符栈栈顶的运运算符，则则将该运运算符入入栈。倘倘若不是是的话，则则将栈顶顶的运算算符从栈栈中弹出出，直到到栈顶运运算符的的优先级级低于当当前运算算符，将将该字符符入栈。 (55)重复复上述操操作(33)-(4)直直至扫描描完整个个简单算算术表达达式，确确定所有有字符都都得到正正确处理理，我们们便可以以将中缀缀式表示示的简单单算术表表达式转转化为逆逆波兰表表示的简简单算术术表达式式。逆波兰表表达式，它它的语法法规定，表表达式必必须以逆逆波兰表表达式的的方式给给出。逆逆波兰表表达式又又叫做后后缀表达达式。这这个知识识点在数数据结构构和编译译原理这这两门课课程中都都有介绍绍，下面面是一些些例子： 正常的表表达式 逆波兰兰表达式式 a+b -> aa,b,+ a+(bb-c) -> a,bb,c,-,+ a+(bb-c)*d -> aa,b,c,-,d,*,+ a+d*(b-c)->>a,dd,b,c,-,*,+ a=1+3 ->> a=1,33 + httpp=(ssmtpp+htttp+tellnett)/110244 ->hhttpp=smmtp,htttp,ttelnnet,+,+,10024,/4. 三地址码码的几种种表示（）四四元式 （op，aarg11，arrg2，rresuult）例：x:=y op z 的的四元式式(op，yy，z，xx)例：a:=b * -c + b* -cc(，cc，_，TT1)(*，bb，T11，T2)(，cc，_，TT3)(*，bb，T33，T4)(+，TT2，T4，T5)(:=，TT5，_，aa)（）三三元式 为了避免免把临时时变量填填入符号号表，用用中间代代码地址址（指针针）代表表运算对对象。（op，aarg11，arrg2）例：a:=b * -c + b * -c(0)(，cc，_ )(1)(*，bb，(00)(2)(，cc，_ )(3)(*，bb，(22)(4)(+，(1)，(3)(5)(:=，aa，(44)例：xi:= yy(0)(= ，xx，i)(1)(:=，yy,（00）)用两条条三元式式表示索索引赋值值。例：x:=yi(0)( =，yy，i) (11)(:=，xx，(00)例9 将将下列语语句翻译译为逆波波兰表示示(后缀缀式)、三元式式和四元元表示： a:=(b+c)*e+(b+cc)/ff【解】解解题思路路把中缀缀式转换换为后缀缀式的简简单方法法：按中中缀式中中各运算算符的优优先规则则，从最最先执行行的部分分开始写写，一层层层套。如ab+ccadda+bbe，先先把b+c写为为bc+；然后后把a套上去去，成为为abcc+；再把把add表示为为ad；然后后把套上去去，成为为abcc+ad，依此此类推。四元式式由4个个部分组组成：算算符opp、第11和第22运算量量argg1和aarg22，以及及运算结结果reesullt。运运算量和和运算结结果有时时指用户户自定义义的变量量，有时时指编译译程序引引进的临临时变量量。如果果op是是一个算算术或逻逻辑算符符，则rresuult总总是一个个新引进进的临时时变量，用用于存放放运算结结果。三元式式只需33个域：op、argg1和aarg22。与四四元式相相比，三三元式避避免了临临时变量量的填入入，而是是通过计计算这个个临时变变量的语语句的位位置来引引用这个个临时变变量。我我们很容容易把一一个算术术表达式式或一个个赋值句句表示为为四元式式序列或或三元式式序列。解答逆波兰兰表示为为：bcc+e*bc+f/+:=三元式式序列为为：(1)(+，bb，c)(2)(* ，(11) ，ee)(3)(+ ，b，cc)(4)(/ ，(33) ，ff)(5)(+ ，(22) ，(4)(6)(:= ，aa，(55)四元式式序列为为：(1)(+ ，b，cc，T11)(2)(* ，T11，e，TT2)(3)(+ ，b，cc，T33)(4)(/ ，T33，f，TT4)(5)(+ ，T22，T44，T55)(6)(:= ，TT5，-，a)练习给出下下列表达达式的逆逆波兰表表示