编译原理-第5章习题解答

1、精选优质文档-倾情为你奉上专心-专注-专业第五章 习题解答5.1 设一 NDPDA 识别由下述 CFG 定义的语言，试给出这个 NDPDA 的完整形式描述。SSASCSAAaAbCDcDDd5.2 消除下列文法的左递归： GA: ABXCZW BAbBc CAxByCp GE: EET+ETT TTF*TF/F F(E)i GX: XYaZbc Y ZdXef ZXeYfa GA: ABa|Aa|cBBb|Ab|d 5.3 设文法 G： : = |ifthen|ifthenelse i|+ |* |()试构造该文法的递归下降子程序。 5.4 设文法 GE： E TE E + E T FT T

2、T F PF F *F精选优质文档-倾情为你奉上专心-专注-专业 P (E) a 构造该文法的递归下降分析程序； 求该文法的每一个非终结符的 FIRST 集合和 FOLLOW 集合； 构造该文法的 LL（1）分析表，并判断此文法是否为 LL（1）文法。 5.5 设文法 GS： S SbAaA B Sb A Bc 将此文法改写为 LL（1）文法； 求文法的每一个非终结符的 FIRST 集合和 FOLLOW 集合； 构造相应的 LL（1）分析表。 5.6 设文法 GS： S aABbcd A ASd B SAheC C SfCg D aBD 求每一个非终结符的 FOLLOW 集合； 对每一个非终结

3、符的产生式选择，构造 FIRST 集合； 该文法是 LL（1）文法。 5.7 设文法 GE： E AaBb A cAeB B bd 试画出其自上而下分析程序框图。第五章习题参考答案5.1 解：NDPDA M=(Q,H,q0,F,Z0)Q=q=a,b,c,dH=S,A,C,D,a,b,c,dq0=qF=qZ0=S: (q,S)=(q,SASC),(q,)(q,A)=(q,Aa),(q,b)(q,C)=(q,DCD)(q,D)=(q,d)(q,a,a)=(q,)(q,b,b)=(q,)(q,c,c)=(q,)(q,d,d)=(q,)精选优质文档-倾情为你奉上专心-专注-专业5.2 解： 利用消除左

4、递归的算法，将非终结符排序为 U1=A，U2=B，U3=C， 则 i=1,j=0 时，对文法无影响。 i=2,j=1 时，因为 Ui=BAb，Uj=ABx|Cz|w 所以将 B 改写为 BBxb|Czb|wb|Bc 消除产生式 B 的左递归： BCzbB|wbB BxbB|cB| i=3,j=1 时，因为 Ui=CAx，Uj=ABx|Cz|w 所以将 C 改写为 CBxx|Czx|wx|By|Cp j=2 时，因为 Ui=CBxx|By，Uj=BCzbB|wbB 所以将产生式 C 改写为 CCZbBxx|CzbBy|wbBxx|wbBy|Czx|wx|Cp 消除产生式 C 的左递归： CwbB

5、xxC|wbByC|wxCCzbBxxC|zbByC|zxC|pC| 所以，文法消除左递归后变为 ABx|Cz|w BCzbB|wbB BxbB|cB| CwbBxxC|wbByC|wxC CzbBxxC|zbByC|zxC|pC| 利用消除左递归的算法，将非终结符排序为：U1=E，U2=T，U3=F 则 i=1,j=0 时，无代入。 消除产生式 E 的左递归： ET(T+|T-) i=2,j=1 时，无代入。 消除产生式 T 的左递归： TF*|F/F i=3,j=1 时，无代入，也无产生式左递归，不改写产生式。 所以，文法消除左递归后变为 ET(T+|T-) TF*|F/F F(E)|I

6、利用消除左递归的算法，将非终结符排序为: U1=X，U2=Y，U3=Z 则 i=1,j=0 时，无代入 i=2,j=1 时，因为 Ui=YZd|Xe|f，Uj=XYa|Zb|c 所以将 Y 改写为 YZd|Yae|Zbe|ce|f 消除左递归，得到 YZdY|ZbeY|ceY|fY YaeY| i=3,j=1 时，因为 Ui=ZXe|Yf|a，Uj=XYa|Zb|c 所以将 Z 改写为 ZYae|Zbe|ce|Yf|a j=2 时, Ui=ZYae|Yf, Uj= YZdY|ZbeY|ceY|fY精选优质文档-倾情为你奉上专心-专注-专业所以将 Z 改写为 ZZdYae|ZbeYae|ceYa

7、e|fYae|ZdYf|ZbeYf|ceYf|fYf|Zbe|ce|a对 Z 消除左递归得到： ZceYaeZ|fYae Z|ceYf Z|fYf Z|ce Z|a ZZdYae Z|beYae Z| dYf Z|beYf Z|be Z| 所以，文法消除左递归以后变为：XYa|Zb|cYZdY|ZbeY|ceY|fYYaeY|ZceYaeZ|fYae Z|ceYf Z|fYf Z|ce Z|a ZZdYae Z|beYae Z| dYf Z|beYf Z|be Z| 利用消除左递归的算法，将非终结符排序为 U1=A， U2=B则i=1, j=0 时，由于产生式 ABa|Aa|c 存在直接左递归

8、，将其修改为 ABaA|cA AaA| i=2,j=1 时，因为 Ui=BAb，Uj=ABaA|cA，所以将产生式 B 修改为 BBb|BaAb|cAb|d 消除产生式 B 的左递归，得 BcAbB|dB BbB|aAbB| 所以文法消除左递归后变为ABaA|cAAaA| BcAbB|dBBbB|aAbB| 5.3 解：首先改写文法，使其满足递归下降分析法对文法的要求。对产生式提取最左公共因子得 : = |ifthen else| 对产生式、消除左递归得 +| *| 得到等价的文法： :=|ifthen else| i +| 精选优质文档-倾情为你奉上专心-专注-专业 *| |() 构造该文法

9、的递归下降分析程序如下： PROCEDURE ； BEGIN IF SYM IN FIRST() THEN BEGIN ； IF SYM=:= THEN BEGIN READAWORD； END ELSE ERROR END ELSE IF SYM=if THEN BEGIN READAWORD； ； IF SYM=then THEN BEGIN READAWORD； ； END ELSE ERROR END ELSE ERROR END； PROCEDURE ； BEGIN IF SYM=else THEN BEGIN READAWORD； END ELSE IF NOT (SYM IN F

10、OLLOW() THEN ERROR END； PROCEDURE ； BEGIN IF SYM=i/* i 表示标识符 */精选优质文档-倾情为你奉上专心-专注-专业 THEN READAWORD ELSE ERROR END； PROCEDURE ； BEGIN ； END； PROCEDURE ； BEGIN IF SYM=+ THEN BEGIN READAWORD； ； END ELSE IF NOT (SYM IN FOLLOW() THEN ERROR END； PROCEDURE ； BEGIN ； END； PROCEDURE ； BEGIN IF SYM=* THEN BE

11、GIN READAWORD； END ELSE IF NOT (SYM IN FOLLOW() THEN ERROR END； PROCEDURE ； BEGIN IF SYM=( THEN BEGIN READAWORD；精选优质文档-倾情为你奉上专心-专注-专业 ； IF (SYM=) THEN READAWORD ELSE ERROR END ELSE IF SYM IN FIRST() THEN ELSE ERROR END；5.4 解：(1)步骤和方法与 5.3 中类似，略。(2)根据 FIRST、FOLLOW 集合的求法可以得到：FIRST(E)=(,a, ; FIRST(E)=+

12、,FIRST(T)=(,a, ; FIRST(T)=(,a, ,FIRST(F)=(,a, ;FIRST(F)=*,FIRST(P)=(,a, .FOLLOW(E)=),$; FOLLOW(E)=),$;FOLLOW(T)=+,),$; FOLLOW(T)=+,),$;FOLLOW(F)=(,a,+,),$; FOLLOW(F)=(,a,+,),$;FOLLOW(P)=(,a,+,),$,*; (3)根据求得的 FIRST、FOLLOW 集合可以得到 SELECT 集合，进而构造出 LL(1)分析表如下：+*()a$EETEETEETEEE+EEEETTFTTFTTFTTTTTTTTTTTTF

13、FPFFPFFPFFPFFFFF*FFFFFFPP(E)PaP空白处为 ERROR。表中每一元素的表达式都是唯一的，因此该文法是 LL(1)文法。5.5 解:(1) 改写文法为 LL(1)文法。因为 SSbA|aA 有左递归，故将其改写为 SaAbA文法变为精选优质文档-倾情为你奉上专心-专注-专业 SaAbA BSb ABc这样的文法满足 LL(1)文法的条件。(2) 文法每一个非终结符号的 FIRST 集合为 FIRST(S)=a FIRST(A)=a FIRST(B)=a文法每一个非终结符号的 FOLLOW 集合为因为 S 为开始符号，且有产生式 SaAbA 和 BSb所以 FOLLOW

14、(S)=#FIRST(b)=#，b因为 SaAbA所以 FOLLOW(A)= FOLLOWSFIRST(bA)=#，b因为 ABc所以 FOLLOW(B)=FIRSTc=c(3) 构造相应的 LL(1)分析表因为 FIRST(aAbA)=a所以 MS,a= “ SaAbA”因为 FIRST(A)=a 所以 MA,a= “ ABc ”因为 FIRST(B)=a所以 MB,a= “BSb ”文法 GS的分析表如下表所示(空白处是 ERROR)。abc#SSaAbAAABcBBSb文法 GS的分析表5.6 解：首先将文法压缩，得到 SaABbcd| AASd| BSAh|eC| CSf|Cg| (1

15、) 求每一个非终结符号的 FOLLOW 集合：因为 S 为开始符号，且有产生式 AASd，BSAh，CSf所以 FOLLOW(S)=#FIRST(d)FIRST(Ah)FIRST(f)=#，d，a，h，f因为 SaABbcd，AASd，BSAh所以 FOLLOW(A)=FIRSTBbcdFIRSTSdFIRSTh=b，a，d，h，e因为 SaABbcd 所以 FOLLOW(B)=FIRSTbcd=b因为 BeC，CCg所以 FOLLOW(C)=FOLLOW(B)FIRST(g)=b，g(2) 对每一个非终结符号的产生式选择，构造 FIRST 集合对 S：FIRST(aABbcd)=a FIRST()=精选优质文档-倾情为你奉上专心-专注-专业对 A：FIRST(ASd)=a，d FIRST()=对 B：FIRST(SAh)=a，d，h FIRST(eC)=e FIRST()=对 C：FIRST(Sf)=a，f FIRST(Cg)=a，f，g FIRST()=(3) 由于存在产生式 CSf|Cg| FIRST(Sf)FIRST(Cg)=a，fa，f，g所以该文法不是 LL(1)文法。 5.7 解：因为该文法无左递归，且对每一个非终结符号，其右部各候选式的首终结符号集合两两互不相交，所以可以采用自上而下分析方法