编译原理select集合的功能

1. 简要说明语义分析的基本功能。

答：语义分析的基本功能包括: 确定类型、类型检查、语义处理和某些静态语义检 查。

2. 考虑文法 G[S]: S → (T) | a+S | a T → T,S | S

消除文法的左递归及提取公共左因子。 解：消除文法G[S]的左递归： S→(T) | a+S | a T→ST′ T′→,ST′| ε 提取公共左因子： S→(T) | aS′ S′→+S | ε T→ST′ T′→,ST′| ε

3. 试为表达式 w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。 解： w a b + c d e 10 - / + 8 + * +

4. 按照三种基本控制结构文法将下面的语句翻译成四元式序列： while (A

if (A ≥ 1) C=C+1; else while (A ≤ D) A=A+2; }。

第1页共6页

解：该语句的四元式序列如下(其中E1、E2和E3分别对应A＜C∧B＜D、A≥1和A≤D，并且关系运算符优先级高)： 100 (j<,A,C,102) 101 (j,_,_,113) 102 (j<,B,D,104) 103 (j,_,_,113) 104 (j=,A,1,106) 105 (j,_,_,108) 106 (+, C, 1, C) 107 (j,_,_,112) 108 (j≤,A,D,110) 109 (j,_,_,112) 110 (+, A, 2, A) 111 (j,_,_,108) 112 (j,_,_,100) 113

5. 已知文法 G[S] 为 S → aSb|Sb|b ，试证明文法 G[S] 为二义文法。 证明：

由文法G[S

实验报告

课程名称：编译原理 实验名称：实验三 扩展功能的PL/0编译程序

班级： 姓名： 学号：

一．实验目的

在分析理解PL/0编译程序的基础上，对其词法分析程序、语法分析程序和语义处理程序进行部分修改扩充。

二．实验内容

在PL/0语言的基础上增加对整型一维数组的支持、扩充IF-THEN-ELSE条件语句、增加REPEAT语句、支持带参数的过程和增加注释等，如下所示：

（1）整型一维数组，数组的定义格式为： VAR<数组标识名>(<下界>:<上界>)

其中上界和下界可以是整数或者常量标识名。

访问数组元素的时候，数组下表是整型的表达式，包括整数、常量或者变量和他们的组合。

(2)扩充条件语句，格式为：

<条件语句> ::= IF<条件>THEN<语句> [ELSE<语句>]

(3)增加REPEAT语句，格式为：

<复合语句> ::= REPEAT<语句>UNTL<条件>

三．实验过程

运行步骤：

把pl0.c和pl0.h两个文件放在同一目录下，直接用Visual C++ 6.0(sp6)打开便可运行

然后运行后输入PL/0源程序文件名，回答是否输

1. 编译程序的功能（P1，图1.1）

1) 高级语言程序（源程序）→编译程序→低级语言程序（目标程序） 2)

2. 编译过程和编译程序的结构（P2）

1) 编译过程划分成了词法分析、语法分析、语义分析、中间代码生成、代码优化、目

标代码生成六个阶段 2) 编译程序结构框图

3)

3. 解释程序（P7）

1) 不需要在运行前把源程序翻译成目标代码，也可以让我们实现在某台机器上运行程

序并生成结果 2)

4. 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程

序的总体结构图。 （P11，习题2） 答：一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。

词法分析程序：从左到右扫描源程序，识别单词及其相关属性

语法分析程序：分析源程序的结构，判别它是否为相应程序设计语言中的一个合法程序

语义分析程序：审查源程序有无语义错误，为代码生成阶段收集类型信息 中间代码生成程序：将源程序变成一种内部 表示形式。

代码优化程序：对中间代码进行变换或改造，使生成的代码更为高效

目标代码生

编译原理实验

吴海涛 2013-11-1

目 录

相关问题说明................................................................................................................ 1 实验题............................................................................................................................ 2 实验1 词法分析（2课时）........................................................................................ 3 实验2 语法分析（2课时）........................................................................................ 5 实验3 语义分析（2课时）.................................

编译原理题库

一、选择题：

1.编译原理是对（C）。A、机器语言的执行B、汇编语言的翻译C、高级语言的翻译D、高级语言程序的解释执行

2.编译程序是将高级语言程序翻译成D。A、汇编语言程序 B、机器语言程序C、高级语言程序 D、汇编语言或机器语言程序

3.文法：G：S→xSx | y所识别的语言是（D）。A、xnyxm B、(xyx)*C、x*yx* D、xnyxm（n≥0） 4.设有文法G[I]： I→I0|I1|I a|Ic|a|b|c

下列符号串中是该文法的句子的有B。 ①ab0 ②a0c01 ③aaa ④bc10

可选项有A、① B、②③④ C、③④ D、①②③④

5.词法分析器的输出结果是（C）。A、单词自身值B、单词在符号表中的位置C、单词的种别编码D、单词的种别编码和自身值

6.为了使编译程序能够对程序设计语言进行正确的翻译，必须采用_C_方法定义程序设计语言。A、非形式化B、自然语言描述问题C、形式化D、自然语言和符号体系相结合

7. 若文法G定义的语言是无限集，则文法必然是（C）A.前后文无关文法B.正规文法C.二义性文法D.递归文法

8、描述一个语言的文法是B。A、唯一的B、不唯一的C、个数有限的 9、表达式（

第一章 编译程序概述

1.1 什么是编译程序

编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都含有不止一个高级语言的编译程序。对有些高级语言甚至配置了几个不同性能的编译程序。 1.2编译过程概述和编译程序的结构

编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。从概念上来讲，一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的。一般一个编译过程划分成词法分析、语法分析、语义分析、中间代码生成，代码优化和目标代码生成六个阶段,这是一种典型的划分方法。事实上，某些阶段可能组合在一起，这些阶段间的源程序的中间表示形式就没必要构造出来了。我们将分别介绍各阶段的任务。另外两个重要的工作：表格管理和出错处理与上述六个阶段都有联系。编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作；如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还

编译原理复习

一、基本概念（填空15分，选择10分，简答：15分）

1、编译程序按扫描源程序的遍数分类可以分为哪两类？ 一遍扫描、多遍扫描 2、高级语言的单词分类有哪些？ 基本字、运算符、标识符、常数、界符

3、二义性文法，二义性语言的定义？二义性文法：文法G对某句型存在至少两种不同的语法

树。 二义性语言：某语言对应的任意一种文法都是二义性文法 4、DFA的定义及组成：确定的有穷自动机； M=(K,∑,f, S,Z)

K是一个有穷集，它的每个元素称为一个状态；

∑是一个有穷字母表，它的每个元素称为一个输入符号，所以也称∑为输入符号表； F是转换函数，是K×∑→K上的映像 S∈K，是唯一的一个初态 Z K，是一个终极态，终态也称为接收状态或结束状态

5、最左推导、规范推导的定义：最左推导：若x和y是符号串α中有两个以上的非终结符号时，

对推导的每一步坚持把α中的最左非终结符号进行替换，称为最左推导。

规范推导：通常，我们把能由最左 (右)推导推出的句型称为左 (右)句型。另外，也常把最右推导称为规范推导，而把右句型称为规范句型。

6、确定的自顶向下分析方法通常有哪两种？采用确定的自顶向下分析的前提条件是什么？ 递归子程序法、预

一、 选择

1、 构造编译程序应掌握（ ）

A.源程序 B.目标文件 C.编译方法 D.以上三项 2、编译程序绝大多数时间花在（）上

A.出错处理 B.词法分析 C.目标代码生成 D.表格管理 3、编译程序是对（）

A.汇编程序的翻译 B.高级语言程序的解释执行 C.机器语言的执行 D.高级语言的翻译 4、词法分析器的输出结果是（ ）

A.单词的种别编码 B.单词在符号表中的位置 C.单词的种别编码和自身值 D.单词自身值 5、正规式M1和M2等价是指（ ） A. M1和M2的状态数相等 B. M1和M22的有向变条数相等 C. M1和M2所识别的语言集相等 D. M1和M2状态数和有向边条数 6、DFA M接受的字集为（ ） A.以0开头的二进制数组成的集合 B.以0结尾的二进制数组成的集合 C.含奇数个0的二进制数组成的集合 D.含偶数个0的二进制数组成的集合 7、文法G[S]:S→xSx|y所识别的语言是（ ）

A.xyx B.（xyx）* C.xnyxn（n≥0） D.xnyxn

编译原理试卷A

选择题(每空2分,共20分) 1.一个正规语言只能对应( B ) A 一个正规文法;

B 一个最小有限状态自动机;

2.文法G[A]:A→ε A→aB B→Ab B→a是( B ): A 正规文法 B 二型文法

3.下面说法正确的是( A ):

A 一个SLR(1)文法一定也是LALR(1)文法 B 一个LR(1)文法一定也是LALR(1)文法

4.一个上下文无关文法消除了左递归,提取了左公共因子后是满足LL(1)文法的( A ): A 必要条件 B 充分必要条件

5. ( D )不是NFA的成分.

A 由穷字母表 B 初始状态集合 C 终止状态集合 D 有限状态集合 6.(C )不是编译程序的组成部分

A 词法分析程序 B 代码生成程序 C 设备管理程序 D 语法分析程序 7.有文法G=({S},{a},{S→SaS, S→ε},S),该文法是( B ).

A. LL(1)文法 B. 二义性文法 C 算符优先文法 D SLR(1)文法

8 给定文法 A→bA|cc,则符号串①cc②bcbc③bcbcc④bccbcc⑤bbbcc中,是该文法句子的是( D )

A ① B ③④⑤ C ②④ D ①⑤

9 表达式A

作业一

1.已知文法G[A]，写出它定义的语言描述 如：G[A]:

A → 0B|1C

B → 1|1A|0BB C → 0|0A|1CC

2. 给出生成下述语言的上下文无关文法：

nnmm

（1）{ abab| n，m>=0}

nm mn

(2) { 1010| n，m>=0}

3. 给出生成下述语言的三型文法：

nm

(1){ ab|n,m>=1 }

nmk

(2){abc|n,m,k>=0 }

4、文法G[E]为： E→E+T|T T→T*F|F F→(E)|i

试给出句型(E+F)*i的短语，简单(直接)短语,句柄。

第3章练习题

一、判断题:

1、 编译程序中的词法分析程序以字符形式的源程序作为输入，输出的单词符号常

采用二元组的形式。

2、 正规式的运算符“|”读作“或“。

3、 若两个正规式所表示的正规集相同，则认为二者是等价的。

4、 用l代表字母，d代表数字，Σ={l，d}，则正规式r=dd*定义了无符号整数单词。 5、 一个确定的有穷自动机DFA M的转换函数f是一个从KⅹΣ到K 的子集的映像。

*

6、 一个非确定的有穷自动机