compiler

1.  Convert the following RE into DFA directly:
a.  a* b ( c? / b+ ) c+ / Ԑ
b.  a / b* / abc*d? / b?
c.  (ab /ba)*
d.  (a* / b*) c? (d+ / Ԑ ) +
e.  (p* / q* )*
f.  (p*q*)*
g.  (a / Ԑ ) + ab*

2.  Thomson’s construction (RE to NFA and NFA to DFA)
a.  (a/b*) abb
b.  (ab*/a*b)*abb(a/b)*
c.  (a*b/ab*)+ abb(a/b)+
d.  (a*/b*)abb
e.  (a+/b+)*abb

3.  Eliminate left recursion
a.  S-> As / Ab
A-> Ab / Sd/ BeA
B-> Be/ AcBd/ j

b.  S-> Aa/b
A-> Ac/Sd/Ԑ

c.  Class lectures

4.  Build LL(1) parsing table
a.  S->(L) / a /b
L-> L,S /S

b.  S-> iEtSS’ / a
S’->eS/Ԑ
E->b

c.  S->aSc/B
B->bBcf/C
C-> cCg / d / Ԑ

d.  S-> aS/Ab
A->XYZ/Ԑ
X->cS/Ԑ
Y->dS/Ԑ
Z->eS

e.  X->YaYb/ZbZa
Y->b
Z->a/Ԑ