《编译原理》模拟试题四.doc

《编译原理》模拟试题四一、是非题（请在括号内，正确的划√，错误的划×）（每个 2 分，共 20 分）1．一个 LL(l)文法一定是无二义的 (× )2．正规文法产生的语言都可以用上下文无关文法来描述 (× )3．一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态 (√)4．目标代码生成时，应考虑如何充分利用计算机的寄存器的问题 (× )5．逆波兰法表示的表达式亦称前缀式 (√ )6．如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的 (√ )7．LR 法是自顶向下语法分析方法 (× )8．数组元素的地址计算与数组的存储方式有关× )9．算符优先关系表不一定存在对应的优先函数 (×)10．对于数据空间的存贮分配， FORTRAN 采用动态贮存分配策略 (×)二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个 4 分，共 40 分)1．词法分析器用于识别_____ A．( ) 字符串 B．( )语句C．( )单词 D．( )标识符2．文法分为四种类型，即 0 型、1 型、2 型、3 型其中 0 型文法是_____。

A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法3．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _____ A．( ) 句子 B．( ) 句型 C．( ) 单词 D．( ) 产生式4．_____是一种典型的解释型语言 A．( ) BASIC B．( ) C C．( ) FORTRAN D．( ) PASCAL5．与编译系统相比，解释系统_____A．( ) 比较简单 , 可移植性好 , 执行速度快 B．( ) 比较复杂 , 可移植性好 , 执行速度快 C．( ) 比较简单 , 可移植性差 , 执行速度慢 D．( ) 比较简单 , 可移植性好 , 执行速度慢 6．用高级语言编写的程序经编译后产生的程序叫_____ A．( ) 源程序 B．( ) 目标程序 C．( ) 连接程序 D．( ) 解释程序7．词法分析器用于识别_____ A. ( ) 字符串 B．( ) 语句 C．( ) 单词 D．( ) 标识符 8．编写一个计算机高级语言的源程序后 , 到正式上机运行之前，一般要经过_____这几步:(1) 编辑 (2) 编译 (3) 连接 (4) 运行 A. ( ) (1)(2)(3)(4) B．( ) (1)(2)(3) C．( ) (1)(3) D．( ) (1)(4)9．把汇编语言程序翻译成机器可执行的目标程序的工作是由_____完成的。

A．( ) 编译器 B．( ) 汇编器 C．( ) 解释器 D．( ) 预处理器10．文法 G 所描述的语言是_____的集合 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串C．( ) 由文法的开始符号推出的所有终极符串D. ( ) 由文法的开始符号推出的所有符号串三、填空题(每空 1 分，共 10 分)1．语法分析是依据语言的__语法___规则进行的，中间代码产生是依据语言的__语义___规进行的2．语法分析器的输入是__单词符号串___，其输出是__语法单位___3．一个名字的属性包括__类型___和__作用域___4．产生式是用于定义___语法成分__的一种书写规则5．逆波兰式 ab+c+ d*e- 所表达的表达式为__(a+b+c)*d-e___ 6．语法分析最常用的两类方法是__自上而下___和__自下而上___分析法 四、简答题（20 分）1. 写出下列表达式的三地址形式的中间表示1) 5+6 *(a + b); (2)for j:=1 to 10 do a[j + j]:=0。

答： (1)100: t1:=a+b 101: t2:=6*t1 102: t3:=5+t2 (2)100: j:=1 101: if j>10 goto NEXT 102: i:=j+j 103: a[i]:=02. 设基本块 p 由如下语句构成： T 0 : =3.14; T 1 :=2*T 0 ; T 2 :=R+r; A:=T l *T 2 ； B:=A; T 3 :=2*T 0 ; T 4 :=R+r; T 5 :=T 3 *T 4 ; T 6 :=R-r ； B:=T 5 *T 6 ；试给出基本块 p 的 DAG 解：基本块 p 的 DAG 图:3. 写出表达式(a+b)/(a-b-(a+b*c)的三元序列及四元序列解：（1）三元式： ①（＋，a，b） ②（－，a，b） ③（/，①，②） ④（*，b，c） ⑤（＋，a，④） ⑥（－，③，⑤） （2）四元式： ①（＋，a，b，T1） ②（－，a，b，T2） ③（/，T1，T2，T3） ④（*，b，c，T4） ⑤（＋，a，T4，T5） ⑥（－，T3，T5，T6）4. 写一个文法使其语言为偶数集，且每个偶数不以 0 开头。

解：文法 G（S）： S→AB|B|A0 A→AD|C B→2|4|6|8 C→1|3|5|7|9|B D→0|C5. 设文法 G （ S ）： S→S ＋ aF|aF| ＋ aF F→*aF|*a （1）消除左递归和回溯；（2）构造相应的 FIRST 和 Follow 集合1） S->aFS'|＋aFS' S'->＋aFS'|ε F->*aF' F'->F|ε （2） FIRST（S）＝｛a，+｝ FOLLOW（S）＝｛＃｝ FIRST（S'）＝｛+，ε ｝ FOLLOW（S'）＝｛＃｝ FIRST（F）＝｛*｝ FOLLoW（F）＝（+，＃｝ FIRST（F'）＝｛*，ε｝ FOLLOW（+，＃｝五.计算题（10 分）已知文法为： S->a|^|(T) T->T,S|S 构造它的 LR(0)分析表 解：加入非终结符 S'，方法的增广文法为： S'->S S->a S->^ S->(T) T->T,S T->S 下面构造它的 LR(0)项目集规范族为： 从上表可看出,不存在移进-归约冲突以及归约归约冲突，该文法是 LR(0)文法。

从而有下面的 LR(0)分析表： 。