编译原理(五) wu-kan

考虑以下文法,写出每个非终端符号的 FIRST 集和 FOLLOW 集

\[S\to aTUV\vert bV\\ T\to U\vert UU\\ U\to\varepsilon\vert bV\\ V\to\varepsilon\vert cV\]
 FIRSTFOLLOW
$S$$a,b$$\text{\textdollar}$
$T$$\varepsilon,b$$\text{\textdollar},b,c$
$U$$\varepsilon,b$$\text{\textdollar},b,c$
$V$$\varepsilon,c$$\text{\textdollar},b,c$

考虑以下文法

\[S\to(L)\vert a\\ L\to L,S\vert S\]

消除文法的左递归

\[S\to(L)\vert a\\ L\to ST\\ T\to ,ST\vert\varepsilon\]

构造文法的 LL(1) 分析表

根据

 FIRSTFOLLOW
S$(\ a$$\text{\textdollar}\ )\ a$
L$(\ a$$)$
T$,\ \varepsilon$$)$

可得

 $($$)$$a$$,$$\text{\textdollar}$
S$S\to(L)$ $S\to a$  
L$L\to ST$ $L\to ST$  
T $T\to\varepsilon$ $T\to,ST$ 

对于句子 $(a, (a, a))$,给出语法分析的详细过程(参照课本 228 页的图 4.21)

MATCHSTACKINOUT
 $S\text{\textdollar}$$(a,(a,a))\text{\textdollar}$ 
 $(L)\text{\textdollar}$$(a,(a,a))\text{\textdollar}$$S\to(L)$
$($$L)\text{\textdollar}$$a,(a,a))\text{\textdollar}$ 
$($$ST)\text{\textdollar}$$a,(a,a))\text{\textdollar}$$L\to ST$
$($$aT)\text{\textdollar}$$a,(a,a))\text{\textdollar}$$S\to a$
$(a$$T)\text{\textdollar}$$,(a,a))\text{\textdollar}$ 
$(a$$,ST)\text{\textdollar}$$,(a,a))\text{\textdollar}$$T\to,ST$
$(a,$$ST)\text{\textdollar}$$(a,a))\text{\textdollar}$ 
$(a,$$(L)T)\text{\textdollar}$$(a,a))\text{\textdollar}$$S\to L$
$(a,($$L)T)\text{\textdollar}$$a,a))\text{\textdollar}$ 
$(a,($$ST)T)\text{\textdollar}$$a,a))\text{\textdollar}$$L\to ST$
$(a,($$aT)T)\text{\textdollar}$$a,a))\text{\textdollar}$$S\to a$
$(a,(a$$T)T)\text{\textdollar}$$,a))\text{\textdollar}$ 
$(a,(a$$,ST)T)\text{\textdollar}$$,a))\text{\textdollar}$$T\to,ST$
$(a,(a,$$ST)T)\text{\textdollar}$$a))\text{\textdollar}$ 
$(a,(a,$$aT)T)\text{\textdollar}$$a))\text{\textdollar}$$S\to a$
$(a,(a,a$$T)T)\text{\textdollar}$$))\text{\textdollar}$ 
$(a,(a,a$$)T)\text{\textdollar}$$))\text{\textdollar}$$T\to\varepsilon$
$(a,(a,a)$$T)\text{\textdollar}$$)\text{\textdollar}$ 
$(a,(a,a)$$)\text{\textdollar}$$)\text{\textdollar}$$T\to\varepsilon$
$(a,(a,a))$$\text{\textdollar}$$\text{\textdollar}$ 

考虑以下文法,这一文法是否是 LL(1) 文法?给出理由

\[S\to aSbS\vert bSaS\vert\varepsilon\]

不是。因为 $\text{FIRST}(S)={a,b,\varepsilon},\text{FOLLOW}(S)={\text{\textdollar},a,b}$,而且 $S\to\varepsilon$ 但 $\text{FIRST}(S)\cap\text{FOLLOW}(S)\neq\emptyset$,不符合 LL(1) 文法的性质。