《各章练习题发送版.docx》由会员分享，可在线阅读，更多相关《各章练习题发送版.docx（18页珍藏版）》请在三一文库上搜索。
1、第三章复习重点：1.文法与语言的对应关系语言 L(G)=L(G)文法G文法Gbn | n0 _n _BbB | bBBb | bb | n 划PbPPPbabn | n0SDB Da BbB | bSaB BBb | bbna | n 刃TPD Da PfbP |TPa PPb(ab)n | n0UEU | E EabUUab | abambn|m0,n0VAB AaA | a BbB | bVaV BbBaB bambn|m 范n0WAB AaA | & BbB | bWaW | B BbB | banbn n0XaXbab(akcd)nbn| k,n0XDXH | DH DAcd AaA
2、|a Hba2n+1bn| n=0YaaYb |aYKYH | a Kaa Hb思路要点：注意结构拆分技巧：如何将表示语言的通用字符串形式作适当的切割?例：语言：L1 = axb2xcy | x, y = 0,给出此语言的文法,并证实此语言是上下文无关语言.提示：该题实际上要求为相应语言设计上下文无关文法.一个文法设计好后,严格来说应当证实此文法是否对应于该语言.解：GS: S - ABA 一 | aAbbB 一 | cB推导过程：S AB +axAb2xB/* 使用 A 一 aAbb x 次*/axb2xB/* 使用 A 一一次*/axb2xcxB/* 使用 B 一 cB x 次*/axb2
3、xcx/* 使用 B 一 一次 */举一反三：语言L2 = axb2ycy | x, y = 0,给出此语言的文法,并证实此语言是上下文无关语言o解：GS: S - ABA 一 | aAB 一 | bBcc练习：14:写出以下语言对应的文法1. ).anbnambm|n,m 02. 1n0m0m0n|n,m03. 1n0m0m0n|n 0,m04. anbmck|n,m,k 0G1: SAAG2: S ABAaAb| AaAb| B- aBb| G: S1S0SAA 0A1A G: S 1S0|AS 1S0|0A1A 0A1|01A 0A1| 例：给出语言akbmcn|k,m,n /的正规文法
4、(3型).解：G: AraA|aBB-bB|bCCfC|c假设不要求正规文法,那么按例中上面分解的方法2.给出文法,证实文法符号串是否为文法的句型,假设是句型,找出这个句型的所有短语、 直接短语、句柄.1 .令文法G E为：Z-bMbM - a|(LL-Ma) 符号用b(Ma)b是否为该文法的一个句型,并证实.假设此符号用是句型,指出这个句型的所有短语、直接短语、句柄.1) (5 分)证实：S= bMb=b(Lb=b(Ma)b所以,符号用b(Ma)b是该文法的一个句型.(2) (5 分)短语：Ma), (Ma), b(Ma)b直接短语：Ma)句柄：Ma)练习：P-(T) | i(10 分)文法
5、 GT: T-T*F | F ; F-FT P | P ;(1)用最右推导法证实B : T*PT (T*F)是GT的一个句型；(2)画出B的语法树；(3)写出B的全部短语、直接短语和句柄.(1) T=T*F=T*F T P=T*F T (T)= T*F T (T*F)=T*P T (T*F)证毕.如图TFTP / /IXP ( T )第3题语法树(3)短语：T*Pf(T*F) ; PT (T*F) ; (T*F) ; T*F ; P直接短语：T*F ; P句柄： P3.证实一个文法是二义性文法.证实下述文法 G S是二义的.(5分)S-iSeS|iS|i解：可见,句型iises有两种不同的语法
6、树,所以GS是二义的.练习：证实下述文法 G:S aSbS|aS|d是二义性文法.解：一个文法,如果存在某个句子有不只一棵语法分析树与之对应,那么称这个 文法是二义性文法.句子aadbd有两棵语法树.如以下图:由此可知,S aSbS|aS|d定义的文法是二义性文法.第四章：重点：1. NFA DFA确实定化及DFA的最小化.2.试写出描述语言L的正规式,构造能识别该语言 L等价的NFA,再确定化 将以下图所示的NFA确定化,再最小化.2021年出过Q用子集法确定化如下表编RIIaIbAAX,1,2,4)B1,2,3,4C1,2,4,YBB(1,2,3,4)B 1,2,3,4C1,2,4,YCC
7、1,2,4,YB 1,2,3,4C1,2,4,Y由于对于非终态的状态 A和B来说,它们输入a、b的下一个状态都是一样的,故状态 A和B可以合并,将合并后的状态重命名为A,而终态那么重命名为 B,那么合并后的状态转换矩阵由此可以得到最小化的为:SabAABBABDFA,如以下图所示:练习1：给出接受字母表 =a, b,语言为以b开头,以aa结尾的字符串集合的正规表达式,并构造与之等价状态的DFA.2021年出过答：依题意,以b开头,以aa结尾的字符串集合的正规表达式可写为：ba|b*aa画NFA,如以下图所示a0 b用子集法确定化如下表 IIa IbXA-1B1 B1,2C1B1,2C112,Y
8、D1B1,2,YD1,2,YD.1Bb10分将以下图的NFA确定化为DFA.2021年重修卷A出过答：用子集法确定化如下表用子集法对所给图确实定化IIaIb状态X,1,21,2.1,2,3X1,2.1,2.1,2,311,2,31,2,Y1,2,321,2,Y1,2.1,2,33确定化后如以下图第五章重点：1.LL(1)的判别要点：(1)计算FirstFollowSelect集,然后判断是否是 LL(1)文法.(2)如果是LL(1)文法,那么构造预测分析表.(消除左递归和左公共因子也要,这点上课我没提到,我将会补充的！ )例：(10分)已给文法 GS:S f PSS aPS| fS |P 一
9、qPP 一 bP |(1)该文法是否是 LL (1)文法,并说明理由.(2)给出该文法的预测分析表.答：(10分)(1) Select (S 一 PS) =first(P)=qSelect(S FPS尸aSelect(S -fS)=fSelect(S 一 )=follow(S 尸follow(S)=#Select(Pf qP)=qSelect(P 一 bP)=bSelect ( P 一)=follow(P )=follow(P)=first(S )- follow(S)=a,f #=a,f,#Select(S FPS) Select(S -fS)Select(S 一 )=Select(P f
10、bP) Select ( Pf)=所以文法是LL (1)文法. (7分)(2)预测分析表：(3分)abfq#SPSS,aPSfS,PqPP,bP(15分)写出以下文法中各候选式的FIRST集和各非终结符的FOLLOW集,构造该文法的LL( 1)分析表,并说明它是否为LL (1)文法.(2021年重修卷A出过)S 一 aA|BAA一 cB|B 一 bB|各候选式的FIRST集(4分)FIRST (aA) =a FIRST (BA) = b , c, FIRST (cB) =cFIRST ( ) = FIRST (bB) = b FIRST ( ) = 各非终Z符的FOLLOW集(4分)FOLLO
11、W(S)= # FOLLOW(A)= # FOLLOW(B)= c , #LL (1)分析表(5分)abcS 一 aAS 一 BAB 一 bB说明它是否为LL (1)文法(2分)S 一 BA S 一 BAAf cBA 一B 一B 一判断1分,理由1分由于LL (1)分析表无冲突,所以该文法是LL (1)文法.2.设文法G(S):S-a | a | (T)T-T,S | S消除左递归；构造相应的FIRST和FOLLOW集合;构造预测分析表解：(1)消除左递,文法变为 GS:S-a | a | (T)1T 一 ST | S丁 -6T | 此文法无左公共左因子.(2)构造相应的 FIRST和FOLL
12、OW 集合：FIRST(S)=a,人,(, FOLLOW(S)=#, , ) FIRST(T)=a, A, ( , FOLLOW(T)= FIRST(T)=, , FOLLOW(F)=) (3)构造预测分析表：aA(),#SS 一 aSfAS 一 (T)TT-STT-STT -STrT 一 e丁 ST;2.给出预测分析表,要求写出某个串的分析过程? 附加题1:对文法GS:(其实是习题1的第(3) (4)小题)? S a| A |(T) T SU U ,SU| ? 证实该文法是 LL(1)的,然后构造该文法的预测分析表,并判断(a,a)#是不是该文法的句子.各非终2符的FIRST集合如下:FIR
13、ST(S)=a,A , (FIRST(T)=FIRST(S)=a,A , (FIRST(U尸,.各非终2符的FOLLOW集合如下：FOLLOW(S)=# U FIRST(U) U FOLLOW(T) U FOLLOW(U)=#, , ,)FOLLOW(T)=)FOLLOW(U)=FOLLOW(T)=)每个产生式的SELECT集合如下：SELECT(S a)=aSELECT(S A )= A SELECT(S (T)=(SELECT(T SU尸FIRST(S)=a, A , (SELECT(U , SU)=, SELECT(U =FOLLOW(U)=)可见,相同左部产生式的SELECT集的交集均
14、为空,所以文法dS是LL文法.文法dS的预测分析表如下：aA()#SaA(T)TSUSUSUU,SU(1)给出输入串(a,a)#的分析过程步骤分析栈剩余输入串所用产生式1#S(a,a)#S (T)2#)T(a,a)#(匹配3#)Ta,a)#T SU4#)USa,a)#S a5#)Uaa,a)#a匹配6#)U,a)#U , SU7#)US,a)#,匹配8#)USa)#S a9#)Uaa)#a匹配10#)U)#U 11#)#)匹配12#接受第七章重点：1,识别活前缀的有限自动机的构造,判断某个文法是否是LR(0)文法,或SLR(1)文法或LR (1)文法,假设不是,请说明理由,假设是,构造相应的L
15、R分析表.2.查LR分析表,进行句子的识别.典型例题：2. (8 分)拓广文法 GS: S-SS-AS I A-aA I b(1)试构造以LR (1)工程集为状态的识别活前缀的有穷自动机；IiI 510(2)试判断文法是否是(1 ) I0:S一. S, #S一. AS, #S-. , #A 一. aA, a/b/#A 一. b, a/b/#LR(1坟法,并说明理由I2:S-A. S, #S一. AS, #S-. , #A 一. aA, a/b/#A 一. b, a/b/#I6:A - aA., a/b/#“归约一归约冲突,因而该(2)有穷自动机所有的状态都不含有“移进归约、文法是LR(1坟法.
16、练习：.(20分)给定文法 GS:S 一 SaA|aA 一 AbS|b(8分)请构造该文法的以LR(0)工程集为状态的识别标准句型活前缀的DFA.(4分)请构造该文法的LR(0)分析表.(4分)什么是LR(0)文法该文法是 LR(0)文法吗?为什么(4) (4分)什么是 SLR(1)文法?该文法是 SLR(1)文法吗为什么答：拓广文法 1分GS : S S S 一 SaA S 一 aA 一 AbS (4)A 一 b该文法的以LR(0)工程集为状态的识别标准句型活前缀的DFA :该文法的LR(0)分析表:状态ACTIONGOTOab#SA0S 211S 3acc2- 3r 3r 33S 544-
17、 2r 2 /S 6r 25-5r 5r 56S 277-4 /S 3r 4r 4LR(0)文法：该文法的以LR(0)工程集为状态的识别标准句型活前缀的DFA中没有冲突状态.该文法不是 LR(0)文法由于存在冲突状态：I 4和I 7(4) SLR(1)文法：该文法的以 LR(0)工程集为状态的识别标准句型活前缀的DFA中有冲突状态,冲突可用 FOLLOW集解决.该文法不是 SLR(1)文法.由于FOLLOW(S)=a,b,#,所以无法解决冲突.其它练习可以直接做书本上我们布置的作业！第八章：1.给出代码,写成代码对应的四元式(三地址码形式！),如while嵌套的译等.2.给出文法要求写语义规那
18、么,根据语法制导译方法重点：(1).赋值语句(2) . For 语句(3) .if then 语句4数组赋值5 .while 语句例：写出下面语句经语法制导译后所生成的四元式代码序列.共10分if xc do c:=c+1 else x:=x+5依次译,再考虑回填！解：假设初始为100,那么四元式代码序列为100ifxcgoto104103goto109104M:=C+1105C:=M106goto102107N:=X+5108X:=N10910分试完成以下语句译的四兀式序列.2021年出过while (AB) doif(CD) then X:=Y*Zelse X:=Y+Z;(1) if AB
19、 goto (3)(2) goto (11)(3)(4) goto (8)(5)(6)X:=T1(7)(8)T2:=Y+Z(9)X:=T2(10)(11)答:(3) if CD goto (5)(5)T1:=Y*Z(7) goto(1)(10) goto (1)练习：源程序如下：prod:=0;i:=1;while i 20 dobeginprod:=prod+ai*bi;i:=i+1end;、数组番S译3句T1:= VARPART与数组元素占的字节数相关比方4*iT2:=不变局部,一般为起始地址A或者起始地址 A减单个数组元素所占字节数比方A-4 如果i从1开始,而且上面写为 4*i,这里那
20、么需要写成 A-4T3:=T2T1试按语法制导译法将源程序译成四元式序列设A是数组a的起始地址,B是数组b的起始地址；机器按字节编址,每个数组元素占四个字节.四元式序列100 prod:=0101i:=1102 if i L.L | LL - LB | BB - 0 | 1解1:提示画出对应于输入101.101的语法树,然后设置相应的属性进行语义规那么的创立.产生式语义规那么S -L1.L2S val = Ll.val 十 L2.val/2 口现由S-LS.val:=L.valL - L1BL.val:=L1.val*2+B.val L.length:=L1.length+1L - BL.va
21、l:=B.valL.length:=1B - 0B.val:=0B - 1B.val:=1第十章：1.程序的传值、传地址的结果2.活动记录1静态链、动态链的连接2 Display表典型例题：1.当参数分别采用“传值、“传地址实现时,下面程序输出a的值分别是什么 5分Program maininput,outputProcedure px,y,z;Begin y:=y+2;z:=z+x;End ;Begina:=2; b:=6; pa+b, a, a;Print a;End.答：2 12 2.类PASCAL程序结构嵌套过程如下,该语言的编译程序采用栈式动态分配策略治理目标程序存储空间.假设过程调
22、用情况为Demo-A-B-B,画出程序运行到第二个B过程的时刻,栈内静态链、动态链的指示情况.Program Demo;Procedure AProcedure BIf d then B else A;End(*B*)Begin(*A*)B;End(*A*)Begin(*Demo*)AEnd(*Demo *)动态链静态链动态链静态链动态链静态链L动态链静态链b的过程活动记录b的过程活动记录A的过程活动记录DEMO的过程活动记录B的过程活动记录B的过程活动记录A的过程活动记录DEMO的过程活动记录练习1:考虑下面的程序:procedure p(x, y, z);beginy:=x+y;z:=z*
23、z;endbeginA:=2;B:=A*2;P(A, A, B);Print A, Bend.试问,假设参数传递的方式分别采用传地址和传值时,程序执行后输出解：传地址A=6,B=16传值A=2,B=4第十一章重点：1、根本块划分,并画出程序流程图2.根据程序流程图,找出循环！典型习题：8分将下面程序划分为根本块,并画出其根本块程序流图.A, B的值是什么2021年出过 if ab goto (2) halt(3) if cB2,对应的循环是 B2, B3, B4o其它的第二章、第九章、第十二章均直接考PL/0的内容,所以代码阅读很重要重点：1. PL/0符号表的生成2. PL/0某一个语法成分
24、的程序填空,如if.then, whiledo,+,+=,这局部在实验课里会讲,请大家要认真听.+=典型习题：练习1: 8分)对PL/0语言扩充单词：(2021年出过)+请完成以下识别单词+和+=设单词内码分别 为PLUS, PLUSPLUS和PLUSBECOMES)的词法分析程序段：if ( CH=+ ) if ( J|) ) SYM=PLUSBECOMES; GetCh(); else if ( CH=+) else 答：GetCh(); CH= SYM=PLUSPLUS; GetCh(); SYM=PLUS;2. PL/0示意程序为：var x;procedure A;var d;beg
25、in (* A *) write(x);end (* A *);procedure B;const n=7;var e,g;procedure D;var j,k;begin (* D *)read(j,k);x:=x+j*n;call A;end ;(* D *)begin (* B *)call D;end ;(* B *)begin (* main *)read(x);call B;end. (* main *)给出PL/0示意程序编译到 D过程体时TABLE表的内容.其中TABLE表的格式可为下表. TABLE表的格式namekindevelvaladr Jsize解：问答第5题PL/0示意程序编译到 D过程体时TABLE表的内容如下表.TABLE表的内容namekindlevelvaladrsizemainprocedure.04xvariable0.dx.Aprocedure0.过程A的入口4Bprocedure0.过程B的入口 待填待填5nconstant.7.evariable1dx.gvariable1dx+1.Dprocedure1过程D的入口51variable2dxkvariable2dx+1由于A和B是并列过程,当编译到 B过程时A过程体已经编译结束, A所定义的标识符不 会再被使用,所以由 B过程定义的标识符覆盖.