(完整word版)编译原理期末复习总结(word文档良心出品)

1、编译原理复习资料i一、简答题1.什么是编译程序？答：编译程序是一种将高级语言程序（源程序）翻译成低级语言（目标程序）的程序。 将高级程序设计语言程序翻译成逻辑上等价的低级语言（汇编语言，机器语言）程序的翻译程序。2请写出文法的形式定义？答：一个文法 G 抽象地表示为四元组 G=（Vn,Vt,P,S）-其中 Vn 表示非终结符号-Vt 表示终结符号，Vn U Vt= V （字母表）,Vn n Vt= -S 是开始符号，-P 是产生式，形如：a T B （ a V+且至少含有一个非终结符号，B V*）3语法分析阶段的功能是什么？答：在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法

2、短语（例:程序、语句、表达式）。确定整个输入串是否构成语法上正确的程序。4局部优化有哪些常用的技术？答：优化技术 1删除公共子表达式优化技术 2复写传播优化技术 3删除无用代码优化技术 4对程序进行代数恒等变换（降低运算强度）优化技术 5代码外提优化技术 6强度削弱优化技术 7删除归纳变量优化技术简介一一对程序进行代数恒等变换（代数简化） 优化技术简介一一对程序进行代数恒等变换（合并已知量）5 编译过程分哪几个阶段？答：逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目 标代码生成。每个阶段把源程序从一种表示变换成另一种表示。6. 什么是文法？答：文法是描述语言的语法结

3、构的形式规则。 是一种工具，它可用于严格定义句子的结构； 用有穷的规则刻划无穷的集合；文法是被用来精确而无歧义地描述语言的句子的构成 方式；文法描述语言的时候不考虑语言的含义。7. 语义分析阶段的功能是什么？答：对语法分析所识别出的各类语法范畴分析其含义，进行初步的翻译（翻译成中间代码）;并对静态语义进行审查。&代码优化须遵循哪些原则？答：等价原则：不改变运行结果有效原则：优化后时间更短，占用空间更少 合算原则：应用较低的代价取得较好的优化效果9词法分析阶段的功能是什么？答：编译原理复习资料ii-功能：,、T oken串（源程序=A词法分析程序|语法分析程序逐个读入源程序字符并按照构词

4、规则切分成一系列单词任务：读入源程序，输出单词符号滤掉空格，跳过注释、换行符 追踪换行标志，指出源程序出错的行列位置宏展开，.10什么是符号表？ 答：符号表在编译程序工作的过程中需要不断收集、记录和使用源程序中一些语法符号 的类型和特征等相关信息。这些信息一般以表格形式存储于系统中。如常数表、变 量名表、数组名表、过程名表、标号表等等，统称为符号表。对于符号表组织、构 造和管理方法的好坏会直接影响编译系统的运行效率。11.什么是属性文法？答：是在上下文无关文法的基础上，为每个文法符号(含终结符和非终结符)配备若干个属 性值，对文法的每个产生式都配备了一组属性计算规则(称为语义规则)。在语法分析

5、 过程中，完成语义规则所描述的动作，从而实现语义处理。12什么是基本块？答：是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句，入口 是其第一个语句，出口是其最后一个语句。13代码优化阶段的功能是什么？答：对已产生的中间代码进行加工变换，使生成的目标代码更为高效(时间和空间)。14文法分哪几类？答：文法有四种：设有 G=(Vn,Vt,P,S)，不同类型的文法只是对产生式的要求不同：0型文法(短文文法):G 的每个产生式 aB 满足：a V+且 a中至少含有一个非 终结符,B V*1型文法(上下文有关文法)： 如果 G 的每个产生式 a B均满足| B 1=1 a |,仅当 S

6、除外，但 S 不得出现在任何产生式的右部2型文法(上下文无关文法)：G 的每个产生式为 A B , A 是一非终结符，B V* 3型文法(正规文法)：G 的每个产生式的形式都是：A a B 或 A a，其中 A,B 是 非终结符，a是终结符串。(右线性文法)。15循环优化常用的技术有哪些？答：代码外提；强度削弱；删除归纳变量。16什么是算符优先文法？答：算符文法 G 的任何终结符 a,b 之间要么没有优先关系，若有优先关系，至多有，中的一种成立，则 G 为一算符优先文法。二、计算题(一)推导、最左推导、最右推导和语法树，复习表达式文法及相关例题。1.表达式的推导例：G = (E, i, +,

7、*, (,) , P , E)编译原理复习资料3P： E t E+E | E*E | (E) | i答：表达式(i)和(i+i)*i 的推导：E 二(E)二(i)E 二 E*E n (E)*E二(E + E)*E 二(i + E)*E n (i + i)*E n (i + i)*iE 二 E*E 二 E*i n (E)* i 二(E + E)*i n (E+ i)*i = (i + i)*i编译原理复习资料4E占E()步推导1E=(i + i)*i6步推导E(i + i)*i6步推导E“(E)直接推导(i+i)*i 的最左推导过程：E 二 E*E 二(E)*E 二(E + E)*E 二(i +

8、 E)*E n (i + i)*E n (i + i)*i (i+i)*i 的最右推导过程：E n E*E n E*i 二(E + E)*i n (E+ i)*i n (i + i)*i2.语法树例：对文法 G = (E, i, +, *, (, ) , P , E)P： E t E + E | E* E | ( E ) | i 答:句子(i+i)*i 的语法树：例: G = (E, i, +, *, (, ) , P , E)P： E t E + E | E * E | ( E ) | i答:句子(i * i + i)的语法树：编译原理复习资料5(1) E二(E)二(E + E)二(E *

9、E + E) = (i * E + E)二(i *i + i)例2J (P3O)考虑文法G仁它定义了什么语言。推导过程tS=bA=baA=baaS=hA =baA=A” - - a归纳得：L(G1)= ba11|nl例22(P30)考虑文法G2S t ABL(G2)=aUJbu|m.nl(二)给定语言求文法它定义的语言是:A B -bBJb编译原理复习资料6思考：构造一个文法G3使得:L(G3) =辺呵|nl a；b的个数相同，贝?J文法G3为二编译原理复习资料7（三）逆波兰式 K逆波兰式：运算对象写在前，运算符写在后（后缀表示形式）例：a+b+(a+b)*cate*/a+b*c/a:=b*c

10、+b*d -磁財bd*+:二a b写出下列算式的逆波兰表示a+b*(c+d/e)a：=b*(cl+b *(-34)not A or not (C or not D)abc-*b34-* +：=A not C D not or not or后缀式的推广（1）赋值语句A:二E,后缀式为：AE:=（2）转向语句GOTO L的后缀式为：L：jnip （3）条件语句if xy then m:=x else m:=y1234567891011 121314Xy11mX114Jmy 1 b +编译原理复习资料228（四）将for语句和if语句翻译成相应的四元式序列1.if例：将下面的IF语句翻译为四元式序列

11、if A and B and (CD) thenif AB then F:二1else F:=0else G： =G1练习:将下面的语句翻译为四元式序列if (AC) and (BD) thenif A=1 thenC:=C+lelse ifAWD then A:=A+2L2.3.4_5.6.7.810.j?C?D?7)6- (j亠5 亠IQ9.(：=丄10. a-;i 5) lk(:=A_,F)12- D)/*AB的四元式引/*F :=1的四元式 T/*F： =0的四元式吟13/+;G?LT) /*G:=G+1的四元式灯14.(：=工G)15.(j, A, C, 3) (j厂,-，14) (

12、j - 14)(j=, A, 1,7) (j5-10)什,C,1,TP(：=,T,-,C) (i 14)2】3A一 sc心编译原理复习资料229= A,D,12) 11-(丄 -,-，14)12. (+, A, 2, T2)13. (- K- A)14.乙编译原理复习资料102 for将下面的语句翻译为四元式序列i,2for i := a+b*2 to c+d+10 do禺4MIOif hg then p:=p+1;56i:=elulaceplace心29(耳t5, j)7+2(+aMt2)10 0 1X12)hgain3 (+,cdt3)Jj A厂.1J J&91:=l+lJ4(+,

13、t3J0, M)12(,h,g,14)Y10it :5(耳2 J)13(j 8)1L6(三t4, ,t)14(+,P(1,t6)11hg-7(j 10)15(:=t6, ,p)13,14p:=pH8 (+,1,1.15)16(j 8)15_17- 16（五）短语、素短语、最左素短语，FirstVT集和LastVT集的求解方法（复习第四章 算符优先文法相关内容）1 短语、素短语、最左素短语例：给定右边文法的- 个句型：T F + i求其短语、素短语、 最左素短语？短语有：i, T * FsT* F + i素短语有二i, T * F最左素短语 是:T * FE9T | E+T丁F | T*FF9i

14、 I (E)E编译原理复习资料112.FirstVT集和LastVT集的求解方法F今F+T IT例：求文法各非终结符的EixstYJ：T9T屮F|FFTE） | i-定义数组；E1111T111F11从而得到工EirstyKE) = +,给定文法GS：S| (T) EirsiYIXS)=练习:给定文法GE:ETE+TTTT*FFT(E)求句型T+T*F+i的短语、素短语、最左素短语。根据语法树可知： 句型打+丁吁用的短语有：T-相对非终统符E的短语T*F 相对非终蛙符T的短语T+T好一相对非终结符E的短语i相对非终结符只玖T的短语T+T*FH 相对非终结符E的短语根据素短语的定义可知：i和厂F

15、为素短语：其中：T-T*F（含T+F素短语卜T+T+F+i（含T*F素短语）和T（不含终结符曲不杲素短语T丁 *F编译原理复习资料12TT.S S Eirsmxi)= La取MTQ)= a.) 1算牙口LtVTMo讼=编译原理复习资料13例：设文法为：Ef#E#; Tf F;EfE+T ; FPT F | P; ET ; P (E); T T*F ; L i;firstYIE)=#fidBOXE)=+,*, t5(J) lastVTffi)= 中的一种 成立，贝临为一算符优先文法。例：EE+E | E*E | (E) | i证明不是算符优先文 法。因 为：EE+E,E=E*E则有+冬*(由规则

16、2)又因为：E-E咛，E=E+E则有+ %由规则3)所以不是算符优先文法灯解：(1)求fixstYl和lastYX集ffcgtyixp)=(7i)la$tVT(E?)=#laVTE)=-*. t .) J wyi(I)=*5t OJ1能丈VJC(E)=)，f，i 编译原理复习资料14算符优先文法的定义： 1算符文法：如果文法G没有P今QR（PQR属于非终结符）的产生式,（主要是看产生式中是否包含 两个非终结符相邻的情况） 2算符优先关系的定义：文法G是一个不含旷产生式的算符文法，定义终结符準b之间的优先关系a工蚯中有或a（在同一 产生 頁中）+m + 7 a1）或R=Qb.（注意ab相邻）斗a

17、池G中有的产生式且R4域R=aQ（注意血相邻）习对右边的文法 G 计算终结符+,笃 T 和）之间的优先关系： 因为；ETE + T, T=T*Fr所以:+ E + TT所以；+ +（规则 3）因为；T9T*F, F=P 个 F,所以；* T*F, 以：* *（规则 3）因为：（E）, E E + T,所以；+ ）（规则 3）因为：FPtF?P=（E）,所以：） T 规则 3） 因为；F9PTF, F=PtF,所以二 Tv 不（规则 2）E-E + TTTFFPTFPT(E)编译原理复习资料ii二、综合题1.NFA的确定化和最小化（参看课件第三章 62 页：例 5）例6：将下述NFA确定化1la

18、lbi丄2S123A124B123AC1Z4B124B123AD(l-2.3-5.6n CEr l32A5?6,fD36F12第5,6 JD1,2,4,6,fEF1?2;4?5,6D例5有NFA如下:(创b)(aaifeb)-编译原理复习资料ii1236fF13,5 Af C2第6胆E编译原理复习资料17等价的DFA单击此处添加文本ITS:A S B C编译原理复习资料182自顶向下分析(参看课件第四章(1) 67 页：综合练习)例：求对应于下述文法的预测分析表：E TEE +TE | & T FTT *FT | & F (E) |i 答：门首先求 first 集：血如 XE

19、叮Ei?或!)=(，i EiXT)=b叮EiSt(E)= (i 2)由于& First(E), & First(T),求 E和 T的 Follow 集:例:设文法 G(S): S-(L) | aS | aL L, S | S(1) 消除左递归和回溯；(2) 计算每个非终结符的 First 和 Follow 集;(3) 构造预测分析表。 _答：(1)消除左递归和回溯：ST EL-SU Lr SL I CEitSt(S)=(，a EirstCS1) (G asEii51(L)=C aEiMLJf ,EEdhMT)=带，)，+3)根据集合的值填表，得到i+()#ETTE*TTE，EF

20、 TTFTTFTT E4FT左-TF-1T(EEPJ1PWIS)=#构造预测分析表:a()#sSxaSS-(L)SSSS J ESksS J ES J ELL7,LLr SLL J E兀(I i ) j) ) 编译原理复习资料193 LR分析方法(参看课件第四章(3) 28 页及 30 页)例：设文法G为:第3步:MSiE”始求项目集规范族由SO = (5f- E7知:Closure(SO) = S E, E爭E *!1B 由此初值C二Closure(SO)再根据GO函数计算后继 状态由此表明显看出匕Go(状态，后继符号)=后继状态状态项目集后继符号 后继状态 W EET GET切E a b1： * P接受态E-a AAT心A-*d A c d10E-b*d B c dsc AA-心A-*d AcdI8sissB-c1BB- - rBB- dBc dallSfiE w上赴#归约S7#归约SsA*#归约 #归约S10A-d #归约B*#归约A T皿I dB cB I d求该文法的LR