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

《sun编译原理总复习(第24讲)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、总复习■第1章1、编译程序是一种翻译程序，它将高级语言所写的源程序翻译成等价的机器语言或者汇编语言的目标程序。2、编译程序是计算机系统中重要的系统软件！3、解释程序与编译程序的主要区别是解释程序在执行过程中不产生目标程序。4、编译的各个阶段。5、T型图。9/15/20211信息学院孙丽云总复习■第2章1、符号串的基本运算。2、简单的说文法由产生式组成；产生式中的符号分为两类：终结符号和非终结符号。3、推导（最左、最右）、句型、句子、短语、句柄4、乔姆斯基层次中：L3L2L1L09/15/202

2、12信息学院孙丽云已知文法G[E]：E→T

3、E+T

4、E-TT→F

5、T*F

6、T/FF→(E)

7、i（1）该文法的开始符号是什么？（2）请给出该文法的终结符号集合VT和非终结符号集合VN。（3）找出句型T+T*F+i的所有短语、直接（简单）短语、句柄。■第2章例题9/15/20213信息学院孙丽云总复习■第3章1、词法分析程序的输出是单词符号序列。2、DFA的三种表示形式——状态转移图、状态转换表和五元组表示（Q,∑,f,S,Z）；3、正规式向DFA的转换：（1）正规式——NFA;（转换原则见下页）（2

8、）NFA——DFA；（3）DFA的最小化。4、DFA向正规式的转换。9/15/20214信息学院孙丽云若r,s为正则式：123rsr*1r1εεsr12r

9、srs■第3章正则式向NFA转换的原则：例：构造与正则表达式R=ba(a

10、b)*等价的状态最少的DFA，并写出该DFA的五元组形式或状态转换表。9/15/20215信息学院孙丽云递归下降法LL(1)分析法回溯分析方法预测分析方法LR(0)parsingSLR(1)parsingLR(1)parsingLALR(1)parsing自顶向下分析方法从

11、根结点出发构造语法树自底向上分析方法从叶结点出发构造语法树语法分析方法L:由左向右的处理输入L:为输入串构造最左推导L:由左向右的处理输入R:为输入串构造最右推导的逆过程■第4章9/15/20216信息学院孙丽云■第4章1、语法分析方法的各种分类；2、LL(1)分析方法。提示：在此算法中注意First集和Follow集的求法。并且一定要注意分析过程中步骤要完整。（分析步骤见下页总结）例：文法：Sa

12、^

13、(T)TT,S

14、S试判断该文法是否是LL(1)文法。有左递归习题4：P1004.34.74.9

15、……9/15/20217信息学院孙丽云（1）简单直接左递归的消除A→Aα

16、βA→βA’A’→αA’

17、ε1、消除文法中的左递归或提取左因子；■LL(1)分析方法相关知识总结（2）将文法G：A→αβ

18、αγ提取左因子。解：A→αA’A’→β

19、γ2、求改写文法中的非终结符的First集和Follow集；3、判断文法是否是LL(1)文法；一个上下文无关文法G是LL(1)文法，当且仅当对G中每个非终结符A的任何两个不同的规则Aαβ满足：Select(Aα)∩Select(Aβ)=4、若该文法是LL(1

20、)文法，则构造预测分析表；（1）对于First(α)中的每个记号a，都将A→α添加到表项M[A,a]中；（2）若ε在First(α)中，则对于Follow(A)的每个元素a(记号或是$)，都将A→α添加到M[A,a]中。5、根据分析表进行自顶向下的语法分析。9/15/20218信息学院孙丽云■第4章3、LR分析的四种方法——LR(0)、SLR(1)、LR(1)、LALR(1)，并注意4种方法的区别。LR(0)项目初始项目：A.α归约项目：Aα.移进项目：A.a待约项目：A.B例：已知

21、文法G[S]，求其LR(0)的分析表。SaA

22、bBAcA

23、dBcB

24、d9/15/20219信息学院孙丽云■LR分析方法步骤比较——自底向上的语法分析共同点：四种LR分析方法的步骤一样，都有如下四步：(1)拓广文法并对产生式编号；(2)构造识别文法活前缀的DFA，根据DFA判断为何文法；(3)分析表的构造；(4)分析过程。不同点：（2）（3）步骤中略有不同：(1)LR(0)与SLR(1)的DFA的状态（有效项目集）中全为LR(0)项（产生式中加点）,LR(1)与LALR(1)的DFA的状态中全

25、为LR(1)项（由LR(0)项和搜索符组成,并由中括号[]括起来）。(2)分析表：移进项目都一样，在归约项目上不同。9/15/202110信息学院孙丽云■第5章1、词法规则的描述工具、语法规则的描述工具、语义规则的常用描述工具：2、文法符号的语义属性可分为综合属性和继承属性；3、语法制导的翻译，见下例：例：给出文法G[S]：SSaA

26、AAAbB

27、BBcSd

28、e为文法G[S]的相应产生式写出语义动作，使句型AacAd经该翻译方案后，输出为114359/15/202