2022年《编译原理》期末复习资料完整版.docx

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

1、名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -读书之法 ,在循序而渐进 ,熟读而精思编译原理期末复习资料【题 1】1.（ a|b）* （aa|bb）（a|b）* 画出状态转换图；Ia Ib 1,2,3 2,3,4 2,3,5 2,3,4 2,3,4,6,7,8 2,3,5 2,3,5 2,3,4 2,3,5,6,7,8 2,3,4,6,7,8 2,3,4,6,7,8 2,3,5,7,8 2,3,5,6,7,8 2,3,4,7,8 2,3,5,6,7,8 2,3,5,7,8 2,3,4,7,8 2,3,5,6,7,8 2,3,4,7,8 2,3,4,6,7

2、,8 2,3,5,7,8 1 Ia Ib 2 3 2 4 3 3 2 5 4 4 6 5 7 5 6 7 5 7 4 6 新的状态转换图如下：细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 1 页,共 15 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -读书之法 ,在循序而渐进 ,熟读而精思（1） A=1,2,3 , B=4,5,6,7 Aa=2,4 C, Ca=2B ,（2） A=1,3 ,B=2 ,C=4,5,6,7 Aa=2B, Ab=3,5 （3） A=1 ,B=

3、2 ,C=3,D=4,5,6,7（单元素可以不用看,必有,古先看D）Da=4,7D , Db=5,6D, Aa=2B, Ab=3C, Ba=4D , Bb=3Cb=5C,就有a b A B C B D C C B D D D D 2.（ a*|b* ）b（ba） *的状态转换图；Ia Ib 1,2,3,4 2,4 3,4,5,6,8 2,4 2,4 5,6,8 3,4,5,6,8 - 3,4,5,6,7,8 5,6,8 - 7 3,4,5,6,7,8 6,8 3,4,5,6,7,8 7 6,8 - 6,8 - 7 1 Ia Ib 2 3 2 2 4 3 - 5 4 - 6 5 7 5 6 7

4、- 7 - 6 新的状态转换图如下：细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 2 页,共 15 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -读书之法 ,在循序而渐进 ,熟读而精思化简：（用终结状态与非终结状态,然后输出状态一样分一类）；（1） A=1,2,6 , B=3,4,5,7 Aa=2 （2） A=1,2 ,B=6 ,C=3,4,7 ,D=5 Cb=5,6 （只要有一个不属于任何一个集合,就不行）（3） A=1,2 ,B=6 ,C=3 ,D=4,7 ,E=5

5、 Ab=3,4 （4） A=1 ,B=2 ,C=6 ,D=3 ,E=4,7 ,F=5 Aa=2 B,Ab=3 D,Ba=2 B,Bb=4 E,Ca=7 E,Db=5 F,Eb=6 C,Fa=7 E,Fb=5 F a b A B D B B E C E - D - F E - C F E F 留意事项 ：学问要点 ：正就表达式：a*,a|b,ab,ab*,a|b*,aa|b *,a|a*b,a|ab*ab；a*,a,aa,aaa,aa；a|ba或ba,b；ab 和bab*,ab,abab,ababab,细心整理归纳 精选学习资料 第 3 页,共 15 页 - - - - - - - - - -

6、- - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -读书之法 ,在循序而渐进 ,熟读而精思a|b*a|ba|ba|b,a,b,aab,aabb,baba,b 构成的符号串集aa|b是最左边一个字母肯定是a ,其余字母为a、b的任意组合,不包括；a|a*ba,b ,ab,aab ,aaab,aaaab,a 和如干个a（包括 0 的情形）后跟一个合 a|ab*a|* ba|b*ab*a,ab,abb ,abbb,abbbb ,a 和 a 后跟如干个（包括0的情形） b 构成的符号串集合 ：状态转换图（有穷状态

7、自动机）aab* acba*a | babaaa*细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 4 页,共 15 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -读书之法 ,在循序而渐进 ,熟读而精思a|b*ab*a【题 2】1.求如下简洁算术表达式文法Genr中语法变量的FOLLOW集；ETEETE|TFTT*FT|FE|id 解答 ：（1）求表达式文法的语法符号的FIRST 集：FIRSTF= （ , id FIRSTT=FIRSTF=（, id FIRSTE=FIR

8、STT=（, id FIRSTE=+, FIRSTT=*, FIRST+=+, FIRST*=* FIRST （= （ FIRST ）= ） 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 5 页,共 15 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -读书之法 ,在循序而渐进 ,熟读而精思FIRSTid=id （2）求表达式文法的语法变量的 FOLLOW集：FOLLOWE = #, FOLLOWE= FOLLOW E = #, FOLLOWT = FIRSTE- FOL

9、LOWEFOLLOWE= +,# FOLLOWT= FOLLOWT= +,# FOLLOWF = FIRSTT FOLLOWTFOLLOWT =*,+,# 6 学问点 First 集合的求法： First 集合最终是对产生式右部的字符串而言的,但其关键是求出非终结符的 First 集合,由于终结符的 First 集合就是它自己,所以求出非终结符的 First 集合后,就可很直观地得到每个字符串的 First集合1. 直接收取：对形如 U-a 的产生式（其中 a 是终结符）,把 a 收入到 FirstU 中2. 反复传送：对形入 U-P1P2P3 Pn 的产生式（其中 P 是非终结符）,应先把

10、FirstP1 中的全部内容传送到 FirstU 中, 假如 P1中有 ,把 FirstP2 中的内容传送到 FirstU 中, 类推直到 Pi 中无 ；Follow 集合的求法： Follow 集合是针对非终结符而言的,FollowU 所表达的是句型中非终结符 U全部可能的后随终结符号的集合,特殊地,“$” 是识别符号的后随符 , 先直接加入到 S 中；1. 直接收取：留意产生式右部的每一个形如“ Ua ” 的组合,把 a 直接收入到 FollowU 中；2. 直接收取：对形如“ UP ” P 是非终结符 的组合,把 FirstP 中非 收入到 FollowU 中；3. 反复传送：对形如 U

11、aP 的产生式（其中 P是非终结符）或 U-aPQP,Q 为非终结符且 Q中含 ,应把 FollowU 中的全部内容传送到 FollowP 中； 例 文法： SABc Aa| Bb| First 集合求法 : 能由非终结符号推出的全部的开头符号或可能的 ,但要求这个开头符号是终结符号；如此题 A 可以推导出 a 和 ,所以 FIRST（A）=a, ；同理 FIRST （B）=b, ;S 可以推导出 aBc,仍可以推导出 bc,仍可以推导出 c,所以 FIRSTS）=a,b,cFollow 集合的求法 :紧跟随其后面的终结符号或；但文法的识别符号包含,在求的时候仍要考虑到 ；详细做法是把全部包含

12、你要求的符号的产生式都找出来,再看哪个有用；Follow （S）=如求 A 的,产生式： SABc Aa| ,但只有 SABc 有用；跟随在 A 后面的终结符号是 FIRST（ B）=b,当FIRST（B）的元素为 时,跟随在 A 后的符号就是 c,所以 Follow（A ）=b,c同理 Follow （B）=c2.对下面的文法 G ：E TE 1运算这个文法的每个非终结符的 FIRST 集和 FOLLOW 集；E E | 2 证明这个方法是 LL1 的； 3 构造它的猜测分析表；T FTT T |F PF F * F |P E | a | b |解：（ 1）运算这个文法的每个非终结符的 FI

13、RST 集合有：FIRST 集和 FOLLOW 集；FIRSTE=FIRSTT=FIRSTF=FIRSTP=,a,b,; FIRSTE=+, 第 6 页,共 15 页 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -读书之法 ,在循序而渐进 ,熟读而精思FIRSTT=FIRSTF=FIRSTP=,a,b,; FIRSTT=FIRSTT =,a,b, ; FIRSTF=FIRSTP=,a,b,; FIRSTF=FIRSTP=*, ; F

14、IRSTP=,a,b,; FOLLOW 集合有：FOLLOWE=,#; FOLLOWE=FOLLOWE=,#; FOLLOWT=FIRSTE FOLLOWE=+,#;/ 不包含 FOLLOWT=FOLLOWT=FIRSTE FOLLOWE=+,#; FOLLOWF=FIRSTTFOLLOWT=,a,b,+,#;/ 不包含 FOLLOWF=FOLLOWF=FIRSTT FOLLOWT=,a,b,+,#; FOLLOWP=FIRSTFFOLLOWF=*,a,b,+,#;/ 不包含 2证明这个方法是 LL1 的；各产生式的 SELECT 集合有：SELECTE-TE=FIRSTT=,a,b,; SE

15、LECTE-+E=+; SELECTE- =FOLLOWE/=,# SELECTT-FT=FIRSTF=,a,b,; SELECTT-T=FIRSTT=,a,b,; SELECTT- =FOLLOWT/=+,#; SELECTF-PF=FIRSTP=,a,b,; SELECTF-*F=*; SELECTF- =FOLLOWF=,a,b,+,#; SELECTP-E= SELECTP-a=a SELECTP-b=b SELECTP-= 可见,相同左部产生式的SELECT 集的交集均为空,所以文法GE 是 LL1 文法；3构造它的猜测分析表；文法 GE 的猜测分析表如下：【题 3】考虑下面的文法G

16、 ： 第 7 页,共 15 页 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -读书之法 ,在循序而渐进 ,熟读而精思1 ETT（1）求出全部语法变量的FIRSTOP 集合和 LASTOP 集合；2EE（2）构造文法G 的算符优先关系表,并判定G 是否为算符优先文法；3 EET4TFF（3）运算文法G 的算符优先函数；5 TT*6TT/F（4）给出表达式id1id2和 id*id+id 的算符优先分析过程；7FE8 Fid解答 ：（1

17、）全部语法变量的 FIRSTOP 集合和 LASTOP 集合如下：FIRSTOP E , ,*, /, , id FIRSTOP T *, /, , id FIRSTOP F , id LASTOP E , ,*, /, , id LASTOP T *, /, , id LASTOP F , id （2）文法 G 的算符优先关系表算符关 系+ - * / id 算 符+ （id 由于文法中任意两个终结符之间只存在一种关系,因此该文法为算符优先文法；（3）文法G 的算符优先函数* / （）id # 优先函数+ - 算符f （栈内优先函数）2 2 4 4 0 4 4 0 g（栈外优先函数）1 1

18、3 3 5 0 5 0 （4）表达式id1id2的算符优先分析过程步骤栈输入串优先关系动作 第 8 页,共 15 页 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -读书之法 ,在循序而渐进 ,熟读而精思1 # id +id2# #id1用移进id12 #id1+id # 23 #F +id # # # Fid归约4 #F+ id # 2用移进 + 5 #F+id2# 移进id26 #F+F # + # Fid归约7 #E # 用E#

19、 # ET归约表达式 id*id+id 的算符优先分析过程步骤栈 S 优先关系当前输入字符R 输入字符串0 # 2 #N * id+id# 3 #N* （id+id# 4 #N* id +id# 6 #N*N + id# 7 #N*N+ id # 9 #N*N+N # 10 #N*N # 11 #N*N # 第 9 页,共 15 页 12 #N*N # 13 #N 停止# 2.已知文法GS 为：细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - -

20、 - -读书之法 ,在循序而渐进 ,熟读而精思S-a|T T- T,S|S 1 运算 GS 的 FIRSTVT 和 LASTVT ；2 构造 GS 的算符优先关系表并说明 3 运算 GS 的优先函数；GS 是否为算符优先文法；4 给出输入串 a,a# 的算符优先分析过程；解：（ 1）各符号的 FIRSTVT 和 LASTVT ：（2）算符优先关系表：由于文法中任意两个终结符之间只存在一种关系,因此该文法为算符优先文法；（3）对应的算符优先函数为：（4）句子 a,a#分析过程如下：学问点 FIRSTVT 及 LASTVT 求法 第 10 页,共 15 页 - - - - - - - - - 构造

21、集合FIRSTVT （ P ）的两条规章；（i）如有产生式Pa,或 PQa,就a FIRSTVT （ P ）；（ii ）如a FIRSTVT （ P ）,且有产生式PQ,就 a FIRSTVT （ P ）；构造集合FIRSTVT （ P ）的两条规章（i）有产生式P a,或 P aQ,就 aLASTVT （P）；细心整理归纳 精选学习资料 - - - - - - - - - - - - - - -名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -读书之法 ,在循序而渐进 ,熟读而精思（ii ）如a LASTVT （ Q ）,且有产生式PQ,就 a FIRST

22、VT （ P ）；【题 4】1.令文法 G：S BB B aB B b 判定该文法是否LR（1）文法,如是构造LR（1）分析表；解 1）将文法 G拓广为 G：（0）SS （1） SBB （2）BAb （ 3）Bb 2 求出 G的非终结符的FOLLOW和 FIRST 集8, IFIRSTA LR（1）A FOLLOWA S # a,b S # a,b B a,b,# a,b 3）构造个 G的 LR1 的项目集族及GO函数I5:SBB.,#I 1:S S.,# B I 2:SB.B,# B.Ab,# S B a b B.b,#I6:Ba.B,# I7:Bb.,#I 0:S .S,# B S .BB

23、,# a B .aB,a|b a a I 3:Ba.B,a|b B .b,a|b B.aB,a|b B B.b,a|b b B.Ab,# B.b,#I9:BaB.,#I8:BaB.,a|b b I 4:Bb.,a|b9 中,每个状态集均无冲突,所以该文法是3 判定文法是否为LR（1）文法；该文法构出的CI0, I1, I2, I3, I4, I5, I6, I7, I文法；4）构造 LR1 分析表状态a b ACTION # S GOTO B 0 S3 S4 acc 1 2 1 2 S6 S7 r1 5 3 S3 S4 8 4 r3 r3 5 6 S6 S7 r3 7 8 r2 r2 r2 9

24、 填空题1. 排除左递归（ P124）文法左递归问题:一个文法是含有左递归的,假如存在非终结符P；PP直接排除见诸于产生式中的左递归：细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 11 页,共 15 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -读书之法 ,在循序而渐进 ,熟读而精思假定关于非终结符P 的规章为 PP | ,其中 不以 P 开头； 那么,我们可以把P 的规章等价地改写为如下的非直接左递归形式：P PP P|都不等于,一般而言, 假定关于 P 的全部产生式

25、是PP 1 | P 2 | | P m | 1 | 2| | n,其中,每个而每个都不以 P 开头 ,那么,排除P 的直接左递归性就是把这些规章改写成：P 1P | 2P | | nPP 1P | 2P | mP | 例 文法 EET | T TT*F | F F E | i 经消去直接左递归后变成：ETE E +TE | TFT T *FT | F E | i 例如文法 SQc|c Q Rb|b RSa|a 虽没有直接左递归,但S、Q、R 都是左递归的SQcRbcSabc 一个文法排除左递归的条件：1不含以为右部的产生式（无空产生式）；2不含回路；PP排除左递归的算法：1. 把文法 G 的全

26、部非终结符按任一种次序排列成2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如 PiPj 的规章改写成Pi 1 | 2 | | k ; P1,P2, ,Pn；按此次序执行；其中 Pj 1| 2| | k 是关于 Pj 的全部规章 排除关于 Pi 规章的直接左递归性 END 3. 化简由 2 所得的文法；即去除那些从开头符号动身永久无法到达的非终结符的产生规章；例 考虑文法 GS SQc|c Q Rb|b R Sa|a 令它的非终结符的排序为 R、Q、S；对于 R,不存在直接左递归；把 R 代入到 Q 的有关候选后,把 Q 的规章变为 QSab |

27、ab | b,现在的 Q 不含直接左递归；把 Q 代入到 S 的有关候选后,S 变成 SSabc | abc | bc | c,由于 S Sabc | abc | bc | c存在直接左递归,消 除 S 的直接左递归后：细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 12 页,共 15 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -读书之法 ,在循序而渐进 ,熟读而精思SabcS | bcS | cS S abcS | QSab |ab | b RSa|a 关于 Q 和

28、R 的规章已是余外的,化简为：SabcS | bcS | cS S abcS | 留意： 由于对非终结符排序的不同,最终所得的文法在形式上可能不一样；但不难证明, 它们都是等价的；同样： 例 考虑文法 GS SQc|c Q Rb|b R Sa|a 非终结符排序选为 S、Q、R,那么,R Qca|ca|a R Rbca|bca|ca|a 最终所得的无左递归文法是：SQc | c QRb | b RbcaR | caR |a R R bca R | 不同排序所得的文法的等价性是明显的；2.文法的分类 Chomsky 体系 （P41）（1）短语结构文法（PSG）假如 G 满意文法定义的要求,就是型文

29、法（短语结构文法 LG 为 PSL；（1）上下文有关文法 CSG PSG: Phrase Structure Grammar ）；假如对于P ,均有 | | |成立 除外 ,就称为型文法；即：上下文有关文法 （CSG）LG 为 1 型/上下文有关 /敏锐语言 CSL ；其他定义方法： 设文法 GS ,如 P 中任一产生式 的形式为1A 21 2 ,其中 1, , 2V T） *, ,A V ；（2）上下文无关文法 CFG 假如对于 P ,均有 | | |,并且 V 成立,就称 G 为型文法； 即：上下文无关文法 CFG: LG 为 2 型/上下文无关语言（CFL）,CFG 能描述程序设计语言的

30、多数语法成分；（3）正规（就）文法 RG 设 , wT+或为,假如对于 P , 均具有如下形式：右线性 Right Linear 文法：A B 或 A左线性 Left Linear 文法：A B 或 A都是型文法 正规文法 RG,LG 为 3 型 /正规集 /正就集 /正就语言（ RL ）,能描述程序设计语言的多数单词；左、右线性文法不行混用；例正规文法（ RG）：G1：S0 | 1 | 00 | 11 0,B 1 第 13 页,共 15 页 G3：S0 | 1 | 0A | 1B,A G5：S0 | 0S 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - -

31、 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -读书之法 ,在循序而渐进 ,熟读而精思G8：A aS | bS | cS | a | b | c 上下文无关文法（CFG）：G2：S A | B | AA | BB, A 0, B 1 G4：S A | B | BB, A 0,B 1 G14：S 0 | 1 | 2 | 3 | 0S0 | 1S1 | 2S2 | 3S3 上下文有关文法（CSG）：G：SCD CaCA CA Ca CaDdaD dAcdec = , T, 是一个文法 , P * G 是 0 型文法, LG

32、 是 0 型语言； -其才能相当于图灵机* | | |:G 是 1 型文法, LG 是 1 型语言 除 ;-其识别系统是线性界限自动机* N : G 是 2 型文法, LG 是 2 型语言 ;- 其识别系统是不确定的下推自动机* A aB 或 A a: G 是右线性文法,LG 是 3 型语言A Ba 或 A : G 是左线性文法,LG 是 3 型语言 -其识别系统是有穷自动机3.逆波兰表示法,请留意 IF-ELSE及 FOR 循环的特例逆波兰表达式又叫做后缀表达式；在通常的表达式中,二元运算符总是置于与之相关的两个运算对象之间,所以,这种表示法也称为中缀表示；波兰规律学家J.Lukasiewi

33、cz于1929 年提出了另一种表示表达式的方法；按此方法,每一运算符都置于其运算对象之后,故称为后缀表示；将一个一般的中序表达式转换为逆波兰表达式的一般算法是：1第一构造一个运算符栈,此运算符在栈内遵循越往栈顶优先级越高的原就；2读入一个用中缀表示的简洁算术表达式,为便利起见 最低的特殊符号“ #”；,设该简洁算术表达式的右端多加上了优先级3从左至右扫描该算术表达式,从第一个字符开头判定,假如该字符是数字,就分析到该数字串的结 束并将该数字串直接输出；4假如不是数字,该字符就是运算符,此时需比较优先关系；做法如下：将该字符与运算符栈顶的运 算符的优先关系相比较；假如,该字符优先关系高于此运算符

34、栈顶的运算符,就将该运算符入栈；假如不 是的话,就将栈顶的运算符从栈中弹出,直到栈顶运算符的优先级低于当前运算符,将该字符入栈；5重复上述操作 3-4 直至扫描完整个简洁算术表达式,确定全部字符都得到正确处理,我们便可以将中缀式表示的简洁算术表达式转化为逆波兰表示的简洁算术表达式；逆波兰表达式,它的语法规定,表达式必需以逆波兰表达式的方式给出；逆波兰表达式又叫做后缀表 达式；这个学问点在数据结构和编译原理这两门课程中都有介绍,下面是一些例子：正常的表达式 逆波兰表达式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 + http=smtp+http+telnet/1024 -http=smtp,