编译原理总复习知识 （框架+例题）期末复习知识资料教学教案.ppt

1 一、课程基本框架 1、基础知识：文法 2、词法分析 理论模型——正规文法与有限自动机 实现——词法分析程序 3、语法分析 理论模型：自上而下分析——下推自动机 自下而上分析——优先分析和LR分析 实现——递归下降分析法、YACC 4、中间代码生成 语法制导翻译 5、运行时数据区的管理：静态存储管理、栈式存储管理、堆式存储管理 6、中间代码优化：局部优化、循环优化、全局优化 2 二、复习范围 第一章、第三章到第十一章 三、复习方法 1、认真理解书中的基本概念、基本原理与基本算法 2、弄懂书中的例题与习题 3、在看书时或理解例题时，一定要画出相应的细节变化过程，通过画图来加深理解 4、在理解的基础上记忆 四、考试题型 选择、填空、简答和综合 3 2、第三章 a)Chomsky文法 主要掌握上下文无关文法和正规文法 b)由语言构造文法 主要掌握上下文无关文法和正规文法 c)根据算法构造无产生式的上下文无关文法 五、各章主要知识点 1、第一章 基本概念（1.2） 4 题型 一.设计一个文法定义一个已知的语言 二.已知一个文法，确定该文法所定义的语言 三.求句型的短语、直接短语和句柄 四．文法二义性的判断 5 例1.设L1={a2nbn|n=1}，试构造生成L1的文法G1。 【解】设n=1， L1 =aab n=2， L1 =aaaabb n=3， L1 =aaaaaabbb …… 所以得：SaaSb Saab 8 语言L(G)=L(G’) {bn | n0} {bn | n=0} {abn | n0} {bna | n=0} 语言和文法构造方法小结 文法G 文法G’ S→bS | b S→Sb | b S→bS | ε S→Sb | ε S→DB B→bB | b D→a S→aB B→Bb | b S→PD D→a P→bP | ε S→Pa P→Pb | ε 9 {(ab)n | n0} {ambn|m0,n0} {ambn|m=0,n0} {anbn | n0} {a2nbn| n=0} S→ES | E E→ab S→Sab | ab S→AB A→aA | a B→bB | b S→aS | aB B→Bb | b S→AB A→aA | ε B→bB | b S→aS | B B→bB | b S→aSb | ab S→DSH|DH D→a H→b S→aaSb|ε S→KSH | ε K→aa H→b 10 例4  已知文法G[E]： 证明：E+T*F是它的一个句型,画出语法树，并指出这个句型的短语﹑简单短语和句柄。 E→E+T | E-T | T T→T*F | T/F | T T→(E) | i 1.短语、直接短语和句柄是对某句型而言的。 2.短语总是句型的某个子串，它对应子树未端结点形成的符号串。 3.直接短语是某条规则右部，它对应简单子树未端 结点形成的符号串。 4.最左边的直接短语是句柄。 注： 11 ∵ EE+TE+T*F 短语:E+T*F、T*F ∴ E+T*F是它的一个句型。 画出该句型的语法树: 句柄:T*F 直接短语:T*F 12 例5 设有文法G[S]: S→iSeS|iS|i   试证明文法G[S]有二义性。 分析：因为对文法的句子 iiiei 有如下两 棵不同的语法树与之对应，所以该文法 是二义的。 13 S→iSeS| iS | i 句子iiiei对应下面两颗语法树： 14 3、第四章 a)词法分析器的功能？什么是单词？ b)闭包、正则闭包，正规式是什么？ c)NFA确定化 子集法 b)DFA最小化 分割法 c)带边的NFA确定化 使用-闭包 d)正规式、正规文法、自动机之间的转换 15 题型： 1、不确定自动机的确定化 （注意是否带空串） 2、确定自动机的最小化 3、正规式、正规文法、自动机之间的转换。 16 4、第五章 a)构造LL(1)预测分析表 First、Follow、SELECT b)判别文法是否属于LL(1)文法，如果不属于，要会转变成等价的LL（1）文法 c) LL(1)分析过程 17 题型 1、消除左递归 2、提取最左公因子 3、构造LL(1)分析表 4、判断文法是否是LL(1)文法 5、利用