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}(Y_1)\subseteq \text{First(X)}$$
2. If $$Y_1\cdots Y_k\Rightarrow *ϵ$$ , then $$\text{First}(Y_{k+1})\subseteq \text{First(X)}$$
3. If $$Y_i\to ϵ,\forall i$$ , then $$ϵ\in \text{First}(X)$$

Follow(X):

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