A top-down table-driven parser

• A parser could be constructed using a driver routine (or control) a stack and the grammar (usually stored in tabular form). The driver routine follows the following algorithm:
  1. Initialize the stack with the start symbol of the grammar.
  2. Repeat until no further actions are possible
     1. If the top of the stack and the next input symbol are the same, pop the top of the stack and consume the input symbol.
     2. If the top of the stack is a nonterminal symbol, pop the stack and push the right hand side of the corresponding grammar rule onto the stack.
  3. If both the stack and input are empty, accept the input otherwise, reject the input.
• This approach is illustrated using the grammar for expressions below and parsing the expression id+id*id.
  • Expression Grammar:
    

       E -> c
       E -> id 
       E -> (E)
       E -> E + E
       E -> E * E 
    

  ---

  STACK        INPUT          RULE/ACTION
  
     E]        id+id*id]     pop & push using E --> E+E
   E+E]        id+id*id]     pop & push using E --> id
  id+E]        id+id*id]     pop & consume
    +E]          +id*id]     pop & consume
     E]           id*id]     pop & push using E --> E*E
   E*E]           id*id]     pop & push using E --> id
  id*E]           id*id]     pop & consume
    *E]             *id]     pop & consume
     E]              id]     pop & push using E --> id
    id]              id]     pop & consume
      ]                ]     accept

  ---

Pushdown automata (PDA)

• Although a top-down table-driven parser is only one of the several parsing algorithms for context-free languages, all parsers must hold some information on a stack.
• In the case of the top-down parser, it must:
  1. pop variables off the stack and push the corresponding right-hand side on the stack, and
  2. pop terminals off the stack when they match the input.
• This observation leads us to the notion of an idealized machine called a pushdown automata.
• A pushdown automata has the following components:
  • an input that it scans from left to right
  • a stack, and
  • a finite control to control the operations of reading the input and pushing data on and popping data off the stack.
• The states in the control are similar to those in finite state automata
  • an initial state
  • a set of final or accepting states
• The transitions are bit more complicated than those in FSA.
  
            (q_i, a, A) --> (q_j, r)
  
  Which is read as: when in the state q_i, reading (or consuming) a in the input and popping A from the stack, then go to state q_j and push the string r into the stack.
• A string is acceptanced by a PDA when:
     (1) the entire string is read;
     (2) control in some final/accepting state;
     (3) the stack is empty.

An Example

• Example: the PDA for {aⁿbⁿ | n>0}
  
  State: {q0, q1}  Initial state: q0; Final states: {q0, q1}
  Input Alphabet: {a, b}
  Stack Alphabet: {A}
  (Note: Stack symbols and input symbols may be from two different alphabets, although there should be some connection in between.)
  Transitions: 
     (q0, a, e) --> (q0, A)
     (q0, b, A) --> (q1, e)
     (q1, b, A) --> (q1, e)
  
• How are ab, aabb accepted and ba, aaab, aabb rejected?
• What role does the stack symbol A plays in this automaton?
  Answer: It is used as a counter to keep track of the number of a's in the initial part of the input string.

Deterministic vs. non-deterministic

• Deterministic: there is at most one move for any situation (current state, next input symbol to be read, and the topmost symbol in the stack). Formally put, a PDA is deterministic iff there are not two instructions
  •    (qi, a, A) --> (qj, r) and
  •    (qi, a, A') --> (qk, s)
    such that A=A' or A=e or A'= e.
• Non-deterministic PDA's are not equivalent to deterministic PDA's, they accept different languages

Equivalence of context free languages and non-deterministic PDA languages

• Conversion from CFG to NPDA
    (1) Initial symbol: (q0, e, e) --> (q1, S)
    (2) Rule: A --> x ==> (q1, e, A) --> (q1, x)
    (3) Terminals: (q1, a, a) --> (q1, e)
• Example: G={V_N, V_T, S, R} or the language {aⁿbⁿ | n>=0}
  V_N = {S}, V_T = {a, b}, R = { S --> aSb, S --> e}
  
  The correspondent NPDA:
     State: {q0, q1}  Initial state: q0; Final states: {q0, q1}
     Input Alphabet: {a, b}
     Stack Alphabet: {S, a, b}
     Transitions: 
        (q0, e, e) --> (q1, S)
        (q1, e, S) --> (q1, aSb)
        (q1, e, S) --> (q1, e)
        (q1, a, a) --> (q1, e)
        (q1, b, b) --> (q1, e)