郑州大学期末编译原理知识点超全总结

1.编译程序的工作过程一般划分为：词法分析、语法分析、语义分析及中间代码生成、代码优化、目标代码生成，五个阶段。2.文法G（S）：S-SbM|M; M-MaN|N; N-c . （最右推导也称为规范推导，规范推导的逆过程，称为最左规约，也称为规范规约。）句型Macbc的规范推导：S=SbM=Sbc=Mbc=MaNbc=Macbc ;(一个句型的最左直接短语称为该句型的句柄，最简树下边为句柄。)句柄是：c。3.语言L=anbicn|n0,i=0对应的文法为：S-AB;A-aAc|ac;B-bB|4.文法G：S0S1|a对应的语言L(G)=0ma1n|n=05.自上而下语法分析（LL（1）分析）的条件：文法不含左递归；设U是文法G的任意一个非终结符，其产生式为U-x1|x2|xn，如果FIRST(xi)FIRST(xj)=(ij,i,j=1,2,n)当FIRST（xi）时，有FIRST（xi）FOLLOW(U)=,则文法G为LL（1）文法。6.属性文法中属性分为综合属性和继承属性。7.正规文法通过定义语言词法规则，上下文无关文法通过定义语言语法规则，属性文法通过定义语言语义规则。8.编译中常见的优化技术有代码外提、强度消弱、合并已知量。9.运行存储分配中，用栈式策略解决递归调用存储分配问题，用堆式策略解决动态数据存储分配问题。一、简答题1.什么是编译程序？答：编译程序是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序 。将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。2.请写出文法的形式定义？答：一个文法G抽象地表示为四元组G=（Vn,Vt,P,S） 其中Vn表示非终结符号 Vt表示终结符号，VnVt=(字母表)，VnVt= S是开始符号， P是产生式，形如：(V+且至少含有一个非终结符号，V*) 3.语法分析阶段的功能是什么？答：在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语(例：程序、语句、表达式)。确定整个输入串是否构成语法上正确的程序。4.局部优化有哪些常用的技术？答：优化技术1删除公共子表达式优化技术2复写传播优化技术3删除无用代码优化技术4对程序进行代数恒等变换（降低运算强度）优化技术5代码外提优化技术6强度削弱优化技术7删除归纳变量优化技术简介对程序进行代数恒等变换（代数简化）优化技术简介对程序进行代数恒等变换（合并已知量）5编译过程分哪几个阶段？答：逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成。每个阶段把源程序从一种表示变换成另一种表示。6. 什么是文法？答：文法是描述语言的语法结构的形式规则。是一种工具，它可用于严格定义句子的结构；用有穷的规则刻划无穷的集合；文法是被用来精确而无歧义地描述语言的句子的构成方式；文法描述语言的时候不考虑语言的含义。7. 语义分析阶段的功能是什么？答：对语法分析所识别出的各类语法范畴分析其含义，进行初步的翻译(翻译成中间代码)；并对静态语义进行审查。8.代码优化须遵循哪些原则？答：等价原则：不改变运行结果有效原则：优化后时间更短，占用空间更少合算原则：应用较低的代价取得较好的优化效果9.词法分析阶段的功能是什么？答：逐个读入源程序字符并按照构词规则切分成一系列单词任务： 读入源程序，输出单词符号 滤掉空格，跳过注释、换行符 追踪换行标志，指出源程序出错的行列位置 宏展开，10.什么是符号表？ 答：符号表在编译程序工作的过程中需要不断收集、记录和使用源程序中一些语法符号的类型和特征等相关信息。这些信息一般以表格形式存储于系统中。如常数表、变量名表、数组名表、过程名表、标号表等等，统称为符号表。对于符号表组织、构造和管理方法的好坏会直接影响编译系统的运行效率。11.什么是属性文法？答：是在上下文无关文法的基础上，为每个文法符号(含终结符和非终结符)配备若干个属性值，对文法的每个产生式都配备了一组属性计算规则(称为语义规则)。在语法分析过程中，完成语义规则所描述的动作，从而实现语义处理。12.什么是基本块?答：是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句，入口是其第一个语句，出口是其最后一个语句。13.代码优化阶段的功能是什么？答：对已产生的中间代码进行加工变换，使生成的目标代码更为高效(时间和空间)。14.文法分哪几类？答：文法有四种:设有G=(Vn,Vt,P,S),不同类型的文法只是对产生式的要求不同： 型文法(短文文法)： G的每个产生式满足：V+且中至少含有一个非终结符,V*型文法(上下文有关文法)：如果G的每个产生式 均满足|=|,仅当除外，但S不得出现在任何产生式的右部型文法(上下文无关文法)：G的每个产生式为A, A是一非终结符，V*型文法(正规文法)：G的每个产生式的形式都是：AB或A，其中A,B是非终结符，是终结符串。(右线性文法)。15.循环优化常用的技术有哪些？答：代码外提；强度削弱；删除归纳变量。16.什么是算符优先文法？答：算符文法G的任何终结符a,b之间要么没有优先关系，若有优先关系,至多有中的一种成立,则G为一算符优先文法。二填空题1.不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静态存储分配方案和动态存储分配方案，而后者又分为（栈式动态存储分配）和（堆式动态存储分配）。2.规范规约是最（左）规约。3.编译程序的工作过程一般划分为5个阶段：词法分析、（语法分析）、语义分析与中间代码生成，代码优化及（目标代码生成）。另外还有（表格管理）和出错处理。4表达式x+y*z/(a+b)的后缀式为（xyz*ab+/+）。5文法符号的属性有综合属性和（继承属性）。6假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a1.15,1.20某个元素ai，j的地址计算公式为（a+(i-1)*20+j-1）。7局部优化是局限于一个（基本块）范围内的一种优化。8 词法规则通常可以用_正规式_，正规文法、_自动机_描述；语法规则通常用_2型文法_来描述；语义规则通常用_属性文法_来描述。9 编译原理的工作过程一般划分为：词法分析、语法分析、语义分析、优化和目标代码生成五个阶段。1.(最右推导 )称为规范推导。2.编译过程可分为（词法分析），（语法分析），（中间代码生成），（代码优化）和（目标代码生成）五个阶段。3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（二义性的）。4.从功能上说，程序语言的语句大体可分为（执行性）语句和（说明性）语句两大类。5.语法分析器的输入是（单词符号），其输出是（语法单位）。6.扫描器的任务是从（源程序）中识别出一个个（单词符号）。7.符号表中的信息栏中登记了每个名字的有关的性质，如（类型、种属、所占单元大小、地址）等等。8.一个过程相应的DISPLAY表的内容为（现行活动记录地址和所有外层最新活动记录的地址）。9.一个句型的最左直接短语称为句型的（句柄）。10.常用的两种动态存贮分配办法是（栈式）动态分配和（堆式）动态分配。11.一个名字的属性包括(类型)和(作用域)。12.常用的参数传递方式有（传地址），（传值）和（传名）。13.根据优化所涉及的程序范围，可将优化分成为（局部优化），（循环优化）和（全局优化）三个级别。14.语法分析的方法大致可分为两类，一类是（自上而下）分析法，另一类是（自下而上）分析法。15.预测分析程序是使用一张（分析表）和一个（符号栈）进行联合控制的。16.常用的参数传递方式有（传地址），（传值）和（传名）。17.一张转换图只包含有限个状态,其中有一个被认为是（初）态;而且实际上至少要有一个（终）态。18.根据优化所涉及的程序范围，可将优化分成为（局部优化），（循环优化）和（全局优化）三个级别。19.语法分析是依据语言的（语法）规则进行。中间代码产生是依据语言的（语义）规则进行的。20.一个句型的最左直接短语称为句型的（句柄）。21.一个文法G，若它的预测分析表M不含多重定义，则该文法是LL(1)文法）文法。22.对于数据空间的存贮分配，FORTRAN采用(静态)策略，PASCAL采用(动态)策略。23.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是(二义性文法)。24.最右推导亦称为（规范推导），由此得到的句型称为（规范）句型。25.语法分析的方法大致可分为两类，一类是（自上而下）分析法，另一类是（自下而上）分析法。26.对于文法G，仅含终结符号的句型称为(句子)。27.所谓自上而下分析法是指（从开始符号出发，向下推导，推出句子）。28.语法分析器的输入是（单词符号），其输出是（语法单位）。29.局限于基本块范围的优化称（局部优化）。30.预测分析程序是使用一张（分析表）和一个（符号栈）进行联合控制的。31.2型文法又称为（上下文无关文法）文法；3型文法又称为（正规）文法。32. 每条指令的执行代价定义为（指令访问主存次数加1）。33. 算符优先分析法每次都是对（最左素短语）进行归约。 文法语言（给你一个文法问语言是什么？）2.2设有文法GN:ND|ND;D0|1|2|3|4|5|6|7|8|9（1） GN定义的语言是什么？（2） 给出句子0123和268的最左推导和最右推导。2.2(1)分析：问题归结为由识别符号 N 出发，将推导出什么样的句子，也就是说 L(GN)是由一些什么样的符号串所组成的集合，找出其中的规律，用式子或自然语言描述出来。 解答： L(GN)=a|a为可带前导0的正整数 或 L(GN)=(0|1|2|3|4|5|6|7|8|9)+（2）分析：最右推导是指在推导过程中任何一步=(和都是句型)，都是对中的最右非终结符进行替换。 最左推导是指在推导过程中任何一步=(和都是句型)，都是对中的最左非终结符进行替换。 解答： 0123 最左推导：N=ND =NDD =NDDD =DDDD =0DDD =01DD =012D =0123 最右推导：N=ND =N3 =ND3 =ND23 =N123 =D123 =0123（2）268最左推导：N =ND =NDD =DDD =2DD =26D =268最右推导：N =ND =N8 =ND8 =N68 =D68 =268注意问题： (1) 推导符号的使用：= ( X)(2) 最左和最右不要混肴2.7下面文法生成的语言是什么？G1：SAB；AaA|；Bbc|bBcG2：SaA|a；AaS2.7（1）分析：S=AB=aAB=aaAB=aiB= aibBc = aib2Bc2 =aibncn所以此文法定义的语言为 L(GN) = aibncn|i 0,n 1解答：L(GN) = aibncn|i 0,n 1存在问题：a与b，c次数是不同的（2）分析：S=aA|a=aaS|a=a2nS|a解答：L(GN)= a2n+1|n 0 语言文法（给你语言求文法）2.3 L1=amdn|m,n1 L2=anbnci|n1i0 L3=anbncmdm|n1m12.3分析：设计文法来描述一个语言，关键是设计一组规则生成语言中的符号串。 设计语言的文法，必须分析这个语言是由怎样一些符号串组成，即首先分析语言中符号串的结构特征。解答：（1）G1：SAB AaA|a BbB|b 注意：a,b次数不同，不能写e m,n=1。（2）G2： SAB AaAb|ab BcB| 或 SSc|A AaAb|ab 注意：a,b次数相同；n=1; i=0 abA X（3）G3：SAB AaAb|ab BcBd|cd2.11已知文法GS:S(AS)|(b)；A(SaA)|(a)2.11分析：首先要判断一下符号串是否是文法的句型。解答：（1）因为S=(AS)=(a)S) (a)所以符号串(a)不是文法的句型，因此它没有短语、直接短语和句柄。（2）因为S=(AS)=(A(A(b)=(A(SaA)(b)所以符号串)=(A(SaA)(b)是文法的句型，该句型的语法树如下图所示：短语：(A(SaA)(b)； (SaA)(b)； (SaA)； (b)直接短语：(SaA)；(b)句柄： (SaA)给正规文法求正规式（用下面的性质）令 A、B和C均为正规式，由下列关系成立：A|B = B|A交换率A|(B|C)=(A|B)|C结合率A(BC)=(AB)C结合率A(B|C)=AB|AC分配率 (A|B) C = AC|BCA = A= AA* AA* | A | A*(A|)A*(A*) * A*求解规则：若 x = x |(或x = x+)，则解为x = *若 x = x|(或x = x+)，则解为x = *设有正规文法：AaB|bB BaC|a|bC|aB试给出该文法生成语言的正规式首先给出相应的正规式方程组（+代替|）A=aB+bB(1)B=aC+a+b (2)C=aB(3)将(3)代入(2)式中得B=aaB+a+b(4)对(4)使用求解规则得B=(aa)*(a+b)(5)将(5)代入(1)得A=(a+b)(aa)*(a+b)即正规文法GZ所生成语言的正规式是 (a|b)(aa)*(a|b)正规式到正规文法的转换字母表上的正规式到正规文法 G(VN,VT,P,S)的转换方法如下：1.令 VT = 2.对任意正规式 R 选择一个非终结符 Z 生成规则ZR，并令 SZ；3.若 a 和 b 都是正规式，对形如 Aab的规则转换成 AaB 和 Bb两规则，其中 B 是新增的非终结符；4.在已转换的文法中，将形如 Aa*b 的规则进一步转换成 AaA | b；5.不断利用规则(3)和(4)进行转换，直到每条规则最多含有一个终结符为止。将描述标识符的正规式R=l(l|d)*转换成相应的正规文法令 S 是文法开始符号，根据规则(2)变换为Sl(l|d)*根据规则(3)变换为SlA A(l|d)* 根据规则(4)变换为SlA A(l|d)A |进一步变换为SlA AlA|dA|进一步变换为（消除规则）Sl|lA Al|d|lA|dA一个确定有穷自动机 DFA M 是一个五元式：M=( Q, , f, S, Z)其中：Q 是一个有限状态集，它的每个元素称为一个状态。是一个有穷字母表，它的每个元素称为一个输入字符。f 是一个从 Q 至 Q 的单值映射。f(qi, a) =qj(qi,qjQ，a)表示：当现行状态为 qi、输入字符为 a 时，自动机将转换到下一状态 qj 。我们称 qj 为 qi 的一个后继。SS，是唯一的初态。ZS，是一个终态集（可空）。1)其等价的 DFA 的开始状态为A=-CLOSURE(X)=0,1,2,作为未标记的状态添加到 Q中。2)此时 Q 中仅有唯一的未标记状态 A，因此f(A,a)=-CLOSURE(f(X,0,1,a) =-CLOSURE(0,2)=0,1,2=B未标记的 B=Qf(A,a)=B 添加到M中。 f(A,b)=-CLOSURE(f(X,0,1,b) =-CLOSURE(0)=0,1=C未标记的 C=Qf(A,b)=C 添加到M中。 对状态 A 做标记3)此时 Q=A,B,C,其中B，C均未加标记f(B,a)=-CLOSURE(f(0,1,2,a) =-CLOSURE(0,2)=0,1,2=B f(B,a)=B 添加到M中。 f(B,b)=-CLOSURE(f(0,1,2,b) =-CLOSURE(0,3)=0,1,3=D未标记的 D=Qf(B,b)=D 添加到M中。 对状态 B 做标记（NFA确定化后的状态矩阵）1.首先 M的状态分成两组：终态组A,B,C,D，非终态组E形成(A,B,C,D,E)2.考察E，不能再分划，把E作为new中的一个子集。3.考察A,B,C,D，A,B,C,Da=BA,B,C,D，但是A,B,C,Db=C,D,E，它既不包含在A,B,C,D中也不包含在E之中，因此，应把A,B,C,D一分为二。因为状态 A,B,C 经 b 弧到达同一子集A,B,C,D中的状态，而状态 D 经 b 弧到达 E，因此，应把 D 分出来，形成D、A,B,C。于是new=(A,B,C,D,E), new，令new4.当前分划是 =(A,C,B,D,E)考察A,C，A,Ca=BB，A,Cb=CA,C，所以A,C不能再分划。此时 new=整个分划过程结束。5.至此，选择 A 代表A,C,将状态 C 从状态图中删去，并将原来引向 C 的弧都引至 A，得到化简后的 DFA M1 文法规范句型的活前缀1.字符串的前缀是指字符串的任意首部。如 abc 的前缀有 、a、ab、abc。2.所谓活前缀是指规范句型的一个前缀，这种前缀不包含句柄之后的任何符号。规范句型：用规