Pushdown Automata & Parsing

Posted By on April 29, 2016


Download PDF
Pushdown Automata Introduction
Turing Machine

Parsing is used to derive a string using the production rules of a grammar. It is used to check the acceptability of a string. Compiler is used to check whether or not a string is syntactically correct. A parser takes the inputs and builds a parse tree.

A parser can be of two types −

  • Top-Down Parser − Top-down parsing starts from the top with the start-symbol and derives a string using a parse tree.
  • Bottom-Up Parser − Bottom-up parsing starts from the bottom with the string and comes to the start symbol using a parse tree.

Design of Top-Down Parser

For top-down parsing, a PDA has the following four types of transitions −

  • Pop the non-terminal on the left hand side of the production at the top of the stack and push its right-hand side string.
  • If the top symbol of the stack matches with the input symbol being read, pop it.
  • Push the start symbol ‘S’ into the stack.
  • If the input string is fully read and the stack is empty, go to the final state ‘F’.

Example

Design a top-down parser for the expression “x+y*z” for the grammar G with the following production rules −

P: S → S+X | X, X → X*Y | Y, Y → (S) | id

Solution

If the PDA is (Q, ∑, S, δ, q0, I, F), then the top-down parsing is −

(x+y*z, I) ⊢ (x +y*z, SI) ⊢ (x+y*z, S+XI) ⊢ (x+y*z, X+XI)

⊢(x+y*z, Y+X I) ⊢ (x+y*z, x+XI) ⊢ (+y*z, +XI) ⊢ (y*z, XI)

⊢ (y*z, X*YI) ⊢ (y*z, y*YI) ⊢ (*z,*YI) ⊢ (z, YI) ⊢ (z, zI) ⊢ (ε, I)

Design of a Bottom-Up Parser

For bottom-up parsing, a PDA has the following four types of transitions −

  • Push the current input symbol into the stack.
  • Replace the right-hand side of a production at the top of the stack with its left-hand side.
  • If the top of the stack element matches with the current input symbol, pop it.
  • If the input string is fully read and only if the start symbol ‘S’ remains in the stack, pop it and go to the final state ‘F’.

Example

Design a top-down parser for the expression “x+y*z” for the grammar G with the following production rules −

P: S → S+X | X, X → X*Y | Y, Y → (S) | id

Solution

If the PDA is (Q, ∑, S, δ, q0, I, F), then the bottom-up parsing is −

(x+y*z, I) ⊢ (+y*z, xI) ⊢ (+y*z, YI) ⊢ (+y*z, XI) ⊢ (+y*z, SI)

⊢ (y*z, +SI) ⊢ (*z, y+SI) ⊢ (*z, Y+SI) ⊢ (*z, X+SI) ⊢ (z, *X+SI)

⊢(ε, z*X+SI) ⊢ (ε, Y*X+SI) ⊢ (ε, X+SI) ⊢ (ε, SI)

 

Pushdown Automata Introduction
Turing Machine

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com