Define a dfa which will give the output various tokens

Assignment Help Programming Languages

Reference no: EM131296943

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

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

harpo = larry++curly

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

V={<program>,<stmtList>, <stmt>, <assign>, <expr>,<term>,<factor>}
T= {ident ∪ {0-9,+,-,*,/,=, ;}}
S = {<program>
Production rules are
<begin> →begin<stmtList> end

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,<program>)

(q1,IntList,Intlit) →(q1,λ)
(q1, λ, <expr>) → (q1, <expr>+<term>)
q1, λ, <expr>) → (q1, <expr>-<term>)
(q1, λ, <factor>) → (q1, ident)
(q1, λ, <term>) → (q1, <term>/<factor>)
(q1, λ, <term>) → (q1, <term>*<factor>)
(q1, λ, <factor>) → (q1, IntLit)
(q1, λ, <term>) → (q1, <factor>)
(q1, λ, <StmtList>) → (q1, <stmt>)
(q1, λ, <program>) → (q1, begin<stmtList>end)
(q1, λ, <assign>) → (q1, ident=<expr>)
(q1, λ, <stmt>) → (q1, <assign>)
(q1, λ, <expr>) → (q1, <term>)
(q1, λ, <stmtList>) → (q1, <stmt>)
(q1, λ, iden)→ (q1, ident)
(q1, +, +)→ (q1, λ)
(q1, -, -)→ (q1, λ)
(q1, *, *)→ (q1, λ)
(q1, /, /)→ (q1, λ)
(q1, ;, ;)→ (q1, λ)
(q1, IntLit, IntLit)→ (q1, λ)
(q1.λ,λ)→(q2,Z)

Reference no: EM131296943

Questions Cloud

Create a competitive advantage for a firm : Identify the steps a firm should take before deciding to compete in a specific market?- How are existing firms in a market affected when a new firm with a competitive advantage enters the market?

Perform a durbin-watson test at the level testing : Perform a Durbin-Watson test at the .05 level testing that there is positive serial correlation. Be sure to report the lower and upper limit critical values and test statistic. What is your decision, and what does this mean?

Why high inflation could adversely affect companies : Explain why high inflation could adversely affect companies like Ben & Jerry's.- Explain why a recession could adversely affect companies like Ben & Jerry's.

What is monte carlo simulation : What is Monte Carlo simulation? Can Monte Carlo simulation be used to explore sensitivity analysis? How?

Define a dfa which will give the output various tokens : This problem is designed to show you how DFA and PDA are used in Compilers - Writing a program for PDA - We need to define a DFA which will give the output various tokens.

What kinds of data does the st louis fed provide : What kinds of data does the St. Louis Fed provide? Look at "About the Fed." What cities are part of the Federal Reserve System?

Evaluate the outcomes of the advocacy work : Elaborate on how advocacy efforts have influenced current attitudes and policies towards issues that affect human services. Profile how advocacy efforts have evolved and changed over time to influence the interaction of human systems.Evaluate the out..

Different kinds of macroeconomic data available : Look at the different kinds of macroeconomic data available on this website. Which data would you use if you were attempting to forecast a recression in the U.S. economy?

Power of relationships for superior performance : Prepare a 2-3 page case study that summarize the Southwest Airlines Way: The Power of Relationships for Superior Performance. Choose two Southwest Practices for Building High Performance Relationships. Present a summary of your findings from the..

User Account

All Pages