文档介绍：课程测试试题(B卷)
一、判断(15分)
1、编译阶段按前后端组合,可分为编译前端和编译后端,其中与目标机有关的阶段一般属于前端,而与源语言相关的阶段一般属于后端。
2、一个句型的最左直接短语称为最左素短语。
3、已存在这样一种算法,它能在有限步内证明任意给定的一个文法是否为二义性的。
4、一个NFA一定是DFA,反之,不成立。
5、逆波兰式又称为四元式,它是一种普遍使用的中间代码形式,它的四个组成部分是算符、两个运算对象和结果。
6、正规文法一定是上下文无关文法。
7、语法制导翻译是指根据文法中的每个规则所对应的语义子程序或语法规则所描述的语义动作进行翻译的办法。
8、对任意给定的一个正规式R,都可以将它转换为与之功能等价的正规文法,或与之功能等价的有穷自动机。
9、不同语义的标识符属性不尽相同,但符号名、符号类型、符号的存储类别、符号的作用域及可视性等属性是各种标识符都需要的通用属性。
10、形如α→β或α::=β的(α,β)有序对称为所规则或产生式或生成式,其中α是
字母表V的正闭包元素,而β是字母表V的闭包元素。
11、由优先关系矩阵构造出的优先函数具有唯一性。
12、算符优先分析方法和LR分析方法都是自下而上的分析方法,它们的分析过程实际上就是规范归约过程。
13、LR(0)项目集规范族中的项目由两部分构成,一部分是心,即原来的LR(1)项目,另一部分是向前搜索符号集。
14、对一个不包含空规则的文法,如果文法中的任意两个终结符构成的符号对之间最多只有大于、小于和等于三种优先关系中的一种成立,则称该文法为算符文法。
15、数据空间的使用和管理方法分为三种,即:静态存储分配、动态存储分配、静态与动态相结合的存储分配。
二、简述代码优化的概念和常用的几种优化技术。(5分)
三、现有文法G[E]: (共12分)
E→EE+
E→EE*
E→F
F→i
证明ii*i+是文法的一个句子。(3分)
构造句型ii*i+的语法推导树。(3分)
指出该句型所有短语、直接短语和句柄。(6分)
四、将正规式R=bb(a|bb)a*b转换为相应的NFA M状态图,使得L(M)=L(R),并将所得NFA M确定化和最小化。(12分)
五、已知G[S]: (18分)
S→b|+|(T)
T→T,S|S
给出(+,(b,+))的最左推导。(2分)
证明G[S]不是LL(1)文法。(3分)
将G[S]改写为LL(1)文法,再给出它的预测分析表;(8分)
4、给出输入串(b,+)#的分析过程。(5分)
六、现有文法G[E']:(共18分)
E'→#E#
E→E+T|T
T→T*F|F
F→P^F|P
P→(E)|i
1、计算G[E']的FIRSTVT和LASTVT;(6分)
2、构造G[E']的算符优先关系矩阵,并说明G[E']是否为算符优先文法。(7分)
3、给出输入串i+i# 的算符优先分析过程。(5分)
七、对任意给定的一个上下文无关文法G[S]: (共20分)
如何判断G[S]是否为LR(0)文法。(4分)
如何判断G[S]是否为SLR(1)文法。(4分)
如何判断G[S]是否为LR(1)文法。(4分)
如何判断G[S]是否为LALR(1)文法。(4分)
5、说明