13 PARSING ACTION OF OPERATOR PRECEDENCE PARSER AND PRECEDENCE FUNCTION

Rajeswari Sridhar

After learning to construct the operator precedence parsing table, in this module we would learn the operator precedence parsing algorithm with an example and the errors that is encountered by an Operator Precedence parser. The precedence graph and precedence function associated with the operator precedence parser will also be discussed in this module.

 

13.1 Ope rator Precedence parsing

 

We have seen the first three steps in the Operator precedence parser. Verifying whether a grammar is operator precedence, computing of LEADING, TRAILING and construction of operator precedence parsing table was already done in the previous module. The next step is the Parsing algorithm and is given in algorithm 13.1

 

Algorithm 13.1 (Grammar G, input string w, Parsing table T)

 

{set p to point to the first symbol of w$ ;

 

repeat forever

 

if ( $ is on top of the stack and p points to $ ) then return; // success else {

 

let a be the topmost terminal symbol on the stack; let b be the symbol pointed to by p;

 

1. if ( a <.b or a =· b ) then { /* SHIFT */

push b onto the stack;
advance p to the next input symbol;
}

2. else if ( a .
> b ) then /* REDUCE */
repeat pop stack
until ( the top of stack terminal is related by <.  to the terminal most  recently popped );
3. else error(); /*ERROR*/

}

 

}

 

The input string “w” is appended with a “$” symbol at the end and is converted to w$. The stack is initialized with the $ symbol to acts as the initial stack symbol. As this parser is a bottom- up parser, the four actions of shift, reduce, error, accepts is handled by this parser also. The parser announces successful parsing and acceptance of a string, if there is a $ that matches the stack and the input. This is given in the beginning of the algorithm. The next step of the

 

algorithm loops until the existence of a string. The stack symbol is compared with the input symbol for precedence relation in the parsing table. If the precedence relation is lesser than or equal to, then the input character is pushed on to the stack and thus making the input pointer advances by one position to the right. If the precedence relation is greater than, then we reduce by popping the stack till the top of stack terminal is related by <. to the terminal most recently popped. If there is no relation defined between the symbols in the stack and input, we announce an error action.

 

Example 13.1 Consider the input string id + id * id and let us see how the parsing action is carried out by the Operator precedence parser. For quick reference, the parsing table is given table 13.1 and the parsing action is given in Table 13.2

 

Table 13.1 Parsing table

13.2 Issues in Operator Precedence parsing.

 

Operator-Precedence parsing cannot handle the unary minus if the grammar has binary subtraction operator. The best approach to solve this problem is to tackle the unary operator at the lexical phase using one or both of the following approaches:

 

  • The lexical analyzer can be made to return two different tokens for the unary minus and the binary minus.
  • The lexical analyzer will need a lookahead to distinguish the binary minus from the unary minus.

After identifying this, we then define the precedence of the all operators in comparison with unary- minus as follows:

  • For any operator q, we set q <. unary- minus
  • We then modify the relation,
  • o if unary- minus has higher precedence than q, we set unary-minus .> q
  • o if unary- minus has lower (or equal) precedence than q , we set unary- minus <. q

 

After constructing the precedence table based on the rules discussed in this section, the parsing action is similar to what has been already discussed.

 

13.3 Precedence Functions

 

The operator precedence parsers usually do not store the precedence table with the relations, rather they are implemented in a special way. Operator precedence parsers use precedence functions that map terminal symbols to integers, and so the precedence re lations between the symbols are implemented by numerical comparison. Not every table of precedence relations has precedence functions but in practice for most grammars such functions can be designed.

 

The precedence table is typically stored as a precedence function. The precedence table is coded as two functions f() and g() corresponding to the row and table. The idea behind the precedence functions is to define nodes and edges for all the terminals of a grammar in terms of

 

the functions f() and g(). For symbols ‘a’ and ‘b’ we define the functions f(a) and g(b) based on the precedence between the operators ‘a’ and ‘b. The following is used as the basis.

  • if a <. b then f(a) < g(b)
  • if a =· b, then f(a) = g(b)
  • if a .> b, then f(a) > g(b)

The algorithm for constructing the precedence function is given in Algorithm 13.2 where the input will be the precedence table.

 

Algorithm 13.2

 

Precedence_Function(Precedence table T, Precedence Function f)

 

{

  1. Create symbols fa and gb for each ‘a’ that is a terminal or $.
  2. Partition the created symbols into as many groups as possible, in such a way that if a =. b, then fa and gb are in the same group.
  3. Create a directed graph whose nodes are the groups found in the previous step. For any ‘a’ and ‘b’, if a <.b , place an edge from the group of gb to the group of fa. If a .> b, place an edge from the group of fa to that of gb.
  4. If the graph constructed has a cycle, then no precedence functions exist. If there are no cycle, let f(a) be the length of the longest path beginning at the group of fa ; let g(a) be the length of the longest path beginning at the group of ga.

}

 

Algorithm 13.2 lists the steps involved in constructing the precedence graph. After constructing the precedence graph the precedence function computes the length of the longest path for all the terminals.

Example 13.2 Consider the expression grammar containing the terminals +. *, id and $ whose precedence table is defined in Table 13.1.

By step 2 of the algorithm, we could define the following functions for f() and g()

  • f+, f*, fi d, f$ are the four functions of ‘f’
  • g+, g*, gi d, g$ are the four function of ‘g’

Since, there is no equal precedence relation in this table, f() and g() for all the terminals will not be in the same group. Using step 3 of the algorithm 13.2 we construct the edges and is given in figure 13.1

 

 

13.4 Error handling in Operator Precedence Parser

 

The operator precedence parser can handle only a small class of grammars. However, it cannot handle the unary minus (the lexical analyzer should handle the unary minus). The issues in Operator precedence parser is it finds difficulty in deciding the language of the grammar. This parser cannot have a relation between the terminal on the top of stack and the next input symbol. A handle is found (reduction step), but there is no production with this handle as RHS.

 

However, to handle the small class of grammar the operator precedence parser has to perform error recovery by one of the following tasks:

  1. As in the LL(1) parser, each empty entry in the precedence table is filled with a pointer to an error routine.
  2. Matches what the popped handle resembles which right hand side of the production and tries to recover from that situation. In order to recover, we must modify (insert/change)
  • Stack or
  • Input or
  • Both

The error recovery routines can be grouped into four scenarios as described below:

 

e1: Scenario: Entire expression is missing: To handle this case, we insert “id” to the input and issue a message – ‘missing operand’ or ‘no input’

e2: Scenario: Expression begins with a right parenthesis: To handle this case, we delete ‘)’ from the input and issue message – ‘unbalanced right parenthesis’

e3: Scenario: Expression has, id or ) is followed by id or (. To handle this situation insert + to the input and issue message – ‘missing operator’

e4: Scenario: expression ends with a left parenthesis. To handle this case,     pop  ( from the stackand issue message: ‘missing right parenthesis’

 

The various scenarios are depicted in Table 13.4

 

Summary: This module discussed the parsing action of an Operator Precedence Parser. We also discussed precedence functions and some error recovery strategies of the operator precedence parser.