# 1. (3 points) List the steps lex (or any lexical analyzer generator) takes in generating a lexical analyzer from a regular expression.
Answer:
1. Converts the regular expression to an NFA
2. Converts the NFA to a DFA
3. Converts the DFA to a minimal DFA
#2. Consider the standard expression grammar:
E --> E + T | T
T --> T * F | F
F --> (E) | x
(a) (3 points) add an exponentiation operator, ^, and change the grammar to allow arithmetic expressions with exponentiation to be generated.
Answer:
E --> E + T | T
T --> T * F | F
F --> F ^ P | P
P --> (E) | x
(b) (2 points) Use your grammar to show a leftmost parse of x + x^x.
Answer:
E ==> E + T ==> T + T ==> F + T ==> P + T
==> x + T ==> x + F ==> x + F ^ P ==> x + P ^ P
==> x + x ^ P ==> x + x ^ x
3a (4 points) What 2 conditions must a grammar satisfy to be LL(1)?
For any pair of productions A --> alpha and A --> beta,
(1) FIRST(alpha) intersect FIRST(beta) must be empty
(2) If alpha or beta derives epsilon (say alpha ==> epsilon)
the FIRST(beta) intersect FOLLOW(A) must be empty
3b (3 points) Show that the expression grammar
E --> E + T | T
T --> T * F | F
F --> (E) | x
is or is not LL(1)
It is not:For the production, E --> E+T and E --> T,
FIRST (E+T) and FIRST(T) both contain "("
and "x".
4. Consider the grammar:
S --> ( S ) | ( )
(a) (2 points) What is L(G)?
Answer:
L(G) = embedded balanced parentheses
(b) (3 points) Is the grammar ambiguous? Justify you answer.
Answer:
No. there is no way to get more than 1 parse tree.
5. (4 points) Use the methods described in class to eliminate left recursion from the
expression grammar. Show your work:
E --> E + T | T
T --> T * F | F
F --> (E) | x
Answer:
E --> E + T | T
This is of the form A --> A a | b with a = "+ T" and b = "T"
Changing to A --> b A', A'--> epsilon| a A', gives:
E --> T E'
E' --> + T E' | epsilon
Similarly,
T --> F T'
T' --> * F T' | epsilon
The resulting grammar is:
E --> T E'
E' --> + T E' | epsilon
T --> F T'
T' --> * F T' | epsilon
F --> (E) | x
6. The following grammar
S --> x | ( S R )
R --> , S R | epsilon
generates Scheme-like expressions such as x and (x , x) and ( x , (x , x) , x)
(a) (4 points)Create a top-down parsing table for this
Answer:
x ( ) , $
-------------------------------------------------------------
|
S | S ->x S -> (SR)
|
|
R | R -> e R -> , SR R -> e
|
(b) (2 points) Parse (x , x) top-down
Answer:
Stack Input Production
$ S ( x , x ) $ S --> ( S R )
$ ) R S ( ( x , x ) $ match
$ ) R S x , x ) $ S --> x
$ ) R x x , x ) $ match
$ ) R , x ) $ R --> , S R
$ ) R S , , x ) $ match
$ ) R S x ) $ S --> x
$ ) R x x ) $ match
$ ) R ) $ R --> e
$ ) ) $ match
$ $ accept