Examples: Top Down Parsing Computer Science Engineering (CSE) Notes | EduRev

Compiler Design

Created by: Cstoppers Instructors

Computer Science Engineering (CSE) : Examples: Top Down Parsing Computer Science Engineering (CSE) Notes | EduRev

The document Examples: Top Down Parsing Computer Science Engineering (CSE) Notes | EduRev is a part of the Computer Science Engineering (CSE) Course Compiler Design.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

Example 2:
Construct a predictive parsing table for the given grammar or Check whether the given grammar is LL(1) or not.
S → iEtSS| a
SI → eS | ∈
E → b
 

Solution: 1. Computation of First () set:

1. First (E) = first (b) = {b}

2. First (SI) = first (eS) È ∪ first (e) = {e, e}

3. first (S) = first (iEtSSI) È∪ first (a) = {i, a}

2. Computation of follow() set:

1. follow (S) = {$} È∪ first (SI)  {e} È ∪ follow (S) È ∪ follow (SI) = {$} È {e} = {e, $}

2. follow (SI) = follow  ∪ (S) = {e, $}

3. follow (E) = first (tSSI) = {t} 
 

3. The parsing table for this grammar is:
 

Examples: Top Down Parsing Computer Science Engineering (CSE) Notes | EduRev  
 

As the table multiply defined entry. The given grammar is not LL(1). 
 

Example 3:
Construct the FIRST and FOLLOW and predictive parse table for the grammar:
S→ AC$
C → c | Î A → aBCd | BQ | Î B → bB | d Q → q

Solution:
1. Finding the first () sets:
First (Q) = {q}
First (B) = {b, d} 
First (C) = {c, e}
First (A) = First (aBCd) È First (BQ) È First (e)
= {a} È First (B) È First (d) È{e}
= {a} È First (bB) È First (d) È {e}
= {a} È {b} È {d} È {e}
= {a, b, d, e} First (S) = First (AC$)
= (First (A)  {e}) È (First (C)  {e}) È First (e)
= ({a, b, d, e}  {e}) È ({c, e}  {e}) È {e}
= {a, b, d, c, e} 


2. Finding Follow () sets: Follow (S) = {#}
Follow (A) = (First (C) – {e}) È First ($) = ({c, e}  {e}) È {$}
Follow (A) = {c, $} Follow (B) = (First (C)  {e}) È First (d) È First (Q)
= {c} È {d} È {q} = {c, d, q} Follow (C) = (First ($) È First (d) = {d, $}
Follow (Q) = (First (A) = {c, $}

3. The parsing table for this grammar is: 
 

Examples: Top Down Parsing Computer Science Engineering (CSE) Notes | EduRev
 

4. Moves made by predictive parser on the input abdcdc$ is:
 

Examples: Top Down Parsing Computer Science Engineering (CSE) Notes | EduRev

Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Dynamic Test

Content Category

Related Searches

Examples: Top Down Parsing Computer Science Engineering (CSE) Notes | EduRev

,

Previous Year Questions with Solutions

,

Examples: Top Down Parsing Computer Science Engineering (CSE) Notes | EduRev

,

MCQs

,

Examples: Top Down Parsing Computer Science Engineering (CSE) Notes | EduRev

,

pdf

,

Exam

,

Important questions

,

study material

,

Sample Paper

,

video lectures

,

Viva Questions

,

Semester Notes

,

Extra Questions

,

practice quizzes

,

shortcuts and tricks

,

Objective type Questions

,

past year papers

,

Summary

,

Free

,

ppt

,

mock tests for examination

;