Compiler-Solution for First set, Follow set and LL(1) Parsing table

Solution for First Set

To compute FIRST(X) for all grammar symbols X, apply the following rules until no more terminals or ε can be added to any FIRST set.

1. If X is a terminal, then $FIRST(X)=\{X\}$.

2. If X is a nonterminal and $X\to Y_1{Y}_2...Y_k$ is a production for some $k\ge 1$, then place $ϵ$ in $FIRST(X)$ if for some $i$, $ϵ$ is in $FIRST(Y_i)$, and $ϵ$ is in all of $FIRST(Y_1),\cdots ,FIRST(Y_{i-1})$. If $ϵ$ is in $FIRST(Y_i)$ for all $i=1,2,...,k$, then add $ϵ$ to $FIRST(X)$. For example, everything in $FIRST(Y_i)$ is surely in $FIRST(X)$. If $Y_i$ does not derive $ϵ$, then we add nothing more to $FIRST(X)$, but if $Y_i\Rightarrow ϵ$, then we add $FIRST(Y_{i+1})$, and so on.

3. If $X\to ϵ$ is a production, then add $ϵ$ to $FIRST(X)$.

Now, we can compute $FIRST$ for any string $X+1X_2\cdots X_n$as follows. Add to $FIRST(X_1{X}_2\cdots X_n)$ all non-$ϵ$ symbols of $FIRST(X_1)$. Also add the non-$ϵ$ symbols of $FIRST(X_2)$, if $ϵ$ is in $FIRST(X_1)$; the non-$ϵ$ symbols of $FIRST(X_3)$, if $ϵ$ is in $FIRST(X_1)$ and $FIRST(X_2)$; and so on. Finally, add $ϵ$ to $FIRST(X_1{X}_2\cdots Xn)$ if, for all $i$, $ϵ$ is in $FIRST(X_i)$.

Solution for Follow Set

To compute $FOLLOW(A)$ for all nonterminals $A$, apply the following rules until nothing can be added to any $FOLLOW$ set:

1. Place $ in $FOLLOW(S)$, where $S$ is the start symbol, and $ is the input right end marker.

2. If there is a production $A\to \alpha B\beta$, then everything in $FIRST(\beta )$ except $ϵ$ is in $FOLLOW(B)$.

3. If there is a production $A\to \alpha B$, or a production $A\to \alpha B\beta$, where $FIRST(\beta )$ contains $ϵ$, then everything in $FOLLOW(A)$ is in $FOLLOW(B)$.

---

1. 对于文法的开始符号$S$,置 $ 于$Follow(S)$中；
2. 若$A\to \alpha B\beta$是一个产生式，则把$First(\beta )/\{\epsilon \}$加入到$Follow(B)$中
3. 若$A\to \alpha B$是一个产生式，或$A\to \alpha B\beta$是一个产生式且$\beta \Rightarrow ϵ$ ，则把$Follow(A)$加入到$Follow(B)$中

（$\alpha$可以是终结符或者非终结符(包括$ϵ$)，β可以是终结符或者非终结符)

Solution for LL(1) Parsing Table

Suppose the parsing table $M$ is $n\times m$, where $n$ is the number of nonterminals and $m$ is the number of terminals. The table is initialized to be empty.

The entry $M[A,\alpha ]$ is a production rule that parser will apply when the current nonterminal is $A$ and the next input symbol is $\alpha$.

For each production $A\to \alpha$ in the (left factored, non-left recursive) grammar, do the following:

1. Foe each token $\alpha$ in $FIRST(\alpha )$, add the grammar production $A\to \alpha$ to $M[A,\alpha ]$.
2. If $ϵ$ is in $FIRST(\alpha )$ then, for each token $b$ in the $FOLLOW(A)$, add $A\to \alpha$ to $M[A,b]$.
3. All other entries in the table are left blank and correspond to a syntax error.

---

流程：

遍历两次 Production Rule

第一次遍历，对每个 Production Rule 检查 Rule-1

• 如果 $\alpha$ 是终结符，则把 $A\to \alpha$ 加入到 $M[A,\alpha ]$ 中
• 如果 $\alpha$ 是非终结符，则把 $A\to \alpha$ 加入到$M[A,b]\mathrm{\forall }b\in FIRST(\alpha )$

第二次遍历，对每个 Production Rule 检查 Rule-2

查看Production Rule 中所有可以产生 $ϵ$ 的非终结符 对这些非终结符把 $A\to ϵ$ 加入到 $M[A,b]\mathrm{\forall }b\in FOLLOW(A)$

---