5.1 设一NDPDA识别由下述CFG定义的语言，试给出这个NDPDA的完整形式描述。
S→SASC
S→ε
A→Aa
A→b
C→DcD
D→d
5.2 消除下列文法的左递归：
① G[A]:
A→BXCzW
B→AbBc
C→AxByCp
② G[E]:
E→ET+ET–T
T→TF*TF/F
F→(E)i
③ G[X]:
X→YaZbc
Y→ ZdXef
Z→XeYfa
④ G[A]:
A→Ba|Aa|c
B→Bb|Ab|d
5.3 设文法G[<语句>]：
<语句>→<变量>: = <表达式>|if<表达式>then<语句>
|if<表达式>then<语句>else<语句>
<变量>→i
<表达式>→<项>|<表达式>+<项>
<项>→<因子>|<项>*<因子>
<因子>→<变量>|′(′<表达式>′)′
试构造该文法的递归下降子程序。
5.4 设文法G[E]：
E→ TE
E→ + E
T→ FT
T→ T
F→ PF
F→ *F
P→ (E) a^
① 构造该文法的递归下降分析程序；
② 求该文法的每一个非终结符的FIRST集合和FOLLOW集合；
③ 构造该文法的LL（1）分析表，并判断此文法是否为LL（1）文法。
5.5 设文法G[S]：
S→ SbAaA
B→ Sb
A→ Bc
① 将此文法改写为LL（1）文法；
② 求文法的每一个非终结符的FIRST集合和FOLLOW集合；
③ 构造相应的LL（1）分析表。
5.6 设文法G[S]：
S→ aABbcd
A→ ASd
B→ SAheC
C→ SfCg
D→ aBD
① 求每一个非终结符的FOLLOW集合；
② 对每一个非终结符的产生式选择，构造FIRST集合；
③ 该文法是LL（1）文法。
5.7 设文法G[E]：
E→ AaBb
A→ cAeB
B→ bd
试画出其自上而下分析程序框图。
第五章习题参
5.1 解：NDPDA M=(Q,∑,H,δ,q0,F,Z0)
Q={q}
∑={a,b,c,d}
H={S,A,C,D,a,b,c,d}
q0=q
F={q}
Z0=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 解：
① 利用消除左递归的算法，将非终结符排序为U1=A，U2=B，U3=C，
则i=1,j=0时，对文法无影响。
i=2,j=1时，因为Ui=B→Ab，Uj=A→Bx|Cz|w
所以将B改写为B→Bxb|Czb|wb|Bc
消除产生式B的左递归：
B→CzbB′|wbB′
B′→xbB′|cB′|
i=3,j=1时，因为Ui=C→Ax，Uj=A→Bx|Cz|w
所以将C改写为C→Bxx|Czx|wx|By|Cp
j=2时，因为Ui=C→Bxx|By，Uj=B→CzbB′|wbB′
所以将产生式C改写为
C→CZbB′xx|CzbB′y|wbB′xx|wbB′y|Czx|wx|Cp
消除产生式C的左递归：
C→wbB′xxC′|wbB′yC′|wxC′
C′→zbB′xxC′|zbB′yC′|zxC′|pC′|
所以，文法消除左递归后变为
A→Bx|Cz|w
B→CzbB′|wbB′
B′→xbB′|cB′|
C→wbB′xxC′|wbB′yC′|wxC′
C′→zbB′xxC′|zbB′yC′|zxC′|pC′|
② 利用消除左递归的算法，将非终结符排序为：U1=E，U2=T，U3=F
则 i=1,j=0时，无代入。
消除产生式E的左递归：
E→T{(T+|T-)}
i=2,j=1时，无代入。
消除产生式T的左递归：
T→{F*|F/F}
i=3,j=1时，无代入，也无产生式左递归，不改写产生式。
所以，文法消除左递归后变为
E→T{(T+|T-)}
T→{F*|F/F}
F→(E)|I
③ 利用消除左递归的算法，将非终结符排序为: U1=X，U2=Y，U3=Z
则 i=1,j=0时，无代入
i=2,j=1时，因为Ui=Y→Zd|Xe|f，Uj=X→Ya|Zb|c
所以将Y改写为 Y→Zd|Yae|Zbe|ce|f
消除左递归，得到 Y→ZdY′|ZbeY′|ceY′|fY′
Y′→aeY′|
i=3,j=1时，因为Ui=Z→Xe|Yf|a，Uj=X→Ya|Zb|c
所以将Z改写为Z→Yae|Zbe|ce|Yf|a
j=2时, Ui=Z→Yae|Yf, Uj= Y→ZdY′|ZbeY′|ceY′|fY′
所以将Z改写为
Z→ZdY′ae|ZbeY′ae|ceY′ae|fY′ae|ZdY′f|ZbeY′f|ceY′f|fY′f|Zbe|ce|a
对Z消除左递归得到：
Z→ceY′aeZ′|fY′ae Z′|ceY′f Z′|fY′f Z′|ce Z′|a Z′
Z′→dY′ae Z′|beY′ae Z′| dY′f Z′|beY′f Z′|be Z′|
所以，文法消除左递归以后变为：
X→Ya|Zb|c
Y→ZdY′|ZbeY′|ceY′|fY′
Y′→aeY′|
Z→ceY′aeZ′|fY′ae Z′|ceY′f Z′|fY′f Z′|ce Z′|a Z′
Z′→dY′ae Z′|beY′ae Z′| dY′f Z′|beY′f Z′|be Z′|
④ 利用消除左递归的算法，将非终结符排序为
U1=A， U2=B
则
i=1, j=0时，由于产生式A→Ba|Aa|c存在直接左递归，将其修改为
A→BaA′|cA′
A′→aA′|
i=2,j=1时，因为Ui=B→Ab，Uj=A→BaA′|cA′，所以将产生式B修改为
B→Bb|BaA′b|cA′b|d
消除产生式B的左递归，得
B→cA′bB′|dB′
B′→bB′|aA′bB′|
所以文法消除左递归后变为
A→BaA′|cA′
A′→aA′|
B→cA′bB′|dB′
B′→bB′|aA′bB′|
5.3解：首先改写文法，使其满足递归下降分析法对文法的要求。
对产生式<语句>提取最左公共因子得
<语句>→<变量>: = <表达式>|if<表达式>then<语句><语句′>
<语句′>→else<语句>|
对产生式<表达式>、<项>消除左递归得
<表达式>→<项><表达式′>
<表达式′>→+<项><表达式′>|
<项>→<因子><项′>
<项′>→*<因子>|
得到等价的文法：
<语句>→<变量>:=<表达式>|if<表达式>then<语句><语句′>
<语句′>→else<语句>|
<变量>→i
<表达式>→<项><表达式′>
<表达式′>→+<项><表达式′>|
<项>→<因子><项′>
<项′>→*<因子>|
<因子>→<变量>|′(′<表达式>′) ′
构造该文法的递归下降分析程序如下：
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 FOLLOW(<语句′>))
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 BEGIN
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′)={+,}
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 | ^ | $ | ||
| E | E→TE′ | E→TE′ | E→TE′ | |||||
| E′ | E′→+E | E′→ | E′→ | E′→ | ||||
| T | T→FT′ | T→FT′ | T→FT′ | |||||
| T′ | T′→ | T′→ | T′→T | T′→ | T′→T | T′→T | T′→ | |
| F | F→PF′ | F→PF′ | F→PF′ | F→PF′ | ||||
| F′ | F′→ | F′→ | F′→*F | F′→ | F′→ | F′→ | F′→ | F′→ |
| P | P→(E) | P→a | P→^ |
5.5 解:
(1) 改写文法为LL(1)文法。
因为S→SbA|aA有左递归，故将其改写为
S→aA{bA}
文法变为
S→aA{bA}
B→Sb
A→Bc
这样的文法满足LL(1)文法的条件。
(2) 文法每一个非终结符号的FIRST集合为
FIRST(S)={a}
FIRST(A)={a}
FIRST(B)={a}
文法每一个非终结符号的FOLLOW集合为
因为S为开始符号，且有产生式 S→aA{bA} 和 B→Sb
所以 FOLLOW(S)={#}∪FIRST(b)={#，b}
因为 S→aA{bA}
所以 FOLLOW(A)= FOLLOW{S}∪FIRST(bA)={#，b}
因为 A→Bc
所以 FOLLOW(B)=FIRST{c}={c}
(3) 构造相应的LL(1)分析表
因为 FIRST(aA{bA})={a}
所以 M[S,a]= “ S→aA{bA}”
因为 FIRST(A)={a}
所以 M[A,a]= “ A→Bc ”
因为 FIRST(B)={a}
所以 M[B,a]= “B→Sb ”
文法G[S]的分析表如下表所示(空白处是ERROR)。
| a | b | c | # | |
| S | S→aA{bA} | |||
| A | A→Bc | |||
| B | B→Sb |
5.6 解：首先将文法压缩，得到
S→aABbcd|
A→ASd|
B→SAh|eC|
C→Sf|Cg|
(1) 求每一个非终结符号的FOLLOW集合：
因为S为开始符号，且有产生式 A→ASd，B→SAh，C→Sf
所以FOLLOW(S)={#}∪FIRST(d)∪FIRST(Ah)∪FIRST(f)={#，d，a，h，f}
因为S→aABbcd，A→ASd，B→SAh
所以FOLLOW(A)=FIRST{Bbcd}∪FIRST{Sd}∪FIRST{h}={b，a，d，h，e}
因为S→aABbcd
所以FOLLOW(B)=FIRST{bcd}={b}
因为B→eC，C→Cg
所以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) 由于存在产生式C→Sf|Cg|
FIRST(Sf)∩FIRST(Cg)={a，f}∩{a，f，g}≠
所以该文法不是LL(1)文法。
5.7 解：因为该文法无左递归，且对每一个非终结符号，其右部各候选式的首终结符号集合两两互不相交，所以可以采用自上而下分析方法而不出现回溯和无限循环。假设用READ(CH)代表读下一个单词，得到文法的自上而下分析程序框图，如下图所示。
(1) (2) (3)
文法的自上而下分析程序框图
Copyright © 2019-2025 51dongshi.net 版权所有
违法及侵权请联系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市万商天勤律师事务所王兴未律师提供法律服务
