当前位置：搜档网 › 《编译原理》模拟试题

《编译原理》模拟试题

《编译原理》期末模拟试题及答案

一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）

1．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。(×)

2．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。(×)

3．递归下降分析法是自顶向上分析方法。(√)

4．产生式是用于定义词法成分的一种书写规则。(×)

5．LR 法是自顶向下语法分析方法。(√)

6．在SLR （1 ）分析法的名称中，S的含义是简单的。(√)

7．综合属性是用于“自上而下”传递信息。(×)

8．符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。(×)

9．程序语言的语言处理程序是一种应用软件。(×)

10．解释程序适用于COBOL 和FORTRAN 语言。(×)

二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分)

1．文法G 产生的_____的全体是该文法描述的语言。

A．( ) 句型B．( ) 终结符集C．( ) 非终结符集D．( ) 句子

2．若文法G 定义的语言是无限集，则文法必然是_____。

A．( ) 递归的B．( ) 前后文无关的

C．( ) 二义性的D．( ) 无二义性的

3．四种形式语言文法中，1型文法又称为_____文法。

A．( ) 短语结构文法B．( ) 前后文无关文法

C．( ) 前后文有关文法D．( ) 正规文法

4．一个文法所描述的语言是_____。

A．( ) 唯一的B．( ) 不唯一的

C．( ) 可能唯一，好可能不唯一D．( ) 都不对

5．_____和代码优化部分不是每个编译程序都必需的。

A．( ) 语法分析B．( ) 中间代码生成

C．( ) 词法分析D．( ) 目标代码生成

6．_____是两类程序语言处理程序。

A．( ) 高级语言程序和低级语言程序B．( ) 解释程序和编译程序

C．( ) 编译程序和操作系统D．( ) 系统程序和应用程序

7．数组的内情向量中肯定不含有数组的_____的信息。

A. ( ) 维数B．( ) 类型C．( ) 维上下界D．( ) 各维的界差

8. 一个上下文无关文法G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组_____。

A．( ) 句子B．( ) 句型

C．( ) 单词D．( ) 产生式

9．文法分为四种类型，即0型、1型、2型、3型。其中2型文法是_____。

A. ( ) 短语文法B．( ) 正则文法

C．( ) 上下文有关文法D．( ) 上下文无关文法

10．文法G 所描述的语言是_____的集合。

A. ( ) 文法G 的字母表V 中所有符号组成的符号串

B．( ) 文法G 的字母表V 的闭包V* 中的所有符号串

C．( ) 由文法的开始符号推出的所有终极符串

D. ( ) 由文法的开始符号推出的所有符号串

三、填空题(每空1分，共10分)

1．一个句型中的最左简单短语称为该句型的___句柄__。

2．对于文法的每个产生式都配备了一组属性的计算规则，称为__语义规则___ 。

3．一个典型的编译程序中，不仅包括__词法分析___、__语法分析___、__中间代码生成___、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。

4．从功能上说，程序语言的语句大体可分为__执行性___语句和__说明性___语句两大类。5．扫描器的任务是从__源程序___中识别出一个个___单词符号__。

6．产生式是用于定义__语法范畴___的一种书写规则。

四、简答题（20分）

1. 写一个文法，使其语言是奇数集，且每个奇数不以0开头。

解：文法G(N)：

N→AB|B

A→AC|D

B→1|3|5|7|9

D→B|2|4|6|8

C→0|D

2. 设文法G(S)：

S→(L)|a S|a

L→L，S|S

(1) 消除左递归和回溯；

(2) 计算每个非终结符的FIRST和FOLLOW。

解：(1)

S→(L)|aS'

S'→S|ε

L→SL'

L'→SL'|ε

(2)

FIRST)S)＝{(，a}FOLLOW(S)＝{#，，，)}

FIRST(S')＝{，a,ε}FOLLOW(S')＝{#，，，)}

FIRST(L)＝{(，a}FOLLOW(L)＝{ )}

FIRST(L')＝{，，ε}FOLLOW(L'〕＝{ )}

3. 已知文法G(E)

E→T|E＋T

T→F|T *F

F→(E)|i

(1)给出句型(T *F＋i)的最右推导；

(2)给出句型(T *F＋i)的短语、素短语。

解：(1) 最右推导：E->T->F->(E)->(E＋T)->(E＋F)->(E＋i) ->(T＋

i)->(T*F＋i)

(2) 短语：(T*F＋i)，T*F＋i，T*F，i

素短语：T*F,i

4. While a＞0 ∨b＜0do

Begin

X：＝X＋1；

if a＞0 then a：＝a－1

else b：＝b＋1

End；

翻译成四元式序列。

解：

(1) (j＞，a，0，5)

(2) (j，－，－，3)

(3) (j＜，b，0，5)

(4) (j，－，－，15)

(5) (＋，×，1，T1)

(6) (：＝，T1，－，×)

(7) (j≥，a，0，9)

(8) (j，－，－，12)

(9) (－，a，1，T2)

(10) (：＝，T2，－，a)

(11) (j，－，－，1)

(12) (＋，b，1，T3)

(13) (：＝，T3，－，b)

(14) (j，－，－，1)

(15)

五.计算题（10分）

已知NFA= （{x,y,z},{0,1},M,{x},{z} ），其中：

M(x,0)={z},M(y,0)={x,y},M(z,0)={x,z},M(x,1)={x}, M(y,1)= φ,M(z,1)={y}, 构造相应的DFA并最小化。

编译原理复习题2017(含试卷)

* 编译原理复习题一．简答题： 1) 什么是句子？什么是语言? 解答：句子——设G 是一个给定的文法，S 是文法的开始符号，如果S x （其中x ∈V T * ），则称x 是文法的一个句子。语言——语言是句子的集合。或——设G[S]是给定文法，则由文法G 所定义的语言L(G)可描述为：L(G)＝{x │ S x,x ∈V T * } 。 2) DFA 与NFA 有何区别 ? 解答:DFA 与NFA 的区别表现为两个方面:一是NFA 可以有若干个开始状态，而DFA 仅只有一个开始状态。另一方面，DFA 的映象M 是从K ×∑到K ，而NFA 的映象M 是从K ×∑到K 的子集，即映象M 将产生一个状态集合（可能为空集），而不是单个状态。 3) 自顶向下的语法分析方法的基本思想是什么? 解答:从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。 4) 自底向上的语法分析方法的基本思想是什么? 解答:从给定的输入串（终结符串）开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。 5) 一个上下文无关文法G 包括哪四个组成部分？解答:一组非终结符号，一组终结符号，一个开始符号，以及一组产生式。 6) 在自底向上的语法分析方法中，分析的关键是什么？

解答:关键是寻找句柄。 7)在自顶向下的语法分析方法中，分析的关键是什么？解答:关键是选择候选式。 8）什么是属性文法？答：是在上下文无关文法的基础上，为每个文法符号(含终结符和非终结符)配备若干个属性值，对文法的每个产生式都配备了一组属性计算规则(称为语义规则)。在语法分析过程中，完成语义规则所描述的动作，从而实现语义处理。一个属性文法形式的定义为一个三元组AG，AG=（G，V，E）。其中G为一个上下文无关文法；V为属性的有穷集；E为一组语义规则。 9）语法制导翻译语法制导翻译：定义翻译所必须的语义属性和语义规则，一般不涉及计算顺序。语法制导翻译(Syntax-Directed Translations)： –一个句子的语义翻译过程与语法分析过程同时进行。在文法中，文法符号有明确的意义，文法符号之间有确定的语义关系。属性描述语义信息，语义规则描述属性间的的关系，将语义规则与语法规则相结合，在语法分析的过程中计算语义属性值。 10）词法分析的主要任务是什么？解答:词法分析器的任务是对构成源程序的字符串从左到右逐个字符逐个字符地进行扫描，依次把它们识别为一个一个具有独立意义的单词，并确定其属性，再转换为长度统一的属 11)图示运行时存储空间的划分（分为哪几个区）。解答: 一般分为静态区和动态区：程序代码区、静态数据区、栈区和堆区 12)常用的中间语言种类有哪几种？解答: 常用的中间语言种类有逆波兰表示、三元式、四元式和树形表示。 13）文法G所描述的语言是什么的集合？解答:是由文法的开始符号推出的所有终结符串的集合。或说是句子的集合。 14）乔姆斯基把文法分为四种类型，即0型、1型、2型、3型。其中2型文法叫什么？解答: 2型文法叫上下文无关文法。 15）常见的动态存贮分配策略有哪两种？解答:常见的两种动态存贮分配策略是栈式动态分配策略和堆式动态分配策略。 16）语法分析的任务是什么？

《编译原理》模拟期末试题汇总 6套,含答案

《编译原理》模拟试题一一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） 1．计算机高级语言翻译成低级语言只有解释一种方式。(×) 2．在编译中进行语法检查的目的是为了发现程序中所有错误。(×) 3．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。 (√ ) 4．正则文法其产生式为 A->a ， A->Bb, A,B∈VN ， a 、b∈VT 。 (×) 5．每个文法都能改写为 LL(1) 文法。 (√) 6．递归下降法允许任一非终极符是直接左递归的。 (√) 7．算符优先关系表不一定存在对应的优先函数。 (×) 8．自底而上语法分析方法的主要问题是候选式的选择。 (×) 9．LR 法是自顶向下语法分析方法。 (×) 10．简单优先文法允许任意两个产生式具有相同右部。 (×) 二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．一个编译程序中，不仅包含词法分析，_____，中间代码生成，代码优化，目标代码生成等五个部分。 A．( ) 语法分析B．( )文法分析C．( )语言分析D．( )解释分析 2．词法分析器用于识别_____。 A．( ) 字符串B．( )语句 C．( )单词 D．( )标识符 3．语法分析器则可以发现源程序中的_____。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正D．( ) 语法错误 4．下面关于解释程序的描述正确的是_____。

(1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A．( ) (1)(2) B．( ) (1)C．( ) (1)(2)(3) D．( ) (2)(3) 5．解释程序处理语言时 , 大多数采用的是_____方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行 C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以 6．编译过程中 , 语法分析器的任务就是_____。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A．( ) (2)(3) B．( ) (2)(3)(4) C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4) 7．编译程序是一种_____。 A. ( ) 汇编程序B．( ) 翻译程序 C．( ) 解释程序 D．( ) 目标程序 8．文法 G 所描述的语言是_____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 9．文法分为四种类型，即0型、1型、2型、3型。其中3型文法是_____。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法 10．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _____。 A．( ) 句子B．( ) 句型 C．( ) 单词 D．( ) 产生式三、填空题(每空1分，共10分)

五套编译原理期末考试试卷及复习资料

得分一．填空题（每空2分，共20分） 1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静态存储分配方案和动态存储分配方案，而后者又分为（1）和（2）。 2.规范规约是最（3）规约。 3.编译程序的工作过程一般划分为 5 个阶段：词法分析、（4）、语义分析与中间代码生成，代码优化及（5）。另外还有（6）和出错处理。 4．表达式 x+y*z/(a+b)的后缀式为（7）。 5．文法符号的属性有综合属性和（8）。 6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组 a[1..15,1..20]某个元素 a[i，j]的地址计算公式为（9）。 7．局部优化是局限于一个（10）范围内的一种优化。得分二．选择题（1-6为单选题，7-8为多选题，每问2分，共20分） 1. 一个上下文无关文法 G 包括四个组成部分：一组终结符，一组非终结符，一个（），以及一组（）。 A．字符串B．产生式C．开始符号D．文法 2.程序的基本块是指（）。 A．一个子程序B．一个仅有一个入口和一个出口的语句 C．一个没有嵌套的程序段D．一组顺序执行的程序段，仅有一个入口和一个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（）分析方法。 A．自左向右B．自顶向下C．自底向上D．自右向左 4．在通常的语法分析方法中，（）特别适用于表达式的分析。 A．算符优先分析法B． LR 分析法 C．递归下降分析法D． LL（1）分析法 5．经过编译所得到的目标程序是（）。 A．四元式序列B．间接三元式序列 C．二元式序列D．机器语言程序或汇编语言程序 6．一个文法所描述的语言是（）；描述一个语言的文法是（）。 A．唯一的B．不唯一的C．可能唯一，也可能不唯一

编译原理期末考试卷

2001年编译原理试题 1．（10分）处于/* 和 */之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态转换图。 2．（10分）为语言 L ＝{a m b n | 0 ≤ m ≤ 2n}（即a的个数不超过b的个数的两倍）写一个LR（1）文法，不准超过6个产生式。（若超过6个产生式，不给分。若所写文法不是LR（1）文法，最多给5分。） 3．（10分）构造下面文法的LL（1）分析表。 D → TL T → int | real L → id R R → , id R | ε 4．（15分）就下面文法 S → ( L) | a L → L , S | S ?给出一个语法制导定义，它输出配对括号的个数。 ?给出一个翻译方案，它输出每个a的嵌套深度。如句子(a, (a, a) )，第一小题的输出是2，第二小题的输出是1 2 2。 5．（10分）Pascal语言for语句的含义见教材第222页习题7.13。请为该语句设计一种合理的中间代码结构。你可以按第215页图7.17的方式或者第219页图7.19的方式写出你的设计，不需要写产生中间代码的语法制导定义。 6．（5分）一个C语言程序如下： func(i1,i2,i3) long i1,i2,i3; { long j1,j2,j3; printf("Addresses of i1,i2,i3 = %o,%o,%o\n",&i1,&i2,&i3); printf("Addresses of j1,j2,j3 = %o,%o,%o\n",&j1,&j2,&j3); } main() { long i1,i2,i3;

编译原理考试试卷

一、填空题（每空 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．确定的有穷自动机是一个，通常表示为。

编译原理实验报告一

实验一词法分析程序实现一、实验目得与要求通过编写与调试一个词法分析程序,掌握在对程序设计语言得源程序进行扫描得过程中,将字符流形式得源程序转化为一个由各类单词符号组成得流得词法分析方法二、实验内容基本实验题目：若某一程序设计语言中得单词包括五个关键字begｉｎ、end、if、then、elsｅ；标识符；无符号常数；六种关系运算符；一个赋值符与四个算术运算符，试构造能识别这些单词得词法分析程序（各类单词得分类码参见表Ｉ）。表Ｉ语言中得各类单词符号及其分类码表输入:由符合与不符合所规定得单词类别结构得各类单词组成得源程序文件。输出：把所识别出得每一单词均按形如(CLASS，VＡLUE）得二元式形式输出,并将结果放到某个文件中。对于标识符与无符号常数，CＬASS字段为相应得类别码得助记符;V AL ＵＥ字段则就是该标识符、常数得具体值；对于关键字与运算符,采用一词一类得编码形式，仅需在二元式得CLASS字段上放置相应单词得类别码得助记符，V ALUE字段则为“空". 三、实现方法与环境词法分析就是编译程序得第一个处理阶段，可以通过两种途径来构造词法分析程序.其一就是根据对语言中各类单词得某种描述或定义(如BＮF)，用手工得方式（例如可用Ｃ语言)构造词法分析程序。一般地,可以根据文法或状态转换图构造相应得状态矩阵,该状态矩阵连同控制程序一起便组成了编译器得词法分析程序;也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序得另外一种途径就是所谓得词法分析程序得自动生成，即首先用正规式对语言中得各类单词符号进行词型描述,并分别指出在识别单词时,词法分析程

编译原理习题及答案(整理后)

第一章 1、将编译程序分成若干个“遍”就是为了。 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、词法分析器得输入就是。 a．单词符号串b．源程序 c．语法单位d．目标程序 8、中间代码生成时所遵循得就是- 。 a．语法规则b．词法规则 c．语义规则d．等价变换规则 9、编译程序就是对。 a．汇编程序得翻译b．高级语言程序得解释执行 c．机器语言得执行d．高级语言得翻译 10、语法分析应遵循。 a．语义规则b．语法规则 c．构词规则d．等价变换规则二、多项选择题 1、编译程序各阶段得工作都涉及到。 a．语法分析b．表格管理c．出错处理 d．语义分析e．词法分析 2、编译程序工作时，通常有阶段。 a．词法分析b．语法分析c．中间代码生成 d．语义检查e．目标代码生成三、填空题 1、解释程序与编译程序得区别在于。 2、编译过程通常可分为5个阶段，分别就是、语法分析、代码优化与目标代码生成。 3、编译程序工作过程中，第一段输入就是，最后阶段得输出为程序。

编译原理模拟试题六

《编译原理》模拟试题六一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） 1．设r和s分别是正规式，则有L(r|s)=L(r)L(s)。(×) 2．确定的自动机以及不确定的自动机都能正确地识别正规集。(√) 3．词法分析作为单独的一遍来处理较好。 (× ) 4．构造LR分析器的任务就是产生LR分析表。 (√) 5．规范归约和规范推导是互逆的两个过程。 (× ) 6．同心集的合并有可能产生新的“移进”/“归约”冲突。 (× ) 7．LR分析技术无法适用二义文法。 (× ) 8．树形表示和四元式不便于优化，而三元式和间接三元式则便于优化。 (×) 9．程序中的表达式语句在语义翻译时不需要回填技术。 (√) 10．对中间代码的优化依赖于具体的计算机。 (× ) 二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．编译程序绝大多数时间花在_____ 上。 A．( ) 出错处理 B．( ) 词法分析 C．( ) 目标代码生成D．( ) 表格管理 2．编译程序是对_____。 A．( ) 汇编程序的翻译 B．( ) 高级语言程序的解释执行 C．( ) 机器语言的执行D．( ) 高级语言的翻译

3．采用自上而下分析，必须_____。 A．( ) 消除左递归 B．( ) 消除右递归 C．( ) 消除回溯 D．( ) 提取公共左因子 4．在规范归约中，用_____来刻画可归约串。 A．( )直接短语B．( )句柄 C．( )最左素短语D．( )素短语 5．若a为终结符，则A->α ·aβ为_____项目。 A．( )归约B．( ) 移进C．( ) 接受D．( ) 待约 6．间接三元式表示法的优点为_____。 A．( ) 采用间接码表，便于优化处理B．( ) 节省存储空间，不便于表的修改 C．( ) 便于优化处理，节省存储空间 D．( ) 节省存储空间，不便于优化处理 7．基本块内的优化为_____。 A. ( ) 代码外提，删除归纳变量B．( ) 删除多余运算，删除无用赋值 C．( ) 强度削弱，代码外提 D．( ) 循环展开，循环合并 8. 在目标代码生成阶段，符号表用_____。 A．( ) 目标代码生成B．( ) 语义检查 C．( ) 语法检查D．( ) 地址分配 9．若项目集Ik含有A->α·，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A->α ·”动作的一定是_____。

编译原理实验指导书

《编译原理》实验指导书太原科技大学计算机学院 -3-1

序《编译原理》是国内外各高等院校计算机科学技术类专业，特别是计算机软件专业的一门重要专业课程。该课程系统地向学生介绍编译程序的结构、工作流程及编译程序各组成部分的设计原理和实现技术。由于该课程理论性和实践性都比较强，内容较为抽象复杂，涉及到大量的软件设计和算法，因此，一直是一门比较难学的课程。为了使学生更好地理解和掌握编译原理和技术的基本概念、基本原理和实现方法，实践环节非常重要，只有经过上机进行程序设计，才能使学生对比较抽象的教学内容产生具体的感性认识，增强学生综合分析问题、解决问题的能力，并对提高学生软件设计水平大有益处。为了配合《编译原理》课程的教学，考虑到本课程的内容和特点，本指导书设置了七个综合性实验，分别侧重于词法分析、NFA的确定化、非递归预测分析、算符优先分析器的构造、LR分析、语义分析和中间代码的生成、基于DAG的基本块优化，以支持编译程序的各个阶段，基本涵盖了《编译原理》课程的主要内容。本指导书可作为《编译原理》课程的实验或课程设计内容，在课程教学的同时，安排学生进行相关的实验。实验平台可选择在MS-DOS或Windows操作系统环境，使用C/C++的任何版本作为开发工具。学生在做完试验后，应认真撰写实验报告，内容应

包括实验名称、实验目的、实验要求、实验内容、测试或运行结果等。

目录实验一词法分析 ........................................................... 错误!未定义书签。实验二 NFA的确定化.................................................... 错误!未定义书签。实验三非递归预测分析 ............................................... 错误!未定义书签。实验四算符优先分析器的构造................................... 错误!未定义书签。实验五 LR分析 .............................................................. 错误!未定义书签。实验六语义分析和中间代码生成................................ 错误!未定义书签。实验七基于DAG的基本块优化................................... 错误!未定义书签。

编译原理期末考试习题及答案知识分享

一、填空题|（每题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) (2) T → ST’ | S (3) T’→ ,ST’ |ε（4分）

编译原理试题

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:

编译原理实验报告2

学生学号实验课成绩武汉理工大学学生实验报告书实验课程名称编译原理开课学院计算机科学与技术学院指导老师姓名饶文碧学生姓名学生专业班级

—学年第学期实验课程名称：编译原理实验项目名称单词的词法分析实验成绩实验者专业班级组别同组者实验日期第一部分：实验分析与设计（可加页）一、实验内容描述（问题域描述）完成对某一种常用高级语言（如Pascal、C语言、PL/0语言）的各类单词进行词法分析，即对源程序从左到右进行扫描，对组成源程序的字符串拼接成为单词；并把其转换成属性字输出。实验要求：（1）选择常用高级程序设计语言（如 Pascal、C语言、PL/0语言）的源程序作为词法分析对象。（2）根据教学要求和学生具体情况，从上列语言之一中选取它的一个适当大小的子集，可以选取一类典型单词，也可以尽可能使各种类型的单词都能兼顾到。其基本要求是：对源程序从左到右进行扫描，对组成源程序的字符串拼接成为单词，并把其转换成属性字输出。

二、实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或者算法描述） #include #include #include #include char *table[7]={" ","main","int","if","then","else","return"},TOKEN[20],ch; //定义关键字 int lookup(char *TOKEN){ //关键字匹配函数 int m,i; for(i=1;i<6;i++){ if((m=strcmp(TOKEN,table[i]))==0) return(i); } return(0); } void out(int c,char *TOKEN){ //输出函数 printf("(%d,%s)\n",c,TOKEN); } void scanner(FILE *fp){ //扫描函数

编译原理复习题及参考答案

中南大学网络教育课程考试复习题及参考答案编译原理一、判断题： 1.一个上下文无关文法的开始符，可以是终结符或非终结符。 ( ) 2.一个句型的直接短语是唯一的。 ( ) 3.已经证明文法的二义性是可判定的。 ( ) 4.每个基本块可用一个DAG表示。 ( ) 5.每个过程的活动记录的体积在编译时可静态确定。 ( ) 6.2型文法一定是3 型文法。 ( ) 7.一个句型一定句子。 ( ) 8.算符优先分析法每次都是对句柄进行归约。 ( ) 9.采用三元式实现三地址代码时，不利于对中间代码进行优化。 ( ) 10.编译过程中，语法分析器的任务是分析单词是怎样构成的。 ( ) 11.一个优先表一定存在相应的优先函数。 ( ) 12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( ) 13.递归下降分析法是一种自下而上分析法。 ( ) 14.并不是每个文法都能改写成 LL(1)文法。 ( ) 15.每个基本块只有一个入口和一个出口。 ( ) 16.一个 LL(1)文法一定是无二义的。 ( ) 17.逆波兰法表示的表达试亦称前缀式。 ( ) 18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( ) 19.正规文法产生的语言都可以用上下文无关文法来描述。 ( ) 20.一个优先表一定存在相应的优先函数。 ( ) 21.3型文法一定是 2型文法。 ( ) 22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。 ( ) 二、填空题： 1.( )称为规范推导。 2.编译过程可分为（），（），（），（）和（）五个阶段。 3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（）。 4.从功能上说，程序语言的语句大体可分为（）语句和（）语句两大类。 5.语法分析器的输入是（），其输出是（）。 6.扫描器的任务是从（）中识别出一个个（）。 7.符号表中的信息栏中登记了每个名字的有关的性质，如（）等等。 8.一个过程相应的DISPLAY表的内容为（）。 9.一个句型的最左直接短语称为句型的（）。 10.常用的两种动态存贮分配办法是（）动态分配和（）动态分配。 11.一个名字的属性包括( )和( )。 12.常用的参数传递方式有（），（）和（）。 13.根据优化所涉及的程序范围，可将优化分成为（），（）和（）三个级别。 14.语法分析的方法大致可分为两类，一类是（）分析法，另一类是（）分析法。 15.预测分析程序是使用一张（）和一个（）进行联合控制的。 16.常用的参数传递方式有（），（）和（）。 17.一张转换图只包含有限个状态,其中有一个被认为是（）态;而且实际上至少要有一个（）态。 18.根据优化所涉及的程序范围，可将优化分成为（），（）和（）三个级别。 19.语法分析是依据语言的（）规则进行。中间代码产生是依据语言的（）规则进行的。 20.一个句型的最左直接短语称为句型的（）。 21.一个文法G，若它的预测分析表M不含多重定义，则该文法是（）文法。 22.对于数据空间的存贮分配， FORTRAN采用( )策略， PASCAL采用( )策略。

编译原理考试试题1

编译原理一、(5×6分)回答下列问题： 1．什么是S-属性文法？什么是L-属性文法？它们之间有什么关系？ 2．什么是句柄？什么是素短语？ 3．划分程序的基本块时，确定基本块的入口语句的条件是什么？ 4．运行时的DISPLAY 表的内容是什么？它的作用是什么？ 5．对下列四元式序列生成目标代码： A:=B*C D:=E+F G:=A+D H:=G*2 其中，H 是基本块出口的活跃变量， R0和R1是可用寄存器二、(8分)设∑={0，1}上的正规集S 由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA 。三、(6分)写一个文法使其语言为L(G)={ a n b m a m b n | m,n ≥1}。四、(8分)对于文法G(E): E →T|E+T T →F|T* F F →(E)|i 1. 写出句型(T*F+i)的最右推导并画出语法树。 2. 写出上述句型的短语，直接短语、句柄和素短语。五、(12分)设文法G(S)： ( |*)B B |B A A A |SiA S A →+→→ 1．构造各非终结符的FIRSTVT 和LASTVT 集合； 2．构造优先关系表和优先函数。六、(9分)设某语言的do-while 语句的语法形式为 S → do S (1) While E 其语义解释为：真假 S (1)的代码 E 的代码

针对自下而上的语法分析器，按如下要求构造该语句的翻译模式： (1) 写出适合语法制导翻译的产生式； (2) 写出每个产生式对应的语义动作。七、(8分)将语句if (A0) then while C>0 do C:=C+D; 翻译成四元式。八、(10分) 设有基本块如下： T1:=S+R T2:= 3 T3:= 12/T2 T4:=S/R A:=T1-T4 T5:=S+R B:=T5 T6:=T5*T3 B:=T6 (1)画出DAG图； (2)设A,B是出基本块后的活跃变量，请给出优化后的四元式序列。九、(9分) 设已构造出文法G(S)： (1) S → BB (2) B → aB (3) B→ b 的LR分析表如下 ACTION GOTO 状态 a b # S B 0 s3 s4 1 2 1 acc 2 s6 s7 5 3 s3 s 4 8 4 r3 r3 5 r1 6 s6 s 7 9 7 r3 8 r2 r2 9 r2 假定输入串为abab，请给出LR分析过程(即按照步骤给出状态，符号，输入串的变化过程)。

编译原理期末考试试卷及答案

期末考试试卷（A）卷一、填空题（每小题2分，共20分） 1、字母表∑，用∑*表示∑上所有有穷长的串集合，∑*称为∑的①。 2、设z=abc，则z的固有头是①。 3、如何由语言基本符号组成程序中各个语法成分（包括程序）的一组规则叫 ①。 4、设∑＝{a,b}，∑上的正规式(a|b)(a|b) 相应的正规集为① 5、NFA的映象f是从"状态×字"映射到"状态子集"，f为①值函数。 6、LR分析是按规范句型的①为可归约串。 7、结点的①属性值由该结点的兄弟结点和父结点的属性值计算。 8、如果分析树中一结点的属性b依赖于属性c，那么这个结点的属性b的语义规则的计算必须在定义属性c的语义规则的计算①。 9、对于栈式符号表，引入一个显示嵌套层次关系表- ①表，该表总是指向当前正在处理的最内层的过程的子符号表在栈符号表中的起始位置。 10、任一有向边序列n1 → n2,n2 → n3,…,nk-1 → nk为从结点n1到结点nk 的一条通路。如果n1=nk，则称该通路为①。二、单项选择（每小题2分，共14分） 1、乔姆斯基把文法分成4种类型，即0型、1型、2型和3型。其中3型文法也称为（）。 A．上下无关文法 B.正规文法 C．上下文有关文法 D.无限制文法 2、生成非0开头的正偶数集的文法是（）。 A． Z::=ABC B. Z::=ABC C::=0|2|4|6|8 C::=0|2|4|6|8 B::=BA|B0|ε B::=BA|B0|0 A::=1|2|3|…|9 A::=1|2|3|…|9 C. Z::=ABC|2|4|6|8 D. Z::=ABC|2|4|6|8 C::=0|2|4|6|8 C::=0|2|4|6|8 B::=BA|B0|0 B::=BA|B0|ε A::=1|2|3|…|9 A::=1|2|3|…|9 3、简单优先分析法从左到右扫描输入串,当栈顶出现（）时进归约。

编译原理实验报告：实验一编写词法分析程序

( 编译原理实验报告 , 实验名称：实验一编写词法分析程序实验类型：验证型实验指导教师：何中胜专业班级：（ 13软件四姓名：丁越学号：实验地点：) 秋白楼B720

实验成绩：日期：2016年 3 月 18 日

一、实验目的通过设计、调试词法分析程序，实现从源程序中分出各种单词的方法；熟悉词法分析程序所用的工具自动机，进一步理解自动机理论。掌握文法转换成自动机的技术及有穷自动机实现的方法。确定词法分析器的输出形式及标识符与关键字的区分方法。加深对课堂教学的理解；提高词法分析方法的实践能力。通过本实验，应达到以下目标：[ 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的词法分析程序。二、实验过程以编写PASCAL子集的词法分析程序为例 1.理论部分 > （1）主程序设计考虑主程序的说明部分为各种表格和变量安排空间。数组 k为关键字表，每个数组元素存放一个关键字。采用定长的方式，较短的关键字后面补空格。 P数组存放分界符。为了简单起见，分界符、算术运算符和关系运算符都放在 p表中（编程时，还应建立算术运算符表和关系运算符表，并且各有类号），合并成一类。 id和ci数组分别存放标识符和常数。 instring数组为输入源程序的单词缓存。￥ outtoken记录为输出内部表示缓存。还有一些为造表填表设置的变量。主程序开始后，先以人工方式输入关键字，造 k表；再输入分界符等造p表。主程序的工作部分设计成便于调试的循环结构。每个循环处理一个单词；接收键盘上送来的一个单词；调用词法分析过程；输出每个单词的内部码。 ⑵词法分析过程考虑将词法分析程序设计成独立一遍扫描源程序的结构。其流程图见图 1-1。 …