Question 1
Given the following grammar:
S-> ( L )
S -> x
L -> S
L -> L , S
Write a parser for this language, i.e. a program that will take any input
and answer "yes" if it corresponds to this grammar, and "no" otherwise.
Solution
Question 2
Giving the following grammar for stack instructions:
S -> A
A -> A ; A
A -> push N
A -> I := pop
N -> "any sequence of digits"
I -> "any single lower-case letter"
Write an evaluator for this language that will process the instructions
and print out the size of the stack (i.e. the number of elements it contains)
at the end. Assume that carrying out a "pop"on an empty stack has no effect.
For example, given the following input:
a:=pop; push 4; push 6; b:=pop; push 7
The result would be: "2"
Solution
Question 3
Given the following grammar for boolean expressions:
S -> E
E -> T or T
E -> T
T -> F and F
T -> F
F -> true
F -> false
F -> ( E )
Write a program that takes any valid input for this language and evaluates
it to either "true" or "false".
Solution