# Homework 2

**Problem 1 out of 3**. Consider the following grammar

**1.**

**Calculate the FIRST sets for all non-‐terminals.**

See chart below.

**2.**

**Calculate the FOLLOW sets for all**

non-‐terminals.See chart below.

non-‐terminals.

**FIRST(E) = { en,(m),u,**

*NOTE:*… depicts this element of the FIRST sets was the

*n*th symbol added to a set, derived using grammar rule

*m*, having FIRST (or FOLLOW) set rule

*u*being applied.

**Problem 2 of 3.**Consider a grammar that has the following rule A → B C D E And we are told that D is the

start symbol. Also, we know that FIRST(B) ⊇ { b } FIRST(C) ⊇ {ε, b}

FIRST(E) ⊇ {ε, e, d}

**1.**

**From what you is given, which elements are**

definitely in FIRST(A)?

definitely in FIRST(A)?

**2.**

**Is it true that for this grammar FIRST(A)**⊇

**FIRST(B) . Explain.**

**3.**

**Adding which grammar rule ensures that FOLLOW(A)**

= FOLLOW(D)? Explain

= FOLLOW(D)? Explain

**Problem 3 of 3.**Consider the grammar

S → A B C | C

A → a A | B |

ε

B → c B | d |

ε

C → e C | f

**Show that this grammar has a predictive parser by showing that it**

satisfies the conditions for predictive parsing.

satisfies the conditions for predictive parsing.

**1.**

**Write the function parse_A() to parse the**

non-terminal A.

non-terminal A.

•

**Assume you**

have functions to parse all other non‐terminals.•

have functions to parse all other non‐terminals.

**You can**

assume that you have a function getToken() to read the next token in the input.

assume that you have a function getToken() to read the next token in the input.

•

**You can**

assume that you have the following token types to use in your code: a-type,

btype, c-type, d-type, e-type, f-type , and EOF.

assume that you have the following token types to use in your code: a-type,

btype, c-type, d-type, e-type, f-type , and EOF.

You'll get 1 file (279.1KB)