sun编译原理总复习(第24讲).ppt

2019/8/5,信息学院 孙丽云,1,总复习, 第1章,1、编译程序是一种翻译程序，它将高级语言所写的源程序翻译成等价的机器语言或者汇编语言的目标程序。 2、编译程序是计算机系统中重要的系统软件！ 3、解释程序与编译程序的主要区别是解释程序在执行过程中不产生目标程序。 4、编译的各个阶段。 5、T型图。,2019/8/5,信息学院 孙丽云,2,总复习,第2章,1、符号串的基本运算。 2、简单的说文法由产生式组成；产生式中的符号分为两类：终结符号和非终结符号。 3、推导（最左、最右）、句型、句子、短语、句柄 4、 乔姆斯基层次中：L3 L2 L1 L0,2019/8/5,信息学院 孙丽云,3,已知文法GE： ET|E+T|E-T TF|T*F|T/F F(E)|i （1）该文法的开始符号是什么？ （2）请给出该文法的终结符号集合VT和非终结符号集合VN。 （3）找出句型T+T*F+i的所有短语、直接（简单）短语、句柄。,第2章例题,2019/8/5,信息学院 孙丽云,4,总复习,第3章,1、词法分析程序的输出是单词符号序列。 2、 DFA的三种表示形式状态转移图、状态转换表和五元组表示（ Q, , f, S, Z ） ； 3、正规式向DFA的转换： （1）正规式NFA;（转换原则见下页） （2）NFADFA； （3）DFA的最小化。 4、DFA向正规式的转换。,2019/8/5,信息学院 孙丽云,5,若r,s为正则式：,r*,r|s,rs,第3章,正则式向NFA转换的原则：,例：构造与正则表达式R=ba(a|b)*等价的状态最少的DFA，并写出该DFA的五元组形式或状态转换表。,2019/8/5,信息学院 孙丽云,6,递归下降法 LL(1)分析法,回溯分析方法 预测分析方法,LR(0) parsing SLR(1) parsing LR(1) parsing LALR(1) parsing,自顶向下分析方法,从根结点出发构造语法树,自底向上分析方法,从叶结点出发构造语法树,语法分析方法,L:由左向右的处理输入 L:为输入串构造最左推导,L:由左向右的处理输入 R:为输入串构造最右推导的逆过程, 第4章,2019/8/5,信息学院 孙丽云,7, 第4章,1、语法分析方法的各种分类； 2、LL(1)分析方法。 提示：在此算法中注意First集和Follow集的求法。并且一定要注意分析过程中步骤要完整。（分析步骤见下页总结）,例：文法：Sa|(T) TT,S|S 试判断该文法是否是LL(1)文法。有左递归,习题4：P100 4.3 4.7 4.9,（1）简单直接左递归的消除 A A| ,1、消除文法中的左递归或提取左因子；, LL(1)分析方法相关知识总结,（2）将文法G： A|提取左因子。,解： AA A|,2、求改写文法中的非终结符的First集和Follow集； 3、判断文法是否是LL(1)文法； 一个上下文无关文法G是LL(1)文法，当且仅当对G中每个非终结符A的任何两个不同的规则A 满足： Select(A ) Select(A ) = 4、若该文法是LL(1)文法，则构造预测分析表； （1）对于First()中的每个记号a，都将A 添加到表项MA, a中； （2）若在First()中，则对于Follow(A)的每个元素a(记号或是$)，都将A 添加到MA, a中。 5、根据分析表进行自顶向下的语法分析。,2019/8/5,信息学院 孙丽云,9, 第4章,3、LR分析的四种方法LR(0)、SLR(1)、LR(1)、LALR(1)，并注意4种方法的区别。,LR(0)项目 初始项目：A. 归约项目：A . 移进项目： A . a 待约项目： A . B,例：已知文法GS，求其LR(0)的分析表。 S aA | bB A cA | d B cB | d,2019/8/5,信息学院 孙丽云,10, LR分析方法步骤比较,自底向上的语法分析,共同点：四种LR分析方法的步骤一样，都有如下四步： (1)拓广文法并对产生式编号； (2)构造识别文法活前缀的DFA，根据DFA判断为何文法； (3)分析表的构造； (4)分析过程。 不同点：（2）（3）步骤中略有不同： (1)LR(0)与SLR(1)的DFA的状态（有效项目集）中全为LR(0)项（产生式中加点）,LR(1)与LALR(1)的DFA的状态中全为LR(1)项（由LR(0)项和搜索符组成,并由中括号括起来）。 (2)分析表：移进项目都一样，在归约项目上不同。,2019/8/5,信息学院 孙丽云,11,第5章,1、词法规则的描述工具、语法规则的描述工具、语义规则的常用描述工具： 2、文法符号的语义属性可分为综合属性和继承属性； 3、语法制导的翻译，见下例：,例：给出文法GS： S SaA|A A AbB|B B cSd|e 为文法GS的相应产生式写出语义动作，使句型AacAd经该翻译方案后，输出为11435,2019/8/5,信息学院 孙丽云,12,第5章,1、常见的中间语言逆波兰式、三地址码、四元式、三元式、间接三元式、树形表示等； 2、各种语句的中间代码翻译（给出一个语句序列能够写出对应的四元式序列）； 例如：求下列语句的四元式序列。 while(x1 ,第6章,1、符号表的处理是编译程序的重要组成部分； 2、课后习题。,2019/8/5,信息学院 孙丽云,13,第7章,1、会划分基本块，并能够给出其程序流图； 2、中间代码的局部优化 会利用DAG对基本块进行优化。,练习题： 1、将下列三地址码序列划分基本块，并画出程序流图。,read a read b c=a add b if r=0 goto (8) a=b b=c goto (3) write(b) halt,2019/8/5,信息学院 孙丽云,14,练习题： 2、已知一基本块如下,B=3 D=A+C E=A*C F=E+D G=B*F H=A+C I=A*C J=H+I K=B*5,请应用DAG对该基本块进行优化。,2019/8/5,信息学院 孙丽云,15,一、单选题（10分） 二、填空题（10分） 三、判断题（5分） 四、简答题（8分） 五、应用题（67分）7个小题 前面14页PPT提到的知识点+期中考试题+列举的大题题型, 考试题型,2019/8/5,信息学院 孙丽云,16,考试和答疑时间,考试时间：第18周； 答疑时间：考试前1天； 答疑地点：F103,考试注意事项,1、审题仔细，步骤完整； 2、题型是平时练习过的； 3、认真复习，从容应考，诚信考试！,假期作业在公共邮箱： 密码：xinxi2008,2019/8/5,信息学院 孙丽云,17,关于上机,完成并给我讲过语法分析程序的同学，上机成绩为“优”；若去上课可考虑语义分析，或者别的语法分析方法； 完成语法分析程