Operator precedence parsing

Why it exists

The string 5 + 3 * 2 could mean $(5 + 3) \times 2$ or $5 + (3 \times 2)$. A grammar such as $E \to E + E \mid E * E \mid \text{id}$ says nothing about it: it is ambiguous. Compilers settle the question with two rules for each operator, its precedence (which operator binds tighter) and its associativity (how a chain of equal operators groups: $8 - 4 - 2$ is $(8 - 4) - 2$). There are three ways to put these rules into a parser: write them into the grammar (one nonterminal per precedence level), declare them to a parser generator (yacc's %left and %right), or use a parser driven directly by a table of precedence relations between terminals: the operator precedence parser. GATE asks to evaluate or parse an expression under an unusual precedence table, to read precedence and associativity off a grammar or a parse tree, and what yacc does with an ambiguous expression grammar.

Prerequisites

You need the stack, the handle and the shift and reduce moves of shift-reduce parsing, and the idea of an ambiguous grammar.

Precise definitions

Precedence and associativity. If operator $\circ_1$ has higher precedence than $\circ_2$, then in $a \circ_2 b \circ_1 c$ the operator $\circ_1$ is applied first: $a \circ_2 (b \circ_1 c)$. If $\circ$ is left associative, $a \circ b \circ c = (a \circ b) \circ c$; if right associative, $a \circ (b \circ c)$. Operators of equal precedence are assumed to share one associativity. The precedence and associativity of the operators in a language are a table, and the value of an expression depends on it.

In a grammar. One nonterminal per precedence level, and recursion on the side of the associativity:

$E \to E + T \mid T, \qquad T \to T * F \mid F, \qquad F \to (E) \mid \text{id}$

Left recursion ($E \to E + T$) makes the operator left associative; right recursion ($E \to T + E$) makes it right associative; an operator introduced in a lower level (here $*$ in $T$, below $+$ in $E$) has higher precedence, because the parser must complete a $T$ before the $E$ can use it. The same grammar read from a parse tree: the operator nearest the root is applied last.

Operator grammar. An operator grammar has no production with an empty right side and none with two adjacent nonterminals. $E \to E + E \mid E * E \mid \text{id}$ is one; $E \to E\, A\, E$ with $A \to + \mid *$ is not (two nonterminals side by side), and neither is $S \to a S b \mid \varepsilon$. Operator precedence parsing is defined only for these.

The relations. An operator precedence parser looks only at terminals. For two terminals $a$ (the topmost terminal on the stack) and $b$ (the next input) the table gives one of

• $a \lessdot b$: $b$ binds tighter, push $b$;
• $a \doteq b$: $a$ and $b$ belong to one handle (a pair of brackets), push $b$;
• $a \gtrdot b$: $a$ binds tighter (or equally, on the left), reduce first;
• empty: syntax error.

Built from the operator table: for two operators, $a \gtrdot b$ if $a$ has higher precedence than $b$, $a \lessdot b$ if lower; at equal precedence $a \gtrdot b$ if they are left associative and $a \lessdot b$ if right associative. Also $\text{id} \gtrdot$ every operator, ) and $; every operator $\lessdot$ id and (; every operator $\gtrdot$ ) and $; ( $\lessdot$ operators, id and (; ( $\doteq$ ); $ $\lessdot$ operators, id and (; two operands in a row (id id), id followed by (, ) followed by id: error.

The parser. Stack of terminals and the nonterminal $E$, starting with $; input followed by $. Repeat: let $a$ be the topmost terminal on the stack and $b$ the next input terminal. If a and b are both $ and the stack is $ E, accept. If $a \lessdot b$ or $a \doteq b$: shift $b$. If $a \gtrdot b$: reduce: pop the handle, the symbols above the last terminal that is related to the one below it by $\lessdot$ (with an $E$ directly below included), and replace it by $E$. If there is no relation: error. The handles are id, E op E and ( E ).

Properties. It is simple and fast, and handles the ambiguous-looking expression grammar with a small table (one entry per pair of terminals, not per state). It accepts only operator grammars; it can miss a syntax error in a grammar that is not carefully written, because it never looks at nonterminals; it handles unary minus awkwardly (the same token is unary and binary). Bottom-up parsers for a more general class of grammars are LR parsers.

Yacc and ambiguous grammars. Given $E \to E + E \mid E * E \mid \text{id}$, a parser generator builds an LALR(1) table with shift-reduce conflicts: after $E + E$ with lookahead * it can reduce by $E \to E + E$ or shift the *. Yacc reports each conflict and resolves it by rules:

1. If the production and the lookahead token both have declared precedence (%left, %right, %nonassoc; later declarations bind tighter; a production takes the precedence of its last terminal): the higher wins: reduce if the production is higher, shift if the token is higher.
2. If equal: %left means reduce, %right means shift, %nonassoc means error.
3. If either has no declared precedence: shift (the default). A reduce-reduce conflict is resolved in favour of the production that appears first.

So an expression grammar with no declarations parses everything as if all operators were right associative and the rightmost operator tightest: $id * id + id$ becomes $id * (id + id)$.

How it works

The relation table for $+$ (left), $*$ (left, tighter) and $\wedge$ (right, tightest), built from precedence and associativity alone. Row: the topmost terminal on the stack; column: the next input.

A parse of $\text{id} + \text{id} * \text{id} \wedge \text{id}$: the stack, the input, the relation that was consulted (outlined in the table), and the tree that grows. Each $\gtrdot$ forces a reduce, so $\wedge$ is reduced first, then $*$, then $+$.

Right associativity. $\text{id} \wedge \text{id} \wedge \text{id}$: since $\wedge \lessdot \wedge$, the second $\wedge$ is pushed instead of reducing the first, and the tree leans to the right.

The same string under four tables. Precedence and associativity decide the value.

Yacc. The ambiguous grammar has four conflicts:

and the parse tree of four inputs depends on the declarations:

Grammars. Associativity and precedence read off a grammar by listing all its parse trees for a string, and which grammars are operator grammars:

Worked examples

#include <stdio.h>
 
/* operators + - * / are indexes 0..3; prec: higher binds tighter; right[i]: 1 if right associative */
static int apply(char op, int a, int b) {
    switch (op) {
    case '+': return a + b;
    case '-': return a - b;
    case '*': return a * b;
    default: return a / b;
    }
}
 
static int index_of(char op) {
    return op == '+' ? 0 : op == '-' ? 1 : op == '*' ? 2 : 3;
}
 
static int eval(const int *vals, const char *ops, int n, const int *prec, const int *right) {
    int out[16], top = -1;
    char stack[16];
    int sp = -1;
    out[++top] = vals[0];
    for (int i = 0; i < n - 1; i++) {
        int p = prec[index_of(ops[i])], r = right[index_of(ops[i])];
        while (sp >= 0 && (prec[index_of(stack[sp])] > p || (prec[index_of(stack[sp])] == p && !r))) {
            int b = out[top--], a = out[top--];
            out[++top] = apply(stack[sp--], a, b);
        }
        stack[++sp] = ops[i];
        out[++top] = vals[i + 1];
    }
    while (sp >= 0) {
        int b = out[top--], a = out[top--];
        out[++top] = apply(stack[sp--], a, b);
    }
    return out[0];
}
 
int main(void) {
    int vals[6] = {5, 3, 2, 8, 4, 1};
    char ops[5] = {'+', '*', '-', '/', '+'};
    /* order of the columns: + - * / */
    int p1[4] = {1, 1, 2, 2}, r1[4] = {0, 0, 0, 0};
    int p2[4] = {1, 1, 1, 1}, r2[4] = {0, 0, 0, 0};
    int p3[4] = {1, 1, 1, 1}, r3[4] = {1, 1, 1, 1};
    int p4[4] = {4, 3, 2, 1}, r4[4] = {0, 1, 1, 1};
    printf("usual table:                         %d\n", eval(vals, ops, 6, p1, r1));
    printf("all equal, left associative:         %d\n", eval(vals, ops, 6, p2, r2));
    printf("all equal, right associative:        %d\n", eval(vals, ops, 6, p3, r3));
    printf("+ tightest, then -, *, / (right):    %d\n", eval(vals, ops, 6, p4, r4));
    return 0;
}

usual table:                         10
all equal, left associative:         3
all equal, right associative:        8
+ tightest, then -, *, / (right):    -9

#include <stdio.h>
#include <string.h>
 
/* terminals in the order + * ^ i ( ) $ ; i stands for id; the stack also holds E */
static const char *T = "+*^i()$";
static const char rel[7][8] = {          /* rel[a][b]: stack top a, next input b; '<' push, '=' push, '>' reduce, ' ' error */
    {'>', '<', '<', '<', '<', '>', '>'},
    {'>', '>', '<', '<', '<', '>', '>'},
    {'>', '>', '<', '<', '<', '>', '>'},
    {'>', '>', '>', ' ', ' ', '>', '>'},
    {'<', '<', '<', '<', '<', '=', ' '},
    {'>', '>', '>', ' ', ' ', '>', '>'},
    {'<', '<', '<', '<', '<', ' ', ' '}};
 
static int idx(char c) { return (int)(strchr(T, c) - T); }
 
static void show(const char *stack, int n, const char *in) {
    printf("stack:");
    for (int i = 0; i < n; i++) printf(stack[i] == 'i' ? " id" : " %c", stack[i]);
    printf("   input:");
    for (const char *p = in; *p; p++) printf(*p == 'i' ? " id" : " %c", *p);
}
 
int main(void) {
    char stack[32] = "$";
    int n = 1;
    const char *in = "i+i*i^i$";
    show(stack, n, in);
    printf("   start\n");
    for (;;) {
        int top = n - 1;
        while (stack[top] == 'E') top--;
        char a = stack[top], b = *in;
        if (a == '$' && b == '$' && n == 2 && stack[1] == 'E') {
            printf("accept\n");
            return 0;
        }
        char r = rel[idx(a)][idx(b)];
        if (r == ' ') {
            printf("error\n");
            return 1;
        }
        if (r == '<' || r == '=') {
            stack[n++] = b;
            in++;
            show(stack, n, in);
            printf("   shift %s\n", b == 'i' ? "id" : (char[]){b, 0});
        } else {
            int k = n;                                       /* find the start of the handle */
            for (;;) {
                k--;
                if (stack[k] == 'E') continue;
                int below = k - 1;
                while (below >= 0 && stack[below] == 'E') below--;
                if (below < 0 || rel[idx(stack[below])][idx(stack[k])] == '<') break;
            }
            if (k > 0 && stack[k - 1] == 'E') k--;
            int len = n - k;
            n = k;
            stack[n++] = 'E';
            show(stack, n, in);
            printf("   reduce %d symbol%s to E\n", len, len == 1 ? "" : "s");
        }
    }
}

stack: $   input: id + id * id ^ id $   start
stack: $ id   input: + id * id ^ id $   shift id
stack: $ E   input: + id * id ^ id $   reduce 1 symbol to E
stack: $ E +   input: id * id ^ id $   shift +
stack: $ E + id   input: * id ^ id $   shift id
stack: $ E + E   input: * id ^ id $   reduce 1 symbol to E
stack: $ E + E *   input: id ^ id $   shift *
stack: $ E + E * id   input: ^ id $   shift id
stack: $ E + E * E   input: ^ id $   reduce 1 symbol to E
stack: $ E + E * E ^   input: id $   shift ^
stack: $ E + E * E ^ id   input: $   shift id
stack: $ E + E * E ^ E   input: $   reduce 1 symbol to E
stack: $ E + E * E   input: $   reduce 3 symbols to E
stack: $ E + E   input: $   reduce 3 symbols to E
stack: $ E   input: $   reduce 3 symbols to E
accept

#include <stdio.h>
 
int main(void) {
    int a, b;
    printf("5 + 3 * 2 - 8 / 4 + 1 = %d\n", 5 + 3 * 2 - 8 / 4 + 1);
    printf("8 - 4 - 2 = %d   (left associative: (8 - 4) - 2)\n", 8 - 4 - 2);
    printf("100 / 10 / 5 = %d   (left associative: (100 / 10) / 5)\n", 100 / 10 / 5);
    printf("2 * 3 %% 4 = %d   (same level, left to right: (2 * 3) %% 4)\n", 2 * 3 % 4);
    printf("-2 * -3 = %d   (unary minus binds tighter than *)\n", -2 * -3);
    a = b = 7;
    printf("a = b = 7: a is %d, b is %d   (assignment is right associative: a = (b = 7))\n", a, b);
    printf("1 + 2 * 3 > 6 && 4 < 5 = %d   (arithmetic, then comparison, then &&)\n", 1 + 2 * 3 > 6 && 4 < 5);
    return 0;
}

5 + 3 * 2 - 8 / 4 + 1 = 10
8 - 4 - 2 = 2   (left associative: (8 - 4) - 2)
100 / 10 / 5 = 2   (left associative: (100 / 10) / 5)
2 * 3 % 4 = 2   (same level, left to right: (2 * 3) % 4)
-2 * -3 = 6   (unary minus binds tighter than *)
a = b = 7: a is 7, b is 7   (assignment is right associative: a = (b = 7))
1 + 2 * 3 > 6 && 4 < 5 = 1   (arithmetic, then comparison, then &&)

Cheat box

Traps and GATE patterns

Connections

An operator precedence parser is a shift-reduce parser whose handle-finding is replaced by a table over terminals. The same information is hidden in the extra nonterminals of the layered grammar that removes the ambiguity, and in yacc's declarations for the LALR(1) parser of CLR and LALR; compare the classes of grammars in the parser comparison.

PYQs

Consider the operator precedence and associativity
rules for the integer arithmetic operators given in
the table below.
Operator
Precedence
Associativity
+
Highest
Left
-
High
Right
*
Medium
Right
/
Low
Right

The value of the expression 3 + 1 + 5 *2/7 +
          2 - 4 -7 -6/2 as per the above rules is ___

Consider the following parse tree for the expression
a#b$c$d#e#f, involving two binary operators $ and #.

Which one of the following is correct for the given
parse tree?

Consider the grammar defined by the following
production rules, with two operators * and +

S → T * P

T → U | T * U

P → Q + P | Q

Q → Id

U → Id

Which one of the following is TRUE?

Consider two binary operators '↑' and '↓' with the
precedence of operator ↓ being lower than that of the
operator ↑. Operator ↑ is right associative while
operator ↓ is left associative. Which one of the
following represents the parse tree for expression
(7↓3↑4↑3↓2) ?

Consider the following expression grammar. The
seman-tic rules for expression calculation are stated
next to each grammar production.

E → number
 E.val = number. val

        | E '+' E
 E(1).val = E(2).val + E(3).val

        | E '×' E
 E(1).val = E(2).val × E(3).val

The above grammar and the semantic rules are fed to
a Yacc tool (which is an LALR (1) parser generator)
for parsing and evaluating arithmetic expressions.
Which one of the following is true about the action of
Yacc for the given grammar?

Self-check

Revision card

References