1 a. Thompson's construction is a method for automatically building a NFA from a regular expression.

1 b. Bison creates a bottom-up parser.

1 c. The resulting SLR table would have a shift-reduce conflict if y (a symbol from the grammar)
is an element of follow (B).

2.

	A	B
*[135]	[2]	[5]
[2]	[-]	[135]
*[5]	[-]	[5]

3. a.

3. b. action table

	A	B
state	a	d	$
0	-	-	-
1	-	-	acc
2	-	-	-
3	r3	r3	r3
4	-	-	r1
5	r2	r2	r2

Note: <eps> denotes the epsilon symbol in the rules below.

4. a. It accepts strings w/ a leading ','. For example, the string: , expr, expr would be accepted.

4. b.
list -> <eps> | list1
list1 -> expr | list1 , expr

4. c.
<eps> | expr (, expr)*

5.
E--> E1 + T { $$ = "(+" + $1 + " " + $3 + ")"; }
| T { $$=$1; }

T--> T1 * F { $$ = "(*" + $1 + " " + $3 + ")"; }
| F { $$ = $1; }

F --> id { $$ = $1; }
| (E) { $$ = $2; }

6 (extra credit).
plusExpr --> id + pERest
{$$= "(" + $1 + " " + $3 + ")" ;}
pERest --> id {$$ = $1 ; }
| id + pERest
{$$ = $1 + " " + $3; }