编译原理总复习2013-2014(2)

1、总总 复复 习习n基本概念基本概念1、编译程序的结构（、编译程序的结构（5+2） 词法、语法、语义、中间代码、优化、目标代码词法、语法、语义、中间代码、优化、目标代码 符号表、出错处理符号表、出错处理2、短语、直接短语、句柄（最左直接短语）短语、直接短语、句柄（最左直接短语）3、最左推导、最右推导（规范推导）是最左归约的逆过程、最左推导、最右推导（规范推导）是最左归约的逆过程4、最左归约（规范归约）、最左归约（规范归约）5、短语、素短语（包含终结符）、最左素短语、短语、素短语（包含终结符）、最左素短语6、句型、句子、语言、句型、句子、语言7、语法树与句型的的关系：、语法树与句型的的关系：从左到

2、右连接叶子结点从左到右连接叶子结点n文法知识文法知识1. 四类文法（上下文无关、正规文法、四类文法（上下文无关、正规文法、）文法二义文法二义和语言二义是不同的概念和语言二义是不同的概念; ; 一个语言的文法不是惟一的。一个语言的文法不是惟一的。2. 二义文法：对同一句型存在至少两棵不同的语法树。二义文法：对同一句型存在至少两棵不同的语法树。3. 文法的描述工具文法的描述工具产生式：产生式： 或或 :=正规式：正规式：* （闭包）（闭包） | （或）（或） （连接）（连接）总总 复复 习习3. 正规式、文法、语言的关系正规式、文法、语言的关系 给定正规式，确定文法：给定正规式，确定文法： a*b

3、* 结果：（结果：（SaSSb ） 正规式的等价关系正规式的等价关系 ：(a*b*)* 结果：结果： (ab)* 给定文法，确定正规式：给定文法，确定正规式： SaSSb 结果：结果： a*b* 给定文法，确定语言：给定文法，确定语言： S S1S0SaScabc 结果：结果：ab0 （错）（错）a0c01（正确）（正确） 给定语言，确定文法：给定语言，确定文法： anbn|n0 解答：解答： (1) SaSb|总总 复复 习习n正规文法正规文法n正规式正规式 例如：正规式：例如：正规式：b*(a b*a b*)* 用图描述用图描述 * | 关系关系n正规文法和正规式的等价性正规文法和正规式的

4、等价性n正规式或正规文法转换成等价的正规式或正规文法转换成等价的NFA总总 复复 习习(0|1)*(000|111)(0|1)*正规式或正规文法转换成等价的正规式或正规文法转换成等价的FAnDFA：可以表达为状态转换图或状态转换矩阵：可以表达为状态转换图或状态转换矩阵n 标出初态标出初态=、终态、终态nDFA与与NFA的不同：的不同：一个状态发出多条相同边一个状态发出多条相同边n构造正规式的构造正规式的NFAn构造构造NFA所对应的等价的所对应的等价的DFA：给出转化表给出转化表nDFA的最小化：的最小化：等价状态等价状态总总 复复 习习IaIbi,1,21,2,31,2,41,2,31,2,

5、3,5,6,f1,2,41,2,41,2,31,2,4,5,6,f1,2,3,5,6,f1,2,3,5,6,f1,2,4,6,f1,2,4,5,6,f1,2,3,6,f1,2,4,5,6,f1,2,4,6,f1,2,3,6,f1,2,4,5,6,f1,2,3,6,f1,2,3,5,6,f1,2,4,6,f4f35621iaaaabbbbNFA的确定化例：的确定化例：n语法分析语法分析1、确定的自顶向下、确定的自顶向下LL(1)分析分析 求求FIRST集合和集合和FOLLOW集合集合 LL(1)文法的判别文法的判别 左递归和左公因子的消除左递归和左公因子的消除 构造构造LL(1)分析表分析表n给

6、出给出LL(1)分析表，分析表，对输入串进行分析的过程对输入串进行分析的过程总总 复复 习习adbe#SaHHaMddMAb AbA aM 预测分析表预测分析表S aHHaMd dM Ab A aM e非终结符非终结符FIRST 集集FOLLOW集集SHaa,da,e, a,e#d,bbn对输入串对输入串aaabd#的预测分析过程如下：的预测分析过程如下：步骤步骤分析栈分析栈剩余输入串剩余输入串推导用产生式或匹配推导用产生式或匹配aaabdS aHaaabda匹配匹配HaabdaMddMaaabda匹配匹配dMabdAbdbAabd aMdbMaabda匹配匹配dbMbd dbbdb匹配匹配d

7、dd匹配匹配分析成功分析成功n语法分析语法分析2、自底向上的语法分析、自底向上的语法分析 算符优先分析：算符优先分析：最左素短语最左素短语、求、求FIRSTVT和和LASTVT集合集合 构造优先关系矩阵构造优先关系矩阵 判断算符优先文法：优先关系矩阵中无优判断算符优先文法：优先关系矩阵中无优先关系冲突。先关系冲突。总总 复复 习习算符优先关系表的构造算符优先关系表的构造首先定义如下两个集合：首先定义如下两个集合：FIRSTVT(B)=bB b 或或 B CbLASTVT(B)=aB a 或或 B aC按如下算法计算出给定文法中任何两个终结符对按如下算法计算出给定文法中任何两个终结符对(a,b)

8、之间的优先关系：之间的优先关系： 1) 关系关系n直接看产生式的右部，若出现了直接看产生式的右部，若出现了A ab或或 A aBb,则则a=b 2) 关系关系n求出每个非终结符求出每个非终结符B的的FIRSTVT(B)n若若AaB,则则 bFIRSTVT(B),则则ab计算算符优先关系计算算符优先关系例文法例文法GE：(0) E#E#(1) EE+T(2) ET(3) TT*F(4) TF(5) FP F|P(6) P(E)(7) PiFIRSTVT(E)=#FIRSTVT(E)=+,*, ,(,iFIRSTVT(T)=*, ,(,iFIRSTVT(F)= ,(,iFIRSTVT(P)=(,i

9、LASTVT(E)=#LASTVT(E)=+,*, ,),iLASTVT(T)=*, ,),iLASTVT(F)= ,),iLASTVT(P)=),i(0) E#E# (1) EE+T (2) ET (3) TT*F (4) TF (5) FP F|P (6) P(E) (7) Pi3)关系关系找形如：找形如：ABb的产生式的产生式E#: 则则 LASTVT(E)#E+: 则则 LASTVT(E)+ T*: 则则 LASTVT(T)* P : 则则 LASTVT(P) E): 则则 LASTVT(E)2）关系关系找形如找形如AaB的产生式的产生式#E：则：则 #FIRSTVT(E)+T: 则则

10、 +FIRSTVT(T) *F: 则则 *FIRSTVT(F) F: 则则 FIRSTVT(F)(E: 则则 ( * ( = i # = (0) E#E# (1) EE+T (2) ET (3) TT*F (4) TF (5) FP F|P (6) P(E) (7) PinLR分析分析 例题例题1、LR(k)文法都是无二义性的。文法都是无二义性的。四类项目：移进，待约，归约，接受。四类项目：移进，待约，归约，接受。 (1) 移进：移进： a A c B e (2) 待约：待约： a A c B e (3) 归约：归约： A b (4) 接受接受: S S 总总 复复 习习nLR分析分析 例题例

11、题2、LR(k)文法的判别文法的判别 LR(0)：构造构造LR(0)项目集规范族项目集规范族 构造对应的构造对应的DFA； 构造构造LR(0)分析表分析表 当无任何冲突时即为当无任何冲突时即为LR(0)文法。文法。总总 复复 习习GS拓广拓广为为:(0) S S S a A c B e A b A Ab(1) B dI I0 : S S S a A c B e I I1 : S S I I2 : S a A c B e A b A AbI I3 : S a A c B e A A bI I4 : A b I I5 : S a A c B e B dI I7 : S a A c B eI I8

12、: B d I I9 : S a A c B e I I6 : A A b SaAbbcBedGL= ab+ cdeACTIONGOTOacebd#SAB0S211acc2S433S5S64r2r2r2r2r2r25S876r3r3r3r3r3r37S98r4r4r4r4r4r49r1r1r1r1r1r1nLR分析分析 2、LR(k)文法的判别文法的判别 当冲突可以由相应的当冲突可以由相应的FOLLOW集解决时，即为集解决时，即为SLR(1)文法文法 当冲突不能由相应的当冲突不能由相应的FOLLOW集解决，而可改集解决，而可改用相应的用相应的FIRST集解决时，即为集解决时，即为LR(1)文法

13、文法 对对LR(1)文法合并同心集后可能会有归约文法合并同心集后可能会有归约归约归约冲突。如无产生新的冲突，即为冲突。如无产生新的冲突，即为LALR(1)文法。文法。总总 复复 习习nLR分析分析3、LR(0),SLR(1),LR(1),LALR(1)的关系的关系 是是LR(0)，一定是，一定是SLR(1),LR(1) 是是LR(1)，不一定是，不一定是SLR(1),LR(0)4、构造、构造LR(k)分析表分析表 LR(k)分析表的组成分析表的组成 由由ACTION表和表和GOTO表组成表组成 LR语法分析栈的内容语法分析栈的内容 识别可归前缀的识别可归前缀的DFA状态状态 总总 复复 习习n

14、语法制导翻译和中间代码生成语法制导翻译和中间代码生成1、中间代码生成的依据、中间代码生成的依据 语义规则语义规则2、语义处理的任务语义处理的任务 静态语义检查静态语义检查 生成中间代码（翻译）生成中间代码（翻译）3、语法制导翻译也分为自顶向下和自底向上分析两种语法制导翻译也分为自顶向下和自底向上分析两种总总 复复 习习n语法制导翻译和中间代码生成语法制导翻译和中间代码生成4、语句翻译、语句翻译 条件语句在语义翻译中需要运用回填技术；条件语句在语义翻译中需要运用回填技术； 赋值和说明语句则不需要。赋值和说明语句则不需要。5、属性文法、属性文法 文法的开始符和终结符只有综合属性文法的开始符和终结符

15、只有综合属性 其它还可能存在继承属性其它还可能存在继承属性6、中间代码中间代码 四元式表示四元式表示 表达式的后缀表示形式（逆波兰式）表达式的后缀表示形式（逆波兰式）总总 复复 习习n中间代码优化中间代码优化1、局部优化、局部优化 合并已知量与复写传播、删除多余运算、删除无用赋值合并已知量与复写传播、删除多余运算、删除无用赋值 基本块的划分基本块的划分 0、1、2型四元式的结点形式型四元式的结点形式 基本块的基本块的DAG图应用图应用 程序流图程序流图2、循环优化、循环优化 代码外提、强度削弱、删除基本归纳变量代码外提、强度削弱、删除基本归纳变量 必经结点必经结点回边回边-循环循环总总 复复 习习考 试 要 求 n所有题目在试卷上做答所有题目在试卷上做答 不够位置时，在试卷背面解答题目，标注清楚题号即可。不够位置时，在试卷背面解答题目，标注清楚题号即可。n给出解题过程，按步骤评分给出解题过程，按步骤评分n题目类型及分数比例题目类型及分数比例 单项选择题（单项选择题（10题题2分分=20分）分） 判断正误题（判断正误题（ 10题题1分分=10分）分） 小解答题（小解答题（5小题小题6分分=30分）分） 大解答题（大解答题（4题题10分分=40分）分）考试说明考试说明n