post on
26 May 2020
about
2131words
require
8min
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) 文法的性质。