学海网

吉首大学2006-2007学年第1学期《编译原理》试卷及答案A卷
一、填空题（共30分，30个空，每空1分）
1、典型高级程序设计语言编译系统的工作过程一般分为六个阶段，即词法分析、语法分析、语义分析、中间代码生成、 、目标代码生成。编译阶段的两种组合方式是 组合法和按遍组合法，这两种组合方式的主要参考因素都是 的特征。
2、Chomsky将文法按其所表示语言的表达能力，由高往低分为四类：0型，1型，2型，3型文法。其中，2型文法也称 ，它的所有规则α→β 都满足：α∈ ，β∈ ((VN∪VT) *且 ，仅当β= ε时例外。
3、现代编译系统多采用 方法，即在语法分析过程中根据各个规则所相联的 或所对应的语义子程序进行翻译的办法。该方法使用 为工具来说明程序设计语言的语义。
4、构造与NFA M等价的正规文法G的方法如下：（1）对转换函数f(A，a)=B或f(A，ε)=B，改成形如 或 的产生式；（2）对可识别终态Z，增加一个产生式： 。
5、代码生成要考虑的主要问题：充分利用 的问题、选择 的问题、选择 的问题。
6、设有穷自动机M=(K，，f，S，Z)，若当M为 时，满足z0∈f(S，α)且z0∈Z，或当M为 时，满足f(S，α)=P∈Z，则称符号串α∈*可被M所 。
7、符号表中每一项对应一个多元组。符号表项的组织可分为 组织、 组织、 组织等。
8、对于A∈ＶN 定义A的后续符号集：FOLLOW(A)={a|S=*>uAβ， a∈ＶT，且a∈ ，u∈ＶT*，β∈Ｖ+;若 ，则#∈FOLLOW(A)。也可以定义为：FOLLOW(A)={a|S=*>…Aa…，a∈ＶT}。若有 ，则规定#∈FOLLOW(A)。
9、基本块的定义：一个基本块是指程序中一个 执行的语句序列，其中只有一个入口和一个出口。入口是程序第一个语句或转移语句的目标语句，或转移语句的后继第一个语句。出口是程序 或转移语句。在基本块范围内的优化称为 。
10、预测分析器由预测分析表、先进后出栈（用来存放分析过程的语法符号）和 三部分组成。其中预测分析表是一个二维矩阵，其形式为M[A，a]，其中A∈VN，a∈VT或#。若有产生式A→α，使得a∈ ，则将A→α填入M[A，a]中。(书写时，通常省略规则左部，只填→α)。对所有 的M[A，a]标记为出错。
二、简述题（共20分，4个小题，每小题5分）
1、简述将NFA转换为最小化DFA的步骤。
2、简述静态存储分配、栈式存储分配和堆式存储分配的特点和主要用途。
3、以表达式 a:=b*(-c)+b/(-d)为例，简述常用的三种中间代码表示形式。
..........
吉首大学2006-2007学年第1学期《编译原理》试卷及答案B卷
一、填空题（共30分，30个空，每空1分）
1、典型编译过程一般分为词法分析、语法分析、语义分析、 （并非所有的编译程序都包含此阶段）、代码优化、目标代码生成六个阶段，其中词法分析的任务是对构成源程序的字符串进行扫描和分解，识别出 (如标识符等)符号；为代码生成阶段收集类型信息，并进行类型审查和违背语言规范的报错处理是 的任务。
2、文法是一些规则的有穷集合，它是以有穷规则集来刻划无穷 集合的工具。文法的四元组表示G =（VN，VT，P，S）中，元素VN，VT 分别是非空有限的 。且二者交集为φ；P为产生式/规则集，是文法的核心部分；S ∈ VN，是文法的开始符号(或识别符) ，它是一个非终结符，至少要在一条规则中作为 出现。
3、构造ＬＲ（０）项目集规范族的项目类型分为四种：形如A→α.aβ的 、形如 的待约项目、形如A→αBβ.的归约项目、形如S'→α.的 。
4、一个优先关系矩阵对应的优先函数 ；所表示优先关系唯一的矩阵不一定存在优先函数；当两个终结符对之间无优先关系时， 可以将相应元素置出错信息，而使用 却无法识别这种情况，不能准确指出出错位置。
5、在编译程序中用符号表来存放语言中出现的有关 的语义特征属性信息。程序设计语言中通用的标识符属性主要有如下几种：符号名、符号的 、符号的存储类别、符号的 、符号变量的存储分配信息及数组的内情向量等其它属性。
6、如果文法G=（ VN，VT，P，S）中不存在形如 A→…BC…的产生式，其中B、C为非终结符，则称之为 。在此基础上，如果 a,b∈VT, a≡b,a≮b,a≯b 至 有一个成立，则称之为 。
..........
吉首大学2005-2006学年第1学期《编译原理》试卷及答案A卷
一、填空 （30分）
1、将编译过程的各阶段划分为前端或后端和将编译程序分遍的主要参考因素都是（ ）和（ ）的特征。
2、（ ）是一种语法分析程序的自动构造工具，用它可以直接构造各种语言的语法分析器；而（ ）是一种词法分析程序的自动构造工具，用它可以直接构造各种语言的词法分析器。
3、假设G[S]是一个文法,如有Sx,则称x是该文法G的（ ）；文法G产生的（ ）的全体称为该文法所描述的语言。
4、所谓2型文法就是指（ ）文法，若用G =（VN，VT，P，S）表示它，则它要求G中的所有规则α→β都满足：α是（ ），而β属于（VN U VT）*。
5、文法中形如U→U的规则称为（ ）规则；由不可达的非终结符或不可终止的非终结符作为左部的规则称为（ ）规则。在实用文法中一般不允许含有这两类规则。
。。。。。。。。。