构造FIRST和FOLLOW的大白话网站

第四章

1

考虑文法G1G_1G1​:
$$\begin{gathered} S\to a|\wedge |(T) \\ T\to T,S|S \end{gathered}$$

先复习左递归如何消除 原书p69页

1. 类似于$P\to Pa|b$的形式，可以改写成

• P→bP′P\\rightarrow bP^{'}P→bP′
• P′→aP′∣ϵP^{'}\\rightarrow aP^{'}|\\epsilonP′→aP′∣ϵ

2. 提公因子 P→Pa1∣...∣Pam∣b1∣...bn∣P\\rightarrow Pa_1|...|Pa_m|b_1|...b_n|P→Pa1​∣...∣Pam​∣b1​∣...bn​∣ 转换为

• P→b1P′∣...∣bnP′∣P\\rightarrow b_1P^{'}|...|b_nP^{'}|P→b1​P′∣...∣bn​P′∣
• P′→a1P′∣...∣amP′∣ϵP^{'}\\rightarrow a_1P^{'}|...|a_mP^{'}|\\epsilonP′→a1​P′∣...∣am​P′∣ϵ

(1) 消除G1G_1G1​左递归。并对每个非终结符，写出不带回溯的递归子程序

1. 消除左递归

分析：不难发现，左递归只在第二条地推中出现，应修改第二条

1. 将b后面塞上一个新非终结符，删去原有的左递归部分
2. 新非终结符可以递推出 左递归右半部分 + 新非终结符

$$\begin{gathered} S\to a|\wedge |(T) \\ T\to SA \\ A\to ,SA|ϵ \end{gathered}$$

2.递归下降子程序

详见原书 p74

procedure S;
beginif (sym = 'a') or (sym = '^')then advancce;else if sym = '('then beginadvance; Tif sym = ')'then advanceelse errorendelse error;
endprocedure T;
beginS;A
endprocedure A;
beginif sym = ','then beginadvance;S;Aendelse error
end

根据74页的定义

advance ：  输入串指示器IP 指向下一个输入符号
sym :       IP当前所指的输入符号
error :     出错程序

根据原文

(2) 改写后的文法是否为LL(1)的，给出预测分析表

知识点

证明文法为LL(1)

$$预测分析表M不含多重定义入口\iff 文法为LL(1)$$

构造分析表M算法

首先需要构造FISRT集

• 若 X∈VTX\\in V_TX∈VT​，则 FIRST(X)={X}FIRST(X) = \\{X\\}FIRST(X)={X}
• 若X∈VN∧X→a...X\\in V_N \\land X\\rightarrow a...X∈VN​∧X→a..., 把a放入 $FIRST(X)$中
  • 若$X\to ϵ$， $ϵ$也放入$FIRST(X)$中
• 若X→Y...∧Y∈VNX\\rightarrow Y... \\land Y\\in V_NX→Y...∧Y∈VN​， 将$FIRST(Y)-ϵ$ 的元素加入 $FIRST(X)$中
  • 若X→Y1Y2...Yk...∧Y1,...,Yi−1非终结符∧对于任何j(1≤j≤i−1),FIRST(Yj)含有ϵX\\rightarrow Y_1Y_2...Y_k... \\land Y_1,...,Y_{i-1}非终结符\\land 对于任何j(1\\le j \\le i - 1), FIRST(Y_j)含有\\epsilonX→Y1​Y2​...Yk​...∧Y1​,...,Yi−1​非终结符∧对于任何j(1≤j≤i−1),FIRST(Yj​)含有ϵ, 则把FIRST(Yi)−ϵFIRST(Y_i)-\\epsilonFIRST(Yi​)−ϵ加入$FIRST(X)中$
  • 特别的，若所有的FIRST(Yj)都含有ϵ,j=1,2,...,kFIRST(Y_j)都含有\\epsilon, j = 1,2,..., kFIRST(Yj​)都含有ϵ,j=1,2,...,k， 把$ϵ$ 加入$FIRST(X)$中

然后构造FOLLOW集

• 对于文法开始符号$S$，放置#到 $FOLLOW(S)$ 中
• 若$A\to \alpha B\beta$，   把$FIRST(\beta )-ϵ$ 放入 $FOLLOW(B)$
• $A\to \alpha B$，    把$FOLLOW(A)$放入$FOLLOW(B)$
• $A\to \alpha B\beta \wedge \beta \Rightarrow ϵ$ (也就是说$ϵ\in FIRST(\beta )$)，   把$FOLLOW(A)$放入$FOLLOW(B)$

最后构造M

1. 对文法 $G$ 产生式 $A\to \alpha$ 进行(2)(3)操作
2. 终结符 $a\in FIRST(\alpha )$ 加入 $M[A,a]$中
3. 若$ϵ\in FIRST(\alpha )$，则对任何$b\in FOLLOW(A)$，把$A\to \alpha$ 放入 $M[A,b]$中
4. 没有定义则出错

解题过程

① 构造FIRST

首先考虑

$$S\to a|\wedge |(T)$$

不难发现，a,^,(都出现在了产生式右端的最左端，
所以有

FIRST(S)={a,∧,(}FIRST(S) = \\{a,\\land, (\\}FIRST(S)={a,∧,(}

考虑

$$T\to SA$$

根据构造FOLLOW集的第四种情况，需要将$FIRST(S)-ϵ所有元素放入FIRST(T)中$

FIRST(T)={a,∧,(}FIRST(T) = \\{a,\\land, (\\}FIRST(T)={a,∧,(}

考虑

$$A\to ,SA|ϵ$$

FIRST(A)={，,ϵ}FIRST(A) = \\{， , \\epsilon\\}FIRST(A)={，,ϵ}

② 构造FOLLOW
我们已经有了
FIRST(S)={a,∧,(}FIRST(S) = \\{a,\\land, (\\}FIRST(S)={a,∧,(}
FIRST(T)={a,∧,(}FIRST(T) = \\{a,\\land, (\\}FIRST(T)={a,∧,(}
FIRST(A)={，,ϵ}FIRST(A) = \\{， , \\epsilon\\}FIRST(A)={，,ϵ}

首先考虑

$$S\to a|\wedge |(T)$$

• 根据规则1，需要存#进 $FOLLOW(S)$
• 根据规则2，需要将$FIRST(）)-ϵ$的元素放进去 $FOLLOW(T)$

于是第一步我们有

FOLLOW(S)={#}FOLLOW(T)={)}FOLLOW(S) = \\{\\#\\}\\\\ FOLLOW(T) = \\{)\\} FOLLOW(S)={#}FOLLOW(T)={)}

考虑

$$T\to SA$$

• 根据规则3，需要将$FOLLOW(T)$的元素放进去 $FOLLOW(A)$

得到

FOLLOW(S)={#}FOLLOW(T)={)}FOLLOW(A)={)}FOLLOW(S) = \\{\\#\\}\\\\ FOLLOW(T) = \\{)\\}\\\\ FOLLOW(A) = \\{)\\} FOLLOW(S)={#}FOLLOW(T)={)}FOLLOW(A)={)}

考虑

$$A\to ,SA|ϵ$$

• 根据规则2，需要将$FIRST(A)-ϵ$的元素放进去 $FOLLOW(S)$
• 根据规则4(A可以推导出$ϵ$)，需要将$FOLLOW(A)$的元素放进去 $FOLLOW(S)$

得到

FOLLOW(S)={，,),#}FOLLOW(T)={)}FOLLOW(A)={)}FOLLOW(S) = \\{，, ),\\#\\}\\\\ FOLLOW(T) = \\{)\\}\\\\ FOLLOW(A) = \\{)\\} FOLLOW(S)={，,),#}FOLLOW(T)={)}FOLLOW(A)={)}

③ 构造M

$$\begin{gathered} S\to a|\wedge |(T) \\ T\to SA \\ A\to ,SA|ϵ \end{gathered}$$

FIRST(S)={a,∧,(}FIRST(T)={a,∧,(}FIRST(A)={，,ϵ}FOLLOW(S)={，,),#}FOLLOW(T)={)}FOLLOW(A)={)}FIRST(S) = \\{a,\\land, (\\}\\quad FIRST(T) = \\{a,\\land, (\\} \\quad FIRST(A) = \\{， , \\epsilon\\} \\\\ FOLLOW(S) = \\{，, ),\\#\\}\\quad FOLLOW(T) = \\{)\\}\\quad FOLLOW(A) = \\{)\\}FIRST(S)={a,∧,(}FIRST(T)={a,∧,(}FIRST(A)={，,ϵ}FOLLOW(S)={，,),#}FOLLOW(T)={)}FOLLOW(A)={)}

对这三个生成式套用步骤2

首先按照 $FIRST(S)$ 我们有

	$a$	$\wedge$	$($	$)$	$,$	$\#$
$S$	$S\to a$	$S\to \wedge$	$S\to (T)$

然后按照 $FIRST(T)$ 我们有

	$a$	$\wedge$	$($	$)$	$,$	$\#$
$S$	$S\to a$	$S\to \wedge$	$S\to (T)$
$T$	$T\to SA$	$T\to SA$	$T\to SA$

根据$FIRST(A)$

	$a$	$\wedge$	$($	$)$	$,$	$\#$
$S$	$S\to a$	$S\to \wedge$	$S\to (T)$
$T$	$T\to SA$	$T\to SA$	$T\to SA$
$A$				$A\to ϵ$	$A\to ,SA$

对这三个生成式套用步骤3，发现满足步骤3的只有$A\to ϵ$ （$A\to ,SA$这个生成式中，$,SA$无法变成$ϵ$）

• $ϵ\in FIRST(A)$,对$\forall b\in FOLLOW(A)$将 $A\to \alpha$ 放入M[A，b]中

不难发现FOLLOW(A)只有右括号 }， 然后重复填入$A\to ϵ$

最终的M没有多重定义入口
所以满足LL(1)

2

考虑文法G:

E→TE′E′→+E∣ϵT→FT′T′→T∣ϵF→PF′F′→∗F′∣ϵP→(E)∣a∣b∣∧E\\rightarrow TE^{'}\\\\E^{'}\\rightarrow +E|\\epsilon\\\\T\\rightarrow FT^{'}\\\\ T^{'}\\rightarrow T|\\epsilon\\\\F\\rightarrow PF^{'}\\\\F^{'}\\rightarrow *F^{'}|\\epsilon\\\\P\\rightarrow (E)|a|b|\\land E→TE′E′→+E∣ϵT→FT′T′→T∣ϵF→PF′F′→∗F′∣ϵP→(E)∣a∣b∣∧

(1) 计算文法G非终结符的FIRST和FOLLOW

计算FIRST

① 首先根据规则1： 若右边第一个符号是终结符或 ε ，则直接将其加入 FIRST（X）构造出最初始的FIRST

FIRST(E)FIRST(E′)={+,ϵ}FIRST(T)FIRST(T′)={ϵ}FIRST(F)FIRST(F′)={∗,ϵ}FIRST(P)={(,a,b,∧}FIRST(E)\\quad FIRST(E^{'}) = \\{+,\\epsilon\\} \\quad FIRST(T) \\quad FIRST(T^{'}) = \\{\\epsilon\\} \\\\ FIRST(F) \\quad FIRST(F^{'}) = \\{*,\\epsilon\\} \\quad FIRST(P) = \\{ (, a, b, \\land \\} FIRST(E)FIRST(E′)={+,ϵ}FIRST(T)FIRST(T′)={ϵ}FIRST(F)FIRST(F′)={∗,ϵ}FIRST(P)={(,a,b,∧}

② 考虑规则2，右边第一个符号是非终结符，则将其 FIRST 集的的非 ε 元素加入 FIRST（X）

FIRST(E)={(,a,b,∧}FIRST(E′)={+,ϵ}FIRST(T)={(,a,b,∧}FIRST(T′)={(,a,b,∧,ϵ}FIRST(F)={(,a,b,∧}FIRST(F′)={∗,ϵ}FIRST(P)={(,a,b,∧}FIRST(E) = \\{ (, a, b, \\land \\}\\quad FIRST(E^{'}) = \\{+,\\epsilon\\} \\quad \\\\ FIRST(T) = \\{ (, a, b, \\land \\} \\quad FIRST(T^{'}) = \\{(, a, b, \\land, \\epsilon\\} \\\\ FIRST(F) = \\{ (, a, b, \\land \\} \\quad FIRST(F^{'}) = \\{*,\\epsilon\\} \\quad FIRST(P) = \\{ (, a, b, \\land \\} FIRST(E)={(,a,b,∧}FIRST(E′)={+,ϵ}FIRST(T)={(,a,b,∧}FIRST(T′)={(,a,b,∧,ϵ}FIRST(F)={(,a,b,∧}FIRST(F′)={∗,ϵ}FIRST(P)={(,a,b,∧}

再次检查规则1，2，3发现无法再使任意一个FIRST集合产生变化，故构造FOLLOW集合

FOLLOW集

首先使用规则1 若A->aBb是一条规则，则把FIRST(b)中的非ε元素加到FOLLOW(B)中,其中#为终止符，默认放在起始符的FOLLOW集合中

$$FOLLOW(E) = {#,)}\\quad
FOLLOW(E^{‘}) = {} \\quad
FOLLOW(T) ={+} \\quad
FOLLOW(T^{’}) = {} \\

FOLLOW(F) = {(, a, b, \\land} \\quad
FOLLOW(F^{'}) = {} \\quad
FOLLOW§ = { * }
$$

使用规则2 若A->aB或A->aBb是一条规则且b=>ε,则把FOLLOW(A)加到FOLLOW(B)中;

FOLLOW(E)={#,)}FOLLOW(E′)={#,)}FOLLOW(T)={#,),+}FOLLOW(T′)={#,),+}FOLLOW(F)={(,a,b,∧,#,),+}FOLLOW(F′)={(,a,b,∧,#,),+}FOLLOW(P)={(,a,b,∧,#,),+,∗}FOLLOW(E) = \\{\\#,)\\}\\quad FOLLOW(E^{'}) = \\{\\#,)\\} \\quad FOLLOW(T) =\\{\\#,),+\\} \\quad FOLLOW(T^{'}) = \\{\\#,),+\\} \\\\ FOLLOW(F) = \\{(, a, b, \\land, \\#,),+\\} \\quad FOLLOW(F^{'}) = \\{(, a, b, \\land, \\#,),+\\} \\quad FOLLOW(P) = \\{ (, a, b, \\land, \\#,),+, * \\} FOLLOW(E)={#,)}FOLLOW(E′)={#,)}FOLLOW(T)={#,),+}FOLLOW(T′)={#,),+}FOLLOW(F)={(,a,b,∧,#,),+}FOLLOW(F′)={(,a,b,∧,#,),+}FOLLOW(P)={(,a,b,∧,#,),+,∗}

(2) 证明文法为LL(1)

除了直接构造矩阵M看是否有多重入口，还可以使用p73的证明

1. 文法无左递归
2. 对文法非终结符A产生的候选符集合两两不相交 对于A→a1∣...∣anFirst(ai)∩First(aj)=∅对于A\\rightarrow a_1|...|a_n\\quad First(a_i)\\cap First(a_j) = \\empty对于A→a1​∣...∣an​First(ai​)∩First(aj​)=∅
3. 文法非终结符A，若他候选符集包含$ϵ$ 则 $FIRST(A)\cap FOLLOW(A)=\varnothing$

① 不难发现，该文法无左递归

② 有多个候选符的产生式为 第二，第四，第六，第七行

不难发现
注意，你要求的是一整个串，比如+E,就得求FIRST(+E)，而 +E的首字符只有+

FIRST(+E)={+}∩FIRST(ϵ)=∅FIRST(T)={(,a,b,∧}∩FIRST(ϵ)=∅FIRST(∗F′)={∗}∩FIRST(ϵ)=∅FIRST((E))={(},与a,b,∧构成的FIRST集两两不相交FIRST(+E) = \\{+\\} \\cap FIRST(\\epsilon) = \\empty\\\\ FIRST(T) = \\{ (, a, b, \\land\\}\\cap FIRST(\\epsilon) = \\empty\\\\ FIRST(*F^{'}) = \\{*\\} \\cap FIRST(\\epsilon) = \\empty \\\\ FIRST((E)) = \\{ (\\},与a,b,\\land构成的FIRST集两两不相交 FIRST(+E)={+}∩FIRST(ϵ)=∅FIRST(T)={(,a,b,∧}∩FIRST(ϵ)=∅FIRST(∗F′)={∗}∩FIRST(ϵ)=∅FIRST((E))={(},与a,b,∧构成的FIRST集两两不相交

③
产生式含$ϵ$的为第二，第四，第六行。显然

FIRST(E′)∩FOLLOW(E′)=∅FIRST(T′)∩FOLLOW(T′)=∅FIRST(F′)∩FOLLOW(F′)=∅FIRST(E^{'}) \\cap FOLLOW (E^{'}) = \\empty \\\\ FIRST(T^{'}) \\cap FOLLOW (T^{'}) = \\empty \\\\ FIRST(F^{'}) \\cap FOLLOW (F^{'}) = \\empty FIRST(E′)∩FOLLOW(E′)=∅FIRST(T′)∩FOLLOW(T′)=∅FIRST(F′)∩FOLLOW(F′)=∅

综上，其为LL(1)文法

(3) 构造它的预测分析表

构造M

1. 对文法 $G$ 产生式 $A\to \alpha$ 进行(2)(3)操作
2. 终结符 $a\in FIRST(\alpha )$ 加入 $M[A,a]$中
3. 若$ϵ\in FIRST(\alpha )$，则对任何$b\in FOLLOW(A)$，把$A\to \alpha$ 放入 $M[A,b]$中
4. 没有定义则出错

对 E→TE′E\\rightarrow TE^{'}E→TE′ , 我们根据规则2

	+	*	（	）	a	b	⋀	#
E			E→TE′E\\rightarrow TE^{'}E→TE′		E→TE′E\\rightarrow TE^{'}E→TE′	E→TE′E\\rightarrow TE^{'}E→TE′	E→TE′E\\rightarrow TE^{'}E→TE′

对 E′→+E∣ϵE^{'}\\rightarrow +E|\\epsilonE′→+E∣ϵ , 我们根据规则2

	+	*	（	）	a	b	⋀	#
E			E→TE′E\\rightarrow TE^{'}E→TE′		E→TE′E\\rightarrow TE^{'}E→TE′	E→TE′E\\rightarrow TE^{'}E→TE′	E→TE′E\\rightarrow TE^{'}E→TE′
E’	E′→+EE^{'}\\rightarrow +EE′→+E

根据规则3

	+	*	（	）	a	b	⋀	#
E			E→TE′E\\rightarrow TE^{'}E→TE′		E→TE′E\\rightarrow TE^{'}E→TE′	E→TE′E\\rightarrow TE^{'}E→TE′	E→TE′E\\rightarrow TE^{'}E→TE′
E’	E′→+EE^{'}\\rightarrow +EE′→+E			E′→ϵE^{'}\\rightarrow \\epsilonE′→ϵ				E′→ϵE^{'}\\rightarrow \\epsilonE′→ϵ

最终得到如下分析表

	+	*	（	）	a	b	⋀	#
E			E→TE′E\\rightarrow TE^{'}E→TE′		E→TE′E\\rightarrow TE^{'}E→TE′	E→TE′E\\rightarrow TE^{'}E→TE′	E→TE′E\\rightarrow TE^{'}E→TE′
E’	E′→+EE^{'}\\rightarrow +EE′→+E			E′→ϵE^{'}\\rightarrow \\epsilonE′→ϵ				E′→ϵE^{'}\\rightarrow \\epsilonE′→ϵ
T			T→FT′T\\rightarrow FT^{'}T→FT′		T→FT′T\\rightarrow FT^{'}T→FT′	T→FT′T\\rightarrow FT^{'}T→FT′	T→FT′T\\rightarrow FT^{'}T→FT′
T’	T′→ϵT^{'}\\rightarrow \\epsilonT′→ϵ		T′→TT^{'}\\rightarrow TT′→T	T′→ϵT^{'}\\rightarrow \\epsilonT′→ϵ	T′→TT^{'}\\rightarrow TT′→T	T′→TT^{'}\\rightarrow TT′→T	T′→TT^{'}\\rightarrow TT′→T	T′→ϵT^{'}\\rightarrow \\epsilonT′→ϵ
F			F→PF′F\\rightarrow PF^{'}F→PF′		F→PF′F\\rightarrow PF^{'}F→PF′	F→PF′F\\rightarrow PF^{'}F→PF′	F→PF′F\\rightarrow PF^{'}F→PF′
F’	F′→ϵF^{'}\\rightarrow \\epsilonF′→ϵ	F′→∗F′F^{'}\\rightarrow *F^{'}F′→∗F′	F′→ϵF^{'}\\rightarrow \\epsilonF′→ϵ	F′→ϵF^{'}\\rightarrow \\epsilonF′→ϵ	F′→ϵF^{'}\\rightarrow \\epsilonF′→ϵ	F′→ϵF^{'}\\rightarrow \\epsilonF′→ϵ	F′→ϵF^{'}\\rightarrow \\epsilonF′→ϵ	F′→ϵF^{'}\\rightarrow \\epsilonF′→ϵ
P			$P\to (E)$		$P\to a$	$P\to b$	$P\to \wedge$

(4) 构造它的递归下降分析程序

procedure E:
beginif sym = '(' or sym = 'a'or sym = 'B'or sym = '^'then beginT;E’endelseerror
endprocedure E’:
beginif sym = '+'then beginadvance;Eendelse if sym <> ')' and sym <> '#'then error
endprocedure T:
beginif sym = '(' or sym = 'a'or sym = 'B'or sym = '^'then beginF;T’endelseerror
endprocedure T’:
beginif sym = '(' or sym = 'a'or sym = 'B'or sym = '^'then beginT;endelse if sym = '*'error
endprocedure F:
beginif sym = '(' or sym = 'a'or sym = 'B'or sym = '^'then beginP;F’endelseerror
endprocedure F’:
beginif sym = '*' then beginadvance;F’end
endprocedure P:
beginif  sym = 'a'or sym = 'B'or sym = '^'then advanceelse if sym = '(' then beginadvance;E;if sym = ')'then advanceelseerrorendelseerror
end

3

下面文法中那些是LL(1)文法？

(1)

$$\begin{gathered} S\to ABc \\ A\to a|ϵ \\ B\to b|ϵ \end{gathered}$$

① 不含左递归

② 显然第二第三行的候选终结首符集两两不相交

③ 由于第二第三行推导式右边含 $ϵ$

先求出相关的FIRST和FOLLOW集合
FIRST(S)={a,b,c}FOLLOW(S)={#}FIRST(A)={a,ϵ}FOLLOW(A)={b,c}FIRST(B)={b,ϵ}FOLLOW(B)={c}FIRST(S) = \\{a,b,c\\} \\quad FOLLOW(S) =\\{\\# \\}\\\\ FIRST(A) = \\{a, \\epsilon\\}\\quad FOLLOW(A) =\\{b,c\\}\\\\ FIRST(B) = \\{b, \\epsilon\\}\\quad FOLLOW(B) =\\{c \\}\\\\ FIRST(S)={a,b,c}FOLLOW(S)={#}FIRST(A)={a,ϵ}FOLLOW(A)={b,c}FIRST(B)={b,ϵ}FOLLOW(B)={c}

不难发现A，B对应的FIRST集与FOLLOW集合相交为空集

满足LL(1)

(2)

$$\begin{gathered} S\to Ab \\ A\to a|B|ϵ \\ B\to b|ϵ \end{gathered}$$

① 不含左递归

FIRST(S)={a,b}FOLLOW(S)={#}FIRST(A)={a,b,ϵ}FOLLOW(A)={b}FIRST(B)={b,ϵ}FOLLOW(B)={b}FIRST(S) = \\{a,b\\} \\quad FOLLOW(S) =\\{\\# \\}\\\\ FIRST(A) = \\{a, b,\\epsilon\\}\\quad FOLLOW(A) =\\{b\\}\\\\ FIRST(B) = \\{b, \\epsilon\\}\\quad FOLLOW(B) =\\{ b\\}\\\\ FIRST(S)={a,b}FOLLOW(S)={#}FIRST(A)={a,b,ϵ}FOLLOW(A)={b}FIRST(B)={b,ϵ}FOLLOW(B)={b}

由于A->B，参考规则2(因为B后面没字符串了，为空船)，需要将follow(A)传递给follow(B)

② 对于第二行导出式子，有FIRST(B)∩FIRST(ϵ)={ϵ}FIRST(B)\\cap FIRST(\\epsilon) = \\{\\epsilon\\}FIRST(B)∩FIRST(ϵ)={ϵ}

不符合LL(1)

(3)

$$\begin{gathered} S\to ABBA \\ A\to a|ϵ \\ B\to b|ϵ \end{gathered}$$

① 不含左递归

FIRST(S)={a,b,ϵ}FOLLOW(S)={#}FIRST(A)={a,ϵ}FOLLOW(A)={b,#}FIRST(B)={a,b,ϵ}FOLLOW(B)={a,b,#}FIRST(S) = \\{a,b,\\epsilon\\} \\quad FOLLOW(S) =\\{\\# \\}\\\\ FIRST(A) = \\{a,\\epsilon\\}\\quad FOLLOW(A) =\\{b,\\#\\}\\\\ FIRST(B) = \\{a, b,\\epsilon\\}\\quad FOLLOW(B) =\\{a, b, \\#\\}\\\\ FIRST(S)={a,b,ϵ}FOLLOW(S)={#}FIRST(A)={a,ϵ}FOLLOW(A)={b,#}FIRST(B)={a,b,ϵ}FOLLOW(B)={a,b,#}

② 对于第二行和第三行，他们的候选终结首符集两两不相交

③：FIRST(B)∩FOLLOW(B)={a,b}≠∅FIRST(B)\\cap FOLLOW(B) = \\{a,b\\} \\neq \\emptyFIRST(B)∩FOLLOW(B)={a,b}=∅

不满足LL(1)

(4)

$$\begin{gathered} S\to aSe|B \\ B\to bBe|C \\ C\to cCe|d \end{gathered}$$

① 不含左递归

FIRST(S)={a,b,c,d}FOLLOW(S)={e,#}FIRST(B)={b,c,d}FOLLOW(B)={e,#}FIRST(C)={c,d}FOLLOW(C)={e,#}FIRST(S) = \\{a,b,c,d\\} \\quad FOLLOW(S) =\\{e,\\#\\}\\\\ FIRST(B) = \\{b,c,d\\}\\quad FOLLOW(B) =\\{e,\\#\\}\\\\ FIRST(C) = \\{c,d\\}\\quad FOLLOW(C) =\\{e,\\#\\}\\\\ FIRST(S)={a,b,c,d}FOLLOW(S)={e,#}FIRST(B)={b,c,d}FOLLOW(B)={e,#}FIRST(C)={c,d}FOLLOW(C)={e,#}

不难发现，均满足条件②和条件③

符合LL(1)文法

4

对下面的文法

$$\begin{gathered} Expr\to -Expr \\ Expr\to (Expr)|VarExprTail \\ ExprTail\to -Expr|ϵ \\ Var\to idVarTail \\ VarTail\to (Expr)|ϵ \end{gathered}$$

构造LL(1)分析表

重命名一下，太花里胡哨了
$$\begin{gathered} E\to -E \\ E\to (E)|VD \\ D\to -E|ϵ \\ V\to idC \\ C\to (E)|ϵ \end{gathered}$$

构造FIRST和FOLLOW
FIRST(E)={−,(,id}FOLLOW(E)={#,)}FIRST(V)={id}FOLLOW(V)={−,#,)}FIRST(D)={−,ϵ}FOLLOW(D)={#,)}FIRST(C)={(,ϵ}FOLLOW(C)={−,#,)}FIRST(E) = \\{-,(,id\\} \\quad FOLLOW(E) = \\{\\# ,)\\}\\\\ FIRST(V) = \\{id\\} \\quad FOLLOW(V) = \\{-,\\# ,)\\}\\\\ FIRST(D) = \\{-,\\epsilon\\} \\quad FOLLOW(D) = \\{\\# ,)\\}\\\\ FIRST(C) = \\{(,\\epsilon\\} \\quad FOLLOW(C) = \\{-,\\# ,)\\}\\\\ FIRST(E)={−,(,id}FOLLOW(E)={#,)}FIRST(V)={id}FOLLOW(V)={−,#,)}FIRST(D)={−,ϵ}FOLLOW(D)={#,)}FIRST(C)={(,ϵ}FOLLOW(C)={−,#,)}

	-	id	(	)	#
E	$E\to -E$	$E\to VD$	$E\to (E)$
D	$D\to -E$			$D\to ϵ$	$D\to ϵ$
V		$V\to idC$
C	$C\to ϵ$		$C\to (E)$	$C\to ϵ$	$C\to ϵ$

给出句子 id--id((id))的分析过程

分析栈	输入	产生式
#E	id–id((id)) #
#DV	id–id((id)) #	E→VD
#DCid	id–id((id)) #	V→idC
#DC	–id((id)) #
#D	–id((id)) #	C→ε
#E-	–id((id)) #	D→-E
#E	-id((id)) #
#E-	-id((id)) #	E→-E
#E	id((id)) #
#DV	id((id)) #	E→VD
#DCid	id((id)) #	V→idC
#DC	((id)) #
#D)E(	((id)) #	C→(E)
#D)E	(id)) #
#D))E(	(id)) #	E→(E)
#D))E	id)) #
#D))DV	id)) #	E→VD
#D))DCid	id)) #	V→idC
#D))DC	)) #
#D))D	)) #	C→ϵ
#D))	)) #	D→ϵ
#D)	) #
#D	#
#	#	D→ϵ

ps:麻了，这作业花了我六七个小时

藏瓷网