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.
NOTE: FIRST(E) = { en,(m),u,
… depicts this element of the FIRST sets was the nth 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)?
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

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.

1.  Write the function parse_A() to parse the
non-terminal A.

•
Assume you
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.

•
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.