Downloaded 17 times
Uploaded byAkhil Kaushik
Parsing in Compiler Design
This document discusses parsing and context-free grammars. It defines parsing as verifying that tokens generated by a lexical analyzer follow syntactic rules of a language using a parser. Context-free grammars are defined using terminals, non-terminals, productions and a start symbol. Top-down and bottom-up parsing are introduced. Techniques for grammar analysis and improvement like left factoring, eliminating left recursion, calculating first and follow sets are explained with examples.
In this document
Powered by AI
Introduction of Akhil Kaushik from TIT Bhiwani, presenting the topic of parsing.
Parsing involves syntax analysis in compilers to verify token grouping by syntax rules and produces parse trees.
Introduction to Context-Free Grammars (CFG) involving terminals, non-terminals, start symbols, and productions.
Discussion on derivations, explaining the process of deriving strings using left-most and right-most methods.
An overview of parser types based on derivation method: Top Down and Bottom Up Parsers.
Top Down Parsing builds parse trees from root to leaf, starting from the start symbol.
Bottom Up Parsing works from leaf nodes to the root, applying production rules in reverse.
Explanation and examples of left factoring in grammars to simplify productions.
Details on left recursion elimination in grammars, with various examples and transformations.
Introduction to FIRST and FOLLOW sets, essential for parsing strategies, with rules for computation.
Examples demonstrating the computation of FIRST sets for given grammars.
Rules for calculating FOLLOW sets with examples to illustrate the application.
Examples calculating FIRST and FOLLOW sets for various grammars, including handling left recursion.
Presentation concludes with Akhil Kaushik's contact information for further inquiries.
Parsing in Compiler Design
- 1. Akhil Kaushik Asstt. Prof.,CE Deptt., TIT Bhiwani 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.
- 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 ")" • Derivation step: replace symbol by RHS of production. • Repeatedly apply derivations
- 8. Derivations • Left-most derivation: Expandleft-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.
- 13. Left Factoring -Examples Consider the following grammar:- • S → iEtS / iEtSeS / a • E → b Solution:- • S → iEtSS’ / a • S’ → eS / ∈ • E → b
- 14. Left Factoring -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.
- 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 & FollowRules 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->Y1 Y2 Y3….Yn 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 Calculatethe 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 Calculatethe 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 & FollowRules 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 Calculatethe 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 Calculatethe 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 , + , $ , ) }
- 38. Akhil Kaushik akhilkaushik05@gmail.com 9416910303 CONTACT MEAT: Akhil Kaushik akhilkaushik05@gmail.com 9416910303 THANK YOU !!!