Programming Language Exercise

Question 1

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

S -> F
S -> (S T)
T -> e
T -> + F T
F -> id
F -> num

a) Compute the First and Follow sets of all non-terminals.

b) Construct the LL (1) parsing table for the grammar.

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))

Question 2

Write a context-free grammar that accepts strings containing zero or more copies of the terminal "a" followed by an equal number of copies of terminal "b". For example:

ab
aabb
aaabbb
and so on, should all be accepted by the grammar

Question 3

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 | e