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)