编译原理期末复习资料完整版.docx

《编译原理期末复习资料完整版.docx》由会员分享，可在线阅读，更多相关《编译原理期末复习资料完整版.docx（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理期末复习资料【题 1】1. a|b*aa|bba|b*画出状态转换图。IaIb 1,2,32,3,42,3,5 2,3,42,3,4,6,7,82,3,5 2,3,52,3,42,3,5,6,7,8 2,3,4,6,7,82,3,4,6,7,82,3,5,7,8 2,3,5,6,7,82,3,4,7,82,3,5,6,7,8 2,3,5,7,82,3,4,7,82,3,5,6,7,8 2,3,4,7,82,3,4,6,7,82,3,5,7,8IaIb123243325446575675746 新的状态转换图如下： 1A=1,2,3，B=4,5,6,7 Aa=2,4 2A=1,3，B=2

2、，C=4,5,6,7 Aa=2B，Ab=3,5 3A=1，B=2，C=3,D=4,5,6,7单元素可以不用看，必有，古先看D Da=4,7D，Db=5,6D，Aa=2B，Ab=3C，Ba=4D，Bb=3C，Ca=2B，Cb=5C，那么有ab ABC BDCCBDDDD2. a*|b*bba*的状态转换图。IaIb 1,2,3,42,43,4,5,6,8 2,42,45,6,8 3,4,5,6,8-3,4,5,6,7,8 5,6,8-7 3,4,5,6,7,86,83,4,5,6,7,8 76,8- 6,8-7IaIb1232243-54-657567-7-6新的状态转换图如下：化简：用终结状态

3、及非终结状态，然后输出状态一样分一类。1A=1,2,6，B=3,4,5,7 Aa=2 2A=1,2，B=6，C=3,4,7，D=5 Cb=5,6 只要有一个不属于任何一个集合，就不行3A=1,2，B=6，C=3，D=4,7，E=5 Ab=3,4 4 A=1，B=2，C=6，D=3，E=4,7，F=5 Aa=2B，Ab=3D，Ba=2B，Bb=4E，Ca=7E，Db=5F，Eb=6C，Fa=7E，Fb=5Fab ABD BBECE-D-FE-CFEF考前须知：学问要点：u 正那么表达式：；是最左边一个字母确定是，其余字母为的随意组合，不包括。a和假设干个a包括0的情形后跟一个b构成的符号串集合a

4、和a后跟假设干个包括0的情形b构成的符号串集合u 状态转换图有穷状态自动机： 【题 2】中语法变量的FOLLOW集。解答：1求表达式文法的语法符号的FIRST集：FIRST(F)=, idFIRST(T)=FIRST(F)=, id FIRST(E)=FIRST(T)=, id FIRST(E)=+，FIRST(T)=*, FIRST(+)=+, FIRST(*)=*FIRST()=FIRST()=FIRST(id)=id2求表达式文法的语法变量的 FOLLOW集：FOLLOW(E) = #, ) FOLLOW(E)= FOLLOW( E ) = #, ) FOLLOW(T) = FIRST(

5、E)-FOLLOW(E)FOLLOW(E)= +,),#FOLLOW(T)= FOLLOW(T)= +,),#FOLLOW(F) = FIRST(T)FOLLOW(T)FOLLOW(T) =*,+,),# 6学问点First集合的求法： First集合最终是对产生式右部的字符串而言的，但其关键是求出非终结符的First集合，由于终结符的First集合就是它自己，所以求出非终结符的First集合后，就可很直观地得到每个字符串的First集合1. 干脆收取：对形如U-a的产生式其中a是终结符，把a收入到First(U)中2. 反复传送：对形入U-P1P2P3Pn的产生式其中P是非终结符，应先把Fi

6、rst(P1)中的全部内容传送到First(U)中,假设P1中有，把First(P2)中的内容传送到First(U)中,类推直到Pi中无。Follow集合的求法： Follow集合是针对非终结符而言的，Follow(U)所表达的是句型中非终结符U全部可能的后随终结符号的集合，特殊地，“$是识别符号的后随符,先干脆参与到S中。1. 干脆收取：留意产生式右部的每一个形如“Ua的组合，把a干脆收入到Follow(U)中。2. 干脆收取：对形如“UP(P是非终结符)的组合，把First(P)中非收入到Follow(U)中。3. 反复传送：对形如UaP的产生式其中P是非终结符或U-aPQ(P,Q为非终结

7、符且Q中含)，应把Follow(U)中的全部内容传送到Follow(P)中。例 文法：SABc Aa| Bb|First集合求法:能由非终结符号推出的全部的开头符号或可能的，但要求这个开头符号是终结符号。如此题A可以推导出a和，所以FIRSTA=a，；同理 FIRSTB=b,;S可以推导出aBc，还可以推导出bc，还可以推导出c，所以FIRST(S=a，b，cFollow集合的求法:紧跟随其后面的终结符号或。但文法的识别符号包含，在求的时候还要考虑到。 详细做法是把全部包含你要求的符号的产生式都找出来，再看哪个有用。 FollowS=如求A的，产生式：SABc Aa| ，但只有SABc 有用。

8、跟随在A后面的终结符号是FIRSTB=b，当FIRSTB的元素为时，跟随在A后的符号就是c，所以 FollowA=b，c同理FollowB=c2.对下面的文法 G ： (1)计算这个文法的每个非终结符的 FIRST 集和 FOLLOW 集。(2) 证明这个方法是 LL(1) 的。(3) 构造它的意料分析表。解：1计算这个文法的每个非终结符的FIRST集和FOLLOW集。 FIRST集合有： FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,; FIRST(E)=+, FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,; FIRST(T)=FIR

9、ST(T)=(,a,b,; FIRST(F)=FIRST(P)=(,a,b,; FIRST(F)=FIRST(P)=*,; FIRST(P)=(,a,b,; FOLLOW集合有： FOLLOW(E)=),#; FOLLOW(E)=FOLLOW(E)=),#; FOLLOW(T)=FIRST(E)FOLLOW(E)=+,),#;/不包含 FOLLOW(T)=FOLLOW(T)=FIRST(E)FOLLOW(E)=+,),#; FOLLOW(F)=FIRST(T)FOLLOW(T)=(,a,b,+,),#;/不包含 FOLLOW(F)=FOLLOW(F)=FIRST(T)FOLLOW(T)=(,a

10、,b,+,),#; FOLLOW(P)=FIRST(F)FOLLOW(F)=*,(,a,b,+,),#;/不包含 (2)证明这个方法是LL(1)的。 各产生式的SELECT集合有： SELECT(E-TE)=FIRST(T)=(,a,b,; SELECT(E-+E)=+; SELECT(E-)=FOLLOW(E/)=),# SELECT(T-FT)=FIRST(F)=(,a,b,; SELECT(T-T)=FIRST(T)=(,a,b,; SELECT(T-)=FOLLOW(T/)=+,),#; SELECT(F-PF)=FIRST(P)=(,a,b,; SELECT(F-*F)=*; SEL

11、ECT(F-)=FOLLOW(F)=(,a,b,+,),#; SELECT(P-(E)=( SELECT(P-a)=a SELECT(P-b)=b SELECT(P-)= 可见，一样左部产生式的SELECT集的交集均为空，所以文法GE是LL(1)文法。 (3)构造它的意料分析表。 文法GE的意料分析表如下： 【题 3】考虑下面的文法：（1） 求出全部语法变量的FIRSTOP集合和LASTOP集合。（2） 构造文法的算符优先关系表，并推断是否为算符优先文法。（3） 计算文法的算符优先函数。（4） 给出表达式和id*(id+id)的算符优先分析过程。解答：（1） 全部语法变量的FIRSTOP集合和

12、LASTOP集合如下：2文法的算符优先关系表算符关 系算 符+-*/()id+-*/id因为文法中随意两个终结符之间只存在一种关系，因此该文法为算符优先文法。（3） 文法的算符优先函数优先函数算符+-*/id#栈内优先函数22440440栈外优先函数11335050（4） 表达式的算符优先分析过程步骤栈输入串优先关系动作1#+#2#+#移进3#F+#用归约4#F+#移进+5#F+#移进6#F+F#+#用归约7#E#+#用归约表达式id*(id+id)的算符优先分析过程步骤栈S优先关系当前输入字符R输入字符串0#id*(id+id)#1#id*(id+id)#2#N*(id+id)#3#N*id

13、+id)#4#N*(id+id)#5#N*(id+id)#6#N*(N+id)#7#N*(N+id)#8#N*(N+id)#9#N*(N+N)#10#N*(N)#11#N*(N)#12#N*N#13#N停顿#2.文法 GS 为： S-a|(T) T- T,S|S (1) 计算 GS 的 FIRSTVT 和 LASTVT 。 (2) 构造 GS 的算符优先关系表并说明 GS 是否为算符优先文法。 (3) 计算 GS 的优先函数。 (4) 给出输入串 (a,a)# 的算符优先分析过程。解：1各符号的FIRSTVT和LASTVT：2算符优先关系表： 因为文法中随意两个终结符之间只存在一种关系，因此该

14、文法为算符优先文法。3对应的算符优先函数为： 4句子(a,a)#分析过程如下： 学问点 FIRSTVT 及 LASTVT 求法 构造集合 FIRSTVT P 的两条规那么。 i假设有产生式 Pa ，或 PQa ，那么 a FIRSTVT P 。 ii假设 a FIRSTVT P ，且有产生式 PQ ，那么 a FIRSTVT P 。 构造集合 FIRSTVT P 的两条规那么 i有产生式Pa，或PaQ，那么aLASTVTP。ii假设 a LASTVT Q ，且有产生式 PQ ，那么 a FIRSTVT P 。【题 4】1. 令文法G：S BB B aB B b 推断该文法是否LR1文法，假设是

15、构造LR1分析表。解1将文法G拓广为G：0SS 1SBB 2BAb 3Bb 2)求出G的非终结符的FOLLOW和FIRST集AFOLLOW(A)FIRST(A)S#a,bS#a,bBa,b,#a,b3构造个G的LR(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 aI8:BaB.,a|b B bI4:Bb.,a|

16、b b3)推断文法是否为LR1文法。 该文法构出的CI0, I1, I2, I3, I4, I5, I6, I7, I8, I9中，每个状态集均无冲突，所以该文法是LR1文法。4构造LR(1)分析表状态ACTIONGOTOab#SB0S3S4121acc2S6S753S3S484r3r35r16S6S77r38r2r29r2填空题1.消退左递归P124文法左递归问题:一个文法是含有左递归的，假设存在非终结符P。u 干脆消退见诸于产生式中的左递归： 假定关于非终结符P的规那么为PPa | b,其中b不以P开头。那么，我们可以把P的规那么等价地改写为如下的非干脆左递归形式：PbPPaP|e 一般而

17、言，假定关于P的全部产生式是PPa1 | Pa2 | | Pam | b1 | b2|bn,其中，每个a都不等于e，而每个b都不以P开头,那么，消退P的干脆左递归性就是把这些规那么改写成： Pb1P | b2P | | bnPPa1P | a2P | | amP | e例 文法 EET | T TT*F | F F(E) | i 经消去干脆左递归后变成： ETE E+TE | e TFT T*FT | e F(E) | i 例如文法SQc|cQRb|bRSa|a 虽没有干脆左递归，但S、Q、R都是左递归的 SQcRbcSabcu 一个文法消退左递归的条件：1) 不含以e为右部的产生式无空产生式

18、；2) 不含回路。u 消退左递归的算法：1. 把文法G的全部非终结符按任一种依次排列成P1，P2，Pn；按此依次执行；2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如PiPjg的规那么改写成 Pid1g|d2g|dkg ; (其中Pjd1|d2|dk是关于Pj的全部规那么) 消退关于Pi规那么的干脆左递归性 END3. 化简由2所得的文法。即去除那些从开始符号动身恒久无法到达的非终结符的产生规那么。例 考虑文法G(S)SQc|cQRb|bRSa|a令它的非终结符的排序为R、Q、S。对于R，不存在干脆左递归。把R代入到Q的有关候选后，把Q的规那么变

19、为QSab | ab | b，如今的Q不含干脆左递归。把Q代入到S的有关候选后，S变成SSabc | abc | bc | c，由于SSabc | abc | bc | c存在干脆左递归，消退S的干脆左递归后：SabcS | bcS | cSSabcS | eQSab |ab | bRSa|a关于Q和R的规那么已是多余的，化简为： SabcS | bcS | cS SabcS | e留意：由于对非终结符排序的不同，最终所得的文法在形式上可能不一样。但不难证明，它们都是等价的。同样：例 考虑文法G(S)SQc|cQRb|bRSa|a非终结符排序选为S、Q、R，那么， R Qca|ca|a R R

20、bca|bca|ca|a最终所得的无左递归文法是： SQc | c QRb | b RbcaR | caR |a R R bca R | e不同排序所得的文法的等价性是明显的。2. 文法的分类(Chomsky体系)P411短语构造文法PSG假设G满意文法定义的要求，那么是型文法短语构造文法PSG: Phrase Structure Grammar 。L(G)为PSL。1上下文有关文法(CSG)假设对于，均有|成立(除外)，那么称为型文法。即：上下文有关文法CSG L(G)为1型/上下文有关/敏感语言(CSL)。其他定义方法：设文法GS，假设P中任一产生式的形式为 ,其中,(VT*,A V。（2

21、） 上下文无关文法(CFG)假设对于，均有|，并且V成立，那么称G为型文法。即：上下文无关文法(CFG:)L(G)为2型/上下文无关语言CFL，CFG能描绘程序设计语言的多数语法成分。3正规那么文法(RG)设,，wT+或为，假设对于,均具有如下形式：右线性(Right Linear)文法：或左线性(Left Linear)文法：或都是型文法(正规文法RG)，L(G)为3型/正规集/正那么集/正那么语言RL，能描绘程序设计语言的多数单词。左、右线性文法不行混用。例正规文法RG：G1：S0 | 1 | 00 | 11 G3：S0 | 1 | 0A | 1B，A 0，B 1G5：S0 | 0SG8：

22、AaS | bS | cS | a | b | c上下文无关文法CFG：G2：SA | B | AA | BB, A 0，B 1 G4：SA | B | BB, A 0，B 1 G14：S0 | 1 | 2 | 3 | 0S0 | 1S1 | 2S2 | 3S3上下文有关文法CSG：G：SCDCaCACACaCaDdaDdAcdecl = (，T，)是一个文法, P*G是0型文法，L(G)是0型语言；-其实力相当于图灵机*|:G是1型文法，L(G)是1型语言(除);-其识别系统是线性界限自动机*N : G是2型文法，L(G)是2型语言;-其识别系统是不确定的下推自动机*AaB或Aa: G是右线

23、性文法，L(G)是3型语言ABa或A: G是左线性文法，L(G)是3型语言-其识别系统是有穷自动机，请留意IF-ELSE及 FOR循环 的特例逆波兰表达式又叫做后缀表达式。在通常的表达式中，二元运算符总是置于及之相关的两个运算对象之间，所以，这种表示法也称为中缀表示。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法。按此方法，每一运算符都置于其运算对象之后，故称为后缀表示。将一个一般的中序表达式转换为逆波兰表达式的一般算法是： (1) 首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原那么。 (2) 读入一个用中缀表示的简洁算术表达式，为便利起见,设该

24、简洁算术表达式的右端多加上了优先级最低的特殊符号“#。 (3) 从左至右扫描该算术表达式，从第一个字符开始推断，假设该字符是数字，那么分析到该数字串的完毕并将该数字串干脆输出。 (4) 假设不是数字，该字符那么是运算符，此时需比较优先关系。做法如下：将该字符及运算符栈顶的运算符的优先关系相比较。假设，该字符优先关系高于此运算符栈顶的运算符，那么将该运算符入栈。倘假设不是的话，那么将栈顶的运算符从栈中弹出，直到栈顶运算符的优先级低于当前运算符，将该字符入栈。 (5)重复上述操作(3)-(4)直至扫描完好个简洁算术表达式，确定全部字符都得到正确处理，我们便可以将中缀式表示的简洁算术表达式转化为逆波

25、兰表示的简洁算术表达式。逆波兰表达式，它的语法规定，表达式必需以逆波兰表达式的方式给出。逆波兰表达式又叫做后缀表达式。这个学问点在数据构造和编译原理这两门课程中都有介绍，下面是一些例子： 正常的表达式 逆波兰表达式 a+b - a,b,+ a+(b-c) - a,b,c,-,+ a+(b-c)*d - a,b,c,-,d,*,+ a+d*(b-c)-a,d,b,c,-,*,+ a=1+3 - a=1,3 + =(smtp+ +telnet)/1024 - =smtp, ,telnet,+,+,1024,/例9 将以下语句翻译为逆波兰表示(后缀式)、三元式和四元表示： a:=(b+c)*e+(b

26、+c)/f【解】解题思路把中缀式转换为后缀式的简洁方法：按中缀式中各运算符的优先规那么，从最先执行的部分开始写，一层层套。如ab+cada+be，先把b+c写为bc+；然后把a套上去，成为abc+；再把ad表示为ad；然后把套上去，成为abc+ad，依此类推。练习给出以下表达式的逆波兰表示（）（） 句柄设有CFG G=(V,T,P,S),G的句型的最左干脆短语称为句柄。附：定义2.27 设有CFG G=(V，T，P，S)，(VT)*，S，A，那么称是句型的相对于变量A的短语(phrase)；假设此时有A，那么称是句型的相对于变量A的干脆短语。在无意义冲突时，简称为句型的干脆短语,干脆短语也叫做

27、简洁短语。例 对于文法的句型来说，它的短语有：，。其中干脆短语有：，。而就是句型的句柄。6. 综合属性和继承属性 2021-2021年已经取消这题假设节点的属性值是通过分析树中该节点或其子节点的属性值计算出来的，那么称其为综合属性；假设节点的属性值是由该节点、该节点的兄弟节点或父节点的属性值计算出来的，那么称其为继承属性。例1 文法符号的属性有综合属性和继承属性两种。例2 S属性文法中的每个文法符号，只含有综合属性。例3 终结符只有综合属性，它们有词法分析器供应。7. 语法制导定义，出如今第四大题的最终一步（0） s-sprintf“0；（1） s-BB printf“1； （2） B-aB printf“2； (3)B-b printf“3； 输入#bab# 输出结果是33210