2022年编译原理和技术期末考试复习题.docx

《2022年编译原理和技术期末考试复习题.docx》由会员分享，可在线阅读，更多相关《2022年编译原理和技术期末考试复习题.docx（24页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精品_精品资料_资料word 精心总结归纳 - - - - - - - - - - - -2.1 考虑文法 GS, 其产生式如下:SL|aLL, S|S,(1) 试指出此文法的终结符号、非终结符号.终结符号为： ,a,非终结符号为：S,L开头符号为：S(2) 给出以下各句子的分析树： a,aa,a,a a,a,a,a,a(3) 构造以下各句子的一个最左推导： a,aSLL,SS,Sa,Sa,a a,a,aSLL,SS,Sa,Sa,La,L,Sa,S,Sa,a,Sa,a,a a,a,a,a,aSLL,SS,Sa,Sa,La,L,S a,S,Sa,L,Sa,L,S,Sa,S,S,Sa,a,S,Sa

2、,a,a,Sa,a,a,L可编辑资料 - - - 欢迎下载精品_精品资料_学习资料 名师精选 - - - - - - - - - -第 1 页,共 12 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品_精品资料_资料word 精心总结归纳 - - - - - - - - - - - -a,a,a,L,Sa,a,a,S,Sa,a,a,a,S a,a,a,a,a(4) 构造以下各句子的一个最右推导： a,aSLL,SL,aS,aa,aa,a , aSLL,SL,LL,L,SL,L,aL,S,aL,a,aS,a,aa,a,aa , a , a , a , aSLL,S

3、L,LL,L,SL,L,LL,L,L,SL,L,L,aL,L,S,aL,L,a,aL,S,a,aL,L,a,aL,L,S,a,aL,L,a,a,aL,S,a,a,aL,a,a,a,aS,a,a,a,aa,a,a,a,a(5) 这个文法生成的语言是什么？.LGS = 1, 2, n 或 a其中 i 1 i n ,即LGS是一个以a 为原子的纯表,但不包括空表.2.2 考虑文法 GSSaSbS|bSaS| (1) 试说明此文法是二义性的.可以从对于句子abab 有两个不同的最左推导来说明.SaSbSabSabaSbSababSababSaSbSabSaSbSabaSbSababSabab所以此文法

4、是二义性的.(2) 对于句子abab 构造两个不同的最右推导.SaSbSaSbaSbSaSbaSbaSbababab SaSbSaSbabSaSbabSababab(3) 对于句子abab 构造两棵不同的分析树. 一 二(4) 此文法所产生的语言是什么？此文法产生的语言是：全部a 的个数与b 的个数相等的由a 和 b 组成的字符串.2.4已知文法 GS 的产生式如下：S L|aL L,S|S属于 LGS的句子是 A,a,a是 LGS的句子, 这个句子的最左推导是B,最右推导是 C,分析树是D ,句柄是 E.A： a a,a L L,aB,C： SLL,SL,aS,aa,a SLL,SS,SS,

5、aa,a可编辑资料 - - - 欢迎下载精品_精品资料_学习资料 名师精选 - - - - - - - - - -第 2 页,共 12 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品_精品资料_资料word 精心总结归纳 - - - - - - - - - - - - SLL,SS,Sa,Sa,aD：E： a,a a,a a a解答： A ：B：C：D：E：3.1 有限状态自动机可用五元组（VT,Q, , q0,Qf ）来描述 , 设有一有限状态自动机M的定义如下：VT=0,1, Q=q0,q 1,q 2 , Qf =q 2 , 的定义为： （ q0, 0） =

6、q1 （ q1, 0） =q2（ q2, 1） =q2 （ q2, 0） =q2M是一个 A有限状态自动机, 它所对应的状态转换图为B , 它所能接受的语言可以用正就表达式表示为 C .其含义为D .A:歧义的非歧义的确定的非确定的B:*C： 0|1000|10|10000|10D：由 0 和 1 所组成的符号串的集合.以 0 为头符号和尾符号、由0 和 1 所组成的符号串的集合.以两个0 终止的,由0 和 1 所组成的符号串的集合.可编辑资料 - - - 欢迎下载精品_精品资料_学习资料 名师精选 - - - - - - - - - -第 3 页,共 12 页 - - - - - - - -

7、 - -可编辑资料 - - - 欢迎下载精品_精品资料_资料word 精心总结归纳 - - - - - - - - - - - -以两个0 开头的,由0 和 1 所组成的符号串的集合.答案A:B:C:D:3.2 1有穷自动机接受的语言是正就语言.（）(2) 如 r 1 和 r 2 是 上的正规式,就r 1|r 2 也是.（）(3) 设 M是一个 NFA,并且 LM x,y,z,就 M的状态数至少为4 个.*(4) 令 a,b,就 上全部以b 为首的字构成的正规集的正规式为b a|b.(5) 对任何一个NFA M,都存在一个DFA M ,使得 LM=LM.（）(6) 对一个右线性文法G,必存在一

8、个左线性文法G ,使得 LG=LG,反之亦然.（）答案1T2T3F4F5T3.3 描述以下各正规表达式所表示的语言.100|1* 0* *2 |0130|100|10|1*40 10 10 10500|11* 01|1000|11* 01|1000|11* *答案1以 0 开头并且以0 结尾的,由0 和 1 组成的全部符号串2 | 0,1即由 0 和 1 组成的全部符号串.(3) 由 0 和 1 组成的符号串,且从右边开头数第3 位为 0.(4) 含 3 个 1 的由 0 和 1 组成的全部符号串. | 0,1+,且 中含有 3个 1 *(5) | 0,1, 中含 0 和 1 的数目为偶数.4

9、.10已知文法GS ,其产生式如下： SL|aLL,S|S文法 GS 的算符优先关系由下表给出.建立与下表相应的算符优先函数并用算符优先分析法分析句子 a,a,a.文法 GS 的算符优先关系表：解：对每个终结符或建立符号f 与 g,把 f 和 g 分成一组.依据 GS 的算符优先关系表,画出如下的有向图:可编辑资料 - - - 欢迎下载精品_精品资料_学习资料 名师精选 - - - - - - - - - -第 4 页,共 12 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品_精品资料_资料word 精心总结归纳 - - - - - - - - - - - -优

10、先函数如下：用算符优先分析法分析句子a,a,a4.19 1存在有左递归规章的文法是LL1 的.(2) 任何算符优先文法的句型中不会有两个相邻的非终结符号.(3) 算符优先文法中任何两个相邻的终结符号之间至少满意三种关系 , 之一.可编辑资料 - - - 欢迎下载精品_精品资料_学习资料 名师精选 - - - - - - - - - -第 5 页,共 12 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品_精品资料_资料word 精心总结归纳 - - - - - - - - - - - -(4) 任何 LL1 文法都是无二义性的.(5) 每一个 SLR1 文法也都是

11、LR1 文法.(6) 存在一种算法,能判定任何上下文无关文法是否是LL1 的.(7) 任何一个LL1 文法都是一个LR1 文法,反之亦然.8 LR1括号中的1 是指,在选用产生式A 进行分析,看当前读入符号是否在FIRST 中.答案： 1 2 3 4 5 6 7 84.20 在编译程序中,语法分析分为自顶向下分析和自底向上分析两类. A 和 LL1 分 析法属于自顶向下分析.B 和 LR分析法属于自底向上分析.自顶向下分析试图为输入符号可编辑资料 - - - 欢迎下载精品_精品资料_串构造一个 C .自底向上分析试图为输入符号串构造一个时,要求文法中不含有E . D .采纳自顶向下分析方法可编

12、辑资料 - - - 欢迎下载精品_精品资料_A、B：深度分析法宽度优先分析法算符优先分析法猜测递归分析法C、D：语法树最左推导有向无环图最右推导E：右递归左递归直接右递归直接左递归A：B：C：D：E：4.21 自底向上语法分析采纳A 分析法,常用的是自底向上语法分析有算符优先分析法和可编辑资料 - - - 欢迎下载精品_精品资料_LR 分析法. LR 分析是查找右句型的 B .而算符优先分析是查找右句型的 C .LR 分可编辑资料 - - - 欢迎下载精品_精品资料_析法中分析才能最强的是 D .分析才能最弱的是E .可编辑资料 - - - 欢迎下载精品_精品资料_A：B、C：递归短语回溯素短

13、语枚举最左素短语移进规约句柄D、E： SLR1LR0 LR1 LALR1A：B：C：D：E：5.5用 S 的综合属性val给出在下面的文法中的S 产生的二进制数的值（例如,对于输入101.101 , S.val=5.625）：SL.L|LLLB|BB0|1（ 1）试用各有关综合属性打算S.val .（ 2）试用一个语法制导定义来打算S.val,在这个定义中仅有B 的综合属性,设为c,它给出由 B 生成的位对于最终的数值的奉献.例如,在101.101 中的第一位和最终一位对于值 5.625 的奉献分别为4 和 0.125 .解答： 1 用综合属性打算s.val的语法制导定义：产生式语义规章S -

14、 LS.val:=L.val;S - L1.L 2S.val:=L1 .val+L 2.val*L2.p;-1L - BL.val:=B.val;L.p:=2;-1L - L1BL.val:=L1 .val*2+B.val;L.p:=L.p*2;可编辑资料 - - - 欢迎下载精品_精品资料_学习资料 名师精选 - - - - - - - - - -第 6 页,共 12 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品_精品资料_资料word 精心总结归纳 - - - - - - - - - - - -B - 0B.val:=0;B - 1B.val:=1;注：

15、L.p 表示复原L.val的因子.2 分析：设 B.c 是 B 的综合属性,是B 产生的位对最终值的奉献.要求出B.c ,必需求出B产生位的权,设B.i .B.i的求法请参看下面的图示：另外,设L.fi为继承因子, L.fs为综合因子,语法制导定义如下：产生式语义规章S - LL.i:=1; L.fi:=2; L.fs:=1; S.val:=L.val;可编辑资料 - - - 欢迎下载精品_精品资料_S - L 1.L 2L1.i=1; L1.fi=2; L1.fs:=1;-1-1L2.i=2; L 2.fi=1; L2.fs:=2;S.val:=L1.val+L2.val;可编辑资料 - -

16、 - 欢迎下载精品_精品资料_L - BL.s:=L.i; B.i:=L.s; L.val:=B.c;可编辑资料 - - - 欢迎下载精品_精品资料_学习资料 名师精选 - - - - - - - - - -第 7 页,共 12 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品_精品资料_资料word 精心总结归纳 - - - - - - - - - - - -可编辑资料 - - - 欢迎下载精品_精品资料_L - L1BL1.i:=L.i*L1.fi; L.s:=L1.s*L 1.fs;B.i:=L.s;L.val:=L1.val+B.c;可编辑资料 - - -

17、 欢迎下载精品_精品资料_B - 0B.c:=0;B - 1B.c:=B.i;5.15 描述文法符号语义的属性有两种,一种称为 A ,另一种称为 B . A 值的运算依靠于分析树中它的 C 的属性值. B 的值的运算依靠于分析树中它的 D 的属性值.A,B:C,D:L- 属性父结点R-属性子结点综合属性兄弟结点继承属性父结点与子结点父结点与兄弟结点解答 :A BCD 5.161语法制导定义中某文法符号的一个属性,既可以是综合属性,又可以是继承属性.(2) 只使用综合属性的语法制导定义称为S- 属性定义.(3) 把 L- 属性定义变换成翻译模式,在构造翻译程序的过程中前进了一大步.(4) 一个特

18、定的翻译模式既适于自顶向下分析,又适于自底向上分析.(5) 用于自顶向下分析的翻译模式,其基础文法中不能含有左递归.(6) 在基础文法中增加标记非终结符不会导致新的语法分析冲突.解答 :1 FALSE2 TRUE3 TRUE4 FALSE5 TRUE6 FALSE6.7 1对于答应递归调用的程序语言,程序运行时的储备安排策略不能采纳静态的储备安排策略.（ ）(2) 如一个程序语言的任何变量的储备空间大小和相互位置都能在编译时确定,就可采纳静态安排策略. （ ）(3) 在不含嵌套过程的词法作用域中,如一个过程中有对名字a 的非局部引用, 就 a 必需在任何过程（或函数）外被说明.（ ）(4) 在

19、答应嵌套的词法作用域的语言中,过程不能作为参数,缘由时不能建立其运行环境的存取链.（ ）(5) 在堆式储备安排中,一个堆中存活的活动记录不肯定是邻接的.（ ）(6) 假如源程序正文中过程p 直接嵌入在过程q 中,那么, p 的一个活动记录中的存取链接指向 q 的最近的活动记录. （ ）解答： 1TRUE 2FALSE 3TRUE 4FALSE 5TRUE 6TRUE6.8 运行时的储备安排策略分A 和 B 两类. B 又分 C 和D .一个语言中不同种类的变量依据定义域和生存期的不同往往采纳不同的储备分配策略, C 语言中的静态变量往往采纳A ,而自动 out类变量往往采纳C .使用 mall

20、ac中申请的内存单元采纳D .可编辑资料 - - - 欢迎下载精品_精品资料_学习资料 名师精选 - - - - - - - - - -第 8 页,共 12 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品_精品资料_资料word 精心总结归纳 - - - - - - - - - - - -A,B,C,D:栈式安排正确安排堆式安排静态安排随机安排动态安排解答：A:B: C: D: 7.2 翻译算术表达式一（a b） * （ c d）（ a b c ）为oparg1arg2result1+abt12+cdt23*t1t2t34uminust3t45+abt56+t5

21、ct67+t4t6t72三元式序列为：oparg1arg21+ab2+cd3*124uminus35+ab6+5c7+46(1) 四元式,2 三元式3间接三元式解答： 1 四元式序列为：3 间接三元式表示：可编辑资料 - - - 欢迎下载精品_精品资料_学习资料 名师精选 - - - - - - - - - -第 9 页,共 12 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品_精品资料_资料word 精心总结归纳 - - - - - - - - - - - -statementoparg1arg211111+ab21212+cd31313*111241414u

22、minus1351115+11c61516+14157169.1 试构造下面的程序的流图,并找出其中全部回边及循环.read P x := 1c := P * Pif c 100 goto L1 B := P * Px := x + 1 B := B + xwrite xhalt L1: B:= 10x := x + 2 B := B + xwrite Bif B n2,所以 n 5 - n2 为一条回边.依据它求出的循环 L 1 = n2, n 5, n 3, n 4 .由于 Dn6 = n0, n 1, n 2, n 5, n 6,且 n 6 - n1,所以 n6 - n1 为一条回边.依据这条回边,求出的循环L 2 = n6, n 1, n 5, n 3, n 4, n 2 .9.8在对编译程序产生的中间代码进行优化时,就实施优化的范畴来说,分A优化和B优化.循环优化属于B优化,它对于提高目标代码的运行速度是特别有效的.循环优化主要采纳的三项优化措施是C、D、E.答案： A：局部B ：全局C ：代码外提D ：削减运算强度E：删除归纳变量可编辑资料 - - - 欢迎下载精品_精品资料_学习资料 名师精选 - - - - - - - - - -第 12 页,共 12 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载