Syntax analysis from the Dragoon Book

by Forrest Sheng Bao

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 BBP1||BPm|Pm+1||Pn

by BPm+1B||PnB andBP1B||PmB|ϵ

How to eliminate common prefixes

Replace the rule Aαβ1|αβ2||αβn|Σ1||Σn+m

by AαA|Σ1||Σn+m

and Aβ1||βn

Top-down parsing

To rule XY1Y2Yn


1. First(Y1)First(X)
2. If Y1Yk*ϵ , then First(Yk+1)First(X)
3. If Yiϵ,i , then ϵFirst(X)


1. $ is contained in Follow(X)
2. If AαSβ, then First(β)/ϵFollow(S)
3. If AαB or AαBβ and β*ϵ , then Follow(A) Follow(B)

No comments: