课程测试试题（B卷）
一、判断（15分）
1、编译程序是一种语言翻译程序，它将源语言程序翻译成功能等价的目标语言程序。
2、所谓规则或产生式是指形如α→β或α::=β的(α,β)有序对，其中α是字母表V的正闭包元素,而β是字母表V的闭包元素。
3、设文法G =（VN，VT，P，S），若P中的每一个规则都是A→aB或A→a，其中A和B是非终结符，而a是终结符，则称此文法G为正规文法或3型文法。
4、实用文法中不得含有形如U→U的有害规则，也不得含有由不可达或不可终止的非终结符所构成的多余规则。
5、对任意给定的一个正规式R，都可以将它转换为与之功能等价的正规文法，或与之功能等价的有穷自动机。
6、LEX是一个用于构造各种各样语言的词法分析程序；YACC是一个用于构造各种各样语言的语法分析程序。
7、假设现有五元组表示的有穷自动机M=（K，V，F，S，Z），若M是NFA，则S表示初态，且S具有唯一性，它是状态集K的一个元素。
8、算符优先分析方法和LR分析方法都是自下而上的分析方法，它们的分析过程实际上就是规范归约过程。
9、LR(0)项目集规范族中的项目由两部分构成，一部分是心，即原来的LR(1)项目，另一部分是向前搜索符号集。
10、所谓优化实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前的代码运行结果相同，但运行速度或占用的存储空间加大。常用的优化技术有删除多余运算、代码外提、强度削弱、变换循环控制条件、合并已知变量与复写传播等。
11、对一个不包含空规则的算符文法，如果文法中的任意两个终结符构成的符号对之间最多只有大于、小于和等于三种优先关系中的一种成立，则称该算符文法为算符优先文法。
12、目标程序运行时的动态数据存储区分为堆区和栈区，它用于存放可变数据以及管理过程活动的控制信息。
13、在语法分析过程中，随着分析的步步进展，根据每个规则所对应的语义
子程序或语义动作进行翻译的办法，称为语法制导翻译，它被现代很多编译程序所采用。
14、可归前缀本身就是活前缀，它是包含句柄在内的活前缀。
15、符号表用来存放语言程序中出现的有关标识符的属性信息，这些信息集中反映了标识符的语义特征属性。
二、将表达式A:=B*（C-D）/D： (共9分) 1、翻译成逆波兰式的中间代码形式。(2分) 2、翻译成四元式的中间代码形式。(4分) 3、将译成的四元式用DAG表示。(3分)
三、现有文法G[E]： (共12分)
E→E+T|E-T|T T→T*F|T/F|F F→i|(E)
4、证明：F+T*(E)是文法的一个句型。(3分) 5、构造句型F+T*(E)的语法推导树。(3分) 6、指出该句型所有短语、直接短语和句柄。(6分)
四、给定正规式R=d(a|bc)*d，要求： (12分)
1、构造对应的NFA M状态图，使得L(M)=L(R)。 (4分) 2、将所得NFA M确定化和最小化。 (8分)
五、现有文法G[S]：(共16分) S →S;D|D
D →D(T)|H H →m|(S) T →T*S|S
1、计算G[S]的FIRSTVT和LASTVT；(4分)
2、构造G[S]的算符优先关系表,并说明G[S]是否为算符优先文法；分)
(6
3、给出输入串(m*m)# 的算符优先分析过程。(4分) 4、根据分析过程总结算符优先分析方法的优缺点。(2分)
六、已知G[S]： (18分)
S→(A)|a|b A→A,S|S
1、给出(a,(b,b))的最左推导。(3分)
2、判断该文法是否为LL(1)文法。若是，直接给出它的预测分析表；若不是，先将其改写为LL(1)文法，再给出它的预测分析表；(10分)
3、给出输入串(b,b)#的分析过程，并说明该串是否为G[S]的句子。(5分)
七、对给定文法G[S’]: (共18分)
0) S’ →S 1) S →A 2）S →B 3) A →aAc 4) A →a 5) B →bBd 6) B →b
1、构造G[S’]的LR(0)项目集规范族DFA，并据此判断G[S’]是否为LR(0)文法。 (6分)
2、进一步判断G[S’]是否为SLR(1)文法，并给出对应的SLR(1)分析表。(6分) 3、给出输入串bbd#的SLR(1)分析过程。(4分)
4、判断G[S’]是否为LR(1)文法和LALR(1)文法。 (2分)
编译原理课程测试试卷评分标准
（数计学院03B卷）
第一题：判断题（15分）
1、共有15道小题，每小题1分， 15×1＝15分。
2、答案：
第二题：（9分)
1、表达式A:=B*（C-D）/D的逆波兰式表示：ABCD-*D/:= 。(2分) 2、表达式A:=B*（C-D）/D的四元式表示：(4分) （1）（-，C，D，t1） （2）（*，B，t1,t2） （3）（/，t2，D，t3） （4）（:=，t3,_,A） 3、 将译成的四元式用DAG表示:（3分）
B
C
D
第三题：（12分）
1、证明（3分）：因为存在推导序列E => E+T => T+T =>F+T =>F+T*F =>
*
F+T*(E)，即有 E
F+T*(E)成立，所以，F+T*(E)是文法的一个句型。
2、语法树（3分）
3、句型分析（6分）
句型F+T*(E)相对于E的短语有: F+T*(E), F。 句型F+T*(E)相对于T的短语有: F, T*(E)。 句型F+T*(E)相对于F的短语有: (E)。 （3分） 句型F+T*(E)相对于T→F的直接短语有: F 。
句型F+T*(E)相对于F→(E)的直接短语有: (E) 。（2分） 句型F+T*(E)的句柄为: F。 （1分） （2）短语每错两个扣1分。
第四题：（12分） 1、NFA M （4分）
2、(1)确定化（4分） 步骤如下表所示（可省）：
将集合T0至T3各用一个状态表示，确定化后所得DFA M如下：
(2)最小化 （4分） 步骤如下表所示（可省）：
最后还有4个不可再分割的子集，每个子集中只包含一个状态，即原DFA M已经是最小化DFA 。
第五题： (16分)
1、对文法进行拓广，加入规则S’→S 后得G[S’]，其非终结符的FIRSTVT、LASTVT 集计算如下：（4分）
由FIRSTVT、LASTVT 集构造≮和≯如下：
2、（1）优先关系表为：（4分）
（2）该文法是算符优先文法（2分）。
3、（1）输入串（m*m）# 的算符优先分析过程：（4分）
（2由上述分析过程可知，用算符优先分析法分析在确定句柄时只考虑终结符之间的优先关系，而与非终结符无关，这使得算符优先分析法具有效率高的优点；但是，由于去掉了单非终结符之间的归约，有可能将错误的句子识别为正确的。上例中对输入串(m*m)#能分析成功，但(m*m)#并不是文法G[S]的句子。这就是算符优先分析法的缺点。
第六题： (18分)
1、给出(a,(b,b))的最左推导：(3分)
S=>(A)=>(A,S)=>(S,S)=>(a,S)=>(a,(A))=>(a,(A,S))=>(a,(S,S))=>(a,(b,S)) =>(a,(b,b))
2、(1)判断：(3分)
计算各条规则的SELECT集及左部相同规则的SELECT集的交集如下：
（2）将G[S]改写如下：(4分)
G[S]： S→a|b|(A) A’→,SA’|ε A→SA’
（2）预测分析表：(3分)
4、
第七题： (18分)
1、（1）G[S’]的LR(0)项目集规范族DFA（4分）：
（2）检查发现I4 ={A →a., A →.aAc, A →.a }和I5 ={B →b., B →.bBd, B →.b }中存在移进—归约冲突，所以，G[S’]不是LR(0)文法。（2分）
2、（1）在I4 ={A →a., A →.aAc, A →.a }中，由于根据归约项目A →a.所得的FOLLOW(A)={c,# }中不含移进项目A →.aAc,或 A →.a中的“a”。在构造LR分析表时，遇到移进项目A →.aAc,或 A →.a时，在“a”列置移进标记S4；遇到归约项目A →a.时，只在“c”,“#”两列置归约标记r4。所以，I4中的移进—归约冲突通过引入FOLLOW集得到了解决。、
同样，在I5 ={B →b., B →.bBd, B →.b }中，由于FOLLOW(B)={d,# }中不含 “b”。在构造LR分析表时，遇到移进项目B →.bBd, B →.b时，在“b”列置移进标记S5；遇到归约项目B →b.时，只在“d”,“#”两列置归约标记r5。所以，I5中的移进—归约冲突通过引入FOLLOW集也得到了解决。
故G[S’]是 SLR（1）文法。（3分） （2）SLR(1)分析表如下：（3分）
3 > LALR(1) > SLR(1) > LR(0) 知：一个LR(0)文法肯定是SLR(1) 文法；一个SLR(1)文法肯定是LALR(1)文法；而一个LALR(1)文法肯定是LR(1)文法。既
然G[S’] 是SLR（1）文法，那么，它肯定也是LR(1)文法和LALR(1)文法。（2分）
课程测试试题（B卷）
一、判断（15分）
1、编译程序是一种语言翻译程序，它将源语言程序翻译成功能等价的目标语言程序。
2、所谓规则或产生式是指形如α→β或α::=β的(α,β)有序对，其中α是字母表V的正闭包元素,而β是字母表V的闭包元素。
3、设文法G =（VN，VT，P，S），若P中的每一个规则都是A→aB或A→a，其中A和B是非终结符，而a是终结符，则称此文法G为正规文法或3型文法。
4、实用文法中不得含有形如U→U的有害规则，也不得含有由不可达或不可终止的非终结符所构成的多余规则。
5、对任意给定的一个正规式R，都可以将它转换为与之功能等价的正规文法，或与之功能等价的有穷自动机。
6、LEX是一个用于构造各种各样语言的词法分析程序；YACC是一个用于构造各种各样语言的语法分析程序。
7、假设现有五元组表示的有穷自动机M=（K，V，F，S，Z），若M是NFA，则S表示初态，且S具有唯一性，它是状态集K的一个元素。
8、算符优先分析方法和LR分析方法都是自下而上的分析方法，它们的分析过程实际上就是规范归约过程。
9、LR(0)项目集规范族中的项目由两部分构成，一部分是心，即原来的LR(1)项目，另一部分是向前搜索符号集。
10、所谓优化实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前的代码运行结果相同，但运行速度或占用的存储空间加大。常用的优化技术有删除多余运算、代码外提、强度削弱、变换循环控制条件、合并已知变量与复写传播等。
11、对一个不包含空规则的算符文法，如果文法中的任意两个终结符构成的符号对之间最多只有大于、小于和等于三种优先关系中的一种成立，则称该算符文法为算符优先文法。
12、目标程序运行时的动态数据存储区分为堆区和栈区，它用于存放可变数据以及管理过程活动的控制信息。
13、在语法分析过程中，随着分析的步步进展，根据每个规则所对应的语义
子程序或语义动作进行翻译的办法，称为语法制导翻译，它被现代很多编译程序所采用。
14、可归前缀本身就是活前缀，它是包含句柄在内的活前缀。
15、符号表用来存放语言程序中出现的有关标识符的属性信息，这些信息集中反映了标识符的语义特征属性。
二、将表达式A:=B*（C-D）/D： (共9分) 1、翻译成逆波兰式的中间代码形式。(2分) 2、翻译成四元式的中间代码形式。(4分) 3、将译成的四元式用DAG表示。(3分)
三、现有文法G[E]： (共12分)
E→E+T|E-T|T T→T*F|T/F|F F→i|(E)
4、证明：F+T*(E)是文法的一个句型。(3分) 5、构造句型F+T*(E)的语法推导树。(3分) 6、指出该句型所有短语、直接短语和句柄。(6分)
四、给定正规式R=d(a|bc)*d，要求： (12分)
1、构造对应的NFA M状态图，使得L(M)=L(R)。 (4分) 2、将所得NFA M确定化和最小化。 (8分)
五、现有文法G[S]：(共16分) S →S;D|D
D →D(T)|H H →m|(S) T →T*S|S
1、计算G[S]的FIRSTVT和LASTVT；(4分)
2、构造G[S]的算符优先关系表,并说明G[S]是否为算符优先文法；分)
(6
3、给出输入串(m*m)# 的算符优先分析过程。(4分) 4、根据分析过程总结算符优先分析方法的优缺点。(2分)
六、已知G[S]： (18分)
S→(A)|a|b A→A,S|S
1、给出(a,(b,b))的最左推导。(3分)
2、判断该文法是否为LL(1)文法。若是，直接给出它的预测分析表；若不是，先将其改写为LL(1)文法，再给出它的预测分析表；(10分)
3、给出输入串(b,b)#的分析过程，并说明该串是否为G[S]的句子。(5分)
七、对给定文法G[S’]: (共18分)
0) S’ →S 1) S →A 2）S →B 3) A →aAc 4) A →a 5) B →bBd 6) B →b
1、构造G[S’]的LR(0)项目集规范族DFA，并据此判断G[S’]是否为LR(0)文法。 (6分)
2、进一步判断G[S’]是否为SLR(1)文法，并给出对应的SLR(1)分析表。(6分) 3、给出输入串bbd#的SLR(1)分析过程。(4分)
4、判断G[S’]是否为LR(1)文法和LALR(1)文法。 (2分)
编译原理课程测试试卷评分标准
（数计学院03B卷）
第一题：判断题（15分）
1、共有15道小题，每小题1分， 15×1＝15分。
2、答案：
第二题：（9分)
1、表达式A:=B*（C-D）/D的逆波兰式表示：ABCD-*D/:= 。(2分) 2、表达式A:=B*（C-D）/D的四元式表示：(4分) （1）（-，C，D，t1） （2）（*，B，t1,t2） （3）（/，t2，D，t3） （4）（:=，t3,_,A） 3、 将译成的四元式用DAG表示:（3分）
B
C
D
第三题：（12分）
1、证明（3分）：因为存在推导序列E => E+T => T+T =>F+T =>F+T*F =>
*
F+T*(E)，即有 E
F+T*(E)成立，所以，F+T*(E)是文法的一个句型。
2、语法树（3分）
3、句型分析（6分）
句型F+T*(E)相对于E的短语有: F+T*(E), F。 句型F+T*(E)相对于T的短语有: F, T*(E)。 句型F+T*(E)相对于F的短语有: (E)。 （3分） 句型F+T*(E)相对于T→F的直接短语有: F 。
句型F+T*(E)相对于F→(E)的直接短语有: (E) 。（2分） 句型F+T*(E)的句柄为: F。 （1分） （2）短语每错两个扣1分。
第四题：（12分） 1、NFA M （4分）
2、(1)确定化（4分） 步骤如下表所示（可省）：
将集合T0至T3各用一个状态表示，确定化后所得DFA M如下：
(2)最小化 （4分） 步骤如下表所示（可省）：
最后还有4个不可再分割的子集，每个子集中只包含一个状态，即原DFA M已经是最小化DFA 。
第五题： (16分)
1、对文法进行拓广，加入规则S’→S 后得G[S’]，其非终结符的FIRSTVT、LASTVT 集计算如下：（4分）
由FIRSTVT、LASTVT 集构造≮和≯如下：
2、（1）优先关系表为：（4分）
（2）该文法是算符优先文法（2分）。
3、（1）输入串（m*m）# 的算符优先分析过程：（4分）
（2由上述分析过程可知，用算符优先分析法分析在确定句柄时只考虑终结符之间的优先关系，而与非终结符无关，这使得算符优先分析法具有效率高的优点；但是，由于去掉了单非终结符之间的归约，有可能将错误的句子识别为正确的。上例中对输入串(m*m)#能分析成功，但(m*m)#并不是文法G[S]的句子。这就是算符优先分析法的缺点。
第六题： (18分)
1、给出(a,(b,b))的最左推导：(3分)
S=>(A)=>(A,S)=>(S,S)=>(a,S)=>(a,(A))=>(a,(A,S))=>(a,(S,S))=>(a,(b,S)) =>(a,(b,b))
2、(1)判断：(3分)
计算各条规则的SELECT集及左部相同规则的SELECT集的交集如下：
（2）将G[S]改写如下：(4分)
G[S]： S→a|b|(A) A’→,SA’|ε A→SA’
（2）预测分析表：(3分)
4、
第七题： (18分)
1、（1）G[S’]的LR(0)项目集规范族DFA（4分）：
（2）检查发现I4 ={A →a., A →.aAc, A →.a }和I5 ={B →b., B →.bBd, B →.b }中存在移进—归约冲突，所以，G[S’]不是LR(0)文法。（2分）
2、（1）在I4 ={A →a., A →.aAc, A →.a }中，由于根据归约项目A →a.所得的FOLLOW(A)={c,# }中不含移进项目A →.aAc,或 A →.a中的“a”。在构造LR分析表时，遇到移进项目A →.aAc,或 A →.a时，在“a”列置移进标记S4；遇到归约项目A →a.时，只在“c”,“#”两列置归约标记r4。所以，I4中的移进—归约冲突通过引入FOLLOW集得到了解决。、
同样，在I5 ={B →b., B →.bBd, B →.b }中，由于FOLLOW(B)={d,# }中不含 “b”。在构造LR分析表时，遇到移进项目B →.bBd, B →.b时，在“b”列置移进标记S5；遇到归约项目B →b.时，只在“d”,“#”两列置归约标记r5。所以，I5中的移进—归约冲突通过引入FOLLOW集也得到了解决。
故G[S’]是 SLR（1）文法。（3分） （2）SLR(1)分析表如下：（3分）
3 > LALR(1) > SLR(1) > LR(0) 知：一个LR(0)文法肯定是SLR(1) 文法；一个SLR(1)文法肯定是LALR(1)文法；而一个LALR(1)文法肯定是LR(1)文法。既
然G[S’] 是SLR（1）文法，那么，它肯定也是LR(1)文法和LALR(1)文法。（2分）