编译原理课程总复习.ppt

编译原理课程总复习前端：依赖于源语言，独立于目标机器。第二章词法分析器词法记号的描述与识别正规定义的例子

Pascal语言的标识符集合
letterA|B|…|Z|a|b|…|z
digit0|1|…|9
idletter(letter|digit)*正规定义的例子
Pascal无符号数集合，例1946,11.28,63.6E8,1.99E6
digit0|1|…|9
digitsdigitdigit*
optional_fraction.digits|
optional_exponent(E(+||)digits)|
numdigitsoptional_fractionoptional_exponent
简化表示
numdigit+(.digit+)?(E(+|)?digit+)?源程序字符流状态转换图有限自动机有限自动机有限自动机NFA到DFA的转换——子集构造法NFA到DFA的转换——子集构造法NFA到DFA的转换——子集构造法NFA到DFA的转换——子集构造法NFA到DFA的转换——子集构造法NFA到DFA的转换——子集构造法NFA到DFA的转换——子集构造法NFA到DFA的转换——子集构造法NFA到DFA的转换——子集构造法NFA到DFA的转换——子集构造法NFA到DFA的转换——子集构造法NFA到DFA的转换DFA的化简DFA的化简DFA的化简DFA的化简将下图的DFA极小化。00最初的划分是{0,1,2,3}和{4}。
1．状态集合的进一步划分是：
{1,2}，{0,3}和{4}
2．忽略了死状态的影响，会认为它们都不需要再分从正规式到有限自动机从正规式到有限自动机从正规式到有限自动机从正规式到有限自动机从正规式到有限自动机从正规式到有限自动机从正规式到有限自动机从正规式到有限自动机从正规式到有限自动机从语言到确定的有限自动机例：识别={0,1}上能被能5整除的二进制数例：识别={0,1}上能被能5整除的二进制数例：识别={0,1}上能被能5整除的二进制数例：识别={0,1}上能被能5整除的二进制数例：识别={0,1}上能被能5整除的二进制数例：识别={0,1}上能被能5整除的二进制数例：识别={0,1}上能被能5整除的二进制数例：识别={0,1}上能被能5整除的二进制数例：识别={0,1}上能被能5整除的二进制数例：识别={0,1}上能被能5整除的二进制数例：识别={0,1}上能被能5整除的二进制数构造DFA,接受0和1的个数都是偶数的字符串小结第三章语法分析器上下文无关文法与正规式比较语言和文法语言和文法语言和文法正规式FIRST集、FOLLOW集FIRST集合计算方法
若Xa..，则将终结符ａ加入FIRST(X)中
若X，则将加入FIRST(X)中
若XY…，且Y属于非终结符，则将FIRST(Y)\{}加入到FIRST(X)中
若XY1Y2..YK,且Y1,Y2,..Yi-1都是非终结符，且Y1,Y2,..Yi-1的FIRST集合中均包含，则将FIRST(Yj)的所有非元素加入到FIRST(X)中，（j=1,2,..i）.特别地，若Y1~YK均有产生式，则将加到FIRST(X)中。
FOLLOW集合计算方法
对文法开始符号S,置$于FOLLOW(S)中。
若有AB，则将FIRST()\{}加入FOLLOW(B)中。（此处可以为空）
若AB或AB,且*（即属于FIRST()）,则将FOLLOW(A)加入FOLLOW(B)中（此处可以为空）。
FIRST集合及FOLLOW集合的计算方法FIRST集合及FOLLOW集合的计算方法FIRST集合及FOLLOW集合的计算方法FIRST集合及FOLLOW集合的计算方法FIRST集合及FOLLOW集合的计算方法FIRST集合及FOLLOW集合的计算方法FIRST集合及FOLLOW集合的计算方法自上而下分析自上而下分析自上而下分析自上而下分析自上而下分析自上而下分析自上而下分析自上而下分析自上而下分析自下而上自下而上分析LR分析器LR分析器LR分析器LR分析器LR分析器LR分析器LR分析器LR分析器LR分析器构造SLR分析表从DFA构造SLR分析表构造规范的LR分析表构造规范的LR分析表构造LR分析表的一般流程判断文法属于哪类文法第四章语法制导的定义本章要点语法制导的定义句子realid1，id2，id3的带注释的分析树的依赖图S属性定义的自下而上计算S属性定义的自下而上计算S属性定义的自下而上计算S属性定义的自下而上计算S属性定义的自下而上计算L属性定义的自上而下计算翻译方案建立翻译模式L属性的自下而上计算L属性的自下而上计算L属性的