编译原理总复习概要

1编译原理复习2第1章引论1、编译的各个过程及其处理对象（6个过程，按照逻辑关系排列）词法分析语法分析语义分析中间代码生成目标代码生成代码优化字符流单词语法短语/语法树中间代码优化了的中间代码有语义信息的语法树注意：每个阶段的处理对象必须熟记！！！这6个步骤的顺序不能颠倒！！！3第1章引论2、理解翻译程序、编译程序、汇编程序分别是什么样的程序以及彼此之间的关系1、翻译程序：2、编译程序：3、汇编程序：高级语言程序（源程序）编译程序低级语言程序（目标程序）汇编语言程序（源程序）汇编程序机器语言程序（目标程序）一种语言程序（源程序）翻译程序另一种语言程序（目标程序）4第3章文法和语言1、几种类型的文法四种文法之间的逐级“包含”关系：2型文法1型文法3型文法0型文法上下文有关文法上下文无关文法5第3章文法和语言2、规范推导和规范归约的含义规范推导：最右推导。规范归约：最左归约。规范推导和规范归约是逆向的过程。6第3章文法和语言3、句型、句子、短语、直接短语、句柄的含义句型：任何能由开始符号推出的符号串。句子：只含有终结符的句型。短语：设αβδ是文法G[S]中的一个句型，如果有S=*αAδ且A=+β，则称β是句型αβδ相对于非终结符A的短语。直接短语：特别的如有A=β，则称β是句型αβδ相对于规则A→β的直接短语（简单短语）。句柄：一个句型的最左直接短语称为该句型的句柄。句柄就是“可归约串”。7第3章文法和语言3、句型、句子、短语、直接短语、句柄的含义表现在语法树中：句型就是树中任意深度的叶子串；句子就是句型中只含终结符的叶子串；短语：每棵子树对应一个短语；直接短语：只有2层的子树所对应的短语；句柄：最左的直接短语。所以，要求短语、直接短语和句柄，就可以根据语法树来求。8第3章文法和语言4、画出句型的树，找出句型相应的短语、直接短语和句柄。例：文法G[E]:E→E+T|T，T→T×F|F，F→（E）|i的一个句型是T×F+i，相应的语法树见右图：EET+TTF×Fi对于句型T×F+i来说：五棵子树对应五个短语（其中2个重复）:T×F，i，T×F+i两层子树的末端结点构成直接短语，两棵两层子树对应两个直接短语：T×F，i位于最左边的两层子树的末端结点构成句柄：T×F9第3章文法和语言5、证明某个句型是规范句型。由规范推导得到的句型称为规范句型。因此，只需要从开始符号出发，根据产生式进行规范推导（即最右推导），最后能到达该句型，则证明完成。例：文法G[E]:E→E+T|T，T→T×F|F，F→（E）|i，证明T×F+i是规范句型。EE+TE+FE+iT+iT×F+i注意：一定要进行规范推导（最右推导）！！！10第3章文法和语言6、理解两种句型分析方法：自上而下分析方法：从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。自下而上分析方法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。11第4章词法分析1、DFA、NFA五元组的具体含义，理解DFA和NFA的区别DFAM=（K,Σ,f,S,Z）NFAM=(K,Σ,f,S,Z)K：有限状态集；K：有限状态集；Σ：有穷字母表；Σ：有穷字母表；f：单值映射函数；f：多值映射函数；S：唯一的初态；S：非空初态集；Z：终态集。Z：终态集。所以，在DFA中没有初始状态集！12第5章自顶向下语法分析方法1、SELECT集的求法对给定的上下文无关文法的产生式A→α，A∈VN，α∈V*，若α≠*ε,则SELECT(A→α)=FIRST(α)若α=*ε,则SELECT(A→α)=(FIRST(α)-{ε})∪FOLLOW(A)13第5章自顶向下语法分析方法例G3[S]:S→aAS→dA→bASA→εSELECT(S→aA)=FIRST(aA)={a}SELECT(S→d)=FIRST(d)={d}SELECT(A→bAS)=FIRST(bAS)={b}SELECT(A→ε)=FOLLOW(A)={#,a,d}若α≠*ε,则SELECT(A→α)=FIRST(α)若α=*ε,则SELECT(A→α)=(FIRST(α)-{ε})∪FOLLOW(A)14第5章自顶向下语法分析方法2、预测分析法①构造预测分析表步骤：(1)求出每条产生式的SELECT集(2)依照SELECT集把产生式填入分析表对每个终结符或‘＃’用a表示若aSELECT(A→)，则把A→放入M[A,a]中，把所有无定义的M[A,a]标上出错标记。15第5章自顶向下语法分析方法FIRSTSTT’S→aS→∧S→(T)T→ST’T’→,ST’T’→εFOLLOWSTT’,a∧(a∧(#)),)ε计算SELECT集SELECT(S→a)={a}SELECT(S→∧)={∧}SELECT(S→(T))={(}SELECT(T→ST’)=First(ST’)={a,∧,(}SELECT(T’→,ST’)={,}SELECT(T’→ε)=Follow(T’)={)}16第5章自顶向下语法分析方法已求得产生式的SELECT集SELECT(S→a)={a}SELECT(S→∧)={∧}SELECT(S→(T))={(}SELECT(T→ST’)={a,∧,(}SELECT(T’→,ST’)={,}SELECT(T’→ε)={)}是LL(1)文法，构造预测分析表如下：a∧(),#SS→aS→∧S→(T)TT→ST’T→ST’T→ST’T’T’→εT’→,ST’注意：必须说明是LL(1)文法！17第5章自顶向下语法分析方法•输入串(a,a)#的分析过程a∧(),#SS→aS→∧S→(T)TT→ST’T→ST’T→ST’T’T’→εT’→,ST’步骤分析栈剩余输入串所用产生式1#S(a,a)#S→(T)2#)T((a,a)#(匹配3#)Ta,a)#T→ST’4#)T’Sa,a)#S→a5#T’aa,a)#a匹配6#)T’,a)#T’→,ST’7#)T’S,,a)#,匹配注意：请记好预测分析法刚开始分析栈中应存放的内容：#S（S为开始符号）注意：用产生式进行替换时，必须将字符反序压入分析栈！18第5章自顶向下语法分析方法a∧(),#SS→aS→∧S→(T)TT→ST’T→ST’T→ST’T’T’→εT’→,ST’步骤分析栈剩余输入串所用产生式8#)T’Sa)#S→a9#)T’aa)#a匹配10#)T’)#T’→ε11#))#)匹配12##接受•输入串(a,a)#的分析过程注意：分析到最后分析栈和剩余输入串均为#才接受！19第6章自底向上优先分析法1、算符优先分析法的思想基本思想：只定义文法中终结符之间的优先关系（不考虑非终结符），并由这种关系指导分析过程。算符优先法每次归约最左素短语而不是句柄。第7章LR分析法1、LR分析法基本思想：根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的K个（K=0）符号就可唯一地确定句柄。LR分析是一种规范归约。LR分析法每次归约的是句柄。2021第7章LR分析法2、几种不同的LR(0)项目开始项目：形如S’→•S的项目，其中S'是文法开始符。即拓广文法开始符的产生式圆点在最左边的项目。移进项目：形如A→α•аβ的项目，其中а∈VT,α,β∈V*。即圆点后面为终结符的项目。待约项目：形如A→α•Bβ的项目，其中B∈VN,α,β∈V*。即圆点后面为非终结符的项目。22第7章LR分析法2、几种不同的LR(0)项目归约项目：形如A→α•的项目，α∈V*,α=ε对应的项目为A→•即圆点在最右端的项目。句柄已形成，可以把α归约为A。接受项目：当归约项目为S’→S•，其中S'是文法开始符即对文法开始符的归约项目。表明输入串可归约为文法开始符，分析结束。23第7章LR分析法3、LR(0)方法aACTIONbcd#EGOTOA状态543210B1S2S3acc4S5S67S8S9r1r1r1r1r110S5S6(0)S’→E(1)E→aА(2)E→bB(3)A→cА(4)A→d(5)B→cB(6)B→d24第7章LR分析法3、LR(0)方法10aACTIONbcd#EGOTOA状态119876Br4r4r4r4r4r2r2r2r2r211S9S8r6r6r6r6r6r3r3r3r3r3r5r5r5r5r5(0)S’→E(1)E→aА(2)E→bB(3)A→cА(4)A→d(5)B→cB(6)B→d25第7章LR分析法输入串bccd＃的LR(0)分析过程步骤状态栈符号栈输入串ACTIONGOTO1234567890#bccd#S303#bccd#S8038#bccd#S80388#bccd#S903889#bccd#####r6110388#bccr511038#bcr5703#br210#accB(11)B(11)B7E1第7章LR分析法4、SLR(1)分析法和LR(1)分析法•SLR(1)分析法只能解决部分“移进--归约”冲突和“归约--归约”冲突；•LR(1)分析法能解决更多的“移进--归约”冲突和“归约--归约”冲突。2627第8章语法制导和中间代码生成1、翻译时的类型检查包括什么内容？运算符分量类型是否相容赋值语句的左右部的类型是否相容形参和实参的类型是否相容……28第8章语法制导和中间代码生成2、表达式的逆波兰式、三元式和四元式表示b*c+b*d逆波兰式：bc*bd*+三元式：四元式：(1)(*,b,c)(1)(*,b,c,t1)(2)(*,b,d)(2)(*,b,d,t2)(3)(+,(1),(2))(3)(+,t1,t2,t3)注意：必须按照从左到右扫描的顺序，不能颠倒！29第8章语法制导和中间代码生成3、控制语句翻译成四元式序列首先画出所给语句的语法树；再根据语法树和翻译规则进行翻译。注意要记得回填！30C→ifEthen{backpatch(E.true,nextstat);C.CHAIN:=E.false}Tp→CS1else/*ifEthenS1else*/{q:=nextstat;emit(jump,－,－,0);/*S1执行完，跳离整个if语句*/backpatch(C.CHAIN,nextstat);Tp.CHAIN:＝merge(q,S1.CHAIN)}S→TpS2/*ifEthenS1elseS2*/{S.CHAIN:＝merge(Tp.CHAIN,S2.CHAIN)}W→while{W.codebegin:＝nextstat}Wd→WEdo/*whileEdo*/{Wd.codebegin:＝W.codebegin;backpatch(E.true,nextstat);Wd.CHAIN:＝E.false}31S→WdS3/*whileEdoS3*/{backpatch(S3.CHAIN,Wd.codebegin);emit(jump,－,－,Wd.codebegin);/*S3执行完，跳至While语句开头*/S.CHAIN:＝Wd.CHAIN)}S→beginLend{S.CHAIN:＝L.CHAIN}S→A{S.CHAIN:＝0}/*赋值句无出口，故置为空链*/Ls→L;{backpatch(L.CHAIN,nextstat)}L→LsS/*L;S*/{L.CHAIN:＝S.CHAIN}L→S{L.CHAIN:＝S.CHAIN}32SWdS3WE1dowhileABCS1ifE2thenCDAX:=Y+ZS→whileEdoS3改写成：W→whileWd→WEdoS→WdS3S→ifEthenS1改写成：C→ifEthenS→CS1whileABdoifCDthenX:＝Y+Z33Wd.begin=100Wd.chain=101W.begin=100E1.begin=100E1.true=100E1.false=101S3.chain=103E2.begin=102E2.true=102E2.false=103S1.chai