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

Adblocker detected! Please consider reading this notice.

We've detected that you are using AdBlock Plus or some other adblocking software which is preventing the page from fully loading.

We don't have any banner, Flash, animation, obnoxious sound, or popup ad. We do not implement these annoying types of ads!

We need money to operate the site, and almost all of it comes from our online advertising.

Please add wikitechy.com to your ad blocking whitelist or disable your adblocking software.

×