CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
考虑以下文法，写出每个非终端符号的 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\]不是。因为 $\text{FIRST}(S)=\lbrace a,b,\varepsilon\rbrace ,\text{FOLLOW}(S)=\lbrace \text{\textdollar},a,b\rbrace $，而且 $S\to\varepsilon$ 但 $\text{FIRST}(S)\cap\text{FOLLOW}(S)\neq\emptyset$，不符合 LL(1) 文法的性质。