Note: This problem is designed to show you how DFA and PDA are used in Compilers. DFA is used for finding the tokens (Problem 1) and PDA for syntax (Problem 2)

Part I

We have the following input file: (for foreign students the name here are of well know comics)

larry = 27
curly = 19
moe = 8
groucho = 11
harpo = larry+curly
harpo = larry-curly
harpo = larry*curly
harpo = larry/curly
harpo = larry*curly+moe*groucho

We need to define a DFA which will give the output various tokens. In this case, the identifiers will be larry, curly, moe , groucho , and harpo. The operators will be /, +, -, *, +, = and integers ( . They will come as an output file.

Here is A DFA for this purpose. (q0 is the starting state, q1, q2 and q3 are accepting states (if it is accepted in state q2, the token is an operator, if it is accepted in q1, the token is an identifier ( , any string that starts with a letter and then continues with any combination of letters and integer digits. The maximum number of characters for any identifier should be 10.)
and q3 if it is an integer (intLit) - you can limit the number of digits to 10). One should write down what strings are accepted (token) and list the names of new tokens .

State operator alpha intLit

q0 q2 q1 q3

q1 q1 q1

q2

q3 q4 q3

q4 q4 q4 q4

Part II

You will be writing a program for PDA. When the file in Q 1 is input, the output should say that it is a valid file. Now change one line from

harpo = larry+curly

to

harpo = larry++curly

The program should say that it is invalid. Here is the grammar for the PDA
G = {V,T,S,P}

V={,, , , ,,}
T= {ident ∪ {0-9,+,-,*,/,=, ;}}
S = {
Production rules are
→begin end

→| ;
→
→ident=
→| +|+
→|*|/
→IntLit |ident

The PDA for this grammar is q0 as the starting state , q1 as the intermediate state and q2 as the accepting state

The transition rules are
(q0, λ,λ) →(q1,)

(q1,IntList,Intlit) →(q1,λ)
(q1, λ, ) → (q1, +)
q1, λ, ) → (q1, -)
(q1, λ, ) → (q1, ident)
(q1, λ, ) → (q1, /)
(q1, λ, ) → (q1, *)
(q1, λ, ) → (q1, IntLit)
(q1, λ, ) → (q1, )
(q1, λ, ) → (q1, )
(q1, λ, ) → (q1, beginend)
(q1, λ, ) → (q1, ident=)
(q1, λ, ) → (q1, )
(q1, λ, ) → (q1, )
(q1, λ, ) → (q1, )
(q1, λ, iden)→ (q1, ident)
(q1, +, +)→ (q1, λ)
(q1, -, -)→ (q1, λ)
(q1, *, *)→ (q1, λ)
(q1, /, /)→ (q1, λ)
(q1, ;, ;)→ (q1, λ)
(q1, IntLit, IntLit)→ (q1, λ)
(q1.λ,λ)→(q2,Z)