编译原理项目集规范族

编译原理作业集

1 第二章 词法分析

1. C或Java语言的标示符是字母和数字组成的序列，第一个字符必须是字母，下划线视为字母，且大小写字母不同。请写出匹配C或Java语言标示符的正规表达式。 2. 为下边所描述的串写正规式，字母表是 {0, 1}. a) 以11 结尾的所有串 b) 只包含一个1的所有串

2 第三章 上下文无关文法

1. ________是描述程序设计语言语法结构的形式工具。 2. 设G=(VN，VT，P，S)是一文法，且 V= VN∪VT，若S =>*α，α∈V，则称α为文法G的 ，若S=>*α，α∈VT，则称α为文法G的 。

3. 给出语言L={ab|j>i>=1}的上下文无关文法。 4. 文法G[S]的产生式如下： S?SaS | SbS | cS | Sd | t 对于输入串 tbctat: (1) 给出一个推导；

(2) 画出(1)中推导对应的分析树；

ij

*

*

(3) 文法G是否是二义性的，请证明你的结论。

3 第四章 语法分析

1. 考虑文法G[S]:

S-> A︱B A->

第一章 引论

一.填空题

1. 对编译程序而言，输入数据是________________；输出数据是_____________。

2. 编译后端通常不依赖于源语言而仅仅依赖于___________________。

3. 如果不需改写编译程序中与机器无关的部分就可以把编译程序移植到另外一个目标机上 ，则称该编译程序是___________________。

4. 描述程序设计语言词法的有效工具是___________________________。

5. 编译过程的每一个阶段都能检测出错误，其中，绝大多数错误在_______________阶段检 测出来的。

6. 编译过程的每一个阶段都能检测出错误，其中，绝大多数错误在_______阶段检测出来的 。

7. 为了使编译后的Java程序从一个平台移到另外一个平台上执行，Java定义了一种称为Byt eCode的虚拟机代码。只要实际使用的操作平台上实现了执行ByteCode的Java解释器，这个

操作平台就可以执行各种Java程序。这就是所谓Java语言的________________。

8. 在一个程序设计环境中，______________起着中心作用。连接程序、调试程

第一章 引论

一.填空题

1. 对编译程序而言，输入数据是________________；输出数据是_____________。

2. 编译后端通常不依赖于源语言而仅仅依赖于___________________。

3. 如果不需改写编译程序中与机器无关的部分就可以把编译程序移植到另外一个目标机上 ，则称该编译程序是___________________。

4. 描述程序设计语言词法的有效工具是___________________________。

5. 编译过程的每一个阶段都能检测出错误，其中，绝大多数错误在_______________阶段检 测出来的。

6. 编译过程的每一个阶段都能检测出错误，其中，绝大多数错误在_______阶段检测出来的 。

7. 为了使编译后的Java程序从一个平台移到另外一个平台上执行，Java定义了一种称为Byt eCode的虚拟机代码。只要实际使用的操作平台上实现了执行ByteCode的Java解释器，这个

操作平台就可以执行各种Java程序。这就是所谓Java语言的________________。

8. 在一个程序设计环境中，______________起着中心作用。连接程序、调试程

第一章 引论

一.填空题

1. 对编译程序而言，输入数据是________________；输出数据是_____________。

2. 编译后端通常不依赖于源语言而仅仅依赖于___________________。

3. 如果不需改写编译程序中与机器无关的部分就可以把编译程序移植到另外一个目标机上 ，则称该编译程序是___________________。

4. 描述程序设计语言词法的有效工具是___________________________。

5. 编译过程的每一个阶段都能检测出错误，其中，绝大多数错误在_______________阶段检 测出来的。

6. 编译过程的每一个阶段都能检测出错误，其中，绝大多数错误在_______阶段检测出来的 。

7. 为了使编译后的Java程序从一个平台移到另外一个平台上执行，Java定义了一种称为Byt eCode的虚拟机代码。只要实际使用的操作平台上实现了执行ByteCode的Java解释器，这个

操作平台就可以执行各种Java程序。这就是所谓Java语言的________________。

8. 在一个程序设计环境中，______________起着中心作用。连接程序、调试程

第一章 引论

一.填空题

1. 对编译程序而言，输入数据是________________；输出数据是_____________。

2. 编译后端通常不依赖于源语言而仅仅依赖于___________________。

3. 如果不需改写编译程序中与机器无关的部分就可以把编译程序移植到另外一个目标机上 ，则称该编译程序是___________________。

4. 描述程序设计语言词法的有效工具是___________________________。

5. 编译过程的每一个阶段都能检测出错误，其中，绝大多数错误在_______________阶段检 测出来的。

6. 编译过程的每一个阶段都能检测出错误，其中，绝大多数错误在_______阶段检测出来的 。

7. 为了使编译后的Java程序从一个平台移到另外一个平台上执行，Java定义了一种称为Byt eCode的虚拟机代码。只要实际使用的操作平台上实现了执行ByteCode的Java解释器，这个

操作平台就可以执行各种Java程序。这就是所谓Java语言的________________。

8. 在一个程序设计环境中，______________起着中心作用。连接程序、调试程

第一章 引论

一.填空题

1. 对编译程序而言，输入数据是________________；输出数据是_____________。

2. 编译后端通常不依赖于源语言而仅仅依赖于___________________。

3. 如果不需改写编译程序中与机器无关的部分就可以把编译程序移植到另外一个目标机上 ，则称该编译程序是___________________。

4. 描述程序设计语言词法的有效工具是___________________________。

5. 编译过程的每一个阶段都能检测出错误，其中，绝大多数错误在_______________阶段检 测出来的。

6. 编译过程的每一个阶段都能检测出错误，其中，绝大多数错误在_______阶段检测出来的 。

7. 为了使编译后的Java程序从一个平台移到另外一个平台上执行，Java定义了一种称为Byt eCode的虚拟机代码。只要实际使用的操作平台上实现了执行ByteCode的Java解释器，这个

操作平台就可以执行各种Java程序。这就是所谓Java语言的________________。

8. 在一个程序设计环境中，______________起着中心作用。连接程序、调试程

编译原理课程项?

计算机学院陈寅

2015-03-09

1简介

本课程为编译原理课程的后序课程。这是?门必修课。2012级的1?5班共214?选修了这门课程。课程项?可以选择完成以下两个题?中的?个。课程项?可以独?完成，也可以?由组合为不超过3个?的?组。如果?组由3?组成，则必须完成可选内容。课程的成绩根据提交的?档和代码评定。

2一阶谓词公式的实例化

我们考虑?个包含?较运算符但是不包含函数符号的?阶语?。谓词??写字母所组成的字符串表?，例如p,q,edge等。变量??写字母开始的字符串表?，例如X,Y,X1,Next等。常量?正整数或者字符串表?，例如1,123,35,”a”,”red”等。常量之间可以?较??。逻辑运算符包括?,∧,∨,→,?,?,?等。?较运算符包括=,<,>,≤,≥,=。?阶逻辑逻辑的公式，?由变元，闭公式，公式的可满?性等概念可参看离散数学的教材。

2.1例子

给定?个?阶公式和它的论域，这个公式的可满?性可以等价为?个对应的命题公式的可满?性。下?是?个例?。设公式集Γ包含如下公式：

?X?Y(p(X)∨?q(Y)∨r(Y))?X(p(X)→?Y(q(Y)∧X=Y))r(1)∧?r(2)

(1)(2)(3)

其中p,q,r是谓词

第二章 高级语言及其语法描述

本章要点

1. 程序语言的定义；

2. 高级程序语言一般结构和主要共同特征； 3. 正确理解上下文无关文法基本概念，包括：

文法的定义、推导、句型、句子、语言、语法树、二义性等； 4. Chomsky文法分类；

本章目标

掌握和理解程序语言的定义、高级语言的一般特征及程序语言的语法描述。

本章重点

1. 语法，词法规则与语法规则； 2. 语义和语义规则； 3. 数据类型与操作；

4. 推导，最左推导和最右推导； 5. 语法分析树和二义性；

本章难点

1. 二义性文法； 2. Chomsky各个文法类；

作业题

一、单项选择题：

（按照组卷方案，至少15道小题）

1. Chomsky把文法分成四种类型，0型、1型、2型和3型。3型文法也称为 ，2型文法也称为 。

a.上下文无关文法 b.上下文相关文法 c.正则文法 d.短语文法 2. 许多广为使用的语言，如Fortran、C、Pascal等，属于 。

a. 强制式语言 b. 应用式语言 c. 基于规则的语言 d. 面向对象的语言 3. 设G是一个文法，S是开始符号。若S?*?，??(VT∪VN)

第二章 高级语言及其语法描述

本章要点

1. 程序语言的定义；

2. 高级程序语言一般结构和主要共同特征； 3. 正确理解上下文无关文法基本概念，包括：

文法的定义、推导、句型、句子、语言、语法树、二义性等； 4. Chomsky文法分类；

本章目标

掌握和理解程序语言的定义、高级语言的一般特征及程序语言的语法描述。

本章重点

1. 语法，词法规则与语法规则； 2. 语义和语义规则； 3. 数据类型与操作；

4. 推导，最左推导和最右推导； 5. 语法分析树和二义性；

本章难点

1. 二义性文法； 2. Chomsky各个文法类；

作业题

一、单项选择题：

（按照组卷方案，至少15道小题）

1. Chomsky把文法分成四种类型，0型、1型、2型和3型。3型文法也称为 ，2型文法也称为 。

a.上下文无关文法 b.上下文相关文法 c.正则文法 d.短语文法 2. 许多广为使用的语言，如Fortran、C、Pascal等，属于 。

a. 强制式语言 b. 应用式语言 c. 基于规则的语言 d. 面向对象的语言 3. 设G是一个文法，S是开始符号。若S?*?，??(VT∪VN)

编译原理作业集 第五章 自下而上语法分析

第五章 语法分析—自下而上分析

本章要点

1. 自下而上语法分析法的基本概念： 2. 算符优先分析法； 3. LR分析法分析过程；

4. 语法分析器自动产生工具YACC； 5. LR分析过程中的出错处理。

本章目标

掌握和理解自下而上分析的基本问题、算符优先分析、LR分析法及语法分析器的自动产生工具YACC等内容。

本章重点

1．自下而上语法分析的基本概念：归约、句柄、最左素短语；

2．算符优先分析方法：FirstVT, LastVT集的计算，算符优先表的构造，工作原理； 3．LR分析器：

（1）LR(0)项目集族，LR(1)项目集簇；

（2）LR(0)、SLR、LR(1)和LALR(1)分析表的构造； （3）LR分析的基本原理，分析过程； 4．LR方法如何用于二义文法；

本章难点

1. 句柄的概念； 2. 算符优先分析法； 3. LR分析器基本；

作业题

一、单项选择题：

1. LR语法分析栈中存放的状态是识别________的DFA状态。

a. 前缀；b. 可归前缀；c. 项目；d. 句柄； 2. 算符优先分析法每次都是对________进行归约：

(a)句柄 （b）最左素短语 (c)素短语