课程测试试题（A卷）
一、填空 （30分）
1、将编译过程的各阶段划分为前端或后端和将编译程序分遍的主要参考因素都是（ ）和（ ）的特征。
2、（ ）是一种语法分析程序的自动构造工具，用它可以直接构造各种语言的语法分析器；而（ ）是一种词法分析程序的自动构造工具，用它可以直接构造各种语言的词法分析器。 3、假设G[S]是一个文法,如有
*S?x,则称x是该文法G的（ ）；文法G产生
的（ ）的全体称为该文法所描述的语言。
4、所谓2型文法就是指（ ）文法，若用G =（VN，VT，P，S）表示它，则它要求G中的所有规则α→β都满足：α是（ ），而β属于（VN U VT）*。 5、文法中形如U→U的规则称为（ ）规则；由不可达的非终结符或不可终止的非终结符作为左部的规则称为（ ）规则。在实用文法中一般不允许含有这两类规则。
6、在用五元组表示的确定的有穷自动机DFAM=（K，V，F，S，Z）中，元素V表示字母表；元素S表示唯一的初态，它是状态集K的一个元素；元素F表示（ ）；元素Z表示终态集，它是状态集K的一个（ ）。
7、语法分析方法分为自上而下与自下而上两类，自上而下的分析方法方要有递归子程序分析法和（ ）；而自下而上的分析方法主要有（ ）和LR分析方法。 8、LR(0)项目集规范族中的项目可分为四类，它们是移进项目、（ ）、归约项目和接受项目。其中，接受项目是（ ）的一种特例。
9、将非LL(1)文法转换为等价的LL(1)文法所采用的两种方法是（ ）和（ ）。但这两种方法并不能保证所有的非LL(1)文法都能转换为等价的LL(1)文法。 10、通常局部优化是指基本块内的优化，所谓基本块是指程序中一顺序执行的语句序列，其中只有一个（ ）语句和一个（ ）语句。
11、算符优先分析时，在句型N1a1N2?ai-1NiaiNi+1ai+1?ajNj+1aj+1Nj+2?中，寻找的最左素短语NiaiNi+1ai+1?ajNj+1中的终结符应满足下优先关系：（ ）、（ ）、（ ）。 12、在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息，这些信息集中反映了标识符的语义特征属性。符号表的功能可以归结为三个主要
方面，即（ ）、作为上下文语义合法性检查的依据和作为（ ）的依据。 13、根据优先关系矩阵计算优先函数可用迭代法或优先关系图法，但先关系图方法计算出来的优先函数不一定有效，当（ ）时，所得的优先函数无效，这时也说明该优先关系矩阵不存在优先函数。
14、当一个过程调用其他过程时，调用过程和被调用过程之间的通信经由非局部变量或者经由参数传递，常用的参数传递方式有（ ）、（ ）等。 15、现代很多编译程序都采用（ ）翻译方法，它是指在语法分析过程中，随着分析的步步进展，根据每个规则所对应的语义子程序或语义动作进行翻译的办法。这种方法使用（ ）为工具来说明程序设计语言的语义。
二、结合你所熟悉的一门高级语言的编译系统，简述典型编译程序在各个工作阶段的任务。(共7分)
三、给定正规式R=(01|10) (01|10)* ，要求： (10分) 1、构造对应的正规文法G，使得L(G)=L(R)。 (4分) 2、构造对应的NFA M状态图，使得L(M)=L(R)。 (3分) 3、将所得NFA M确定化为DFA。 (3分)
四、现有文法G[E]： (共10分)
E→E+T|E-T|T T→T*F|T/F|F F→i|(E)
1、证明：E-F*(i)是文法的一个句型。(3分) 2、构造句型E-F*(i)的语法推导树。(2分) 3、指出该句型所有短语、直接短语和句柄。(5分)
五、任意给定一个文法G[S]： (10分)
1、给出判断G[S]是否为LL(1)文法的步骤。(4分)
2、如果G[S]是LL(1)文法，怎样构造它的预测分析表？(3分) 3、怎样根据预测分析表对给定的某个输入串进行预测分析？(3分)
六、现有文法G[E]：(共15分)
E → E;D|D D→D(T)|H H→a|(E) T→T*E|E
1、计算G[E]的FIRSTVT和LASTVT；(4分)
2、构造G[E]的算符优先关系表,并说明G[E]是否为算符优先文法；(5分) 3、给出输入串(a*a)# 的算符优先分析过程，并据此说明算符优先分析方法的优点和缺点。(6分)
七、现有文法G[S’]： (共18分)
0) S' → S 1) S → L = R 2) S → R 3) L → * R 4) L → i 5) R → L
1、构造G[S’]的LR(0)项目集规范族DFA，并据此判断G[S’]是否为LR(0) 文法或SLR(1)文法。(6分)
2、构造G[S’]的LR(1)项目集规范族DFA，并据此判断G[S’]是否为LR(1)文法或LALR(1)文法。(6分)
3、给出相应的LALR(1)分析表。(3分) 4、简述LR分析算法。(3分)
编译原理课程测试试卷评分标准
（数计学院03A卷）
第一题：填空题（30分）
1、共有30个空，每空1分， 30×1＝30分。 2、参考答案：
题号 1* 2 3 参考源语言、目标机 YACC、LEX 句型、句子 答案 题号 4 5 6 参考上下文无关文法、有害规则、多余规则 状态转换函数、子集 答案 一个非终结符 题号 7 8 9* 参考预测分析方法、算提取左公共因子、消除待约项目、归约项目 答案 符优先分析方法 左递归 题号 10 11* 12 参考ai-1≮ai、aj≯aj+1 收集符号属性、目标代入口、出口 答案 ai≡ai+1≡?≡aj-1≡aj 、 码生成阶段地址分配 题号 13 14* 15 参考图中存在环/回路 传值、传地址 语法制导、属性文法 答案 第二题： （7分)
典型编译程序在各个工作阶段的任务参考答案：
1、词法分析阶段的任务：对构成源程序的字符串进行扫描和分解,识别出单词(如标识符等)符号序列。（1分）
2、语法分析阶段的任务：根据语言的语法规则对单词符号串(符号序列)进行语法分析,识别出各类语法短语(可表示成语法树的语法单位),判断输入串在语法上是否正确。（1分）
3、语义分析阶段的任务：按语义规则对语法分析器归约出的语法单位进行语义分析,审查有无语义错误,为代码生成阶段收集类型信息,并进行类型审查和违背语言规范的报错处理。（1分）
4、中间代码生成阶段的任务：将语义分析得到的源程序变成一种结构简单,含义明确,容易生成,容易译成目标代码的内在代码形式。（1分）
5、代码优化阶段的任务：对中间代码或目标代码进行等价的变换改造等优化处理,使生成的代码更高效。（1分）
6、目标代码生成阶段的任务：将中间代码生成特定机器上的绝对或可重定位的指令代码或汇编指令代码。（1分） 第三题：（10分）
1、正规文法G[S]（4分）：
S→0A|1B A→1S|1 B→0S|0 2、NFA （3分） ：
3、DFA（3分） ： 步骤如下表所示（可省）：
标记 T0 T1 T2 T3 新状态 {S} {A} {B} {S,Z} I0 {A} φ {S,Z} {A} I1 {B} {S,Z} φ {B} 将集合T0至T3各用一个状态表示，确定化后所得DFA M如下：
第四题：（10分）
1、证明（3分）：因为存在推导序列E=>E-T=>E-T*F=>E-F*F=>E- F*(E) =>E-
F*(T)=>E-F*(F)=>E-F*(i)，即有
法的一个句型。 2、语法树（2分）：
E E - T T * F F （ E ） T F *E?E-F*(i)成立，所以，E-F*(i)是文