1.编译程序的工作过程一般划分为：词法分析、语法分析、语义分析及中间代码生成、代码优化、目标代码生成，五个阶段。 2.文法G（S）：S->SbM|M; M->MaN|N; N->c . （最右推导也称为规范推导，规范推导的逆过程，称为最左规约，也称为规范规约。）句型Macbc的规范推导：S=>SbM=>Sbc=>Mbc=>MaNbc=>Macbc ;(一个句型的最左直接短语称为该句型的句柄，最简树下边为句柄。)句柄是：c。
3.语言L={anbicn|n>0,i>=0}对应的文法为：S->AB;A->aAc|ac;B->bB|? 4.文法G：S→0S1|a对应的语言L(G)={0ma1n|n>=0} 5.自上而下语法分析（LL（1）分析）的条件：①文法不含左递归；②设U是文法G的任意一个非终结符，其产生式为U->x1|x2|…xn，如果FIRST(xi)?FIRST(xj)=?(i≠j,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表示终结符号，Vn∪Vt=Ｖ(字母表)，
Vn∩Vt=φ
– S是开始符号，
– P是产生式，形如：α→β(α∈V+且至
少含有一个非终结符号，β∈V*)
3.语法分析阶段的功能是什么？
答：在词法分析的基础上，根据语言的语法规则，将
单词符号串分解成各类语法短语(例：程序、语句、表达式)。确定整个输入串是否构成语法上正确的程序。
4.局部优化有哪些常用的技术？
答：优化技术1—删除公共子表达式
优化技术2—复写传播
优化技术3—删除无用代码
优化技术4—对程序进行代数恒等变换（降低运算强度）
优化技术5—代码外提 优化技术6—强度削弱
优化技术7—删除归纳变量
优化技术简介——对程序进行代数恒等变换（代数简化）
优化技术简介——对程序进行代数恒等变换（合并已知量）
5．编译过程分哪几个阶段？
答：逻辑上分五个阶段：词法分析、语法分析、语义
分析与中间代码生成、代码优化、目标代码生成。每个阶段把源程序从一种表示变换成另一种表示。
6. 什么是文法？
答：文法是描述语言的语法结构的形式规则。是一种
工具，它可用于严格定义句子的结构；用有穷的规则刻划无穷的集合；文法是被用来精确而无歧义地描述语言的句子的构成方式；文法描述语言的时候不考虑语言的含义。
7. 语义分析阶段的功能是什么？
答：对语法分析所识别出的各类语法范畴分析其含
义，进行初步的翻译(翻译成中间代码)；并对静态语义进行审查。
8.代码优化须遵循哪些原则？ 答：等价原则：不改变运行结果
有效原则：优化后时间更短，占用空间更少 合算原则：应用较低的代价取得较好的优化效果 9.词法分析阶段的功能是什么？ 答：
逐个读入源程序字符并按照构词规则切分成一
系列单词
任务： 读入源程序，输出单词符号
— 滤掉空格，跳过注释、换行符 — 追踪换行标志，指出源程序出错的行列位置
— 宏展开，……
10.什么是符号表？
答：符号表在编译程序工作的过程中需要不断收集、
记录和使用源程序中一些语法符号的类型和特
1
征等相关信息。这些信息一般以表格形式存储于系统中。如常数表、变量名表、数组名表、过程名表、标号表等等，统称为符号表。对于符号表组织、构造和管理方法的好坏会直接影响编译系统的运行效率。
11.什么是属性文法？
答：是在上下文无关文法的基础上，为每个文法符
号(含终结符和非终结符)配备若干个属性值，对文法的每个产生式都配备了一组属性计算规则(称为语义规则)。在语法分析过程中，完成语义规则所描述的动作，从而实现语义处理。
12.什么是基本块?
答：是指程序中一顺序执行的语句序列，其中只有
一个入口语句和一个出口语句，入口是其第一个语句，出口是其最后一个语句。
13.代码优化阶段的功能是什么？
答：对已产生的中间代码进行加工变换，使生成的目标代码更为高效(时间和空间)。 14.文法分哪几类？ 答：文法有四种:设有G=(Vn,Vt,P,S),不同类型的文法只是对产生式的要求不同：
０型文法(短文文法)： G的每个产生式α?β满足：α∈V+且α中至少含有一个非终结符,β∈V*
１型文法(上下文有关文法)：如果G的每个产生式α? β均满足|β|>=|α|,仅当Ｓ?ε除外，但S不得出现在任何产生式的右部 ２型文法(上下文无关文法)：G的每个产生式为A?β, A是一非终结符，β∈V*
３型文法(正规文法)：G的每个产生式的形式都是：A?αB或A?α，其中A,B是非终结符，α是终结符串。(右线性文法)。
15.循环优化常用的技术有哪些？
答：代码外提；强度削弱；删除归纳变量。 16.什么是算符优先文法？
答：算符文法G的任何终结符a,b之间要么没有优先关系，若有优先关系,至多有
中的一种成立,则G为一算
符优先文法。
二填空题
1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静态存储分配方案和动态存储分配方案，而后者又分为（栈式动态存储分配） 和 （堆式动态存储分配） 。 2. 规范规约是最（左 ）规约。
3. 编译程序的工作过程一般划分为5个阶段：词法分
析、（语法分析 ） 、语义分析与中间代码生成，代码优化及（目标代码生成） 。另外还有（表格管理）和出错处理。 4．表达式x+y*z/(a+b)的后缀式为 （xyz*ab+/+ ） 。 5．文法符号的属性有综合属性和 （继承属性）。 6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15,1..20]某个元素a[i，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.一张转换图只包含有限个状态,其中有一个被认为是（初 ）态;而且实际上至少要有一个（终 ）态。
2
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设有文法G[N]:N→D|ND;D→0|1|2|3|4|5|6|7|8|9 （1）G[N]定义的语言是什么？
（2）给出句子0123和268的最左推导和最右推导。 2.2(1)分析：问题归结为由识别符号 N 出发，将推导出什么样的句子，也就是说 L(G[N])是由一些什么样的符号串所组成的集合，找出其中的规律，用式子或自然语言描述出来。 解答：
L(G[N])={a|a为可带前导0的正整数} 或 L(G[N])={(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：S→AB；A→aA|?；B→bc|bBc G2：S→aA|a；A→aS
2.7（1）分析：S=>AB=>aAB=>aaAB=>…=>aiB=> aibBc => aib2Bc2 =>…=>aibncn
所以此文法定义的语言为 L(G[N]) = {aibncn|i ≥ 0,n ≥1} 解答：L(G[N]) = {aibncn|i ≥ 0,n ≥1} 存在问题：a与b，c次数是不同的 （2）分析：S=>aA|a=>aaS|a=>a2nS|a 解答：L(G[N])= {a2n+1|n ≥0} 语言→文法（给你语言求文法） 2.3 L1={amdn|m,n≥1} L2={anbnci|n≥1i≥0} L3={anbncmdm|n≥1m≥1}
2.3分析：设计文法来描述一个语言，关键是设计一组规则生成语言中的符号串。
设计语言的文法，必须分析这个语言是由怎样一些符号串组成，即首先分析语言中符号串的结构特征。 解答：
（1）G1：S→AB
A→aA|a B→bB|b
注意：a,b次数不同，不能写? m,n>=1。 （2）G2： S→AB
A→aAb|ab B→cB|? 或 S→Sc|A A→aAb|ab
注意：a,b次数相同；n>=1; i>=0 abA X （3）G3：S→AB
A→aAb|ab B→cBd|cd
2.11已知文法G[S]:S→(AS)|(b)；A→(SaA)|(a)
2.11分析：首先要判断一下符号串是否是文法的句型。 解答：
（1）因为S=>(AS)=>((a)S) ≠>(a)
所以符号串(a)不是文法的句型，因此它没有短语、直接
3
短语和句柄。
（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|BC
εA = Aε= A
A*＝ AA* | ε＝ A | A*＝(A|ε)A* (A*) * ＝ A* 求解规则：
若 x = αx |β(或x = αx+β)，则解为x = α*β 若 x = xα|β(或x = xα+β)，则解为x = βα* 设有正规文法Ｇ： A→aB|bB B→aC|a|b C|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)
即正规文法G[Z]所生成语言的正规式是 (a|b)(aa)*(a|b)
正规式到正规文法的转换
字母表∑上的正规式到正规文法 G＝(VN,VT,P,S)的转换方法如下： 1.令 VT = ∑
2.对任意正规式 R 选择一个非终结符 Z 生成规则 Z→R，并令 S＝Z；
3.若 a 和 b 都是正规式，对形如 A?ab的规则转换
成 A→aB 和 B→b两规则，其中 B 是新增的非终结符； 4.在已转换的文法中，将形如 A→a*b 的规则进一步转换成 A→aA | b；
5.不断利用规则(3)和(4)进行转换，直到每条规则最多含有一个终结符为止。
将描述标识符的正规式R=l(l|d)*转换成相应的正规文法 令 S 是文法开始符号，根据规则(2)变换为 S→l(l|d)*
根据规则(3)变换为S→lA A→(l|d)* 根据规则(4)变换为S→lA A→(l|d)A |ε 进一步变换为S→lA A→lA|dA|ε
进一步变换为（消除?规则）S→l|lA A→l|d|lA|dA
一个确定有穷自动机 DFA M 是一个五元式： M=( Q, ∑, f, S, Z) 其中：
Q 是一个有限状态集，它的每个元素称为一个状态。 ∑是一个有穷字母表，它的每个元素称为一个输入字符。
f 是一个从 Q×∑ 至 Q 的单值映射。 f(qi, a) =qj (qi,qj∈Q，a?∑)
表示：当现行状态为 qi、输入字符为 a 时，自动机将转换到下一状态 qj 。我们称 qj 为 qi 的一个后继。 S∈S，是唯一的初态。 Z
S，是一个终态集（可空）。
1)其等价的 DFA 的开始状态为 A=?-CLOSURE({X})={0,1,2},作为未标记的状态添加到 Q’中。
2)此时 Q’ 中仅有唯一的未标记状态 A，因此
4
①f’(A,a) =?-CLOSURE(f({X,0,1},a)) =?-CLOSURE({0,2})={0,1,2}=B 未标记的 B=>Q’ f’(A,a)=B 添加到M中。 f’(A,b) =?-CLOSURE(f({X,0,1},b)) =?-CLOSURE({0})={0,1}=C 未标记的 C=>Q’ f’(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=>Q’ f’(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,D}a={B}?{A,B,C,D}，但是{A,B,C,D}b={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≠Ⅱ，令Ⅱ＝Ⅱnew 4.当前分划是 Ⅱ=({A,C},{B},{D},{E})
考察{A,C}，{A,C}a={B}{B}，{A,C}b={C}{A,C}， 所以{A,C}不能再分划。 此时 ?new=?
整个分划过程结束。
5.至此，选择 A 代表{A,C},将状态 C 从状态图中删去，并将原来引向 C 的弧都引至 A，得到化简后的 DFA M’
1 文法规范句型的活前缀
1.字符串的前缀是指字符串的任意首部。 如 abc 的前缀有 ?、a、ab、abc。
2.所谓活前缀是指规范句型的一个前缀，这种前缀不包含句柄之后的任何符号。
规范句型：用规范推导推导出的句型称为规范句型 注意有下列事实：
* 之所以称为活前缀，在右边增添一些终结符号后就可以使它成为一个规范句型。
* 规范句型中句柄右部（未处理输入串）不包含任何非终结符。
* 在 LR 分析的任何时候，栈里的文法符号（对输入串分析已经移进和归约得到的）自底向上应该构成活前缀，如果整个输入串没有错误，那么，输入串剩下的部分接在这个活前缀之后，一定构成一个规范句型。 对句柄的识别变成对规范句型活前缀的识别。 LR(0)项目
·由活前缀的定义，活前缀和句柄之间的关系有三种： ·活前缀中已经包含句柄的全部符号。
此时意味着某一产生式 A→α 的右部符号串 α 已经出现在栈顶，相应的分析动作应该是按该产生式归约。 ·活前缀中只包含句柄的一部分。
此时意味着形如 A→α1α2 产生式的右部子串 α1 已经出现在栈顶，正期待着从剩余的输入串中能移进或归约得α2。
·活前缀中不包含句柄的任何符号。
此时意味着期待从剩余的输入串中能移进或归约得到某产生式 A→α 的右部 α。
为了刻画在分析过程中文法的一个产生式右部已经有多大一部分被识别，可在每个产生式右部某个位置上加一个圆点来表示。针对上述三种情况，标有圆点的产生式分别为： A→α. A→α1.α2 A→.α
我们把文法 G 中右部添加一个圆点的产生式称为文法 G 的一个 LR(0)项目。
特别地， A→ε只有一个项目 A→.。
5
郑州大学期末编译原理知识点超全总结 - 图文
