四川大学编译原理期末复习总结

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

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

3、定义句子的结构； 用有穷的规则刻划无穷的集合；文法是被用来精确而无歧义地描述语言的句子的构成 方式；文法描述语言的时候不考虑语言的含义。7. 语义分析阶段的功能是什么？答：对语法分析所识别出的各类语法范畴分析其含义， 进行初步的翻译（翻译成中间代码）; 并对静态语义进行审查。&代码优化须遵循哪些原则？答：等价原则：不改变运行结果有效原则：优化后时间更短，占用空间更少 合算原则：应用较低的代价取得较好的优化效果9词法分析阶段的功能是什么？答：-功能：源程序（Tokenf词法分析程序= 语法分析程序7IJ逐个读入源程序字符并按照构词规则切分成一系列单词 任务：读入源程序，输出单词符号滤掉空格，跳过

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

5、什么是基本块？答：是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句，入口 是其第一个语句，出口是其最后一个语句。13. 代码优化阶段的功能是什么？答：对已产生的中间代码进行加工变换，使生成的目标代码更为高效（时间和空间）。14. 文法分哪几类？答：文法有四种：设有G=（Vn,Vt,P,S），不同类型的文法只是对产生式的要求不同：0型文法（短文文法）:G的每个产生式aT P满足：a V+且a中至少含有一个非 终结符,P V*1型文法（上下文有关文法）：如果G的每个产生式a T P均满足| P |=| a I，仅当S T 6除外，但S不得出现在任何产生式的右部2型文法（上下文无关

6、文法）：G的每个产生式为At P , A是一非终结符，P V* 3型文法（正规文法）：G的每个产生式的形式都是：At a B或At a，其中A,B是 非终结符，a是终结符串。（右线性文法）015. 循环优化常用的技术有哪些？答：代码外提；强度削弱；删除归纳变量。16. 什么是算符优先文法？答：算符文法 G的任何终结符 a,b之间要么没有优先关系，若有优先关系 ，至多有 -r- laA =haA=baas=bA =AbaA=A-= Aba a归纳得：L(G1) = W例22(P30)考虑文法G2:A T aAla它定义的语言是:B T laBibL(G2)=ab Im.nl(二)给定语言求文法思

7、考.构造一-文法G3使得:L(G3) = 规呵 I心 1 弘b的个数相同，贝rj文法G3为二(三)逆波兰式-K逆波兰式：-运算对象写在前, 例：a+b 9 (a+b)*c a+b*c &:=b*c+b*d 9a b运算符写在后(后缀表示形式)我+ate*躯:二写出下列算式的逆波兰表示a+b*(c+d/e)a:=b*(-gl+b *(-34)not A or not (C or not D)a b c * b 34 * +A not C D not or not or后缀式的推广-(1)赋值语句A三E,后缀式为：AE:=(2)转向语句GOTO L的后缀式为：UTO (3)条件语句if xy th

8、en m;=x else m:=y12345678g1011121314Xy11mX114Jmy* fe *（四）将for语句和if语句翻译成相应的四元式序列例.将下面的IF语句翻译为四元式序列 if A and B and (CD) thenif ACD 严CAD的四元式 Ci 亠 13)7. (jA.B,9)8。亠 11)9.(：=丄_巧10g；15)II. (：=e-F)12. D)2 L3 -4 _15F;=)r：=o15/*AB的四元式*/*F ：=1的四元式*/*F ：=0的四元式和13. (+,GJ,T) /*G:=G+1 的四元式竹14. (:=匚丄 G)15.练习:将下面的语

9、句翻译为四元式序列if (AC) and (BD) thenif A=1 then C:=C+1else ifAWD then A:=A+2L (j. A, C, 3)2- (j, -,14)3. (j, B, D, 5)4. (j,- 14)反(j= A, 1, 7)6. (j,- 10)7- (+,C, 1, TP8 (:= T,- C)9- (j,-厂,14)10. (jl,t12)她HilT: _ : 1V3 (+,c,d,t3)11G，, ,17)8h,g,14)Yit 1-mLi15 :=12, ,1)13(j 8)T6 (:二皿,t)14(+pht6)11hM7 010)15(:

10、=t6p)1M14 kPil 18(+J,1,t5)16(j 8)15 jmp again 17 16N1256（五）短语、素短语、最左素短语，FirstVT集和LastVT集的求解方法*生 4 It+d+IO * i*eL placet:=e2.卩flcefor i := a+b*2 to c+d+10 do if hg then p:=p+1;（复习第四章 算符优先文法相关内容）1短语、素短语、最左素短语E9T 1 E-HT例：给定右边文法的一T-F 1 T*F个句型；T r + 1F9i 1 (E)求其短语、素短语、E最左素短语？E + T f短语有：i, T * F, T * F +

11、11TF素短语有:1, T * F/ 最左素短语是：T * FT” Fi-练习:给定文法GE:ETE+T TTTT*FFFT(E) i求句型T+T*F+i的短语. 素短语.最左素短语。很据语法树可知：句型#T+T*田訓勺短语有：T-相对非终统符E的短语PF 相对非终蛙符T的短语T+T*F -相对非终结符E的短语 i相对非终结符R F、T的短语 T+T*FT 相对非终星符E的短语根据素短语的定义可知：I和計F为素短屋其中：T+T+F （含T+F素短语）、 T+T*FT （含T*T素短语）和 T（不含终结符吃不是素短语PT为最左素短语，2.FirstVT集和LastVT集的求解方法FTF+T I

12、T 例二求文法各非终结符的Eimt卫T: T-T*F I FFTE） I i-定义数组二咔从而得到匸ElrstYXCE) = +, UEJo?tOOCT)=曾耳EiotYXCK) = K3给定文法GSS a I (T)T T T,S I S计算EjxstYI和 L朋*工集。-EkstYIXS)= a/ EkslAOXI) = 比( Last乂IXS) = a,) Last丈工CT) = aj, 因为；EE+E , EE*E又因为：EE*E, EnE+E则有+冬*（由规则2） 则有+ A*（由规则3）例：设文法为：E f #E#; T f F; E f E+T ; FPt F | P; ET ;

13、 P (E); T T*F ; L i;解：求fixstYT和皿tVT集 firstyiXE9=#festYX(E )=+,*, T , ( , i)fix戎V1XE)= t , (，i) &或MTXR)= ( J ) la5tyT(E9=# la3tYTO)=+/, t J J lastyTa)=(*, f J,i lastyiCE)= ), t , iLastV工(R)= f i13.算符优先文法 优先关系的定义：宀算符优先文法一算符文法G的任何终结符8, b之间要么没有优先关 系，若有优先关系，至多有工,中的一种 成立，贝UG为一算符优先文法.证明不是算符优先文例：EE+E I E*E

14、I （E） I i 法.所以不是算符优先文法口算符优先文法的定义： L算符文法：如果文法G没有P9QR（PQR 属于非终结符）的产生式（主要是看产生式中是否包含 两个非终结符相邻的情况）-2算符优先关系的定义：文法G是一个不含旷产生 式的算符文法，定义终结符已.b之间的优先关系 a =b,G中有Pab或PTa（在同一产生 式中）ab或 R=Qb（注意血相邻）丄E-E + T TTF tpTf P吠E）Cb池G中有PRb的产生式，且R*滅 R=aQ （注意ab相邻）-对右边的文法G计算终结符 +,匕T和）之间的优先关系:因为; 因为; 因为: 因为; 因为; 因为: 因为;* （规则2）EE +

15、 T , T=T*F,所以：+ E + T.所以：+ +（规则3） TTT*F, F=PTF,所以I * *M则3） P夕（E）, E=E + T ,所以：+ ）（规则3） F9pTf,P = （E）,所以：） t 规则3）F夕 P Tf, F=Ptr,所以：TvT （规则2）、综合题1.NFA的确定化和最小化（参看课件第三章62页：例5）例5：有NFA如下：口但冋您砂口吧rg) E -但iRWteb伽r E54bS6aaa7s48b - bba6例6：将下述NFA确定化aa24a61 1laU1UJS1,23A124123A12,5,6,0C124124B123A124,5601,2,5,6

16、,0Cfl.23_5.6_nCfl.2.4.6 .flh2A5.6,fD1236,0F124 仅 6,f12460E123,6,fF12,4,5,6,01,236,0F1,23=5,6,fC1246fBBDEDDE2. 自顶向下分析（参看课件第四章（1） 67页：综合练习）例：求对应于下述文法的预测分析表:ETEE+TE |TFTT*FT |F(E) |i答：1)首先求first集:阪2)二(，1 EirMOE) = +，叮 Etol=(，i EkstaXW E EiME)= (，i 2)由于 First(E), &迂 First(T),求 E和 T的 Follow 集:EqIWEX 他)Ee

17、ig姒r)=他)，+3)根据集合的值填表，得到L+*()E-TEtTFE，-+TE T-FTtFTT f+Kr TFF-1t(E)First 和 Follow 集;S-(L)| 躍 S S I L-SUU f 純 I E例:设文法 G(S): S-(L) | aS | aL L, S | S(1) 消除左递归和回溯；(2) 计算每个非终结符的(3) 构造预测分析表。答：(1)消除左递归和回溯：Ekst(S)= C a EirsX(S)=Ca, E Ekg)=C a，) EoUoydXt)=) EftfaQL)=)构造预测分析表:at()井sSrraSSf (L)SSTS S-SS E5 J L

18、LTUsuLLr SLL J E3. LR分析方法(参看课件第四章(3)28页及30页)(f|lg：Af cA最后得到LR (0)的项目集规范族Io：SJ -EZZ Ea矗bB(附)单击此处富QAf c*AA f tcA扎f -dI? ：E f 3+ A A cAAf -dC4l|g A d aA*TEf bBB f yBBf dTEfc*BB 一 cBBf dcdcB例：设文法G为：E 建4 1 bBAI d第2步；写出拓广后的BtcB I d文法的项目集:求该文法的LR(0分析表.1m TE2* S* tE 第1步:拓广文法,3 E T g4. E Ta A并对产生式给予序5- E -A

19、6. E T * bR号二(0) S* tE7- E -b * B& E TbB *(1) E 占 A9. A - *10. A Tc * A E tubII.AtW12, Ad A -313. A Td -14.B T sB(4) A -d(5) B tcB16 B B (6) B -d17. B - dl&B -d 1.短语、直接短语、句柄例：考虑如下文法：E =T | E+TT=F | T*F F =i| (E)求句型i1 * i2 + i3的短语、直接短语和句柄E = i1 * i2 + F(E =i2 +i3)答: E = F * i2 + i3E = i1 * F + i3E =

20、T + i3 (T =T*F =i1 * i2 )F=iE = i1 * i2 + i3因此：短语有：i1, i2, i3, i1*i2,i1*i2+i3直接短语有：i1, i2 , i3句柄是：i1i2 + i3不是短语，因为 E = i1 * E2. 什么是语法制导翻译一般不涉及计算顺序。语法制导翻译：定义翻译所必须的语义属性和语义规则，语法制导翻译(Syntax-Directed Translations)-一个句子的语义翻译过程与语法分析过程同时进行。在文法中，文法符号有明确的意义，文法符号之间有确定的语义关系。属性描述语义信息， 语义规则描述属性间的的关系，将语义规则与语法规则相结合

21、，在语法分析的过程中计算语 义属性值。编译翻译程序：把一种语言程序转换成另一种语言程序，且在功能上是相同的这样的程序。 程序：把咼级语言转换成低级语言，且在功能上是相同的这样的程序。解释程序：边解释边执行源程序的程序。区别：编译程序有中间代码，而解释程序没有。 译过程的五个阶段：1、词法分析 任务：对构成源程序的字符串进行扫描和分解，识别出一个个单词。2、语法分析 任务：在词法分析的基础上，根据语言规则，把单词符号串分解成各类语法 单位。3、语义分析和中间代码产生 任务：对语法分析所识别出的各类语法范畴，分析其含义 并进行初步翻译。4、优化任务：对前段产生的中间代码进行加工变换，以期在最后阶段

22、能产生出更为高效 的目标代码。5、目标代码生成 任务：把中间代码变换成特定机器上的低级语言代码。编译程序的七个部分词法分析器，语法分析器、语义分析与中间代码产生器、优化器、目标 代码生成器、表格管理和出错处理。编译程序生成的五个办法：机器语言、高级语言、移植、自编译方式和使用工具自动生成。 法规则：指单词符号的形成规则。(也就是正规式)空字:语法规则：规定了如何从单词符号形成更大的结构。就是语法单位的形成规则。包含任何符号的序列。 闭包： 中所有的符号组成的集合。上下文无关文法是指：所定义的语法范畴是完全独立于这种范畴可能出现的环境的文法。 下文无关文法的四个组成部分：一组终结符号、一组非终结符号、一个开始符号和一组产生 式。终结符号也就是不可再分的基本符号。开始符号是语言中我们最感兴二元式表示：（种非终结符号是用来代表语法范畴，表示一定符号串的集合。 趣的语法范畴。 产生式是定义语法范畴的书写规则。 句子：文法中从开始符号推导的终结符号串。 句型：从开始符号推导的符号串 语言：