《2022年南邮《编译原理》习题解答 .pdf》由会员分享，可在线阅读，更多相关《2022年南邮《编译原理》习题解答 .pdf（31页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、编译原理习题解答：第一次作业：P14 2、何谓源程序、目标程序、翻译程序、汇编程序、编译程序和解释程序？它们之间可能有何种关系？答：被翻译的程序称为源程序；翻译出来的程序称为目标程序或目标代码；将汇编语言和高级语言编写的程序翻译成等价的机器语言，实现此功能的程序称为翻译程序；把汇编语言写的源程序翻译成机器语言的目标程序称为汇编程序；解释程序不是直接将高级语言的源程序翻译成目标程序后再执行，而是一个个语句读入源程序，即边解释边执行；编译程序是将高级语言写的源程序翻译成目标语言的程序。关系：汇编程序、解释程序和编译程序都是翻译程序，具体见P4 图 1.3。P14 3、编译程序是由哪些部分组成？试述
2、各部分的功能？答：编译程序主要由8 个部分组成： （ 1）词法分析程序； （2）语法分析程序； （ 3）语义分析程序；（ 4）中间代码生成； （ 5）代码优化程序； （ 6）目标代码生成程序；（7）错误检查和处理程序； （ 8）信息表管理程序。具体功能见P7-9。P14 4、语法分析和语义分析有什么不同？试举例说明。答：语法分析是将单词流分析如何组成句子而句子又如何组成程序，看句子乃至程序是否符合语法规则，例如：对变量x：= y 符合语法规则就通过。语义分析是对语句意义进行检查，如赋值语句中x 与 y 类型要一致，否则语法分析正确，语义分析则错误。补充：为什么要对单词进行内部编码？其原则是什么
3、？对标识符是如何进行内部编码的？答：内部编码从“源字符串”中识别单词并确定单词的类型和值；原则：长度统一，即刻画了单词本身，也刻画了它所具有的属性，以供其它部分分析使用。对于标识符编码，先判断出该单词是标识符，然后在类别编码中写入相关信息，以表示为标识符，再根据具体标识符的含义编码该单词的值。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 31 页 - - - - - - - - - 第二次作业：P38 1、设 T1 11， 010， T20， 01， 1001，计算：
4、T2T1， T1*，T2+。T2T1 011， 0010， 0111， 01010， 100111 ， 1001010 T1* ， 11，010， 1111 ， 11010， 01011， 010010, T2+ 0， 01， 1001， 00， 001， 01001，010， 0101, P38-39 8、设有文法GS：S aAb A BcA | B B idt |试问下列符号串（1）aidtcBcAb （2） aidtccb（4） abidt 是否为该文法的句型或句子。（ 1） SaAbaBcAbaidtcAbaidtcBcAb 句型但不是句子；（ 2）SaAbaBcAbaidtcAbai
5、dtcBcAbaidtccAbaidtccBbaidtccb；是句型也是句子；（ 4）该文法的句子或句型的最后一个字符串一定是字符“b” ；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 31 页 - - - - - - - - - 第三次作业：P39 11、试分别描述下列文法所产生的语言（文法开始符号为S） ：（ 1）S 0S | 01 （ 2）S aaS | bc （ 1）L(G) 0n1| n 1；解题思路：将文法转换为正规表达式 （ 2）L(G) a2nbc |
6、n 0。P39 12、试分别构造产生下列语言的文法：（ 1） abna | n=0， 1，2， 3, （ 3） aban | n 1 （ 5） anbmcp | n，m， p0 （ 1） G VN，VT， P， S， VNS，A ， VTa， b，P： S aAa A bA |（ 3） G VN，VT， P， S， VNS，A ， VTa， b，P： S abA A aA | a （ 5） G VN， VT， P，S， VN S， A ， B， C， VT a， b， c，P： S ABC A aA |B bB |C cC | G VN， VT， P，S， VN S， VT a，b， c，P：
7、 S aS | bS | cS | P39 15. 设文法 G 规则为：S： ： =AB B： ： =a|Sb A： ： =Aa|bB 对下列句型给出推导语法树，并求出其句型短语，简单短语和句柄。（ 2） baabaab (3)bBABb 解（ 2）S AB Aa S b b B AB a b B a a 句型 baabaab 的短语 a, ba, baa, baab, baabaab，简单短语a，句柄a 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 31 页 - -
8、- - - - - - - S （ 3）AB bB S b AB 短语 bB, AB, ABb， bBABb 简单短语bB, AB，句柄 bB 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 31 页 - - - - - - - - - 第四次作业P41 24. 下面文法那些是短语结构文法，上下文有关文法，上下文无关文法，及正规文法？1.S:=aB B:= cB B:=bC:=c 2.S:=aB B:=bC C:=c C:= 3.S:=aAb aA:=aB aA:=aaA
9、B:=b A:=a 4.S:=aCd aC:=B aC:=aaAB:=b 5.S:=AB A:=a B:=bC B:=b C:=c 6. S:=AB A:=a B:=bC C:=c C:= 7. S:=aAS:= A:=aAA:=aB A:=a B:=b8. S:=aAS:= A:=bAb A:=a短语结构文法（0）4 上下文有关文法（1）3 上下文无关文法（2）5 6 8 或者2 5 6 7 8 正规文法（ 3）1 2 7 或者1 P42 29. 用扩充的BNF 表示以下文法规则：1Z:=AB|AC|A 2A:=BC|BCD|AXZ|AXY 3S:=aABb|ab 4A:=Aab| 解 :
10、1 Z:=A （ B|C| ） :=AB|C 2 A:=BC（ |D ）|X（ Z|Y） := BCD|X （ Z|Y） 3 A:=a(AB| )b) := aABb4 A:=ab| :=ab名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 31 页 - - - - - - - - - 第五次作业：P74 4. 画出下列文法的状态图：Z： ： =Be B： ： =Af A： ：=e|Ae 并使用该状态图检查下列句子是否该文法的合法句子：f, eeff, eefe。由状态图可
11、知只有eefe 是该文法的合法句子。P74 5. 设右线性文法G=(S, A, B, a, b, S, P) ，其中P 组成如下：S： ： =bA A： ： =bB A： ： =aAA： ： =b B： ： =a 画出该文法的状态转换图。P74 6. 构造下述文法GZ 的自动机，该自动机是确定的吗？它相应的语言是什么？Z： ：=A0 A： ： =A0|Z1|0 解 1：将左线性文法转换为右线性文法，由于在规则中出现了识别符号出现在规则右部的情形，因此不能直接使用书上的左右线性文法对应规则，可以引入非终结符号B，将左线性文法变为Z： ： =A0 A： ： =A0|B1|0 B： ： =A0，具体
12、为：A := Z1 A := B1 A := A01 Z := A0 B := A0 将所得的新左线性文法转换成右线性文法：此时利用书上规则，其对应的右线性文法为：A： ：=0A|0B|0 Z： ：=0AB： ：=1A 解 2：先画出该文法状态转换图：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 31 页 - - - - - - - - - NFA=（ S， A， Z， 0， 1，M，S，Z ）其中 M：M（S， 0） =A M（ S， 1） =?M（ A， 0） =A
13、，Z M（ A， 1） =?M（ Z， 0） =? M（ Z， 1） =A 显然该文法的自动机是非确定的；它相应的语言为：0， 1上所有满足以00 开头以0结尾且每个1 必有 0直接跟在其后的字符串的集合；那么如何构造其相应的有穷自动机呢？先构造其转换系统：根据其转换系统可得状态转换集、状态子集转换矩阵如下表所示：I I0I1S 0 1 S , S A 0 1 A A, Z, Z 1 2 A, Z, Z A, Z, Z A 2 2 1 则其相应的DFA 为：P74 8. 设 (NFA) M = ( A, B, a, b, M, A, B )，其中M 定义如下：M (A, a) = A, B M
14、 (A, b) = B M (B, a) = ? M (B, b) = A, B 请构造相应确定有穷自动机(DFA) M 。解：构造一个如下的自动机(DFA) M ，(DFA) M =K, a, b, M , S, Z K 的元素是 A B A, B由于 M（ A, a） =A, B ，故有 M （ A, a） =A, B 同样M （ A ， b ） =B M （ B ，a） = ?M （ B ，b） =A， B由于 M（A， B， a）= M（ A， a） U M（ B， a） = A， BU ?= A ， B 故M （ A， B， a）= A，B 由于 M（A， B， b）= M （ A，
15、 b） U M（ B， b） =BU A ， B = A ， B 故M （ A， B， b） = A， B S Z0 0 1 A 0 Z S1 2 0 1 0 0 0 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 31 页 - - - - - - - - - S=A，终态集Z=A ，B，B 重新定义：令0=A 1=B 2=A, B ，则 DFA 如下所示：可以进一步化简，把M 的状态分成终态组1，2和非终态组 0由于 1， 2a=1， 2b=21， 2，不能再划分。至此
16、，整个划分含有两组1， 20 令状态 1 代表 1， 2，化简如图：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 31 页 - - - - - - - - - 第六次作业：P74 11（ 1） (0 | 11*0)* 解：先构造该正规式的转换系统：由上述转换系统可得状态转换集K=S, 1, 2, 3, 4, Z ，状态子集转换矩阵如下表所示：I I0I1K 0 1 S, 1, Z 1, Z 2, 3, 4 0 1 2 1, Z 1, Z 2, 3, 4 1 1 2 2,
17、 3, 4 1, Z 3, 4 2 1 3 3, 4 1, Z 3, 4 3 1 3 P74 12. 将图 3.24 非确定有穷自动机NFA 确定化和最少化。解：设 (DFA)M = K, VT, M, S, Z ，其中， K=0, 0, 1, 1 ， VT =a, b， M：1 0 a a, b a 图 3.24 NFA 状态转换图S Z (0 | 11*0)* 1 1 S Z 1 0 11*0 S Z 1 0 2 1 3 1 0 4 1 1 3 0 1 00 1 0 1 1 2 由状态子集转换矩阵可知，状态 0 和 1 是等价的，而状态2和 3 是等价的，因此，合并等价状态之后只剩下2 个
18、状态，也即是最少状态的DFA。1 0 0 1 0 1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 31 页 - - - - - - - - - M (1, a) =0 M (1, b) = M (0, 1, a) =0, 1 M (0, 1, b) =1 M (0, a) =0, 1 M (0, b) =1 S=1， Z=0, 0, 1 令 0, 1=2，则其相应的状态转换图为：现在对该DFA 进行化简，先把状态分为两组：终态组0, 2 和非终态组1，易于发现0, 2
19、 不可以继续划分，因此化简后的状态转换图如下：P74 18. 根据下面正规文法构造等价的正规表达式：S:=cC | a , A:=cA | aB , B:=aB | c , C:=aS | aA | bB | cC | a , 解：由式可得B= aB + c B=a*c 由式可得A= cA + aB A= c*aa*c 由式可得S= cC + a 由式可得C= aS + aA + bB + cC + a C= c*( aS + aA + bB + a) C= c*( aS + ac*aa*c + ba*c + a) S= cc*( aS + ac*aa*c + ba*c + a) + a =
20、cc*aS+ cc*( ac*aa*c + ba*c + a) + a = (cc*a)*( cc*( ac*aa*c + ba*c + a) + a) = (cc*a)*( cc*( ac*aa*c | ba*c | a) | a) 另一种答案是S= c(ac | c)*( ac*aa*c | ba*c | aa | a) | a 1 0 a b a a 2 b 1 0, 2 a b a 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 31 页 - - - - - -
21、 - - - 第七次作业：P142 1. 试分别消除下列文法的直接左递归（采用两种方法重复法和改写法）（ 1） GE: E:=T | EAT , T:=F | TMF , F:=(E) | i , A:=+ | - , M:=* | / , 解：先采用“重复法”：再采用“改写法” ：E:=TAT E:=TE T:=FMF E := ATE | F:=(E) | i T:=FT A:=+ | - T :=MFT | M:=* | / F:=(E) | i A:=+ | - M:=* | / P142 2. 试分别消除下列文法的间接左递归（ 2） GZ: Z:=AZ | b , A:=Z A |
22、a , 解：将式代入式可得，Z:=ZAZ | aZ | b 消除左递归后得到：Z:=(aZ | b)Z Z :=AZZ | A:=ZA | a P143 5. 对下面的文法GE: E:=TE E :=+E | T:=FT T :=T | F:=PF F :=*F |P (E) |a |b |（ 1）计算这个文法的每个非终结符号的FIRST 和 FOLLOW ；（ 2）证明这个文法是LL（ 1）文法；（ 3）构造它的LL （ 1）分析表并分析符号串a*b+b; 解 :（ 1）构造 FIRST 集：FIRST(E )=+, FIRST(F )=*, FIRST(E)=FIRST(T)=FIRST(
23、F)=FIRST(P) = (， a， b， FIRST(T )= ( ， a，b, ， 构造 FOLLOW 集：规则一 FOLLOW(E) FOLLOW(E)=# 规则二名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 31 页 - - - - - - - - - ) FOLLOW(E) FOLLOE(E)= )，# FIRST(E ) -FOLLOW(T) FOLLOW(T)=+ FIRST(T ) -FOLLOW(F) FOLLOW(F)= (，a， b， FIRS
24、T(F )- FOLLOW(P) FOLLOW(P)=* 规则三FOLLOW(E) FOLLOW(E ) FOLLOW(E )=#， ) FOLLOW(E) FOLLOW(T) FOLLOW(T)=，） FOLLOW(T) FOLLOW(T ) FOLLOW(T)= ，） FOLLOW(T) FOLLOW(F) FOLLOW(F)= (， )， a， b， FOLLOW(F) FOLLOW(F ) FOLLOW(F)= (，)， a，b， FOLLOW(F) FOLLOW(P) FOLLOW(P)= (， )， a， b，,* 最后结果为：FIRST(E )=+, FIRST(F )=*, F
25、IRST(E)=FIRST(T)=FIRST(F)=FIRST(P) = (， a， b， FIRST(T )= ( ， a，b, ， ) FOLLOE(E)= ), FOLLOW(E )= ， ) FOLLOW(T)=，） FOLLOW(T)= ，） FOLLOW(F)= (，)， a， b， FOLLOW(F )= (， )， a， b， FOLLOW(P)= (，)， a，b，,* （ 2）证明该文法是LL （ 1）文法：证明：对于规则E :=+E | ， T :=T | ，F :=*F |（仅有一边能推出空串）有 FIRST(+E)=+FIRST( )= ?， FIRST(T)=(,
26、a, b, FIRST( )= ?FIRST(*F )=* FIRST( )= ?， FIRST(+E)=+ FOLLOW(E )= #, )=?FIRST(T)=(, a, b, FOLLOW(T )= +, #, )=?FIRST(*F )=* FOLLOW(F )= ( ，)， a，b，=?所以该文法是LL （ 1）文法。（ 3）构造文法分析表a b + * ( ) # E E TEE TEE TEE TEEE +E E E T T FTT FTT FTTFT名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 -
27、 - - - - - - 第 12 页，共 31 页 - - - - - - - - - TTT T T T T T TT T TF F PFF PFF PFFPFFFFF F *F FFFFP P a P b P (E) P 下面分析符号串a*b+b 步骤分析栈余留输入串所用的产生式1 #E a*b+b# E TE2 #ETa*b+b# T FT3 #ETF a*b+b# FPF4 #ETFP a*b+b# P a 5 #ETFa a*b+b# 6 # ETF *b+b# F *F7 # ETF* *b+b# 8 # ETF b+b# F9 # ET b+b# TT 10 # ET b+b#
28、 T FT11 # ETF b+b# F PF12 # ETFP b+b# P b 13 #ETFb b+b# 14 #ETF +b# F15 #ET +b# T16 #E +b# E +E 17 #E+ +b# 18 #E b# E TE19 #E T b# T FT20 #E T F b# F PF21 # E T F P b# P b 22 # E T F b b# 23 # E T F # F24 # ET # T25 #E # E 26 # # 成功所以符号串a*b+b 是该文法的句子；P144 6. 对下列文法，构造相应的FIRST 和 FOLLOW ：（ 1） S aAd A B
29、C B b |C c |（ 2） A BCc | gDB B | bCDE C DaB | ca D | dD E gAf | c 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 31 页 - - - - - - - - - 解： （1）构造 FIRST 集FIRST(S)=a FIRST(B)=b ， FIRST(C)=c ， FIRST(A)=b ，c， 构造 FOLLOW集规则一 FOLLOW(S) FOLLOW(S)=# 规则二dFOLLOW(A) FOLLOE
30、(A)=d FIRST(C)- FOLLOW(B) FOLLOW(B)=c 规则三FOLLOW(A) FOLLOW(B) FOLLOW(B)=d， c FOLLOW(A) FOLLOW(C) FOLLOW(C)=d 最后结果为：FIRST(S)=a FIRST(A)=b ，c， FIRST(B)=b ， FIRST(C)=c ， FOLLOW(S)=# FOLLOW(A)=d FOLLOW(B)=d，c FOLLOW(C)=d （ 2）构造 FIRST 集规则二FIRST(A)=g, FIRST(B)=b ， , FIRST(C)= c, FIRST(D)=d ， , FIRST(E)= g
31、， c . 规则三FIRST(A)=g ， b， c, FIRST(C)=a ， c， d, FIRST(A)= a ， b， c，d， g. 构造 FOLLOW集规则一 FOLLOW(A) FOLLOW(A)=# 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 31 页 - - - - - - - - - 规则二f FOLLOW(A) FOLLOE(A)= f， c FOLLOW(C) FOLLOE(C)= c aFOLLOW(D) FOLLOE(D)= a FIRS
32、T(Cc)- FOLLOW(B) FOLLOW(B)=c， d， a FIRST(B)- FOLLOW(D) FOLLOW(D)=b， a FIRST(DE)- FOLLOW(C) FOLLOW(C)=d， g， c FIRST(E) FOLLOW(D) FOLLOW(D)=b， c， a， g 规则三FOLLOW(A) FOLLOW(B) FOLLOW(B)=a， c， d， f， # FOLLOW(A) FOLLOW(D) FOLLOW(D)=a， b， c， f， g ， FOLLOW(B) FOLLOW(E) FOLLOW(E)= a， c， d， f， # FOLLOW(C) FOL
33、LOW(B) FOLLOW(B)= a， c， d， g ， f， # FOLLOW(B) FOLLOW(E) FOLLOW(E)= a， c， d， g， f， # 最后结果为：FIRST(A)= a ， b， c，d， g, FIRST(B)=b ， , FIRST(C)=a ， c， d, FIRST(D)=d ， , FIRST(E)= g ， c , FOLLOE(A)= f， FOLLOW(B)= a， c， d， g， f， #, FOLLOW(C)=d， g， c, FOLLOW(D)=a， b， c，f， g， , FOLLOW(E)= a， c， d，g， f，#. P14
34、4 9. 设已给文法GS: S SaB | bB A Sa B Ac （ 1）将此文法改写为LL（ 1）文法（ 4）构造 LL （1）分析表解：此题消除左递归之后，构造LL（ 1）分析表存在“多重入口”问题，故采用以下方法：（ 1）改写为LL（ 1）文法：S bBaB 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 31 页 - - - - - - - - - A Sa B Ac （ 4）FIRST(S)= b , FIRST(A)=b, FIRST(B)=b, FOL
35、LOE(S)=a， , FOLLOW(A)= c, FOLLOW(B)=a， . P144 10. 证明下述文法不是简单优先文法：（ 1）S bEb E E+T | T （ 2）S bEb E F | F+T | T | i T i | (E) 证明：(1)画语法树：S b E b E + T 可以得出b=E 和 bE,因此该文法不是简单优先文法。(2)因该文法中含E=i T =i 右部两个产生式相同，故该文法不是简单优先文法. P145 11. 构造下述文法的优先关系矩阵，它们是简单优先文法吗？S M | U M iEtMe M | a U iEtS | iEtMeU E b 解：a b c
36、 # S S bBaB A A Sa B B Ac 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 31 页 - - - - - - - - - S M U E i t e a b S M U E i t e a b S 0 0 0 0 0 0 0 0 0 S 0 1 1 0 0 0 0 0 0 M 0 0 0 0 0 0 1 0 0 M 0 0 0 0 1 0 0 1 0 U 0 0 0 0 0 0 0 0 0 U 0 0 0 0 1 0 0 0 0 = E 0 0
37、0 0 0 1 0 0 0 = E 0 0 0 0 0 0 0 0 1 i 0 0 0 1 0 0 0 0 0 i 0 0 0 0 0 0 0 0 0 t 1 1 0 0 0 0 0 0 0 t 0 0 0 0 0 0 0 0 0 e 0 1 1 0 0 0 0 0 0 e 0 0 0 0 0 0 0 0 0 a 0 0 0 0 0 0 0 0 0 a 0 0 0 0 0 0 0 0 0 b 0 0 0 0 0 0 0 0 0 b 0 0 0 0 0 0 0 0 0 S M U E i t e a b S M U E i t e a b S 0 0 0 0 0 0 0 0 0 S 0 1 1
38、0 1 0 0 1 0 M 0 0 0 0 0 0 1 0 0 M 0 0 0 0 1 0 0 1 0 U 0 0 0 0 0 0 0 0 0 U 0 0 0 0 1 0 0 0 0 = E 0 0 0 0 0 1 0 0 0 = E 0 0 0 0 0 0 0 0 1 i 0 0 0 1 0 0 0 0 0 i 0 0 0 0 0 0 0 0 0 t 1 1 0 0 0 0 0 0 0 t 0 0 0 0 0 0 0 0 0 e 0 1 1 0 0 0 0 0 0 e 0 0 0 0 0 0 0 0 0 a 0 0 0 0 0 0 0 0 0 a 0 0 0 0 0 0 0 0 0 b 0
39、0 0 0 0 0 0 0 0 b 0 0 0 0 0 0 0 0 0 = S M U E i t e a b S M U E i t e a b S 0 0 0 0 0 0 0 0 0 S 0 1 1 0 0 0 0 0 0 M 0 0 0 0 0 0 0 0 0 M 0 1 0 0 0 0 0 1 0 U 0 0 0 0 0 0 0 0 0 U 1 0 1 0 0 0 0 0 0 = E 0 0 0 0 0 0 0 0 0 = E 0 0 0 0 0 0 0 0 1 i 0 0 0 0 0 0 0 0 1 i 0 0 0 0 0 0 0 0 0 t 0 1 1 0 1 0 0 1 0 t
40、0 0 0 0 0 0 0 0 0 e 0 0 0 0 1 0 0 1 0 e 0 0 0 0 0 0 0 0 0 a 0 0 0 0 0 0 0 0 0 a 0 0 0 0 0 0 0 0 0 b 0 0 0 0 0 0 0 0 0 b 0 0 0 0 0 0 0 0 0 S M U E i t e a b S M U E i t e a b S 1 1 1 0 0 0 0 1 0 S 1 1 1 0 0 0 0 1 0 M 0 1 0 0 0 0 0 1 0 M 0 1 0 0 0 0 0 1 0 U 1 1 1 0 0 0 0 0 0 U 1 1 1 0 0 0 0 1 0 = E 0
41、0 0 0 0 0 0 0 0 = E 0 0 0 0 0 0 0 0 0 i 0 0 0 0 0 0 0 0 0 i 0 0 0 0 0 0 0 0 0 t 0 0 0 0 0 0 0 0 0 t 0 0 0 0 0 0 0 0 0 e 0 0 0 0 0 0 0 0 0 e 0 0 0 0 0 0 0 0 0 a 0 0 0 0 0 0 0 0 0 a 0 0 0 0 0 0 0 0 0 B BLBL2BL+B BRB B BL+BR2B R3名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - -
42、- - 第 17 页，共 31 页 - - - - - - - - - b 0 0 0 0 0 0 0 0 0 b 0 0 0 0 0 0 0 0 0 S M U E i t e a b S M U E i t e a b S 1 1 1 0 0 0 0 1 0 S 1 0 1 0 0 0 0 0 0 M 0 1 0 0 0 0 0 1 0 M 1 1 1 0 0 0 0 0 0 U 1 1 1 0 0 0 0 1 0 U 1 0 1 0 0 0 0 0 0 = E 0 0 0 0 0 0 0 0 1 = E 0 0 0 0 0 0 0 0 0 i 0 0 0 0 0 0 0 0 0 i 0
43、0 0 0 0 0 0 0 0 t 0 0 0 0 0 0 0 0 0 t 0 0 0 0 0 0 0 0 0 e 0 0 0 0 0 0 0 0 0 e 0 0 0 0 0 0 0 0 0 a 0 0 0 0 0 0 0 0 0 a 1 1 1 0 0 0 0 0 0 b 0 0 0 0 0 0 0 0 0 b 0 0 0 1 0 0 0 0 0 S M U E i t e a b S M U E i t e a b S 1 1 1 0 1 0 0 1 0 S 0 0 0 0 0 0 0 0 0 M 0 1 0 0 1 0 0 1 0 M 0 0 0 0 0 0 1 0 0 U 0 0 1
44、0 1 0 0 0 0 = U 0 0 0 0 0 0 0 0 0 = E 0 0 0 1 0 0 0 0 1 E 0 0 0 0 0 0 0 0 0 i 0 0 0 0 1 0 0 0 0 i 0 0 0 0 0 0 0 0 0 t 0 0 0 0 0 1 0 0 0 t 0 0 0 0 0 0 0 0 0 e 0 0 0 0 0 0 1 0 0 e 0 0 0 0 0 0 0 0 0 a 0 0 0 0 0 0 0 1 0 a 0 0 0 0 0 0 1 0 0 b 0 0 0 0 0 0 0 0 1 b 0 0 0 0 0 1 0 0 0 S M U E i t e a b S M U
45、E i t e a b S 0 0 0 0 0 0 0 0 0 S 1 1 1 0 1 0 0 1 0 M 0 0 0 0 0 0 1 0 0 M 0 1 0 0 1 0 0 1 0 U 0 0 0 0 0 0 0 0 0 U 0 0 1 0 1 0 0 0 0 = = E 0 0 0 0 0 0 0 0 0 E 0 0 0 1 0 0 0 0 1 i 0 0 0 0 0 0 0 0 0 i 0 0 0 0 1 0 0 0 0 t 0 0 0 0 0 0 0 0 0 t 1 1 0 0 0 1 0 0 0 e 0 0 0 0 0 0 0 0 0 e 0 1 1 0 0 0 1 0 0 a 0
46、0 0 0 0 0 1 0 0 a 0 0 0 0 0 0 0 1 0 b 0 0 0 0 0 1 0 0 0 b 0 0 0 0 0 0 0 0 1 S M U E i t e a b S 0 0 0 0 0 0 0 0 0 M 0 0 0 0 0 0 1 0 0 U 0 0 0 0 0 0 0 0 0 = E 0 0 0 0 0 0 0 0 0 i 0 0 0 0 0 0 0 0 0 t 0 0 0 0 0 0 0 0 0 e 0 0 0 0 0 0 0 0 0 a 0 0 0 0 0 0 1 0 0 b 0 0 0 0 0 1 0 0 0 BR+B (R+)TBL*B B (R+)TB
47、BL*B (R+)TB 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 31 页 - - - - - - - - - 优先关系矩阵如下：S M U i E t e a b S M =U i = E = t = = e = = a b 其中含多重定义的表项，因而该文法不是简单优先文法。P145 12. 根据图 4.25的语法树，确定全部优先关系：(a) E=+ +=T T=* *=F (=E E=) *( +F + * i* )+ T+ F+ (b) =; BEGIN =
48、 REAL = =:= ;= :=i BEGIN BEGINREAL REALi ; ; ;i ; ; i; i:= P145 13. 利用表 4.6文法 GE的优先关系矩阵，来分析符号串#b(aa)a)a)b# 和 #(aa)a)#。(1) 步骤符号栈关系输入串规则1 # b(aa)a)a)b# 2 #b (aa)a)a)b# 3 #b( (aa)a)a)b# 4 #b( (aa)a)a)b# 5 #b( a)a)a)b# 7 #b(M = a)a)a)b# M=a 8 #b(Ma = )a)a)b# 9 #b(Ma) a)a)b# 10 #b(L a)a)b# L =Ma) 11 #b(M
49、 = a)a)b# M=(L 12 #b(Ma = )a)b# 13 #b(Ma) a)b# 14 #b(L a)b# L =Ma) 15 #b(M = a)b# M=(L 16 #b(Ma = )b# 17 #b(Ma) b# 18 #b(L b# L =Ma) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 31 页 - - - - - - - - - 19 #bM = b# M=(L 20 #bMb # 21 #Z # Z =bMb (2) 步骤符号栈关系输入串规
50、则1 # (aa)a)# 2 #( (aa)a)# 3 #( a)a)# 5 #(M = a)a)# M=a 6 #(Ma = )a)# 7 #(Ma) a)# 8 #(L a)# L =Ma) 9 #(M = a)# M=(L 10 #(Ma = )# 11 #(Ma) # 12 #(L # L =Ma) 13 #M # M=(L P146 17. 设已给文法GS: E E+T | T T T*F | F F P F | P P (E) | i （ 1）构造此文法的算符优先矩阵；解： （1） E T F P ( i * + ) E 0 0 0 0 0 0 0 0 0 0 T 0 0 0 0