Compiler Design and Construction - Old Questions

4.  Explain the role of the parser. Write an algorithm for non-recursive predictive parsing.

A syntax analyzer or parser takes the input from a lexical analyzer in the form of token streams. The parser analyzes the source code (token stream) against the production rules to detect any errors in the code. The output of this phase is a parse tree.

The parser obtains a string of tokens from the lexical analyzer and verifies that the string can be generated by the grammar for the source language. It has to report any syntax errors if occurs.

The tasks of parser can be expressed as

• Analyzes the context free syntax
• Generates the parse tree
• Provides the mechanism for context sensitive analysis
• Determine the errors and tries to handle them

Algorithm for non-recursive predictive parsing:

1. Set ip to the first symbol of the input string.

2. Set the stack to $S where S is the start symbol of the grammar G.

3. Let X be the top stack symbol and ‘a’ be the symbol pointed by ip then

  Repeat

    a. If X is a terminal or ‘$’ then

        i. If X = a then pop X from the stack and advance ip

        ii. else error()

    b. Else

        If M[X,a] = Y₁Y₂Y₃....... Y_k then

            1. Pop X from Stack

            2. Push Y_k , Y_k-1, .....Y₂, Y₁ on the stack with Y₁ on top.

            3. Output the production X → Y₁Y₂Y₃....... Y_k

Until X = ‘$’.