Mumbai University > Computer Engineering > Sem6 > System Programming and Compiler Construction

Marks: 10M

Year: May 2015

Precedence Relations

• Bottom-up parsers for a large class of context-free grammars can be easily developed using operator grammars.
• Operator grammars have the property that no production right side is empty or has two adjacent nonterminal.
• This property enables the implementation of efficient operator-precedence parsers.
• These parser rely on the following three precedence relations:

• These operator precedence relations allow to delimit the handles in the right sentential forms: <• marks the left end, =. appears in the interior of the handle, and .> marks the right end.

• Let assume that between the symbols ai and ai+1 there is exactly one precedence relation. Suppose that $\$$ is the end of the string.

• Then for all terminals we can write: $\$$ <• b and b •> $\$$. If we remove all nonterminal and place the correct precedence relation :<•, =•, •> between the remaining.

terminals, there remain strings that can be analyzed by easily developed parser.

• For example, the following operator precedence relations can be introduced for simple expressions:

Example: The input string:

$id_1 + id_2 * id_3$

after inserting precedence relations becomes

$\$$ <• id1 •> + <• id2•>* <• id3 •> $\$$

• Having precedence relations allows to identify handles as follows:

  -Scan the string from left until seeing •>

  -Scan backwards the string from right to left until seeing <•

  -Everything between the two relations <• and •> forms the handle.

Note that not the entire sentential form is scanned to find the handle.

Operator Precedence Parsing Algorithm

Initialize: Set ip to point to the first symbol of w$\$$

Repeat: Let X be the top stack symbol, and a the symbol pointed to by ip

If $ is on the top of the stack and ip points to $ then return
                Else
                Let a be the top terminal on the stack, and b the symbol pointed to by ip
                    If a<• b or a =• b then
                        Push b onto the stack
                        Advance ip to the next input symbol
                    Else if a •>bthen
                        repeat
                            Pop the stack
                        until the top stack terminal is related by <•
                            to the terminal most recently popped
                    else error ()
                end

Making Operator Precedence Relations

• 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 relations 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.

Algorithm for Constructing Precedence Functions

1. Create functions $f_a$ for each grammar terminal a and for the end of string symbol;
2. Partition the symbols in groups so that $f_a$ and $g_b$ are in the same group if a =• b (there can be symbols in the same group even if they are not connected by this relation);

3. Create a directed graph whose nodes are in the groups, next for each symbols a and b do: place an edge from the group of $g_b$ to the group of fa if a <• b, otherwise if a •>b place an edge from the group of fa to that of $g_b$;

4. If the constructed graph has a cycle then no precedence functions exist. When there are no cycles collect the length of the longest paths from the groups of fa and gb respectively.

Example: Consider the above table

Using the algorithm leads to the following graph:

From which we extract the following precedence functions:

Error Recovery in operator-precedence parsing:

There are two points in the parsing process at which an operator-precedence parser can discover syntactic error:

• If no precedence relation holds between the terminal on top of the stack and the current input.
• If a handle has been found, but there is no production with this handle as a right side.

The error checker does the following errors:

• Missing operand
• Missing operator
• No expression between parenthesis
• Illegal b on line (line containing b)
• Missing d on line (line containing c)
• Missing E on line (line containing b)

These error diagnostic issued at handling of errors during reduction.

During handling of shift/reduce errors; the diagnostic’s issues are:

• Missing operand
• Unbalanced right parenthesis
• Missing right parenthesis
• Missing operator

Advantages:

• Simplicity, easy to construct by hand

Disadvantages:

• It is hard to handle tokens like the unary operators

• Since the relationship between a grammar for the language being parsed and the operator precedence parser itself is tenuous, one cannot always be sure the parser accepts exactly the desired language.

• Only a small class of grammars can be parsed using operator-precedence techniques.