OPERATOR PRECEDENCE PARSING

Operator Grammars: no production right side is e or has two adjacent non-terminals.

Precedence Relations

In operator-precedence parsing, we define three disjoint precedence relations between certain pairs of terminals.
            
              a <. b       b has higher precedence than a

       a =.b        b has same precedence as a

       a .> b       b has lower precedence than a

The determination of correct precedence relations between terminals are based on the traditional notions of associativity and precedence of operators. (Unary minus causes a problem).

Methods

Two Methods to determine a precedence relation between a pair of terminals

1. Based on associativity and precedence relations of operators

2. Using Operator Precedence Grammar

Compute LEADING (A)

• LEADING (A) = {a| A → γaδ, where γ is ε or a single non-terminal.}

• Rule 1: a is in LEADING (A) if there is a production of the form A → γaδ, Where γ is ε or a single non-terminal

• Rule 2: a is in LEADING (B) and if there is a production of the form A → Bα, then a is in LEADING (A)

Compute TRAILING (A)

• TRAILING (A) = {a| A → γaδ, where δ is ε or a single non-terminal.}

• Rule 1: a is in TRAILING (A) if there is a production of the form A → γaδ, Where δ is ε or a single non-terminal

• Rule 2: a is in TRAILING (B) and if there is a production of the form

A → αB, then a is in TRAILING (A)

 Example: