Question 1. (15 points) Consider the following LL (1) grammar with starting symbol S.

S F

S (S T)

T

T + F T

F id

F num

a) Compute the First and Follow sets of all non-terminals (5 points)

b) Construct the LL (1) parsing table for the grammar (5 points)

c)Show step-by-step (content of stack and input string, as well as the production taken) how the

following string is parsed: ((20 + 30 + a)) (5 points)

Question 2. (5 points)

Write a grammar that recognizes a list of variable definition lines. Each line contains a type (int or char) followed by a list of simple variables (identifiers) separated by

comma (,). Each line ends with a semicolon (;). For example:

int a, b, d;

char aa;

int ccc, ddd;

char x, y;

Question 3. (5 points)

What is the language recognized by the following grammar? You can either give the set representation of the language or describe the set in English. The starting symbol is S.

S A a | b

A A c |