Predictive Parsing Algorithm | Compiler Design Predictive Translation




Compiler Design Predictive Translation

  • The following algorithm generalizes the construction of predictive parsers to implement a translation scheme based on a grammar suitable for top-down parsing.

Algorithm:

  • Construction of a predictive syntax-directed translator.

Input:

  • A syntax-directed translation scheme with an underlying grammar suitable for predictive parsing.

Output:

  • Code for a syntax-directed translator.

Method:

The technique is a modification of the predictive-parser construction

  • For each nonterminal A, construct a function that has a formal parameter for each inherited attribute of A and that returns the values of the synthesized attributes of A
  • The code for nonterminal A decides what production to use based on the current input symbol.
  • The code associated with each production does the following. We consider the tokens, nonterminals, and actions on the right side of the production from left to right.
    • For token X with synthesized attribute x, save the value of x in the variable declared for X.x. Then generate a call to match token X and advance the input.
    • For nonterminal B, generate an assignment c := B ( b1, b2, …, bk) with a function call on the right side, where b1, b2, …, bk are the variables for the inherited attributes of B and c is the variable for the synthesized attribute of B.
    • For an action, copy the code into the parser, replacing each reference to an attribute by the variable for that attribute.

Example

  • The grammar is LL( 1 ) and hence suitable for top-down parsing can be generated by predicting a suitable production rule.
E -> E1 + T {E.nptr := mknode('+', E1.nptr, T.nptr)}
E -> E1 - T {E.nptr := mkrtodr('-', E1.nptr, T.nptr)}
E -> T {E.nptr := T.nptr}
E -> R {E.nptr := R.nptr}
R -> E
T -> id {T.nptr := mkleaf(id, id.entry)}
T -> num {T.nptr := mkleaf(num, num.entry)}

Combine two of the E-productions to make the translator smaller. The new productions use token op to represent + and -.

E -> E1 op T {E.nptr := mknode('op', E1.nptr, T.nptr)}
E -> T {E.nptr := T.nptr}
E -> R {E.nptr := R.nptr}
R -> E
T -> id {T.nptr := mkleaf(id, id.entry)}
T -> num {T.nptr := mkleaf(num, num.entry)}


Related Searches to Predictive Parsing Algorithm | Compiler Design Predictive Translation