Parsing in Compiler Design

This ppt gives all details about the parsing phase of compiler design.

1. Parsing Introduction

2. What is Parsing? In the syntax analysis phase, a compiler verifies whether or not the tokens generated by the lexical analyzer are grouped according to the syntactic rules of the language. This is done by a parser. It detects and reports any syntax errors and produces a parse tree from which intermediate code can be generated .

3. What is Parsing?

4. Context-Free Grammars Terminals - Basic symbols from which strings are formed. Non-terminals - Syntactic variables that denote sets of strings. Start Symbol - Denotes the nonterminal that generates strings of the languages Productions - A = X … X - Head/left side (A) is a nonterminal - Body/right side (X … X) zero or more terminals and non-terminals

5. Context-Free Grammars Non-terminals , terminals can be derived from productions. First production defines start symbol.

6. CFG Notation A, B, C: non-terminals l: terminals a, b, c: strings of non-terminals and terminals (alpha, beta, gamma in math) w, v: strings of terminal symbols

7. Derivations Derivation - derives in zero or more steps E =>* "-" "(" ID "+" ID ")" D erivation step: replace symbol by RHS of production. Repeatedly apply derivations

8. Derivations Left-most derivation: Expand left-most non-terminal at each step. Right-most derivation: Expand right-most non-terminal at each step

9. Types of Parser The process of deriving the string from the given grammar is known as derivation (parsing). Depending upon how derivation is done we have two kinds of parsers :- Top Down Parser Bottom Up Parser

10. Top Down Parser Top down parsing attempts to build the parse tree from root to leave. Top down parser will start from start symbol and proceeds to string. It follows leftmost derivation.

11. Bottom Up Parser Bottom-up parsing starts from the leaf nodes of a tree and works in upward direction till it reaches the root node . Here , we start from a sentence and then apply production rules in reverse manner in order to reach the start symbol.

12. Left Factoring

13. Left F actoring - Examples Consider the following grammar:- S → iEtS / iEtSeS / a E → b Solution:- S → iEtSS’ / a S’ → eS / ∈ E → b

14. Left F actoring - Examples Consider the following grammar:- A → aAB / aBc / aAc Solution:- A → aA ’ A’ → AB / Bc / Ac // This has to done again A → aA ’ A’ → AD / Bc D → B / c

15. Left Factoring - Examples Consider the following grammar:- S → aAd / aB A → a / ab B → ccd / ddc Solution :- S → aS’ S’ → Ad / B A → aA ’ A’ → b /  ∈

16. Eliminating Left Recursion

17. Left Recursion - Examples Consider the following grammar - A → ABd / Aa / a B → Be / b The grammar after eliminating left recursion is- A → aA ’ A’ → BdA ’ / aA ’ / ∈ B → bB ’ B’ → eB ’ / ∈

18. Left Recursion - Examples Consider the following grammar and eliminate left recursion- E → E + E / E x E / a The grammar after eliminating left recursion is- E → aA A → +EA / xEA / ∈

19. Left Recursion - Examples Consider the following grammar and eliminate left recursion- E → E + T / T T → T x F / F F → id E → E + T E → T T → T x F T → F F → id OR

20. Left Recursion - Examples The grammar after eliminating left recursion is- E → TE’ E’ → +TE’ / ∈ T → FT’ T’ → xFT ’ / ∈ F → id

21. First & Follow FIRST(X) for a grammar symbol X is the set of terminals that begin the strings derivable from X . Follow(X) to be the set of terminals that can appear immediately to the right of Non-Terminal X in some sentential form. Why calculate FIRST? It is useful to calculate FOLLOW. Both are useful in parsing (both Top-Down and Bottom-Up)

22. First & Follow Rules Rules to compute FIRST set:- If x is a terminal, then FIRST(x) = { ‘x’ } If x-> Є, is a production rule, then add Є to FIRST(x). If X->Y 1 Y 2 Y 3 …. Y n is a production, then FIRST(X) = FIRST(Y1) If FIRST(Y1) contains Є then FIRST(X) = { FIRST(Y1) – Є } U { FIRST(Y2) } If FIRST (Yi) contains Є for all i = 1 to n, then add Є to FIRST(X).

23. First - Examples Calculate the first functions for the given grammar-   S  → aBDh B → cC C → bC / ∈ D → EF E → g / ∈ F → f / ∈

24. First - Examples First(S) = { a } First(B) = { c } First(C) = { b , ∈ } First(D) = { First(E) – ∈ } ∪ First(F) = { g , f , ∈} First(E) = { g , ∈ } First(F) = { f , ∈ }

25. First - Examples Calculate the first functions for the given grammar- S  → A A → aB / Ad B → b C → g

26. First - Examples First(S) = First(A) = { a } First(A) = { a } First(A’) = { d , ∈ } First(B) = { b } First(C) = { g }

27. First & Follow Rules Rules to compute FOLLOW set :- Follow(S) = {$} where S is the start symbol. If A-> pBq is a production where p , B, q any grammar symbols then everything in FIRST(q) except Є is in FOLLOW(B ). If A-> pB is a production or a production A-> pBq where FIRST(q ) contains Є then everything in FOLLOW(A) is in FOLLOW(B ).

28. Follow - Examples Calculate the follow functions for the given grammar-   S  → aBDh B → cC C → bC / ∈ D → EF E → g / ∈ F → f / ∈

29. Follow - Examples Follow(S) = { $ } Follow(B) = { First(D) – ∈ } ∪ First(h) = { g , f , h } Follow(C) = Follow(B) = { g , f , h } Follow(D) = First(h) = { h } Follow(E) = { First(F) – ∈ } ∪ Follow(D) = { f , h } Follow(F) = Follow(D) = { h }

30. Follow - Examples Calculate the follow functions for the given grammar- S  → A A → aB / Ad B → b C → g

31. Follow - Examples Follow(S) = { $ } Follow(A) = Follow(S) = { $ } Follow(A’) = Follow(A) = { $ } Follow(B) = { First(A’) – ∈ } ∪ Follow(A) = { d , $ } Follow(C) = NA

32. First & Follow - Examples Calculate the first and follow functions for the given grammar-   S  → AaAb / BbBa A → ∈ B → ∈

33. First & Follow - Examples First(S) = { First(A) – ∈ } ∪ First(a) ∪ { First(B) – ∈ } ∪ First(b) = { a , b } First(A) = { ∈ } First(B) = { ∈ } Follow(S) = { $ } Follow(A) = First(a) ∪ First(b) = { a , b } Follow(B) = First(b) ∪ First(a) = { a , b }

34. First & Follow - Examples Calculate the first and follow functions for the given grammar-   E → E + T / T T → T x F / F F → (E) / id

35. First & Follow - Examples The given grammar is left recursive . After eliminating left recursion, we get - E → TE’ E’ → + TE’ / ∈ T → FT’ T’ → x FT’ / ∈ F → (E) / id

36. First & Follow - Examples First(E) = First(T) = First(F) = { ( , id } First(E’) = { + , ∈ } First(T) = First(F) = { ( , id } First(T’) = { x , ∈ } First(F) = { ( , id }

37. First & Follow - Examples Follow(E) = { $ , ) } Follow(E’) = Follow(E) = { $ , ) } Follow(T) = { First(E’) – ∈ } ∪ Follow(E) ∪ Follow(E’) = { + , $ , ) } Follow(T’) = Follow(T) = { + , $ , ) } Follow(F) = { First(T’) – ∈ } ∪ Follow(T) ∪ Follow(T’) = { x , + , $ , ) }