编译原测验题(共8页)

1、第1-2章测试题一、选择题1 文法 G 产生(chnshng)的_的全体是该文法描述的语言。dA句型(j xn) B 终结符集 C非终结符集 D 句子(j zi)2 若文法 G 定义的语言是无限集，则文法必然是 _。 aA递归的 B前后文无关的 C二义性的 D 无二义性的3 一个文法所描述的语言是_。aA 唯一的 B 不唯一的 C可能唯一，好可能不唯一 D都不对4_是两类程序语言处理程序。 bA 高级语言程序和低级语言程序 B 解释程序和编译程序 C 编译程序和操作系统 D 系统程序和应用程序 5. 一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，

2、以及一组 _。 dA句子 B句型C 单词 D 产生式二、解答题1何谓编译程序？2.一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？三、推导题1.已知文法G(E) ET|ET TF|T *F F(E)|i 和句型(T +F)*i+T (1)画出句型的语法树； (2)给出句型的全部短语、简单短语和句柄。2.设有文法G：S SS | S*S | i |（S）（1）对于输入串i+i*i给出一个最左推导；（2）该文法是否是二义性文法？请证明你的结论。第3章测试题一、选择题1词法(cf)分析器用于识别_。CA 字符串 B语句(yj) C 单词(dnc)D标识符2词法分析器的输出结果是_。CA

3、单词的种别编码 B单词在符号表中的位置 C单词的种别编码和自身值 D 单词自身值3词法分析所用的文法为_。DA0型文法B1型文法 C2型文 D3型文法二、解答题1构造正规式 1(0|1)*101 相应的DFA。1构造正规式 1(0|1)*101 相应的DFA。解：先构造NFA： 确定化： 重新命名，令AB为B、AC为C、ABY为D得： 所以，可得DFA为： 2已知 NFA=（ x,y,z,0,1,M,x,z ），其中：M(x,0)=z,M(y,0)=x,y,M(z,0)=x,z,M(x,1)=x, M(y,1)= ,M(z,1)=y, 构造相应的DFA并最小化。NFA图: 下表由子集法将NFA

4、转换为DFA： 下面将该DFA最小化： (1) 首先将它的状态集分成两个子集：P1=A,D,E,P2=B,C,F (2) 区分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等价。由于F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而D，E不等价（见下步），从而B与C，F可以区分。有P21=C,F,P22=B。 (3) 区分P1:由于A，E输入0到终态，而D输入0不到终态，所以D与A，E可以区分，有P11=A,E,P12=D。 (4) 由于F(A,0)=B,F(E,0)=F,而B，F不等价，所以A，E可以区分。 (5) 综上所述，

5、DFA可以区分为P=A，B，D，E，C，F。所以最小化的DFA如下： 第4章测试题一、选择题1在语法分析处理(chl)中， FIRST 集合、 FOLLOW 集合、 SELECT 集合均是_。BA.非终结符集 B终结符集 C字母表 D.状态(zhungti)集 2 在自顶向下的语法分析方法(fngf)中，分析的关键是_。DA.寻找句柄 B.寻找句型 C. 消除递归 D.选择候选式 3.语法分析器用于识别_。BA字符串 B语句 C单词D标识符4语法分析所用的文法为_。CA0型文法B1型文法 C2型文 D3型文法5在规范归约中，用_来刻画可归约串。BA直接短语 B句柄 C最左素短语 D素短语 二、

6、解答题1设文法G(S)： S(L) | a S | a LL，S | S (1) 消除左递归和回溯； (2) 计算每个非终结符的first、follow和select集，判断是否为LL（1） 文法。解：(1) S(L)|aS SS| LSL LSL| (2) FIRST)S)(，aFOLLOW(S)#，) FIRST(S)，a, FOLLOW(S)#，) FIRST(L)(，aFOLLOW(L) ) FIRST(L)，FOLLOW(L )FIRST)S)(，aFOLLOW(S)#，) FIRST(S)，a, FOLLOW(S)#，) FIRST(L)(，aFOLLOW(L) ) FIRST(L

7、)，FOLLOW(L )SELECT （S(L)）=( SELECT （SaS ）=a SELECT （SS）=(，a SELECT （S）=#，) SELECT (LSL)= (，a SELECT (L)= )因为(yn wi)SELECT （S(L)）=( 和SELECT （SaS ）=a的交集(jioj)为空集；SELECT （SS）=(，a 和SELECT （S）=#，) 的交集(jioj)为空集；SELECT (LSL)= (，a SELECT (L)= ) 的交集为空集。因此是LL（1）文法。自底向上语法分析测验题一、填空题（每空2分，共20分）1语法分析最常用的两类方法是_ _

8、和_ _ 分析法。自顶向下、自底向上2语法分析器的输入是_ _其输出是_ _。单词、语法单位3.一个LR分析器包括三部分：一个总控程序、 和 。分析表、分析栈4.简单优先分析归约和LR分析法归约的是 ，算符优先分析法归约的是 。 句柄、最左素短语5.LR分析表包括action表和 表，一般会把两张表合并成一张表。ACTION表包含的动作有移进、 接受和报错四种。goto表、归约二、计算题（每题40分，共80分）1.构造算符文法GH：HH;M|M Md|aHb的算符优先关系。由Md和Ma得：FIRSTVT(M)=d,a； 由H-H;得：FIRSTVT(H)=； 由HM得：FIRSTVT(M) c

9、FIRSTVT(H)，即FIRSTVT(H)=;,d,a 由Md和Mb得：LASTVT(M)=d,b； 由H-，；m得：LASTVT(H)=； 由HM得：LASTVT（M）cLASTVT(H），即LASTVT(H)=;,d,b 对文法开始符H,有#H#存在，即有=，#,也即；，#d. #, b#。 对形如Pab，或PaQb，有a=b，由Ma|b得：a=b； 对形如PaR，而bFIRSTVT(R)，有ab。 由H；M得：；FIRSTVT(M)，即：d，：a 由MaH得：aFIRSTVT(H)，即：a；，a;，即：；，d；，b； 由MHb得：LASTVT(H)b，即：；b，db，bb；2已知文法为

10、： S-a|(T) T-T,S|S 构造它的 LR(0)分析表。 （LR（1）分析法自己从书上找例题复习）解：加入非终结符S，方法的增广文法为： S-S S-a S- S-(T) T-T,S T-S 下面构造(guzo)它的LR(0)项目集规范族为： 从上表(shn bio)可看出,不存在移进-归约冲突以及归约归约冲突，该文法是LR(0)文法。 从而有下面的LR(0)分析表： 第7-10章测试题班级(bnj) 学号 姓名(xngmng) 成绩(chngj) 一、填空题1.常用的参数传递方式有 ， 和 。传地址，传值和传名2.局部优化是 在范围内进行的一种优化。基本块3一个名字的属性包括 和_

11、_。类型、作用域二、选择题1程序所需的数据空间在程序运行前就可确定，称为_管理技术。CA.动态存储 B.栈式存储 C.静态存储 D.堆式存储2编译程序绝大多数时间花在_上。DA.出错处理 B.词法分析 C.目标代码生成 D.管理表格3. 优化可生成 的目标代码。DA 运行时间较短 B 占用存储空间较小C 运行时间短但占用内存空间大 D运行时间短且占用存储空间小4下列 优化方法不是针对循环优化进行的。CA.强度削弱 B删除归纳变量 C删除多余运算 D 代码外提二、语法制导翻译1 Whilea0 b0do Begin x：x1； if a0 then a：a1 End； 翻译成四元(s yun)式序列。 (1) (j，a，0，5) (2) (j，3) (3) (j，b，0，5) (4) (j，12) (5) (，1，T1) (6) (：，T1，) (7) (j，a，0，9) (8) (j，1)