编译原理作业.doc

编译原理作业P7：1.1；1.2自编2.1；2.2自编2.3； 2.4自编2.5自编3.1自编3.2自编3.3；3.4P100.4.1；4.2自编4.3；4.4自编5.1自编5.2自编7.1；7.2自编8.1P7：1.1P7；1.2自编2.1文法GS：SxSxy所识别的语言是 。 a. xyx b. (xyx)* c. xnyxn(n0) d. x*yx*【解答】自编2.2令文法GN为 GN: NDNDD0123456789(1) GN的语言L(G)是什么?(2) 给出句子0127、34和568的最左推导和最右推导。【解答】 自编2.3对于文法GS: S(L)aSaLL, SS(1) 画出句型(S,(a)的语法树；(2) 写出上述句型的所有短语、直接短语、句柄。【解答】 自编2.4已知文法GS为SSaS，试证明文法GS为二义文法。【解答】 自编2.5按指定类型，给出语言的文法。 (1) L=aibjji1的上下文无关文法；(2) 字母表=a,b上的同时只有奇数个a和奇数个b的所有串的集合的正规文法；自编3.1什么是扫描器？扫描器的功能是什么？自编3.2结合自动机证明：正规式(ab)*a与正规式a(ba)*是否等价？给出分析过程。 自编3.3已知自动机DFA如图3-4所示图3-4 DFA写出其对应的语言，分别用正规文法和自然语言描述。【解答】自编3.4设有L(G)=a2n+1b2ma2p+1|n0,p0,m1。(1) 给出描述该语言的正规表达式；(2) 构造识别该语言的确定有限自动机(可直接用状态图形式给出)。【解答】P100：4.1P100；4.2自编4.3在算符优先分析法中，为什么要在找到最左素短语的尾时才返回来确定其对应的头，能否按扫描顺序先找到头后再找到对应的尾，为什么？ 【解答】 自编4.4设有文法GS: Sa|b|(A)ASdA|S(1) 构造算符优先关系表；(2) 给出句型(SdSdS)的短语、简单短语、句柄、素短语和最左素短语；【解答】自编5.1(1) 四元式之间的联系是通过 实现的。 a. 指示器 b. 临时变量 c. 符号表 d. 程序变量(2) 间接三元式表示法的优点为 。 a. 采用间接码表，便于优化处理 b. 节省存储空间，不便于表的修改 c. 便于优化处理，节省存储空间 d. 节省存储空间，不便于优化处理(3) 表达式(AB)(CD)的逆波兰表示为 。 a. ABCD b. ABCDc. ABCD d. ABCD【解答】 自编5.2(4) 有一语法制导翻译如下所示： SbAb print1A(B print2Aa print3BAa) print4若输入序列为b(aa)a)a)b，且采用自下而上的分析方法，则输出序列为 。【解答】 自编7.1将下面程序划分为基本块并作出其程序流图。 read(A,B) F=1 C=A*A D=B*B if C100 goto L2 halt L2: F=F-1 goto L1【解答】 自编7.2试画出如下中间代码序列的程序流图，并求出：(1) 各结点的必经结点集合D(n)；(2) 流图中的回边与循环。J=0L1：I=0if I 8 goto L3L2：A=B+CB=D*CL3：if B =0 goto L4write Bgoto L5L4：I= I+1if I8 goto