this project implement deterministic PDA to check if a string conforms to a grammar that generates statement blocks consisting of zeroJava Programming

Deterministic PDA implementation

Project Goal

The goal of this project is to implement a deterministic PDA to check if a string conforms to a grammar that generates statement blocks consisting of zero or more assignment statements followed by an arithmetic expression. The left side of an assignment statement is a variable name and the right side is an arithmetic expression. If it is valid, the PDA outputs the derivation starting from the start symbol else produce error if the string is not valid.

 

Grammar

It is a CFG grammar G = (V, Σ, P, S), where V = {S, B, T, T1, T2, F1, F2, X, C, N, I},

∑ = { a, b, c,…..z, A,B,C,……Z,0,1,2,…..9, +, -, *, /, (, ), =, ;, $} which

includes assignment operator = and statement separator symbol ;. The starting variable is S; and the rule set P is given as follows:

𝑺 → $𝑩$

𝑩 → 𝑻 | 𝑿 = 𝑻 ; 𝑩

𝑻 → 𝑻 + π‘»πŸ | π‘»πŸ

π‘»πŸ  → π‘»πŸ − π‘»πŸ | π‘»πŸ

π‘»πŸ  → π‘»πŸ ∗  π‘­πŸ | π‘­πŸ

π‘­πŸ → π‘­πŸ / π‘­πŸ | π‘­πŸ

π‘­πŸ → 𝑰 | 𝑿 | (𝑻)

𝑰 → 𝑡 𝑰 | 𝑡

𝑡 → 𝟎 | 𝟏 |𝟐 | πŸ‘ |πŸ’ |πŸ“ |πŸ” |πŸ•|πŸ–|πŸ—

𝑿 → π‘ͺ𝑿 | π‘ͺ

π‘ͺ → 𝒂 | 𝒃 |𝒄|… . 𝒛 |𝑨|𝑩|π‘ͺ| … … |𝒁

 

Note that the variable symbols B,S,T,I,N,X and C are different from the terminal uppercase characters.

 

Leftmost derivation of the string “$a = 2; b = (a+5)*(a/2); fg = a-b; fg$” is given follows:

 

𝑺  → $𝑩$   → $𝑿 = 𝑻; 𝑩$   → $π‘ͺ = 𝑻; 𝑩$ → $𝒂 = 𝑻; 𝑩$ → $𝒂 = π‘»πŸ; 𝑩$

→ $𝒂 = π‘»πŸ; 𝑩$ → $𝒂 = π‘­πŸ; 𝑩$ → $𝒂 = π‘­πŸ; 𝑩$ → $𝒂 = 𝑰; 𝑩$

→ $𝒂 = 𝑡; 𝑩$ → $𝒂 = 𝟐; 𝑩$ → $𝒂 = 𝟐; 𝑿 = 𝑻; 𝑩$ → $𝒂 = 𝟐; π‘ͺ = 𝑻; 𝑩$

→  $𝒂 = 𝟐; 𝒃 =  π‘»; 𝑩$    →  $𝒂 = 𝟐; 𝒃 =  π‘»πŸ; 𝑩$    → $𝒂 = 𝟐; 𝒃 = π‘»πŸ ∗ π‘­πŸ ;

→  $𝒂 = 𝟐; 𝒃 =  π‘­πŸ ∗ π‘­πŸ; 𝑩$   → $𝒂 = 𝟐; 𝒃 = π‘­πŸ ∗ π‘­πŸ; 𝑩$

→  $𝒂 = 𝟐; 𝒃 =  (𝑻) ∗ π‘­πŸ; 𝑩$   → $𝒂 = 𝟐; 𝒃 = (𝑻 + π‘»πŸ) ∗ π‘­πŸ; 𝑩$

→ $𝒂 = 𝟐; 𝒃 = (π‘»πŸ + π‘»πŸ) ∗ π‘­πŸ; 𝑩$ → $𝒂 = 𝟐; 𝒃 = (π‘»πŸ + π‘­πŸ) ∗ π‘­πŸ; 𝑩$

…….→ $𝒂 = 𝟐; 𝒃 = (𝒂 + π‘­πŸ) ∗ π‘­πŸ; 𝑩$ …. → $𝒂 = 𝟐; 𝒃 = (𝒂 + πŸ“) ∗ π‘­πŸ; 𝑩$

→  $𝒂 = 𝟐; 𝒃 = (𝒂 + πŸ“) ∗  π‘­πŸ; 𝑩$   → $𝒂 = 𝟐; 𝒃 = (𝒂 + πŸ“) ∗ (𝑻); 𝑩$

...→ $𝒂 = 𝟐; 𝒃 = (𝒂 + πŸ“) ∗ (a/2); 𝑩$ …→ $𝒂 = 𝟐; 𝒃 = (𝒂 + πŸ“) ∗ (a/2); X= T;

𝑩$ …. ...→ $𝒂 = 𝟐; 𝒃 = (𝒂 + πŸ“) ∗ (a/2); fg = a-b; B$

...→ $𝒂 = 𝟐; 𝒃 = (𝒂 + πŸ“) ∗ (a/2); fg = a-b; T$

......→ $𝒂 = 𝟐; 𝒃 = (𝒂 + πŸ“) ∗ (a/2); fg = a-b; fg$....

 

Rightmost derivation of the string “$a = 2; b = (a+5)*(a/2); fg = a-b; fg$” is given follows:

 

𝑺  → $𝑩$   → $𝑿 = 𝑻; 𝑩$ → $𝑿 = 𝑻; 𝑿 = 𝑻; 𝑩$ → $𝑿 = 𝑻; 𝑿 = 𝑻; 𝑿 = 𝑻; 𝑩 $

→ $𝑿 = 𝑻; 𝑿 = 𝑻; 𝑿 = 𝑻; π‘»πŸ$ → $𝑿 = 𝑻; 𝑿 = 𝑻; 𝑿 = 𝑻; π‘»πŸ$ …

→ $𝑿 = 𝑻; 𝑿 = 𝑻; X = T;fg$ → $𝑿 = 𝑻; 𝑿 = 𝑻; 𝑿 = π‘»πŸ; fg$

→ $𝑿 = 𝑻; 𝑿 = 𝑻; 𝑿 = π‘»πŸ − π‘»πŸ; fg$ …→ $𝑿 = 𝑻; 𝑿 = 𝑻; 𝑿 = π‘»πŸ − 𝒃; fg$ .. →

$𝑿 = 𝑻; 𝑿 = 𝑻; 𝑿 = 𝒂 − 𝒃; fg$ → $𝑿 = 𝑻; 𝑿 = 𝑻; π‘ͺ𝑿 = 𝒂 − 𝒃; fg$

→ $𝑿 = 𝑻; 𝑿 = 𝑻;  π‘ͺ𝑿 =  π’‚ − 𝒃; 𝐟𝐠$   → $𝑿 = 𝑻; 𝑿 = 𝑻; π‘ͺπ‘ͺ = 𝒂 − 𝒃; fg$

→ $𝑿 = 𝑻; 𝑿 = 𝑻; π‘ͺπ’ˆ = 𝒂 − 𝒃; fg$ → $𝑿 = 𝑻; 𝑿 = 𝑻 ; π’‡π’ˆ = 𝒂 − 𝒃; fg$ ….

→ $𝑿 = 𝑻; 𝐛 = (𝐚 + πŸ“) ∗ (𝐚/𝟐) ; π’‡π’ˆ = 𝒂 − 𝒃; fg$

….→ “$a = 2; b = (a+5)*(a/2); fg = a-b; fg

If you look at the reverse of the rightmost derivation, then we use reduction from left to right. For example after seeing “$a”, we first replace “a” by C which is again replaced by X to get $X. Then when we see “2”, we will replace it by I which is again replaced by X and then to T so we get $X=T based on what we have seen so far in the string. We keep adding input to $X=T until we reduce “b = (a+5)*(a/2)” by X=T so that we have $X=T; X=T reducing the string $a = 2; b = (a+5)*(a/2). Continuing this way we will reduce the string “$a = 2; b = (a+5)*(a/2); fg = a-b; fg” by $X=T; X=T; X=T;T. Reducing this we get $X=T; X=T; X=T;B which will be reduced to $X=T; X=T;B and so on until we get $B. When we see the final $, we will reduce $B$ by S. Parsers work this way by using shift-reduce actions; shift action involves pushing symbol from input string to stack and reduce action involves replacing the string from the top of the stack that

matches the right-hand side of a production rule by the non-terminal symbol on the left side of that rule. For example when the stack has “X = T; B” (first symbol is at top of the stack), reduce action can replace it by B using the production rule

𝑩 → 𝑿 = 𝑻 ; 𝑩

Deterministic PDA

Note that since the grammar is unambiguous you can define a deterministic PDA to recognize the language. There will be unique left-most and right-most derivations as mentioned before. Your first task is to design a deterministic PDA M= (Q,Σ,Γ,δ,q0,F) that recognizes strings that can be generated by the above grammar.

The PDA M must satisfy the following conditions:

 

  • The PDA must be defined with the alphabet Σ defined in equation (1). In other words the PDA must be able to handle any string of symbols from Σ. The PDA can handle certain strings not in A by crashing, i.e., the drawing does not have an edge leaving a state corresponding to particular symbols read and

  • The PDA must have exactly one accept

(c ) The states in the PDA must be labeled qo,q2,q3,...,qn-1, where q0 is the start state and n is the number of states in the PDA.

  • All edges in the PDA must correspond to reading a symbol from Σ; i.e., no edge can correspond to reading ε. There is no restriction on pushing or popping ε on

  • There is exactly one edge leaving the start state, and that arc has label “$, ε → $”. Thus, the first thing the PDA does is it reads a $ and pushes a $ on the

(f )Any edge going into the accept state has label “$, $ → ε”.

 

(g) There cannot be two edges corresponding to reading the same symbol a ∈ Σ and popping the same symbol b ∈ Γ leaving a single state.

You will not be able to use the construction specified in Lemma 2.21 to convert the CFG to a PDA as the resulting PDA will not satisfy the all the last four properties (d)-(g).

The drawing of your PDA must include all edges that are ever used in accepting a string in

  1. But to simplify your drawing, those edges that will always lead to a string being rejected should be omitted. Specifically, when processing a string on your PDA, it might become clear at some point that the string will be rejected before reaching the end of the input. For example, if the input string is “$ab+*bc$”, then it is clear on reading the * that the string will

not be accepted. Moreover, if an input string ever contains the substring +*, then the input string will be rejected. Thus, your drawing should omit the transition corresponding to reading the * in this case, so the PDA drawing will crash at this point

Attachments:

Instructions Files

Java Programming Experts

expert
Neno S.
Java Programming

60 Answers

expert
Ray Bjork
Java Programming

90 Answers

View More Experts
Disclaimer

The ready solutions purchased from Library are already used solutions. Please do not submit them directly as it may lead to plagiarism. Once paid, the solution file download link will be sent to your provided email. Please either use them for learning purpose or re-write them in your own language. In case if you haven't get the email, do let us know via chat support.

Get Free Quote!

270 Experts Online