2022年编译原理与技术模拟试题二 .pdf

模拟试题二一、填空题（ 10分）1. 1 正规式 0*(10*1)*0*所表示的语言是含有。1.2 最右推导 ( 或规范推导 ) 是与规范归约（最左归约）互逆的一个过程，规范归约每次归约的符号串称为。1.3 3 型文法是正规文法，对应的分析器是自动机； 2 型文法是，对应的分析器是自动机。1.4 文法 G产生的的全体是该文法描述的语言，记为 L(G) 。文法 G1和 G2等价当且仅当。1.5 编译器分析源程序时遇到的错误可分为两类。表达式中括号不匹配是错误， 运算对象与运算符号不匹配是错误。1.6 表达式 (a+b*c)/(a+b)-d的后缀式为。二、选择题（ 20分）2.1不属于程序语言翻译软件。A. 编译程序B. 解释程序C. 汇编程序D. 编辑程序2.2表达式中的类型检查在时进行。A. 词法分析B. 语法分析C. 语义分析D. 优化2.3 中间代码的主要形式有后缀式、和树（或图）。A. 三地址码B. 正规式C. 产生式D. 符号表2.4 数组元素的地址计算公式由不变部分和可变部分这两部分组成，。A. 可变部分在编译时确定，不变部分在运行时确定B. 不变部分在编译时确定，可变部分在运行时确定C. 不变部分和可变部分均在编译时确定D. 不变部分和可变部分均在运行时确定2.5 常用的存储分配策略有分配、栈分配和堆分配。A. 数组B. 链表C. 静态D. 动态2.6 显示表 (Display)用来记录各嵌套层次活动记录的sp，它的内容在时确定。A. 编译B. 运行C. 优化D. 代码生成2.7 过程的嵌套层次树反映了过程之间的嵌套关系；活动的活动树反映了顺序执行程序的活动的。A. 运行时间长短B. 大小C. 状态D. 调用关系2.8 编译器和解释器是两种高级语言处理程序，与编译器相比，。A. 解释器不参与运行控制，程序执行的速度慢名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - B. 解释器参与运行控制，程序执行的速度慢C. 解释器参与运行控制，程序执行的速度快D. 解释器不参与运行控制，程序执行的速度快2.9 语法分析中的预测分析法是的一种语法分析方法。A. 自左至右B. 自上而下C. 自下而上D. 自右至左2.10当程序运行陷于死循环时，说明程序中存在。A. 语法错误B. 静态的语义错误C. 词法错误D. 动态的语义错误三、简答题（ 20分）3.1 （5 分）指出 NFA与 DFA的主要区别。3.2 （5 分）举例说明下述文法G是二义的。有哪些方法可以消除文法的二义性。 G：S 0A|B1 A1A| B0 3.3 （10 分）对下述 C+ 程序， (a) 指出 p1 和 p2 分别采用什么样的参数传递方式； (b) 给出程序的执行结果。void p1(int a, int b, int c) c=c+10; b=a*b+c; void p2(int &a, int &b, int &c)c=c+10; b=a*b+c; void main() int x=80, y=20, z=0, t=0; z=x+y*90; p1(x+y,x,z); cout p1结果 = x; t=x+y; p2(t,x,z); cout p2结果 = x endl; 3.4 （5 分）简述活动记录和访问链的主要作用，以及访问链的指向。3.5 （5 分）为什么可以给变量赋值而不可以给常量赋值？四、综合题（ 40分）4.1 （10 分） 有 NFA N如右图 : (a) 求出 N的最小 DFA D；(b) 给出 N所识别语言的正规式r 。4.2 （10 分）下图所示的分析树用到了某个上下文无关文法的所有产生式。(a) （2 分）给出该文法的所有非终结符号集合N和终结符号集合T。1234aaaab名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - (b) （3 分） 给出该文法的产生式集合。(c) （3 分） 写出句型 aAaBcbdcc 的直接短语和句柄。Sa A c BA a B b S c Ac b B d c4.3 （20 分）有上下文无关无法G1 和语法制导翻译如下：(1) V id var_no:=var_no+1; (2) | id(E) arr_no:=arr_no+1; (3) E E + V exp_no:=exp_no+1; (4) | V exp_no:=exp_no+1; (a) （6 分）给出 G1的识别活前缀的DFA ；(b) （4 分） G1是 LR(0) 的吗？为什么？是SLR(1)的吗？为什么？(c) （3 分） 给出句型 id(id(id)+id)的分析树；(d) （2 分） 若语义变量var_no 、arr_no和 exp_no 的初值均为0，请给出分析句子id(id(id)+id)之后它们各自的值；(e) （5 分）说明 G1不是 LL(1) 文法的理由并将G1改写为 LL(1) 文法 G1 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - 模拟试题二参考答案一、填空题（ 10分）1. 1 正规式 0*(10*1)*0*所表示的语言是含有偶数个 1 的串 。1.2 最右推导 ( 或规范推导 ) 是与规范归约（最左归约）互逆的一个过程，规范归约每次归约的符号串称为句柄。1.3 3 型文法是正规文法，对应的分析器是有限自动机； 2 型文法是上下文无关文法，对应的分析器是下推自动机。1.4 文法 G产生的句子的全体是该文法描述的语言，记为 L(G) 。文法 G1和 G2等价当且仅当 L(G1)=L(G2) （或两者描述的语言相同）。1.5编译器分析源程序时遇到的错误可分为两类。表达式中括号不匹配是语法错误，运算对象与运算符号不匹配是语义 错误。1.6 表达式 (a+b*c)/(a+b)-d的后缀式为 abc*+ab+/d- 。二、选择题（ 20分）2.1D 不属于程序语言翻译软件。A. 编译程序B. 解释程序C. 汇编程序D. 编辑程序2.2表达式中的类型检查在C 时进行。A. 词法分析B. 语法分析C. 语义分析D. 优化2.3 中间代码的主要形式有后缀式、A 和树（或图）。A. 三地址码B. 正规式C. 产生式D. 符号表2.4 数组元素的地址计算公式由不变部分和可变部分这两部分组成，B 。A. 可变部分在编译时确定，不变部分在运行时确定B. 不变部分在编译时确定，可变部分在运行时确定C. 不变部分和可变部分均在编译时确定D. 不变部分和可变部分均在运行时确定2.5 常用的存储分配策略有C 分配、栈分配和堆分配。A. 数组B. 链表C. 静态D. 动态2.6 显示表 (Display)用来记录各嵌套层次活动记录的sp，它的内容在B 时确定。A. 编译B. 运行C. 优化D. 代码生成2.7 过程的嵌套层次树反映了过程之间的嵌套关系；活动的活动树反映了顺序执行程序的活动的D 。A. 运行时间长短B. 大小C. 状态D. 调用关系2.8 编译器和解释器是两种高级语言处理程序，与编译器相比，B 。A. 解释器不参与运行控制，程序执行的速度慢名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - B. 解释器参与运行控制，程序执行的速度慢C. 解释器参与运行控制，程序执行的速度快D. 解释器不参与运行控制，程序执行的速度快2.9 语法分析中的预测分析法是B 的一种语法分析方法。A. 自左至右B. 自上而下C. 自下而上D. 自右至左2.10当程序运行陷于死循环时，说明程序中存在D 。A. 语法错误B. 静态的语义错误C. 词法错误D. 动态的语义错误三、简答题（ 20分）3.1 （5 分）指出 NFA与 DFA的主要区别。解： 主要区别在于在当前状态下遇到下一个符号的状态转移是否确定，NFA不确定， DFA确定。3.2 （5 分）举例说明下述文法G是二义的。有哪些方法可以消除文法的二义性。 G：S 0A|B1 A1A| B0 解： G 的一个句子“ 01”可以有如下的两棵分析树：可以改写文法为非二义的，也可以规定文法符号的优先级和结合性，限制分析的每一步仅有唯一选择。3.3 （10 分） 对下述 C+ 程序， (a) 指出 p1 和 p2 分别采用什么样的参数传递方式； (b) 给出程序的执行结果。void p1(int a, int b, int c) c=c+10; b=a*b+c; void p2(int &a, int &b, int &c)c=c+10; b=a*b+c; void main() int x=80, y=20, z=0, t=0; z=x+y*90; p1(x+y,x,z); cout p1结果 = x; t=x+y; p2(t,x,z); cout p2结果 = x endl; 解： p1 采用值调用， p2 采用引用调用。程序执行结果为： p1 结果 =80 p2 结果 =9890 3.4 （5 分）简述活动记录和访问链的主要作用，以及访问链的指向。解：活动记录用于提供活动所需的环境，访问链用于访问非本地数据。访问链的指向有两种：SB10S0A1A名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - 非显示表指向直接外层的最新活动记录，显示表指向同层次新活动记录。3.5 （5 分）为什么可以给变量赋值而不可以给常量赋值？解： 因为变量有存储空间( 左值) ，常量仅是值 ( 右值 ) 。四、综合题（ 40分）4.1 （10 分） 有 NFA N如右图 : (a) 求出 N的最小 DFA D；(b) 给出 N所识别语言的正规式r。解： (a) 确定化：m(1, a)=2 1=A(初态 ) m(2, a)=3,4 m(2, b)=2 2=B, m(3 4, a)=2 3,4=C(终态 ) 即：m(A, a)=B m(B, a)=C( 终态 ) m(B, b)=B m(C, a)=B 它已经是最小DFA 。(b) r=a(b|aa)*a，它所描述的语言是由a 开始和结尾的、偶数个a 组成的 a、b 串。4.2 （10 分）下图所示的分析树用到了某个上下文无关文法的所有产生式。(a) （2 分）给出该文法的所有非终结符号集合N和终结符号集合T。(b) （3 分）给出该文法的产生式集合。(c) （3 分）写出句型 aAaBcbdcc 的直接短语和句柄。解：(a) 非终结符集合N=S, A, B 终结符集合T=a, b, c, d (b) 产生式集合： S aAcB | Bd A AaB | c B BScA | b |(c) 句型 aAaBcbdcc 的直接短语是AaB(AAaB)、(B )、c(Ac) ，其中 AaB是句柄。4.3 （20 分）有上下文无关无法G1 和语法制导翻译如下：(1) V id var_no:=var_no+1; (2) | id(E) arr_no:=arr_no+1; (3) E E + V exp_no:=exp_no+1; (4) | V exp_no:=exp_no+1; (a) （6 分）给出 G1的识别活前缀的DFA ；(b) （4 分） G1是 LR(0) 的吗？为什么？是SLR(1)的吗？为什么？1234aaaabABCaaabSa A c BA a B b S c Ac b B d c名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - (c) （3 分） 给出句型 id(id(id)+id)的分析树；(d) （2 分） 若语义变量var_no 、arr_no和 exp_no 的初值均为0，请给出分析句子id(id(id)+id)之后它们各自的值；(e) （5 分）说明 G1不是 LL(1) 文法的理由并将G1改写为 LL(1) 文法 G1 。解：(a) G1 的识别活前缀的DFA如下：(b) G1不是 LR(0) 文法，因为在 I2 中有移进 / 归约冲突。G1是 SLR(1)文法，因为 FOLLOW(V)=), +, # ，与移进项中的) 不交，即此冲突可以用SLR方法解决。(c) 句型 id(id(id)+id)的分析树如下：(d) 若 var_no 、arr_no 和 exp_no 的初值均为0，分析句子id(id(id)+id)之后， var_no=2 ，arr_no 2， exp_no=3。(e) 因为 G1中有直接左递归（EE+V）和公共左因子（Vid|id(E)） ，所以 G1不是 LL(1)文法，消除左递归和提取左因子之后，得到G1如下，它是LL(1) 文法。V id B B |(E) E V E E + V E |V .V I0V.idV.id(E)VV . I1Vid . I2Vid .(E)Vid (.E) I3E .E+VE .VV .idV .id(E)Vid (E.) I5EE .+VEV . I4EE +.V I7V.idV.id(E)Vid (E). I6EE+V. I8Vidid(idVEV)+Vid ( E )E + VV idid ( E )Vid名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -