## 考虑以下文法，写出每个非终端符号的 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} SS\to(L) S\to a LL\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$