总复习
■第1章
1、编译程序是一种翻译程序，它将高级语言所写的源程序翻译成等价的机器语言或者汇编语言的目标程序。
2、编译程序是计算机系统中重要的系统软件！
3、解释程序与编译程序的主要区别是解释程序在执行过程中不产生目标程序。
4、编译的各个阶段。
答：整个编译过程可以分为5个阶段：词法分析，语法分析，语义分析及中间代码生成，代码优化和目标代码生成。
5、编译程序的结构框图或步骤。
6、遍（趟）：是对源程序或源程序的中间结果从头到尾扫描一遍，并作有关加工处理，生成新的中间结果或目标程序的过程。
■第2章
1、符号串的基本运算。
2、简单的说文法由产生式组成；产生式中的符号分为两类：终结符号和非终结符号。
3、推导（最左、最右）、句型、句子、短语、句柄
4、乔姆斯基层次中：L3 ? L2 ? L1 ? L0
■第2章例题
已知文法G[E]：
E→T|E+T|E-T
T→F|T*F|T/F
F→(E)|i
（1）该文法的开始符号是什么？
（2）请给出该文法的终结符号集合VT和非终结符号集合VN。
（3）找出句型T+T*F+i的所有短语、直接（简单）短语、句柄。
■第3章
1、词法分析程序的输出是单词符号序列。
2、DFA的三种表示形式——状态转移图、状态转换表和五元组表示（Q, ∑, f, S, Z ）；
3、正规式向DFA的转换：
（1）正规式——NFA;（转换原则见下页）
（2）NFA——DFA；
（3）DFA的最小化。
4、DFA向正规式的转换。
正则式向NFA转换的原则：
例：构造与正则表达式R=ba(a|b)*等价的状态最少的DFA，并写出该DFA的五元组形式或状态转换表。■第4章
1、语法分析方法的各种分类；
2、LL(1)分析方法。
提示：在此算法中注意First集和Follow集的求法。并且一定要注意分析过程中步骤要完整。（分析步骤见下页总结）
例：文法：S?a|^|(T) T?T,S|S
试判断该文法是否是LL(1)文法。
习题4：P100 4.3 4.7 4.9
■LL(1)分析方法相关知识总结
1、消除文法中的左递归或提取左因子；
（1）简单直接左递归的消除
A →βA’
A →Aα| β→
A’ →αA’| ε
（2）将文法G：A→αβ|αγ提取左因子。
解：A→αA’A’→β|γ
2、求改写文法中的非终结符的First集和Follow集；
答：First集合定义：FIRST(α) =
{a | α=> * aβ，a ∈T , α,β∈ (T?N)*}
若α=> * ε，则规定ε∈ FIRST(α)
该集合称为α的头符号集合。First集合算法P67
例题1、求文法G的FIRST集合(Simple integer expression grammar) expr →expr addop term∣term
addop →+|-
term →term mulop factor ∣factor
mulop →*
factor →(expr) ∣number
解：(1) expr →expr addop term
(2) expr →term
(3) addop →+
(4) addop →-
(5) term →term mulop factor
(6) term →factor
(7) mulop →*
(8) factor →(expr)
(9) factor →number
First(expr)={(,number}
First(term)={(,number}
First(factor)={(,number}
First(addop)={+,-}
First(mulop)={*}
例题2、求文法G的FIRST集合
G: (1) E→E aop T
(2) E→T
(3) aop →+
(4) aop →-
(5) T →T mop F
(6) T →F
(7) mop →*
(8) mop →/
(9) F →(E)
(10) F →i
解：同上换符号
例题3、求文法G的FIRST集合(Left factored grammar of if-statement) statement →if-stmt | other
if-stmt →if (exp) statement else-part
else-part →else statement | ε
exp→0 | 1
解：(1) statement →if-stmt
(2) statement →other
(3) if-stmt →if (exp) statement else-part
(4) else-part →else statement
(5) else-part →ε
(6) exp →0
(7) exp →1
First(statement)={if,other}
First(if-stmt)={if}
First(else-part)={else,ε}
First(exp)={0,1}
例题4、求文法G的FIRST集合(Grammar for statement sequences) stmt-sequence →stmt stmt-seq’
stmt-seq’ →; stmt-sequence|ε
stmt→s
解：(1) stmt-sequence →stmt stmt-seq’
(2) stmt-seq’ →; stmt-sequence
(3) stmt-seq’ →ε
(4) stmt→s
First(stmt-sequence)={s}
First(stmt-seq’)={;, ε}
First(stmt)={s}
求文法G的FIRST集合
G: (1) M→TB
(2) T→Ba| ε
(3) B →Db|eT| ε
(4) D →d| ε
First(M)={e,a,d,b, ε}
First(T)= {e,a,d,b, ε}
First(B)= {e, d,b, ε}
First(D)= {d, ε}
Follow集合定义：FOLLOW(A)={a| S=> * …Aa…，a∈T}A∈N,
S开始符号特殊地：若S => *...A ，则$∈FOLLOW(A)
1)求文法G的FOLLOW集合(the simple expression grammar)
(1) expr →expr addop term
(2) expr →term
(3) addop →+
(4) addop →-
(5) term →term mulop factor
(6) term →factor
(7) mulop →*
(8) factor →(expr)
(9) factor →number
解：First(expr)={(,number}
First(term)={(,number}
First(factor)={(,number}
First(addop)={+,-}
First(mulop)={*}
Follow(expr)={$,+,-, ) }
Follow(addop)={(,number}
Follow(term)={ $,+,-, *,) }
Follow(mulop)={(,number}
Follow(factor)={ $,+,-, *,) }
2)求文法G的Follow集合(Left factored grammar of if-statement)
statement →if-stmt | other
if-stmt →if (exp) statement else-part
else-part →else statement | ε
exp→0 | 1
解：First(statement)={if,other}
First(if-stmt)={if}
First(else-part)={else,ε}
First(exp)={0,1}
Follow(statement)={$,else}
Follow(if-stmt)={$,else}
Follow(else-part)={$,else}
Follow(exp)={ ) }
3)求文法G的FOLLOW集合(Grammar for statement sequences)
stmt-sequence →stmt stmt-seq’
stmt-seq’ →; stmt-sequence|ε
stmt→s
解：First(stmt-sequence)={s}
First(stmt-seq’)={;, ε}
First(stmt)={s}
Follow(stmt-sequence)={$}
Follow(stmt)={;, $}
Follow(stmt-seq’)={$}
4)求文法G的FOLLOW集合
E→TE’
E’→+TE’|ε
T→FT’
T’→*FT’|ε
F→(E)|i
解：FIRST(F)={ (，i }
FIRST(T’)={*,ε}
FIRST(T)= { (，i}
FIRST(E’)={+,ε}
FIRST(E)= {(，i}
FOLLOW(E)={$, )} FOLLOW(E’)={$, )} FOLLOW(T)={+, ), $} FOLLOW(T’)= {+,),$}
FOLLOW(F)={*, + , ), $}
3、判断文法是否是LL(1)文法；
一个上下文无关文法G是LL(1)文法，当且仅当对G中每个非终结符A的任何两个不同的规则A?α∣β满足：
Select(A?α) ∩Select(A?β) = φ
4、若该文法是LL(1)文法，则构造预测分析表；
（1）对于First(α)中的每个记号a，都将A →α添加到表项M[A, a]中；
（2）若ε在First(α)中，则对于Follow(A)的每个元素a(记号或是$)，都将A →α添加到M[A, a]中。
5、根据分析表进行自顶向下的语法分析。
3、LR分析的四种方法——LR(0)、SLR(1)、LR(1)、LALR(1)，并注意4种方法的区别。
LR(0)项目
初始项目：A?.α
归约项目：A?α.
移进项目：Aα→ . aβ
待约项目：Aα→ . Bβ
例：已知文法G[S]，求其LR(0)的分析表。
S → aA | bB
A → cA | d
B → cB | d
■LR分析方法步骤比较——自底向上的语法分析
共同点：四种LR分析方法的步骤一样，都有如下四步：
(1)拓广文法并对产生式编号；
(2)构造识别文法活前缀的DFA，根据DFA判断为何文法；
(3)分析表的构造；
(4)分析过程。
不同点：（2）（3）步骤中略有不同：
(1)LR(0)与SLR(1)的DFA的状态（有效项目集）中全为LR(0)项（产生式中加点）,LR(1)与LALR(1)的DFA的状态中全为LR(1)项（由LR(0)项和搜索符组成,并由中括号[]括起来）。
(2)分析表：移进项目都一样，在归约项目上不同。
■第5章
1、词法规则的描述工具、语法规则的描述工具、语义规则的常用描述工具：
2、文法符号的语义属性可分为综合属性和继承属性；
3、语法制导的翻译，见下例：
例：给出文法G[S]：S ? SaA|A
A ? AbB|B
B ? cSd|e
为文法G[S]的相应产生式写出语义动作，使句型AacAd经该翻译方案后，输出为11435
1、常见的中间语言——逆波兰式、三地址码、四元式、三元式、间接三元式、树形表示等；
2、各种语句的中间代码翻译（给出一个语句序列能够写出对应的四元式序列）；
例如：求下列语句的四元式序列。
while(x<1&&y==0)
{ a=x+y;
if(a
else x=x-y;
x--;
y=x*x;
}
■第6章
1、符号表的处理是编译程序的重要组成部分；
2、符号表的作用是什么？
答：符号表是编译程序中主要的数据结构之一。它主要用来存放程序语言中出现的有关标识符的信息。编译程序处理标识符时主要涉及两部分内容，一是标识符自身，二是与标识符相关的信息。编译程序的不同分析阶段都要使用符号表。如何有效地组织和快速查找符号表直接影响编译的效率。
3、符号表的组织方式有哪几种？
答：符号表的组织方式一般可分为：直接方式和间接方式。（1）、直接方式：程序中定义的所有标识符及其相关信息都直接填入统一格式的符号表中。优点：结构简单、方便填写和查找；缺点：符号表表项应按
信息量最大的名字设计填表，造成大量空间的浪费。（2）、间接方式：单独设置一个字符串数组，其中存放所有标识符，在符号表的名字栏中设置2项内容：指针和整数。
1.统一符号表：无论什么名字都填入统一格式的符号表中，符号表表项应按信息量最大的名字设计填表；特点：查表比较方便，结构简单，但浪费大量空间。
2.对于不同种类的名字分别建立各种符号表；特点：节省空间，但是填表和查表不方便。
3.折中办法: 大部分共同信息组成统一格式的符号表，特殊信息另设附表,两者用指针连接。
4、如何建立和查找符号表？
答：符号表的基本操作：填表(插入)、查表(查找)和删除。填表:当分析到程序中的说明或定义语句时应将说明或定义的名字以及与之有关的信息填入符号表中。建立符号表可以用不同的数据结构，如线性表：按扫描顺序建表,查表要逐项查找.。二分查找和二叉排序树以及散列表。查表意义:(1) 填表前查表检查在程序的同一作用域内名字是否重复定义；(2) 检查名字的种类是否与说明一致；(3) 生成目标指令时要取得所需要的地址。
■第7章
1、会划分基本块，并能够给出其程序流图；
2、中间代码的局部优化
——会利用DAG对基本块进行优化。
练习题：
1、将下列三地址码序列划分基本块，并画出程序流图。
(1)read a
(2)read b
(3)c=a add b
(4)if r==0 goto (8)
(5)a=b
(6)b=c
(7)goto (3)
(8)write(b)
(9)halt
练习题：
2、已知一基本块如下
(1)B=3
(2)D=A+C
(3)E=A*C
(4)F=E+D
(5)G=B*F
(6)H=A+C
(7)I=A*C
(8)J=H+I
(9)K=B*5
请应用DAG对该基本块进行优化。
应用题知识点
1.正规式、DFA、正规文法的相互转换。
2.句型的证明、短语等相关概念，语法制导的翻译；
3.First/Follow集合；LL(1)文法
4.LR分析方法；
5.中间代码的翻译；
6.基本块的划分；
7.代码优化。
1、基本块的划分及程序流图；
2、基本块内代码优化；
3、将下述语句翻译成四元式形式：
while(a if(a=1) c=c+1; else while(a a=a+2; 4、设有文法：S?BB B?cB|d 请采用合适的LR分析方法判断cdd是否为该文法定义的句子。 5. 文法：S?aAcB|Bd A?AaB|c B?bScA|b （1）消除左递归、提取左因子； （2）求改写后文法每个非终结符的First/Follow集； （3）判断改写后文法是否为LL(1)文法。 6、已知文法G： E?ET+|T T?TF*|F F?F&|a （1）证明EFa&*+T+是该文法的句型。 （2）指出该句型的所有短语、简单短语和句柄。 （3）句型EFa&*+T+经自底向上的语法制导翻译后，输出为tnmzxx，请为文法G的相应产生式写出语义动作。 7、构造与a(a|b)*a(a|b)(ab)*b等价的状态最少的DFA . 编译过程的六个阶段：词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成 解释程序：把某种语言的源程序转换成等价的另一种语言程序——目标语言程序，然后再执行目标程序。 解释方式是接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执 行结果，然后再接受下一句。 编译程序：就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序)。 解释程序和编译程序的根本区别：是否生成目标代码 句子的二义性（这里的二义性是指语法结构上的。）:文法G[S]的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。 文法的二义性:一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。 LL(1)的含义：(LL(1)文法是无二义的； LL(1)文法不含左递归) 第1个L：从左到右扫描输入串第2个L：生成的是最左推导 1：向右看1个输入符号便可决定选择哪个产生式 某些非LL(1)文法到LL(1)文法的等价变换: 1. 提取公因子 2. 消除左递归 文法符号的属性:单词的含义，即与文法符号相关的一些信息。如，类型、值、存储地址等。 一个属性文法(attribute grammar)是一个三元组A=(G, V, F) G：上下文无关文法。 V：属性的有穷集。每个属性与文法的一个终结符或非终结符相连。属性与变量一样，可以进行计算和传递。 F：关于属性的断言或谓词(一组属性的计算规则)的有穷集。断言或语义规则与一个产生式相联，只引用该产生式左端或右端的终结符或非终结符相联的属性。 综合属性:若产生式左部的单非终结符A的属性值由右部各非终结符的属性值决定,则A的属性称为综合属继承属性:若产生式右部符号B的属性值是根据左部非终结符的属性值或者右部其它符号的属性值决定的,则B的属性为继承属性。 (1)非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性。 (2) 终结符只有综合属性，没有继承属性，它们由词法程序提供。 在计算时：综合属性沿属性语法树向上传递；继承属性沿属性语法树向下传递。 语法制导翻译：是指在语法分析过程中，完成附加在所使用的产生式上的语义规则描述的动作。 语法制导翻译实现：对单词符号串进行语法分析，构造语法分析树，然后根据需要构造属性依赖图，遍历语法树并在语法树的各结点处按语义规则进行计算。 中间代码（中间语言） 1、是复杂性介于源程序语言和机器语言的一种表示形式。 2、一般，快速编译程序直接生成目标代码。 3、为了使编译程序结构在逻辑上更为简单明确，常采用中间代码，这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理，并且可以在中间代码一级进行优化工作，使得代码优化比较容易实现。 何谓中间代码：源程序的一种内部表示，不依赖目标机的结构，易于代码的机械生成。 为何要转换成中间代码:(1)逻辑结构清楚；利于不同目标机上实现同一种语言。 (2)便于移植，便于修改，便于进行与机器无关的优化。 中间代码的几种形式：逆波兰记号，三元式和树形表示，四元式 符号表的一般形式：一张符号表的的组成包括两项，即名字栏和信息栏。 信息栏包含许多子栏和标志位，用来记录相应名字和种种不同属性，名字栏也称主栏。主栏的内容称为关键字（key word）。 符号表的功能：（1）收集符号属性(2) 上下文语义的合法性检查的依据：检查标识符属性在上下文中的一致性和合法性。(3)作为目标代码生成阶段地址分配的依据 编译原理的复习提纲 1.编译原理=形式语言+编译技术 2.汇编程序： 把汇编语言程序翻译成等价的机器语言程序 3.编译程序： 把高级语言程序翻译成等价的低级语言程序 4.解释执行方式： 解释程序，逐个语句地模拟执行 翻译执行方式： 翻译程序，把程序设计语言程序翻译成等价的目标程序 5.计算机程序的编译过程类似，一般分为五个阶段： 词法分析、语法分析、语义分析及中间代码生成、代码优化、目标代码生成 词法分析的任务： 扫描源程序的字符串，识别出的最小的语法单位（标识符或无正负号数等） 语法分析是： 在词法分析的基础上的，语法分析不考虑语义。语法分析读入词法分析程序识别出的符号，根据给定的语法规则，识别出各个语法结构。 语义分析的任务是检查程序语义的正确性，解释程序结构的含义，语义分析包括检查变量是否有定义，变量在使用前是否具有值，数值是否溢出等。 语法分析完成之后，编译程序通常就依据语言的语义规则，利用语法制导技术把源程序翻译成某种中间代码。所谓中间代码是一种定义明确、便于处理、独立于计算机硬件的记号系统，可以认为是一种抽象机的程序 代码优化的主要任务是对前一阶段产生的中间代码进行等价变换，以便产生速度快、空间小的目标代码 编译的最后一个阶段是目标代码生成，其主要任务是把中间代码翻译成特定的机器指令或汇编程序 编译程序结构包括五个基本功能模块和两个辅助模块 6.编译划分成前端和后端。 编译前端的工作包括词法分析、语法分析、语义分析。编译前端只依赖于源程序，独立于目标计算机。前端进行分析 编译后端的工作主要是目标代码的生成和优化后端进行综合。独立于源程序，完全依赖于目标机器和中间代码。 把编译程序分为前端和后端的优点是： 可以优化配置不同的编译程序组合，实现编译重用，保持语言与机器的独立性。 7.汇编器把汇编语言代码翻译成一个特定的机器指令序列 第二章 1.符号，字母表，符号串，符号串的长度计算P18，子符号串的含义，符号串的简单运算XY，Xn， 2.符号串集合的概念，符号串集合的乘积运算，方幂运算，闭包与正闭包的概念P19，P20A0 ={ε} 3.重写规则，简称规则。非xx（V 中间语言与语法制导翻译 重点与难点 重点：语法制导翻译的基本思想，属性文法，翻译模式，说明语句的翻译方案。 三地址码，各种语句的目标代码结构、属性文法与翻译模式。 难点：属性的意义，对综合属性，继承属性，固有属性的理解，属性计算，怎么通过属性来表达翻译。布尔表达式的翻译，对各种语句的目标代码结构、属性文法与翻译模式的理解。 基本要求 掌握语法制导翻译的基本思想，属性文法，综合属性，继承属性，固有属性，属性计算，S_属性文法，L_属性文法，说明语句的翻译方案，翻译模式、属性文法的实现掌握中间语言与语义分析的基本概念；熟练掌握语法（结构）树、三地址代码、赋值与控制语句的翻译、说明语句的翻译；掌握组合数据说明的翻译、过程调用翻译。 例题解析 例1 给定文法 E --> T { R.i := T.p } R { E.p := R.s } R --> addop T { R1.i := mknode( addop.val, R.i, T.p ) } R { R.s := R1.s } R --> { R.s := R1.s } T --> ( E ) { T.p := E.p } T --> id { T.p := mkleaf( id, id.entry ) } T --> num { T.p := mkleaf( num, num.val ) } (1) 指出文法中的各非终结符具有哪些综合属性和哪些继承属性 ⑵画出按本翻译模式处理表达式 a + 20 + ( b - 10 ) 时所生成的语法树 【解】 (1)E的综合属性 p，R的继承属性i，综合属性s；T的综合属性p (2) 处理表达式 a + 20 + ( b - 10 ) 时所生成的语法树如下 + （NUM, 20） - ( ID, b) (NUM, 10) 例2 定义一个计算器的属性文法,完成一个输入表达式值的计算和显示, 【解】计算器的文法 L → E 一、填空题|（每题4分，共20分） 1. 乔母斯基定义的3型文法（线性文法）产生式形式 A→Ba|a,或A→aB|a，A，B∈Vn, a,b∈Vt 。 2.语法分析程序的输入是单词符号，其输出是语法单位。 3 型为 B → .aB 的LR（0）项目被称为移进项目，型为 B → a.B 的LR（0） 项目被称为待约项目， 4.在属性文法中文法符号的两种属性分别为继承属性和综合属性。 5、运行时存贮管理方案有静态存储分配、动态存储分配和堆式存储分配和方案。 二.已知文法 G(S) (1) E → T | E+T (2) T → F | F*F (3) F →（E）| i （1）写出句型（T*F+i）的最右推到并画出语法树。（4分） （2）写出上述句型的短语，直接短语和句柄。（4分） 答：（1）最右推到（2分） E ==> T ==> F ==> (E) ==> (E+T) ==> (E+F) ==> (E+i) ==> (T+i) ==> (T*F+i) (2) 语法树（2分） （3）（4分） 短语：（T*F+i），T*F+i ，T*F ， i 直接短语：T*F ， i 句柄：T*F 三. 证明文法G(S) ：S → SaS |ε是二义的。（6分） 答：句子aaa对应的两颗语法树为： 因此，文法是二义文法 四.给定正规文法G（S）： (1) S → Sa | Ab |b (2) A → Sa 请构造与之等价的DFA。（6分） 答：对应的NFA为：（6分） 状态转换表： a b {F} Φ{S} {S} {S,A} Φ {S,A} {S,A} {S} 五. 构造识别正规语言b*a(bb*a)*b* 最小的DFA（要求写出求解过程）。（15分）答：（1）对应的NFA（5分） a b {0} {1，3} {0} {1,3} Φ{2，3} {2,3} {1,3} {2,3} （5分） 六. 已知文法G(S) : (1) S → ^ | a | (T) (2) T → T,S | S 试：（1）消除文法的左递归；（4分） （2）构造相应的first 和 follow 集合。（6分） 答：（1）消除文法的左递归后文法 G’（S）为： (1) S → ^ | a | (T) 扬州大学编译原理课程设计 学号：091202122 姓名： 专业：计算机科学与技术 课程：编译原理 指导教师：陈宏建 目录 一．程序简介与分析---------------------------------------------------------3 二．程序适用范围-----------------------------------------------------------3 三．词法分析---------------------------------------------------------------3 四．语法分析---------------------------------------------------------------4 五．语义分析和中间代码生成------------------------------------------------10 六．代码生成--------------------------------------------------------------12 七．流程图----------------------------------------------------------------13 八．实现------------------------------------------------------------------14 九．程序运行结果----------------------------------------------------------14 十．总结------------------------------------------------------------------18 十一.附录（源程序）--------------------------------------------------------18 一、填空题（每空 2 分，共 30 分） 1、编译程序的整个过程可以从逻辑上划分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等几个阶段，另外还有两个重要的工 作是表格管理和出错处理 2、规范规约中的可归约串是句柄，算符优先分析中的可归约串是最左素短语。 3、语法分析方法主要可分为自顶向下和自底向上两大类。 4、 LR （ 0）文法的项目集中不会出现移进 -归约冲突和归约 -归约冲突。 5、数据空间的动存态储分配方式可分为栈式和堆式两种。 6、编译程序是指能将源语言程序翻译成目标语言程序的程序。 7、确定有穷自动机DFA 是NFA的一个特例。 8、表达式 (a+b)*c的逆波兰表示为ab+c*。 二、选择题（每题 2 分，共 20 分） 1、 L R 语法分析栈中存放的状态是识别B的 DFA 状态。 A 、前缀B、可归前缀C、项目 D 、句柄 2、D不可能是目标代码。 A 、汇编指令代码 B 、可重定位指令代码 C、绝对机器指令代码 D 、中间代码 3、一个控制流程图就是具有C的有向图 A 、唯一入口结点B、唯一出口结点C、唯一首结点 D 、唯一尾结点 4、设有文法G[S] ： S→ b|bB B → bS ，则该文法所描述的语言是C。 A 、 L （ G）={b i|i≥ 0}B、 L （G） ={b 2i |i≥0} C、 L （ G）={b 2i+1|i≥ 0} D 、 L （ G）={b 2i+1|i ≥1} 5、把汇编语言程序翻译成机器可执行的目标程序的工作是由 B完成的。 A 、编译器 B 、汇编器C、解释器D、预处理器6、在目标代码生成阶段，符号表用于D。 A 、目标代码生成 B 、语义检查C、语法检查D、预处理器地址分配0 7、规范归约是指B。 A 、最左推导的逆过程 B 、最右推导的逆过程C、规范推导D、最左归约逆过程 8、使用A可以定义一个程序的意义。 A 、语义规则B、词法规则C、语法规则D、左结合规则 9、经过编译所得到的目标程序是D。 A 、三元式序列B、四元式序列C、间接三元式 D 、机器语言程序或汇编语言程序 10、在一个基本块内进行的代码优化是B。 A 、全局优化B、局部优化C、循环优化D、代码外提 三、简答题（ 3 小题，共 30 分） 1、已知文法G[S]：S→Ac|aB A→ ab B→ bc 证明该文法具有二义性（本题 6 分） 证明：因为该文法的句型abc 存在如下两棵语法树： 所以，该文法具有二义性 一、填空题（每空 1分，共 20分） 1．编译过程一般分为、、中间代码生成、 和目标代码生成五个阶段。 2．语法分析最常用的两类方法是和分析法。 3．确定的有穷自动机是一个，通常表示为。 编译原理期末复习 鉴于编译原理马上就要期末考试，我将手中集中的一些资料上的题目进行了整理归类，每种类型题目给出了所涉及到的基本知识，然后对每类题目中的第一道例题进行了做法进行了讲解，剩下的例题请给大家作为练习，答案也都给出，希望对大家复习有所帮助，最后由于时间很紧，整理的有些仓促，整理中难免有遗漏或错误，请大家见谅。 注：下面出现的字母中，若无特别说明，小写英文字母为终结符，大写英文字母为非终结符，希腊字母为终结符与非终结符的任意组合。 1、简答题（或者名词解释） 下面涉及到的概念中，加下划线的都是在以往一些试卷中出现的原题，务必掌握。 注：这类题目老师说答案不会超过一百个字，否则写的再多也不给分，有些点到即可，不要重复啰嗦。（1）简述编译程序的概念及其构成 答：1）编译程序：它特指把某种高级程序设计语言翻译成等价的低级程序设计语言的翻译程序。 2)构成： （2）简述词法分析阶段的主要任务（也有可能问语法分析阶段主要任务）答：词法分析的任务是输入源程序，对源程序进行扫描，识别其中的单词符号，把字符串形式的源程序转换成单词符号形式的源程序。 语法分析的主要任务是对输入的单词符号进行语法分析（根据语法规则进行推导或者归约），识别各类语法单位，判断输入是不是语法上正确的程序 (3) 简述编译程序的构造过程（这个大家看看，是对（1）和（2）的综合） 答：1）构造词法分析器：用于输入源程序进行词法分析，输出单词符号； 2）构造语法分析器：对输入的单词符号进行语法分析，识别各类语法单位，判断输入是不是语法上正确的程序 3）构造语义分析和中间代码产生器：按照语义规则对已归约出的语法单位进行语义分析并把它们翻译成中间代码。 4）构造优化器：对中间代码进行优化。 5) 构造目标代码生成器：把中间的代码翻译成目标程序。 6) 构造表格管理程序：登记源程序的各类信息和编译各阶段的进展情况。 7)构造错误处理程序：对出错进行处理。 (4) 说明编译和解释的区别： 1)编译要程序产生目标程序，解释程序是边解释边执行，不产生目标程序； 2)编译程序运行效率高而解释程序便于人机对话。 （5）文法：描述语言语法结构的形式规则，一般用一个四元式表示： G=(V T，V N，S，P)，其中V T：终结符集合(非空) V N：非终结符集合(非空)，且V T ?V N=? S：文法的开始符号，S?V N P：产生式集合(有限)。 2.1 设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以及A+和A*. x0=(aaa)0=ε| x0|=0 xx=aaaaaa |xx|=6 x5=aaaaaaaaaaaaaaa | x5|=15 A+ =A1∪A2∪…. ∪A n∪…={a,aa,aaa,aaaa,aaaaa…} A* = A0 ∪A1 ∪A2∪…. ∪ A n ∪…={ε,a,aa,aaa,aaaa,aaaaa…} 2.2 令∑={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3 xy=abcb |xy|=4 xyz=abcbaab |xyz|=7 (xy)3=(abcb)3 =abcbabcbabcb | (xy)3 |=12 2.3设有文法G[S]：S∷=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语 法树。 S => SS* => Sa* => SS+a* => Sa+a* => aa+a* 2.4 已知文法G[Z]：Z∷=U0∣V1 、U∷=Z1∣1 、V∷=Z0∣0 ,请写出全部由此文法描述的只含有四个符号的句子。 Z=>U0=>Z10=>U010=>1010 Z=>U0=>Z10=>V110=>0110 Z=>V1=>Z01=>U001=>1001 Z=>V1=>Z01=>V101=>0101 2.5 已知文法G[S]：S∷=AB A∷=aA︱εB∷=bBc︱bc , 写出该文法描述的语言。 A∷=aA︱ε描述的语言: {a n|n>=0} B∷=bBc︱bc描述的语言：{b n c n|n>=1} L(G[S])={a n b m c m|n>=0,m>=1} 2.6 已知文法E∷=T∣E+T∣E-T 、T∷=F∣T*F∣T/F 、F∷=(E)∣i，写出该文法的开始符号、终结符号集合V T、非终结符号集合V N。 开始符号：E V t={+, - , * , / ,（, ）, i} V n={E , F , T} 2.7 对2.6题的文法，写出句型T+T*F+i的短语、简单短语以及句柄。 短语：T+T*F+i T+T*F Array i i T T*F 简单短语：i T*F T 句柄：T 编译原理复习题 一、选择题 1、编译原理是对(C)。 A、机器语言的执行 B、汇编语言的翻译 C、高级语言的翻译 D、高级语言程序的解释执行 2、(A)是一种典型的解释型语言。 A．BASIC B．C C．FORTRAN D．PASCAL 3、把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。 A. 编译器 B. 汇编器 C. 解释器 D. 预处理器 4、用高级语言编写的程序经编译后产生的程序叫(B) A．源程序 B．目标程序C．连接程序D．解释程序 5、(C)不是编译程序的组成部分。 A.词法分析程序 B.代码生成程序 C.设备管理程序 D.语法分析程序 6、通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。 A．模拟执行器B．解释器 C．表格处理和出错处理D．符号执行器 7、编译程序绝大多数时间花在(D)上。 A．出错处理B．词法分析C．目标代码生成D．表格管理 8、源程序是句子的集合，(B)可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈 9、词法分析器的输出结果是(D)。 A、单词自身值 B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值 10、词法分析器不能(D) A. 识别出数值常量 B. 过滤源程序中的注释 C. 扫描源程序并识别记号 D. 发现括号不匹配 11、文法：G：S→xSx | y所识别的语言是(D)。 A、xyx B、(xyx)* C、x*yx* D、x n yx n (n≥0) 12、如果文法G是无二义的，则它的任何句子α(A) A．最左推导和最右推导对应的语法树必定相同 B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同 D．可能存在两个不同的最左推导，但它们对应的语法树相同 1997年编译原理试题 1．（10分）某操作系统下合法的文件名为 device:name.extension 其中第一部分（device:）和第三部分（.extension）可缺省，若device, name和extension都是字母串，长度不限，但至少为1，画出识别这种文件名的确定有限自动机。 2．（20分） a. 下面的二义文法描述命题演算公式，为它写一个等价的非二义文法。 S—> S and S | S or S | not S | p | q | (S) b. 下面文法是否为LL(1)文法？说明理由。 S—> A B | P Q x A—> x y B—> b c P—> d P | εQ—> a Q | ε 3．（10分）某些语言允许给出名字表的一个属性表，也允许声明嵌在另一个声明里面，下面文法抽象这个问题。 D —> attrlist namelist | attrlist (D) namelist —> id, namelist | id attrlist —> A attrlist | A A —> decimal | fixed | float | real D —> attrlist namelist的含义是：在namelist中的任何名字有attrlist 中给出的所有属性。D—> attrlist (D) 的含义是：在括号中的声明提到的所有名字有attrlist 中给出的所有属性，而不管声明嵌套多少层。写一个翻译方案，它将每个名字的属性个数填入符号表。为简单起见，若属性重复出现，则重复计数。4．（10分）把表达式 -(a+b)*(c+d)+(a+b+c) 翻译成四元式。 5．（10分）由于文法二义引起的LR（1）分析动作冲突，可以依据消除二义的规则而得到LR（1）分析表，根据此表可以正确识别输入串是否为相应语言的句子。对于非二义非LR（1）文法引起的LR（1）分析动作的冲突，是否也可以依据什么规则来消除LR（1）分析动作的冲突而得到LR（1）分析表，并且根据此表识别相应语言的句子？若可以，你是否可以给出这样的规则？ 6．（5分）UNIX 下的C编译命令cc的选择项g和O的解释如下，其中dbx 的解释是“dbx is an utility for source-level debugging and execution of programs written in C”。试说明为什么用了选择项g后，选择项O便被忽略。 -g Produce additional symbol table information for dbx(1) and dbxtool(1) and pass -lg option to ld(1) (so as to include the g library, that is: 《编译原理》期末复习 【题型】 一、填空题：每空1分，共10分； 二、单选题：每题2分，共20分； 三、应用题：每小题6分，共48分； 四、综合分析题：每小题11分，共22分。 【知识点】 1.编译程序的整个过程从逻辑上依次分为哪6个阶段，其中还涉及哪2个重要工作。 2.语法分析有哪两大类方法？ 3.编译程序和解释程序的概念，二者最主要的区别是？ 4.句柄的定义。 5.什么是规范推导？ 6.语言、句型、句子的定义。 7.LR分析法中的项目类型定义（待约项目、移入项目、归约项目）。 8.中间代码和目标代码区别。 9.文法与正则表达式所描述的语言及句子。 10.如何判断自动机（状态转换图）所能识别的字符串。 11.中间代码生成时主要依据什么规则？ 12.根据给定文法，通过推导，画出指定句子的语法树。 13.自底向上的语法分析过程中，构造LR分析表时可能会面临的两种冲突。 14.判断源程序中出现的某类错误可能在编译的哪个阶段被发现。 15.词法分析及语法分析的输入输出是什么？ 16.0、1、2、3型文法的定义、别名及描述能力强弱排名。 17.证明给定文法是二义性的（参考第二章课后练习）。 18.消除文法的左递归及提取公共左因子。 19.给定一个文法和该文法的句型，要求写出句型的最左推导、画出语法分析树、指出短语、简单短 语、句柄（参考第二章课后练习及课件中的例题）。 20.根据有限自动机的定义（五元组），给出其状态转换矩阵和状态转换图。 21.画出按照给定翻译模式分析某句子时所产生的分析树，分析其输出结果（参考第六章课后练习及 课件中的例题）。 22.针对给定的语言构造一个文法G，然后判断该文法类型（0、1、2、3型）（参考第二章课后练习）。 23.根据有限自动机M的定义（五元组），画出M的状态转换图，并说明它所识别或接受的语言是 什么（参考课件第三章例题）。 24.给出一个复合表达式，写出该表达式的三元式和四元式（如：-a*(b+c)/d）。 25.判断某语法制导定义在给定输入下的输出结果，分析文法产生的语言，指出语法制导定义功能。 26.已知文法及其LR分析表，给出对该文法某个句子的分析过程。（参考例题及习题） 27.给定一个文法，消除其左递归和提取左公因子，求所有非终结符的FIRST和FOLLOW集，构造 该文法的LL(1)分析表，根据分析表给出某句子的分析过程（参考第四章课后练习）。 编译原理及实现课后习题解答 2.1设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5 以及A+和A*. x0=(aaa)0=ε| x0|=0 xx=aaaaaa |xx|=6 x5=aaaaaaaaaaaaaaa | x5|=15 A+ =A1∪A2∪ …. ∪A n∪…={a,aa,aaa,aaaa,aaaaa…} A* = A0 ∪A1 ∪A2 ∪…. ∪A n ∪…={ε,a,aa,aaa,aaaa,aaaaa…} 2.2令∑={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3 xy=abcb |xy|=4 xyz=abcbaab |xyz|=7 (xy)3=(abcb)3 =abcbabcbabcb | (xy)3 |=12 2.3设有文法G[S]：S∷=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语 法树。 S => SS* => Sa* => SS+a* => Sa+a* => aa+a* S S S * S S + a a a 2.4 已知文法G[Z]：Z∷=U0∣V1 、U∷=Z1∣1 、V∷=Z0∣0 ,请写出全部由此文法描述的只含有四个符号的句子。 Z=>U0=>Z10=>U010=>1010 Z=>U0=>Z10=>V110=>0110 Z=>V1=>Z01=>U001=>1001 Z=>V1=>Z01=>V101=>0101 2.5已知文法G[S]：S∷=AB A∷=aA︱εB∷=bBc︱bc , 写出该文法描述的语言。 A∷=aA︱ε描述的语言: {a n|n>=0} B∷=bBc︱bc 描述的语言：{b n c n|n>=1} L(G[S])={a n b m c m|n>=0,m>=1} 2.6已知文法E∷=T∣E+T∣E-T 、T∷=F∣T*F∣T/F 、F∷=(E)∣i，写出该文法的开始符号、终结符号集合V T、非终结符号集合V N。 开始符号：E V t={+, - , * , / ,（, ）, i} V n={E , F , T} 第3章文法和语言 第1题 文法G＝({A,B,S},{a,b,c},P,S)其中P为： S→Ac|aB A→ab B→bc 写出L(G[S])的全部元素。 答案： L(G[S])={abc} 第 11题 令文法 G[E]为： E→T|E+T|E-T T→F|T*F|T/F F→(E)|i 证明 E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。答案： 此句型对应语法树如右，故为此文法一个句型。 或者：因为存在推导序列: E=>E+T=>E+T*F，所 以E+T*F句型 此句型相对于E的短语有:E+T*F；相对于 T的短语 有 T*F 直接短语为：T*F 句柄为：T*F 第 13题 一个上下文无关文法生成句子abbaa的推导树如下： (1)给出串abbaa最左推导、最右推导。 (2)该文法的产生式集合 P可能有哪些元素？ (3)找出该句子的所有短语、直接短语、句柄。 A S a S B B B A S a 《编译原理》课后习题答案第三章 答案： (1)串abbaa最左推导: S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa 最右推导： S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa (2)产生式有：S→ABS |Aa|ε A→a B→SBB|b abbaa aaabbaa ? 可能元素有：ε aa ab (3)该句子的短语有： a是相对 A的短语 ε是相对 S的短语 b是相对 B的短语 εbb是相对 B的短语 aa是相对 S的短语 aεbbaa是相对 S的短语 直接短语有：a ε b 句柄是：a 编译原理考试 ————————————————————————————————作者：————————————————————————————————日期： 一、判断对错：（对√；错 ；每小问2分共24分） <1>算符优先分析法是一种规范归约分析法。（ ） <2>若文法Gs中不含形如T→…BD…的产生式，T、B、D∈V N，则称Gs为算符文法。（√） <3>若一个语言是有穷集合，则定义该语言的文法一定是递归的。（ ） <4>若两个正规式所表示的正规集相同，则认为二者是等价的。（√） <5>LR分析法是一种规范归约分析法。（√） <6>一个LR(0)项目集I={B →α.bβ, P →aA.},则说I中含有“移进—归约”冲突。（√） <7>SLR(1)文法是无二义性文法。（√） <8>消除左递归后的文法一定是LL(1)文法。（ ） <9>对任何编译程序而言，代码优化是必不可少的。（ ） <10>编译程序与具体的机器无关。（ ） <11>在自动机的概念中，终态与非终态是可区别的。（√） <12>逆波兰式ab+cd+*所代表的中缀表达式是：(a+b)*(c+d)（√） 1. 一个语言有文法是不惟一的。（√） 2. 若一个语言是无穷集合，则定义该语言的文法一定是递归的。（√） 3. 紧跟在条件转移语句后面的语句是基本块的入口语句。（√） 4. 算符优先分析法是一种规范归约分析法。（ ） 5. 自下而上语法自导翻译的特点：当栈顶形成句柄时，在归约的同时执行其语义动作。（√） 6. LR(0)文法、SLR(1)文法都是无二义性文法。（√） 7．K、∑分别表示有限状态集和有穷字母表, DFA M的转换函数f是一个从K ?∑到K的单值映射。（√） 8. 对任何编译程序而言，代码优化是必不可少的。（ ） 9. 直接短语是某规则的右部，它对应简单子树叶结点从左到右排列形成的符号串。（√） 10. 两个有穷自动机等价是指它们的状态数和有向弧数相等。（ ） 11. 一个LR(0)项目集为：I={A→α.bβ, D→β.},则说I中含有“移进--归约”冲突。 （√） 12. 若两个正规式所表示的正规集相同，则认为二者是等价的。（√） 13. 无左递归的文法是LL(1)文法。（ ） 14. 逆波兰式abcde/+*+所代表的中缀表达式是：a+b*(c+d/e)（√） 15. 编译程序结构中，中间代码优化及目标代码生成两个阶段与具体的机器有关。（ ） 16. LALR分析法中，同心集的合并不会产生“移进--归约”冲突。（√） 编译原理历史与发展 姓名：费张烨学号：09923206 指导老师：朱文华 基于形式语言理论中的有关概念来讨论编译实现问题。即 编译原理=形式语言理论+编译技术 编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。编译原理是计算机专业设置的一门重要的专业课程。虽然只有少数人从事编译方面的工作，但是这门课在理论、技术、方法上都对学生提供了系统而有效的训练，有利于提高软件人员的素质和能力。 编译器是将一种语言翻译为另一种语言的计算机程序。编译器将源程序（source language）编写的程序作为输入，而产生用目标语言（target language ）编写的等价程序。通常地，源程序为高级语言（high-level language ），如C或C + + ，而目标语言则是目标机器的目标代码（object code，有时也称作机器代码（machine code ）），也就是写在计算机机器指令中的用于运行的代码。这一过程可以表示为： 源程序→编译器→目标程序 编译技术的历史 在20世纪40年代，由于冯·诺伊曼在存储-程序计算机方面的先锋作用，编写一串代码或程序已成必要，这样计算机就可以执行所需的计算。开始时，这些程序都是用机器语言（machine language ）编写的。机器语言就是表示机器实 际操作的数字代码，例如：C7 06 0000 0002 表示在IBM PC 上使用的Intel 8x86处理器将数字2移至地址0 0 0 0 （16进制）的指令。 南京工业大学继续教育学院编译原理期末考试试卷 (2012-2013学年) A卷 一、选择题（每题2分，共20分） 得分 1. 一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符，一个_____，以及一组产生式。 A．字符串 B．运算符号 C．开始符号 D．文法 2.程序的基本块是指_____。 A．一个子程序 B．一个仅有一个入口和一个出口的语句 C．一个没有嵌套的程序段 D．一组顺序执行的程序段，仅有一个入口和一 个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于_____分析方法。 A．自左向右 B．自顶向下 C．自底向上 D．自右向左 4．经过编译所得到的目标程序是_____。 A．四元式序列 B．间接三元式序列 C．二元式序列 D．机器语言程序或汇编语言程序 5．运行阶段的存储组织与管理的目的是_____。 ①提高编译程序的运行速度②节省编译程序的存储空间 ③提高目标程序的运行速度④为运行阶段的存储分配做准备 A. ①② B. ②③ C. ③④ D. ④②6．词法分析器的输出结果是_____。 A．( ) 单词的种别编码B．( ) 单词在符号表中的位置C．( ) 单词的种别编码和自身值D．( ) 单词自身值 7．正规式M 1 和M 2 等价是指_____。 A．( ) M1和M2的状态数相等B．( ) M1和M2的有向边条数相等 C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等 8．文法G：S→xSx|y所识别的语言是_____。 A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx* 9．语言是_____。 A．句子的集合B．产生式的集合 C．符号串的集合D．句型的集合 10．编译程序前三个阶段完成的工作是 A．词法分析、语法分析和代码优化 B．代码生成、代码优化和词法分析 C．词法分析、语法分析、语义分析和中间代码生成 D．词法分析、语法分析和代码优化 二、名词解释（每题2分，共20分） 得分 1.最左推导： 2.语法： 3.文法： 4.基本块： 5.语法制导翻译： 6.短语： 7.规范句型： 一、填空题（每空2分，共20分） 1．编译程序首先要识别出源程序中每个单词，然后再分析每个句子并翻译其意义。 2．编译器常用的语法分析方法有自底向上和自顶向下两种。 3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合。 4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即静态存储分配方案和动态存储分配方案。 5．对编译程序而言，输入数据是源程序，输出结果是目标程序。 1．计算机执行用高级语言编写的程序主要有两种途径：解释和编译。 2．扫描器是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。 3．自下而上分析法采用移进、归约、错误处理、接受等四种操作。 4．一个LL（1）分析程序需要用到一张分析表和符号栈。 5．后缀式abc-/所代表的表达式是a/(b-c)。 二、单项选择题（每小题2分，共20分） 1．词法分析器的输出结果是__C。 A．单词的种别编码B．单词在符号表中的位置 C．单词的种别编码和自身值D．单词自身值 2．正规式M 1 和M 2 等价是指__C_。 A．M1和M2的状态数相等 B．M1和M2的有向边条数相等 C．M1和M2所识别的语言集相等D．M1和M2状态数和有向边条数相等 3．文法G：S→xSx|y所识别的语言是_C____。 A．xyx B．(xyx)* C．xnyxn(n≥0) D．x*yx* 4．如果文法G是无二义的，则它的任何句子α_A____。 A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握____D__。 A．源程序B．目标语言C．编译方法D．以上三项都是 6．四元式之间的联系是通过__B___实现的。 A．指示器B．临时变量C．符号表D．程序变量 7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为__B___。 A．┐AB∨∧CD∨B．A┐B∨CD∨∧ C．AB∨┐CD∨∧D．A┐B∨∧CD∨ 8. 优化可生成__D___的目标代码。 A．运行时间较短 B．占用存储空间较小 C．运行时间短但占用内存空间大D．运行时间短且占用存储空间小 9．下列___C___优化方法不是针对循环优化进行的。 A. 强度削弱B．删除归纳变量C．删除多余运算D．代码外提 10．编译程序使用_B_区别标识符的作用域。 A. 说明标识符的过程或函数名B．说明标识符的过程或函数的静态层次 C．说明标识符的过程或函数的动态层次 D. 标识符的行号 三、判断题（对的打√，错的打×，每小题1分，共10分） 2．一个有限状态自动机中，有且仅有一个唯一的终态。x 3．一个算符优先文法的每个非终结符号间都也可能存在优先关系。X 4．语法分析时必须先消除文法中的左递归。X 1、给出下面语言的相应文法。L1={a n b n c i|n≥1,i≥0} 答案：S→AB|B A→a|aA B→bBc|bc 2．给出下面语言的相应文法 L1={a n b n c m d m| m,n≥1，n为奇数，m为偶数}。 答案：文法G(S):S→AC A→aaAbb/ab C→ccCcc/cc 3、构造一个DFA，它接受 ={a，b}上所有包含ab的字符串。 （要求：先将正规式转化为NFA，再将NFA确定化，最小化） (一)相应的正规式为(a|b)*ab(a|b)* (二)①与此正规式对应的NFA为 答案；在自己写的纸上 4、对下面的文法G: E→TE’E’→+E|εT→FT’T’→T|ε F→PF’F’→*F’|εP→(E)|a|b|∧ （1）证明这个文法是LL(1)的。 考虑下列产生式: E’->E|ε T’->T|ε F’->*F’ |ε P->(E) |∧a|b FIRST(+E)∩FIRST(ε)={+}∩{ε}=φ FIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φ FIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φ FIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φ FIRST(*F')∩FIRST(ε)={*}∩{ε}=φ FIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φ FIRST((E))∩FIRST(a) ∩FIRST(b) ∩FIRST(^)=φ 所以,该文法式LL(1)文法. 计算这个文法的每个非终结符的FIRST和FOLLOW。（8分） 答案：FIRST(E)={(,a,b,^} FIRST(E')={+,ε} FIRST(T)={(,a,b,^} FIRST(T')={(,a,b,^,ε} FIRST(F)={(,a,b,^} FIRST(F')={*,ε} FIRST(P)={(,a,b,^} FOLLOW(E)={#,)} FOLLOW(E')={#,)} FOLLOW(T)={+,),#} FOLLOW(T')={+,),#} FOLLOW(F)={(,a,b,^,+,),#} FOLLOW(F')={(,a,b,^,+,),#} FOLLOW(P)={*,(,a,b,^,+,),#} （3）构造它的预测分析表。（6分） 答案；在手机上 写出表达式a+b*(c-d)对应的逆波兰式和三元式序列。 答案：逆波兰式：(abcd-*+) 三元式序列: OP ARG1 ARG2 (1) - c d (2) * b (1) (3) + a (2) 给出下面语言的相应文法 L1={a n b n a m b m|n,m≥0} 给出下面语言的相应文法 答案：S→AB|A|B|∑ A→aAb|ab B→aBb|ab编译原理概念_名词解释
编译原理知识点汇总
编译原理试题
编译原理期末考试习题及答案
编译原理课程设计---C语言编译器的实现
编译原理考试试卷
编译原理期末复习
编译原理及实现课后习题答案(1)
编译原理复习题
编译原理试题
【新版】《编译原理》期末复习
(完整版)编译原理及实现课后习题答案
编译原理复习资料
编译原理考试
编译原理发展史
编译原理考试试卷
编译原理期末考试题目及复习资料
编译原理复习题--有答案版
相关主题
文本预览