《编译原理》复习.ppt

《《编译原理》复习.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、编译原理复习课Relaxed一个简单的世界Asimpleworld考核方式闭卷考试，时间110分钟共三大题：判断（10道，每题2分）选择（10道，每题2分）综合（7道，6题8分，1题12分）评分方式总评成绩=期末成绩x70%+期中成绩x20%+平时成绩x10%考试范围前五章，其中2,3,4章是重点。第一章编译器概述能够区分低级语言、高级语言、机器语言、源语言、目标语言、翻译器(translator)、编译器(compiler)、解释器(interpreter)、解释型语言、编译型语言了解编译器的组成及各部分功能编译器各组

2、成的分组依据第二章词法分析了解词法分析器的作用熟悉状态转换图、NFA、DFA的特点会写简单的正规式，会描述简单正规式所表示的正规集和语言会画简单正规式的DFA的状态转化图第三章语法分析掌握上下文无关文法的基本定义，会(或根据正规式)设计简单语言的上下文无关文法，能描述具体上下文无关文法所对应的语言或正规式掌握LL(1)文法的判断方法及消除左递归、提左因子的方法，熟悉预测分析过程掌握SLR(1)、规范的LR(1)、LALR(1)文法分析表的构造方法及判断方法，熟悉移进-规约分析过程第四章语法制导的翻译熟悉语法制导翻译的思想

3、熟悉综合属性和继承属性的定义，以及S属性和L属性的特点掌握语法制导定义的方法，能够为简单的文法编写语法制导定义掌握翻译方案的方法，能够为简单的文法编写翻译方案第五章类型检查熟悉类型在程序设计中的作用能够以实际语言中的实例来说明静态检查中涉及的检查类别复习习题课第二章词法分析第三章语法分析第四章语法制导的翻译第五章类型检查第二章词法分析1、一字母表Σ={a,b}，试写出Σ上所有以a为首的字组成的正规集相对应的正规式。a(a

4、b)*2、令Σ={a,b}，则正规式a*b

5、b*a表示的正规集是什么？{a,b,ab,ba,aab

6、,bba……}3、令Σ={a,b}，则正规式(ab

7、a)*表示的第二章词法分析3、描述由正规式b*(abb*)*(a

8、ᵋ)定义的语言，并画出接受该语言的最简DFA。不含子串aa的所有串的集合。最简DFA如下：4、描述由正规式b*a(bb*a)*b*定义的语言，并画出接受该语言的最简DFA。该正规式定义的语言是：至少含一个a，但不含子串aa的所有a和b的串集。最简DFA如下：start1abb2start2abb10ab第三章语法分析0123baaεε-+1、令Σ={a,b}，则正规式(ab

9、a)*表示的正规集所对应语言

10、的上下文无关文法是？NFA:DFA:化简：得文法：G:A→aB

11、a

12、ε；B→aB

13、bA

14、a

15、b

16、ε；可化简为：G:A→aB

17、ε；B→aB

18、bA

19、ε012aaba-+++12aab-++第三章语法分析2、令Σ={a,b}，为字母表{a,b}上的下列每个语言设计一个文法。a和b的个数相等的所有串。a和b的个数不相等的所有串。S->abS

20、bA

21、εS->aB

22、bA

23、εA->aS

24、bAAB->bS

25、aBB第三章语法分析3、令Σ={0,1}，设计一个文法，使得在每一个0后至少立即跟随一个1的由0和1组成的符号串的全体。S1S

26、

27、01S

28、(1

29、01)*第三章语法分析4、考虑文法G[S]:S→(T)

30、a+S

31、aT→T,S

32、S消除文法的左递归及提取公共左因子。消除文法G[S]的左递归：S→(T)

33、a+S

34、a，T→ST′，T′→,ST′

35、ε提取公共左因子：S→(T)

36、aS′，S′→+S

37、ε，T→ST′，T′→,ST′

38、ε第三章语法分析5、对下面的文法G：E->TEE'->+TE

39、ᵋT->FTT->*FT

40、ᵋF->(E)

41、id(1)计算这个文法的每个非终结符的FIRST集和FOLLOW集。(2)证明这个方法是LL(1)的。(3)构造它的预测分析表。第

42、三章语法分析6、证明下面文法是LL(1)的但不是SLR(1)文法.SAaAb

43、BbBaABFirst(AaAb)={a}First(BbBa)={b}First(AaAb)∩First(BbBa)=ᵩ所以文法是LL(1)的。构造SLR(1)项目集:I0:S’->.SS->.AaAbS->.BbBaA->.B->.Follow(A)=Follow(B)={a,b}存在归约-归约冲突,所以该文法不是SLR(1)文法.第三章语法分析7、证明下面文法是SLR(1)文法,并构造其SLR分析表.EE+T(1)FF*(5

44、)ET(2)Fa(6)TTF(3)Fb(7)TF(4)第三章语法分析I0:E’.EE.E+TE.TT.TFT.FF.F*F.aF.bI1:E’E.EE.+TI2:ET.TT.FF.F*F.aF.bI3:TF.FF.*I4:Fa.I5:Fb.I6:EE+.TT.TFT