# 编译原理（五）

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

$S\to aTUV\vert bV\\ T\to U\vert UU\\ U\to\varepsilon\vert bV\\ V\to\varepsilon\vert cV$
FIRST FOLLOW
$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) 分析表

FIRST FOLLOW
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）

MATCH STACK IN OUT
$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$