Assignment 2

Due date October 18.

1. Consider the following grammar for a language of simple straight-line programs:

Non-Terminals = {S, E, L}
Terminals = {id, num, (, ), +, :=, semicolon, comma}
Keywords = {print}

S ::= S ; S
S ::= id := E
S ::= print (L)
E ::= id
E ::= num
E ::= E + E
E ::= (S, E)
L ::= E
L ::= L, E

This grammar is unsuitable for top-down parsing: it is ambiguous and has left-recursion. Transform the grammar to remove the ambiguity and the left-recursion, compute the First and Follow set for non-terminals, and build the LL(1) table for the language.

Consider the following grammar, whose terminals are {id, :} :

S ::= G
G ::= P
G ::= P G
P ::= id : R
R ::= epsilon
R ::= id R

2. Left-factor the grammar, and compute the FIRST and FOLLOW sets for the resulting grammar. Verify that the grammar is not LL (1) by indicating the conflicts that arise when trying to build the parse table. Show that the language is LL (2), by showing convincingly that the conflicts can be resolved by looking ahead one more token.