### Syntax analysis from the Dragoon Book

by Forrest Sheng Bao http://fsbao.net

I got quite confused about my compiler class this semester. The textbook we used is the famous "Dragoon Book" - Compilers, Principles, Techniques and Tools, by Alfred V. Aho, Monica S. Lam, Ravi Sethi and Jeffrey D. Ullman. Now I have figured everything out regarding syntax analysis. So I decide to write the algorithms in my way.

### How to eliminate left recursion

Replace the rule $B\to B{P}_{1}|\cdots |B{P}_{m}|{P}_{m+1}|\cdots |{P}_{n}$

by $B\to {P}_{m+1}{B}^{\prime }|\cdots |{P}_{n}{B}^{\prime }$ and${B}^{\prime }\to {P}_{1}{B}^{\prime }|\cdots |{P}_{m}{B}^{\prime }|ϵ$

### How to eliminate common prefixes

Replace the rule $A\to \alpha {\beta }_{1}|\alpha {\beta }_{2}|\cdots |\alpha {\beta }_{n}|{\mathrm{\Sigma }}_{1}|\cdots |{\mathrm{\Sigma }}_{n+m}$

by $A\to \alpha {A}^{\prime }|{\mathrm{\Sigma }}_{1}|\cdots |{\mathrm{\Sigma }}_{n+m}$

and ${A}^{\prime }\to {\beta }_{1}|\cdots |{\beta }_{n}$

### Top-down parsing

To rule $X\to {Y}_{1}{Y}_{2}\cdots {Y}_{n}$

#### First(X):

1. $\text{First}\left({Y}_{1}\right)\subseteq \text{First(X)}$
2. If ${Y}_{1}\cdots {Y}_{k}⇒*ϵ$ , then $\text{First}\left({Y}_{k+1}\right)\subseteq \text{First(X)}$
3. If ${Y}_{i}\to ϵ,\forall i$ , then $ϵ\in \text{First}\left(X\right)$

#### Follow(X):

1. \$ is contained in Follow(X)
2. If $\forall A\to \alpha S\beta$, then $\text{First}\left(\beta \right)/ϵ\subseteq \text{Follow}\left(S\right)$
3. If $A\to \alpha B$ or $A\to \alpha B\beta$ and $\beta ⇒*ϵ$ , then Follow(A) $\subseteq$ Follow(B)