(完整版)(整理完)编译原理网上作业题参考答案20121101

1、东北农业大学网络教育学院编译原理作业题参考答案第一章 编译概述多项选择题：1. 编译程序各阶段的工作都涉及到（ BC。（*）A.语法分析B.表格管理C.出错处理 D.语义分析E.词法分析2. 编译程序工作时，通常有（ ABCE阶段。 （*）A.词法分析B.语法分析C.中间代码生成 D.语义检查E.目标代码生成填空题:1 解释程序和编译程序的区别在于（是否生成目标程序）。（*）（代码优（*）2编译过程通常可分为 5个阶段，分别是（词法分析）、（语法分析）、（中间代码生成）、 化）和（目标代码）生成。（*）3编译程序工作过程中，第一段输入是（源程序），最后阶段的输出为（目标代码生成）程序。4编译程

2、序是指将（高级语言编写的）程序翻译成（目标语言）程序的程序。（*）综合题：1. 画出编译程序的总体结构图，简述各部分的主要功能。（*） 解答：编译程序的总体结构如下图所示：词法分析程序：输入源程序，进行词法分析，输出单词符号。语法分析程序：在词法分析的基础上，根据语言的语法规则（方法规则）把单词符号串分解成各类语 法单位，并判断输入串是否构成语法上正确的“程序”。中间代码生成程序：按照语义规则把语法分析程序归约（或推导）出的语法单位翻译成一定形式的中 间代码，比如说四元式。优化程序：对中间代码进行优化处理。目标代码生成程序：把中间代码翻译成目标语言程序。表格管理模块保存一系列的表格，登记源程序

3、的各类信息和编译各阶段的进展情况。编译程序各阶段 所产生的中间结果都记录在表格中，所需信息多数都需从表格中获取，整个编译过程中都在不断地和表格 打交道。出错处理程序对出现在源程序中的错误进行处理。此外，编译的各个阶段都可能出现错误。出错处理 程序对发现的错误都及时进行处理。第二章文法和语言的基本知识多项选择题：1. ABC 2. ACE 3. BCD 4. AC 5. BC填空题：1 文法中的终结符和非终结符的交集是（空集）。词法分析器交给语法分析器的文法符号一定是（终结符），它一定只出现在产生式的（右）部。（*）2最左推导是指每次都对句型中的（最左）非终结符进行扩展。（*）3在语法分析中，最

4、常见的两种方法一定是（自上而上）分析法，另一是（自下而上）分析法。（*）4采用（自上而下）语法分析时，必须消除文法的左递归。（*）5. （语法）树代表推导过程，（分析）树代表归约过程。（*）6自下而上分析法采用（移进）、归约、错误处理、（接受）等四种操作。（*）7. Chomsky把文法分为（4）种类型，编译器构造中采用（2型）和（3型）文法，它们分别产生（上下文无关语言）和（正规语言）语言，并分别用（下推自动机）和（有限）自动机识别所产生的语言。（*）判断题：1.正确 2 .错误 3 .错误 4 .错误 5 .错误6. 错误7 .正确 8 .正确 9 .错误简答题1句柄：（*）解答：一个句型

5、的最左直接短语称为该句型的句柄。2.素短语：（*）解答：至少含有一个终结符的素短语,并且除它自身之外不再含任何更小的素短语。3.语法树：（*）解答：满足下面4个条件的树称之为文法 GS的一棵语法树。 每一终结均有一标记，此标记为Vn U Vt中的一个符号； 树的根结点以文法 GS的开始符S标记； 若一结点至少有一个直接后继，则此结点上的标记为Vn中的一个符号； 若一个以A为标记的结点有 K个直接后继，且按从左至右的顺序，这些结点的标记分别为Xi,X2,，准则AX i,X2,，冶 必然是G的一个产生式。4.归约：（*）解答：我们称 仏丫直接归约出a A0仅当Ay是一个产生式，且a（Vn U Vt

6、）*。归约过程就是从输入串开始，反复用产生式右部的符号替换成产生式左部符号，直至文法开始符。5.推导：（*）解答：我们称a AB直接推出丫,俱卩a A3 Ta y仅当丫是一个产生式,且 a 3 (Vn U Vt)*。如果 a=a -a,则我们称这个序列是从ai至a的一个推导。若存在一个从al an的推导，则称ai可推导出a。推导是归约的逆过程。问答题1 .给出上下文无关文法的定义。（*）解答：一个上下文无关文法G是一个四元式（Vt,Vn,S, P ），其中:VtQV N=；ia,其中，PV N,a (VtUVn)Vt是一个非空有限集，它的每个元素称为终结符号； Vn是一个非空有限集，它的每个元

7、素称为非终结符号, S是一个非终结符号，称为开始符号；。开始符号S至少必须在某个产生式的左部出现一次。2. 文法 GS:S aSPQ|abQQi PQbi bbbCH bc cCH cc(1) 它是Chomsky哪一型文法？(2) 它生成的语言是什么？ (*)解答：(1)由于产生式左部存在终结符号，且所有产生式左部符号的长度均小于等于产生式右部的符号长 度，所以文法GS是Chomskyl型文法，即上下文有关文法。(2)按产生式出现的顺序规定优先级由高到低(否则无法推出句子)，我们可以得到：S 二；abQ 二 abcS 二：aSPQ二 aabQP aabPQQ： aabbQQ二：aabbcQ二

8、aabbccS 二：aSPQ二 aaSPQPg aaabQPQPQ： aaabPQQPQ： aaabPQPQQ aaaPPQQQ aaabbPqqq 二 aaabbQQg aaabbbcQQ二 aaabbbccQ 二 aaabbbccc于是得到文法 GS生成的语言L=a nbncn|n 13. 按指定类型，给出语言的文法。L=aibj|j i 1的上下文无关文法。(*)解答：由L=ai bj |j i 1知，所求该语言对应的上下文无关文法首先应有SaSb型产生式，以保证 b的个数不少于a的个数；其次，还需有 St Sb或St bS型的产生式，用以保证 b的个数多于a的个数；也即 所求上下文无关

9、文法 GS为：GS : StaSb|Sb|b4. 有文法 G: St aAcB|BdAt AaB|c Bt bScA|b(1) 试求句型 aAaBcbbdcc和aAcbBdcc的句柄；(2) 写出句子 acabcbbdcc的最左推导过程。(*)解答：(1 )分别画出对应两句型的语法树，如下图所示句柄:AaB Bd(2)句子acabcbbdcc的最左推导如下：ST 二 aAcB 二 aAaBcB 二 acaBcB = acabcB 二 acabcbScA 二 acabcbBdcA 二 acabcbbdcA 二 acabcbbdcc5. 对于文法GS:S( L) |aS|aLt L, S|S(1)

10、 画出句型(S, (a)的语法树。(2) 写出上述句型的所有短语、直接短语、句柄和素短语。(*)解答：(1)句型(S, ( a)的语法树如下图所示。(L )图句型(S, (a)的语法树(2)由上图可知： 短语：S、a、(a)、S,(a)、(S,(a); 直接短语：a、S; 句柄：S; 素短语：素短语可由图2-8-3中相邻终结符之间的优先关系求得，即;# 0 i 09.已知语言L(G)=ab nc |n 1试对该语言构造相应文法。(*)解答 ：GZ:Zt aBCBb|b10证明下列文法的二义性 1GZZtaZbZ|aZ|a(*)2 GSStABAtbB|bC|ba BtSb|ba|a CtBb|

11、b解答： （ 1）对于句子aaaba,画出二棵不同的语法树，因而是二义的。2)GS对于句子baba,画出二棵不同的语法树，因而是二义的。11. 有文法 GS: St iSeS|iS|i该文法是否是二义的。试证明之。（*） 解答:对于句子 iiiei ，有两棵不同的语法树，故文法是二义的。12. 文法GT :aR , FH Tb|d生成的语言是什么？GT是否为3型文法？ （*）解答：不是 3 型文法。13. 试写出能够描述下列电话号码格式的文法。(*)67391742010-67391742(010)67391742解答： 文法产生式规则如下： t t tt()tDIGDIGtDIGDIGDIG

12、tDIGDIGDIG DIGtDIGDIGDIGDIG14. 试构造生成语言的上下文无关文法。 (*)(1) a nbnci | n 1,i 0 (2) w | w a,b +,且w中a的个数恰好比 b多1 解答：(1)把anbnci分成anbn和c，两部分，分别由两个非终结符号生成，因此，生成此文法的产生式为:S t ABA t aAb|abB t cB| e（2）令S为开始符号，产生的 w中a的个数恰好比b多一个，令E为一个非终结符号，产生含相同个 数的a和b的所有串，则产生式如下：S t aE|Ea|bSS|SbS|SSbE t aEbE|bEaE| GS:S - S AND S | S

13、 OR15. 下面的二义性文法描述命题演算公式，为它写一个等价的非二义性文法。S | NOT S |p | q | （S）（*）解答：GS:S - S AND A | AA - A OR B | BB - NOT B |p | q | （S）16. 对于下列语言分别写出它们的正规表达式。（*）（1）英文字母组成的所有符号串，要求符号串中顺序包含五个元音。（2）英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。解答：（1） 令Letter表示除这五个元音外的其它字母。(letter)*A(letter)*E(letter)*l(letter)*O(letter)*U(letter)*

14、(2)A*B*.Z*第三章词法分析与有穷自动机多项选择题：1. ACE 2. ABD填空题：1.确定有限自动机 DFA是（NFA ）的一个特例。（*）2 若二个正规式所表示的（正规集）相同，则认为二者是等价的。（*）3. 个字集是正规的，当且仅当它可由（DFA/NFA）所 （识别）。（*）判断题：1.错误2 .错误3 .错误4 .正确5 .正确6.正确 7 .正确 8 .正确 9 .错误 10 .正确综合题：1设M =( x,y, a,b, f,x,y)为一非确定的有限自动机，其中f定义如下：f (x,a) = x,yf (a,b)= yf (y,a)= 0f (y,b)= x,y试构造相应的

15、确定有限自动机M。(*)解答：对照自动机的定义 M=(S,X ,f,So,z),由f的定义可知f(x,a)、f(y,b)均为多值函数，所以是一非确定有 限自动机，先画出 NFAM 相应的状态图，如图下所示。图 NFAM用子集法构造状态转换矩阵下表所示。将转换矩阵中的所有子集重新命名而形成下表所示的状态转换矩阵。表状态转换矩阵即得到M=( 0,1,2, a,b, f,0, 1,2),其状态转换图如下图所示。将上图的DFAM 最小化。首先，将M的状态分成终态组1 , 2与非终态组0;其次，考察1,2。由于1,2a=1,2b=21,2 ，所以不再将其划分了， 也即整个划分只有两组 0 ，1,2 ：令

16、状态 1代表1,2 ，即把原来到达 2 的弧都导向 1，并删除状态 2。 最后，得到如下图所示化简 DFAM 。图化简后的DFAM2 对给定正规式 b* ( d|ad) (b|ab) +，构造其NFAM。(*)解答：首先用A +=AA *改造正规式得：b*(d|ad)(b|ab)(b|ab)* ；其次，构造该正规式的NFAM，如下图所示。图 NFAM3字母表a, b上的正规式R= (ba|a) *，构造R的相应DFA。 (*) 解答：，并构造与之等价状态4. 请写出在E= (a,b)上，不是最少的DFA。(*)解答：根据题意，不以a开头就意味着以b开头，且以aa结尾的正规式为：b(a|b)*

17、aa根将图1所示的NFA确定化，如图2所示。NFA 将图 1 所示的 NFA 确定化，如图从图 2可知已为最简状态，由于开始状态 0 只能输入字符 b 而不能与状态 1 合并，而状态 2 和状态 3 面对输入符号的下一状态相同，但两者一为非终态、一为终态，故也不有合并，故图 2 所示的状态转换矩 阵已是最简的 DFA，如图3所示据正规式画出 NFA，如图1所示。图 2 状态转换矩阵图 3 最简 DFA5. 人运狼、羊、菜过河，一次运一件，不让羊吃掉菜，也不让狼吃掉羊，画出渡河的状态转换图。可否将其抽象为一个有限自动机。（*）解答：先写出渡河的方法，串中对象顺序为人来回渡河时所运的货物的顺序：羊

18、空菜羊狼空羊羊空狼羊菜空羊现给出一个 NFA:M=（S ,Q,0,9, S ）其中=羊，空，菜，狼Q=0,1,2,3,4,5,6,7,8,9转形函数S （0, 羊）=1,S （1, 空）=2,S （2, 菜）=3,S （2, 狼）=5S （3, 羊）=4,S （5, 羊）=6,S （4, 狼）=7,S （6, 菜）=7S （7,空）=8,S （8,羊）=96对于正规表达式（a|b） *a（a|b）构造最小状态的 DFA （*）解答：NFA M: DFA M:化简：中的DFA M中没有等价状态，因此为最小化的DFA M第四章语法分析多项选择题：1. AD 2. CE 3. ACDE 4. CE

19、5. ABCE 6. ACDE填空题:1 对于一个文法，如果能够构造（LR（0）文法）。使得它的 （每个入口）均是唯一确定的，则称该文法为LR文法。（*）2. 字的前缀是指该字的（任意首部）。（*）3. 活前缀是指（规范句型）的一个前缀，这种前缀不含（句柄） 之后的任何符号。（*）4. 在LR分析过程中，只要（输入串） 的已扫描部分保持可归约成一个（活前缀），则扫描过的部分正确。（*）5. 将识别（活前缀） 的NFA确定化，使其成为以（项目集合）为状态的DFA这个DFA就是建立 （LR分析算法）的基础。（*）6. Aa称为（归约）项目；对文法开始符Sfa为（接受）项目；若a为终结符，则称Aaa

20、 3 为（移进） 项目；若B为非终结符，则称 Aaa 3为（待约） 项目。（*）7. LR （ 0）分析法的名字中“ L”表示（自左至右分析），“ R表示 （采用最右推导的逆过程即最左归约），“ 0”表示 （向右查看0个字符）。（*）判断题：1正确简答题：综合题：1构造下面文法的 LL (1)分析表。(*)X TLTt int | realLt id RRt , id R |解答： LL ( 1)分析表见下表。分析 虽然这个文法很简单，我们还是从求开始符号集合和后继符号集合开始。FIRST(D) =FIRST(T) =int, real FOLLOW (D) =FOLLOW (L)=#FIRS

21、T( L) =idFOLLOW ( T) =idFIRST (R) = , ,FOLLOW (R) =#有了上面每个非终结符的FIRST集合，填分析表时要计算一个产生式右部a的FIRST ( a)就不是件难事了。填表时唯一要小心的时，&是产生式FT&右部的一个开始符号，而 #在FOLLOW ( R)中，所以FTs填在输入符号 #的栏目中。表 LL ( 1 )分析表2. 下面文法 GS是否为LL (1)文法？说明理由。(*)St AB|PQxAt xybePdP| eQaQ| e解答：该文法不是 LL (1)文法，见下面分析中的说明。分析只有三个非终结符有两个选择。(1 ) P的两个右部dP和e

22、的开始符号肯定不相交。(2) Q的两个右部aQ和e的开始符号肯定不相交。(3) 对S来说，由于x FIRST(AB)，同时也有x FIRST(PQx)(因为P和Q都可能为空)。所以该 文法不是LL (1)文法。3. 设有以下文法：(*)GS : StaAbDeldat BSD|eBt SAc|cD| eDTSe| e(1) 求出该文法的每一个非终结符U的FOLLOW集。(2) 该文法是LL (1 )文法吗？(3) 构造CS的LL (1)分析表。解答：(1)求文法的每一个非终结符U的FOLLOW 集的过程如下：因为： S是识别符号，且有 At BSD、Bt sac、DTSe，所以FOLLOW (

23、S)应包含FIRST(D) U FIRST(Ac) U FIRST(e) U #=a,d U a,d,c,e U e U #=a,c,d,e# 又因为Atb SD和DTe ,所以FOLLOW中还包含FOLLOW(A)。因为St aAbDe和BtSAc,所以FOLLOW (A) =FIRST ( bDe)U FIRST (e) =b,e综合、得 FOLLOW (S) =a,d,e,e,# U a,b,e,d,e,#因为 At BSD，所以 FOLLOW (B) =FIRST ( SD) =a,d因为 StaAbDe | d、AtBSD| e 和 BtSAc | eD，所以FOLLOW (D) =

24、FIRST (e)U FOLLOW (A )U FOLLOW ( B)=e U b,e U a,d=a,b,e,d,e(2) GS不是 LL (1)文法。因为产生式BtSAc|cD| e中FIRST (SAc) n FOLLOW (B) =a,d工(3)构造GS的LL ( 1)分析表。按照LL (1)分析表的构造算法构造方法GS的LL (1)分析表如下表所示。表 GS的LL (1)分析表4. 将文法GV改造成为LL(1)的。(*)GV : SN|NEi V|V+ENRi解答：对文法 GV 提取公共左因子后得到文法：G V: S NAAf |Ei VBBf |+ENRi求出文法G V中每一个非终

25、结符号的FIRST集：FIRST(V)=iFIRST(A)=, FIRST(E)=iFIRST(B)=+, FIRST(N)=i求出文法G V中每一个非终结符号的FOLLOW集：FOLLOW(V)=# U U FOLLOW(E)=#,+,FOLLOW(A)= FOLLOW(V)=+,# U sU FOLLOW(E)=FOLLOW(B)= FOLLOW(E)= sU FOLLOW(V)=,+,#可以看到，对文法 G V的产生式As |E,有FIRST(E) A FOLLOW(A)=A +,#= 对产生式Bs |+E有FIRST(+E)A FOLLOW(B)=+A =而文法的其他产生式都只有一个不

26、为s的右部，所以文法 G V是 LL(1)文法。5. 已知文法：(*)GA : AaAa| &( 1 )该文法是 LL ( 1 )文法吗？为什么？(2) 若采用LL (1)方法进行语法分析，如何得到该文法的LL (1 )分析表?(3) 若输入符号串“aaaa”请给出语法分析过程。解答：(1)因为产生式 AtaAa| &有空产生式右部，而FOLLOW(A)=# U FIRST(a)=a, #造成 FIRST(A) n FOLLOW(A)=A& n a, #工所以该文法不是 LL ( 1)文法。(2)若采用 LL (1)方法进行语法分析，必须修改该文法。因该文法产生偶数(可以为 0 )个a,所以得

27、到文法G A： Z aaA| 此时对产生式 2aaA| ,有 FOLLOW(A)=# U FOLLOW(A)=#，因而FIRST(A)n FOLLOW(A)=a,& n #=所以文法G A是 LL (1)文法，按LL (1 )分析表构造算法构造该文法的LL ( 1)分析表如下表所示。表 文法G A的LL分析表(3)若采用LL(1)方法进行语法分析，对符号串“aaaa的分析过程如下表所示。表对符号串“aaasS勺分析过程6 .设有文法 GS为：(*)St a|b|(A)At SdA|S( 1 )完成下列算符优先关系表，见下表，并判断GS 是否为算符优先文法。表 算符优先关系表（2）给出句型（Sd

28、SdS）的短语、简单短语、句柄、素短语和最左素短语。（ 3）给出输入串（ adb） #的分析过程。解答：（ 1）先求文法GS 的 FIRSTVT 集和LASTVT 集：由 Sta|b|(A)得：FIRSTVT(S)=a,b,( ) ；由At Sd得：FIRSTVT(A)=d；又由At s得FIRSTVT(S)由 Sta|b|(A)得；LASTVT(S)=a,b,;由AtdA 得FIRSTVT(A) ，即 FIRSTVT(A)=d,a,b,( ；LASTVT(A)=d, 又 由AtS得LASTVT(S)构造优先关系表方法如下：LASTVT(A) ，即 LASTVT(A)=d,a,b,)对iab，

29、或iaQb，有ab；对 iaR，而b FIRSTVT(R)，有ab；有 ab。)；对 iRb，而 a FIRSTVT(R)由此得到： 由St(A)得：(d，(a，(b，(（；由AtdA得dFIRSTVT(A)即d d， da，db， d( ； 由 St A)得,LASTVT(A)d )， a )，b)， ) ；由At Sd得LASTVT(S)d即d，）d；此外，由#S#得：#；由#FIRSTVT(S) 得b，#(由LASTVT(S)#得#，a#，b#，)#。最后得到算符优先关系表，见下表。表 算符优先关系表由上表可以看出，任何两个终结符之间至少只满足三种优先关系之一，故 GS 为算符优先文法。

30、（2）为求出句型（SdSdS）的短语、简单短语、句柄，我们先画出该句型对应的语法树，如下图所示。由图得到：短语： S， SdS， SdSdS，（ SdSdS）简单短语（即直接短语） ：S句柄（即最左直接短语） ：S素短语：SdS，它同时也是该句型的最左素短语。图句型（SdSdS）的语法树3）输入串（ adb） #的分析过程见下表。表 输入串（ adb） #的分析过程7.设有文法 GS为：（*）St a|b|（A）A t SdA|S1）完成下列算符优先关系表，见下表，并判断 GS 是否为算符优先文法。表 算符优先关系表（2）给出句型（SdSdS）的短语、简单短语、句柄、素短语和最左素短语。（ 3

31、）给出输入串（ adb） #的分析过程。解答：（ 1）先求文法GS 的 FIRSTVT 集和LASTVT 集：由 Sta|b|(A)得：FIRSTVT(S)=a,b,( ) ；由At Sd得：FIRSTVT(A)=d；又由At s得FIRSTVT(S)由 Sta|b|(A)得；LASTVT(S)=a,b,;由atdA得FIRSTVT(A) ，即 FIRSTVT(A)=d,a,b,( ；LASTVT(A)=d, 又 由AtS得LASTVT(S)构造优先关系表方法如下：LASTVT(A) ，即 LASTVT(A)=d,a,b,)对iab，或iaQb，有ab；对 iaR，而b FIRSTVT(R)，

32、有ab；有 ab。)；对 iRb，而 a FIRSTVT(R)由此得到：由St(A)得：(d，(a，(b，(（；由AtdA得dFIRSTVT(A)即d d， da，db， d( ； 由 St A)得,LASTVT(A)d )， a )，b)， ) ；由d，）d；此外，由#S#得：#；由#FIRSTVT(S) 得b，#(由LASTVT(S)#得#，a#，b#，)#。最后得到算符优先关系表，见下表。表 算符优先关系表由上表可以看出，任何两个终结符之间至少只满足三种优先关系之一，故 GS 为算符优先文法。（2）为求出句型（SdSdS）的短语、简单短语、句柄，我们先画出该句型对应的语法树，如下图所示。

33、由图得到：短语： S， SdS， SdSdS，（ SdSdS）简单短语（即直接短语） ：S句柄（即最左直接短语） ：S素短语：SdS，它同时也是该句型的最左素短语。图句型（SdSdS）的语法树3）输入串（ adb） #的分析过程见下表。表 输入串（ adb） #的分析过程&对于文法 GS : St AS|bA SA|a（ 1）列出所有 LR （0）项目；(2)列出构成文法LR ( 0)项目集规范族。(*)解答：首先将文法G拓广为GS:SfSt AS|b8.At-SA3.St-AS11.At-a6.St-b3.St-AS8. At-SA6.St-b11.At-aI 2：4.StA-SI 5：5

34、.StAS-3.St-AS9.AtS-A6.St-b8.At-SA8.At-SA11 .At-a11 .At-a3.St-AS6.St-b注意：I i中的Sts 和At - SA是由状态Io中的1和3读入一个S字符后得到的下一个项目;，而14中的At SA和At A-S则是由13中的9和3读入一个A字符后得到的下一个项目;I 5中的 StAS-AtS-A 则是由 I 4中的 4和 8 读入一个S字符后得到的下一个项目。状态全体构成了文法 G的LR (0)规范族。(1)文法GS的LR ( 0)项目是：1.St-s5.StAS-9 .AtS-A2.St S-6.St-b10.AtSA-3.St-A

35、S7.St b -11 . AT-a4.StA-S8.At-SA12.Ata-(2)用&-CLOSURE(闭包)办法构造文法 G的LR (0)项目集规范族如下I 0：1.St-SI 3：9.ATS-AI 6：12.ATa-3.St-AS8 .AT-SAI 7： 7 .STb-8.At-SA3 .ST-AS11.At-a6 .ST-b6.St-b11.AT-aI1：2.StS-I 4：10.ATSA-At SA|a9. atS- A4.S t a-S9. 有文法 GSSta| A | ( T)TtT, S|S该文法是否是 LL (1)文法，若不是，请进行改写。并给出它的分析表。(*)解答：不是。

36、Tt STTt T, S|SFIRST(S)=FIRST(T)=a, A, ( FIRST(T)= , , FOLLOW(S)=#,， )FOLLOW(T)=FOLLOW(T)= )分析表如下：10有文法 GS( 1)StA( 2)StB( 3)AtaAb( 4)Atc( 5)BtaBb( 6)Btd试构造相应的解答：LR ( 0)项目集规范族及相应的分析表。(*)11. 已知文法 GS ，其产生式如下：St (L)|aLt L , S|S从GS中消除左递归，并为之构造一个非递归预测分析器LL(1)分析表。请说明在句子(a , (a ,a)上的分析器的动作。(*)答： 将所给文法消除左递归得G

37、：S t(L)|a L t SLLt , SL |实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合控制，下面构造预测分析表： 根据文法G有FOLLOW(S) = ) , , , $ FOLLOW(L) = ) FOLLOW(L ) = ) FIRST(s) = ( , a )FIRST(L) = ( , a )FIRST(L) = , 按以上结果，构造预测分析表M如下:文法G是LL(1)的，因为它的LL(1)分析表不含多重定义入口。 预测分析器对输入符号串 (a, (a, a) 做出的分析动作如下:i&A输出$s(3.(a(a)$)L(a. (a,s 今(L)$)La

38、. (a. a)$)LSa. (a. a)$SU$)Laa. (a. a)$S $)L.(a. a)$)LS,.(a.司)$U , SL$)LS(a. a)$)L)L(a, a)$3(L) n$)LJLa, a)$)L)LhSa非SU$)L)Lb3a. a)$S T巧$)L】L? $)L)LhS.a)$ a) )5U 今,SLSJLJLSa)$)L)LFa邨S a$)LK$)L)L$)LE$)$12.证明下面文法是 SLR(1)文法，并构造其 SLR分析表。E+T|TTF|FFt F*|a|b(*)答：该文法的拓厂文法G为(0) E t E(1) EtE+TE t T(3) TtTFT t F

39、(5) FtF*(6) F t a(7) Ftb其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下：Io = E E, E E+T, E T, T TF, T F, F f*,a, F b1 :=ET E-,E TE- +T2 =ET T ,T tT - F, F t F*, F t a, F t b3 :=TT F ,F T F *4 =Ft a 15 = F t b 16 = E t e+ T, T TF, T F, F F*, F a, F b17 = T tTF , F t f *18 = F tf* 19 = E t E+T , T tt F, F t f*, F t

40、a, F t b求 FOLLOW!：FOLLOW(E)=+ ,$ FOLLOW(T)=+ ,$ , a, bFOLLOW(F)=+ ,$ , a, b, *构造的SLR分析表如下：狀态actiongoto+*ab$ETF0S4S5123136acc2r2S4ssd应73国S3rdr4r44rG怕rGr6r7r?ar7r7S4S5937治S3r3r5r3Sr5r5rSr59nS4S5r11显然，此分析表无多重定义入口，所以此文法是SLR文法第五章 语法制导翻译技术和中间代码生成多项选择题:1. ACDE 2. BCD 3. BC4. BD 5. BCE填空题：等形式，生成中间代码主要目标） 指令

41、，甚至可用来对输入（标号定义） 时才能确定，综合属性） 。（*）1中间代码有 （逆波兰记号）、（树形表示）、（三元式）、（四元式）是为了使 （目标代码的优化容易实现）。（*）2语法制导翻译既可以用来产生（中间） 代码，也可以用来产生串进行 （解释执行） 。（*） 3当源程序中的标号出现“先引用后定义”时，中间代码的转移地址须持 因而要进行 （回填） 。（*） 4文法符号的属性有两种，一种称为（继承属性） ，另一种称为5后缀式 abc-/ 所代表的表达式是（ a/（b-c） ），表达式 （a-b）*c 可用后缀式（ ab-c* ）表示。 （*）6用一张 （间接码表） 辅以 （三元式表） 的办法来表示中间代码，这种表示法称为间接三元式。（*)问答题：1给出下列表达式的逆波兰表示（后缀式）：（*） a*（-b+c）（A V B） A （CVq D A E）解答：.abc+*;AB V CDn EAVA2写出算术表达式：A+B*（C-D）+E/（C- D） fN 的：（*） 四元式序列； 三元式序列； 间接三元式序列 解答：3. 写出下面算术表达式 E值的语义描述：(*)(1) E 1+E2(2) 0解答：E.Val:=E.Val2.Vdl EE.Val:= 0E.Val:= 14. 给出下列表达式的逆波兰表式。(*)(1) ad V a+be(