《编译原理》复习.ppt

编译原理复习课 Relaxed 一个简单的世界 A simple world 考核方式 闭卷考试，时间110分钟 共三大题： 判断（10道，每题2分） 选择（10道，每题2分） 综合（7道，6题8分，1题12分） 评分方式 总评成绩=期末成绩x70%+期中成绩x20%+平时成绩x10% 考试范围 前五章，其中2,3,4章是重点。 第一章 编译器概述 能够区分低级语言、高级语言、机器语言、源语言、目标语言、翻译器(translator)、编译器(compiler)、 解释器(interpreter)、 解释型语言 、编译型语言 了解编译器的组成及各部分功能 编译器各组成的分组依据 第二章 词法分析 了解词法分析器的作用 熟悉状态转换图、NFA、DFA的特点 会写简单的正规式，会描述简单正规式所表示的正规集和语言 会画简单正规式的DFA的状态转化图 第三章 语法分析 掌握上下文无关文法的基本定义，会(或根据正规式)设计简单语言的上下文无关文法，能描述具体上下文无关文法所对应的语言或正规式 掌握LL(1)文法的判断方法及消除左递归、提左因子的方法，熟悉预测分析过程 掌握SLR(1)、规范的LR(1)、LALR(1)文法分析表的构造方法及判断方法，熟悉移进-规约分析过程 第四章 语法制导的翻译 熟悉语法制导翻译的思想 熟悉综合属性和继承属性的定义，以及S属性和L属性的特点 掌握语法制导定义的方法，能够为简单的文法编写语法制导定义 掌握翻译方案的方法，能够为简单的文法编写翻译方案 第五章 类型检查 熟悉类型在程序设计中的作用 能够以实际语言中的实例来说明静态检查中涉及的检查类别 复习习题课 第二章 词法分析 第三章 语法分析 第四章 语法制导的翻译 第五章 类型检查 第二章 词法分析 1、一字母表Σ={a, b}，试写出Σ上所有以a为首的字组成的正规集相对应的正规式。 a ( a | b )* 2、令Σ={a,b}，则正规式a*b|b*a 表示的正规集是什么？ {a,b,ab,ba,aab,bba……} 3、令Σ={a,b}，则正规式(ab|a)*表示的 第二章 词法分析 3、描述由正规式b*(abb*)*(a| ᵋ)定义的语言，并画出接受该语言的最简DFA。 不含子串aa的所有串的集合。最简DFA如下： 4、描述由正规式b*a(bb*a) *b*定义的语言，并画出接受该语言的最简DFA。 该正规式定义的语言是：至少含一个a，但不含子串aa的所有a和b的串集。最简DFA如下： 第三章 语法分析 1、令Σ={a,b}，则正规式(ab|a)*表示的正规集所对应语言的上下文无关文法是？ NFA: DFA: 化简： 得文法： G: A→aB|a|ε； B→aB|bA|a|b|ε；可化简为：G: A→aB|ε；B→aB|bA|ε 第三章 语法分析 2、令Σ={a,b}，为字母表{a,b}上的下列每个语言设计一个文法。 a和b的个数相等的所有串。 a和b的个数不相等的所有串。 S-abS | bA |ε S-aB | bA |ε A-aS | bAA B-bS | aBB 第三章 语法分析 3、令Σ={0,1}，设计一个文法，使得在每一个0后至少立即跟随一个1的由0和1组成的符号串的全体。 S  1S | 01S |  (1|01)* 第三章 语法分析 4、考虑文法 G[S]: S → (T) | a+S | a T → T,S | S 消除文法的左递归及提取公共左因子。 消除文法G[S]的左递归： S→(T) | a+S | a ，T→ST′ ，T′→,ST′| ε 提取公共左因子： S→(T) | aS′，S′→+S | ε ，T→ST′ ，T′→,ST′| ε 第三章 语法分析 5、对下面的文法 G ： E-TE E-+TE|ᵋ T-FT T-*FT|ᵋ F-(E)|id (1)计算这个文法的每个非终结符的 FIRST 集和 FOLLOW 集。 (2)证明这个方法是 LL(1) 的。 (3)构造它的预测分析表。 第三章 语法分析 6、 证明下面文法是LL(1)的但不是SLR(1)文法. S  A a A b | B b B a A   B   First(AaAb)={a} First(BbBa)={b} First(AaAb) ∩First(BbBa) = ᵩ 所以文法是LL(1)的。 构造SLR(1)项目集: I0: S’ - .S S - .AaAb S - .BbBa A - . B - . Follow(A) = Follo