GATE CS 2000 Q2.21 — Parsing (LL, LR)

In a context-free grammar representing expressions, the precedence of operators is determined by their position in the derivation hierarchy:

• Operators defined in non-terminals closer to the start symbol (higher in the grammar) have lower precedence.
• Operators defined in non-terminals further from the start symbol (lower in the grammar, closer to the operands) have higher precedence because they group more tightly.

Let's analyze the given grammar:

$$\begin{align*}E &\to E * F \mid F + E \mid F \\F &\to F - F \mid id\end{align*}$$

Here, $E$ is the start symbol, which defines the operators $*$ and $+$. The non-terminal $F$ is lower in the hierarchy (since $E$ derives $F$) and defines the operator $-$.

Since $F$ is at a lower level in the grammar than $E$, the operator $-$ has higher precedence than both $*$ and $+$.

Example: Consider the expression $id * id - id$. The parse tree for this expression is:

      E
     /|\
    E * F
    |  /|\
    F F - F
    | |   |
   id id  id

In this tree, the subtraction ($id - id$) is grouped as a sub-tree under $F$ and must be evaluated before the multiplication ($*$) at $E$. This structurally demonstrates that $-$ has higher precedence than $*$.