**Related Content:** CS606 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Compiler Construction

The derivations can be represented in a tree-like fashion. The interior nodes contain the non-terminals used during the derivation

'

These two derivations point out a problem with the grammar. It has no notion of
precedence, or implied order of evaluation. The normal arithmetic rules say that
multiplication has higher precedence than subtraction. To add precedence, create a non- terminal for each level of precedence. Isolate corresponding part of grammar to force

parser to recognize high precedence sub-expressions first. Here is the revised grammar:

This grammar is larger and requires more rewriting to reach some of the terminal symbols. But it encodes expected precedence. Let’s see how it parses

x – 2 * y

This produces same parse tree under leftmost and rightmost derivations

Both leftmost and rightmost derivations give the same expression because the grammar directly encodes the desired precedence.

If a grammar has more than one leftmost derivation for a single sentential form, the grammar is ambiguous. The leftmost and rightmost derivations for a sentential form may differ, even in an unambiguous grammar. Let’s consider the classic if-then-else example

**Stmt ? if Expr then Stmt
| if Expr then Stmt else Stmt
| … other stmts ….**

The following sentential form has two derivations:

The convention in most programming languages is to match the else with the most recent if.

We can rewrite grammar to avoid generating the problem and match each else to innermost unmatched if:

**Stmt ? If E then Stmt****| If E then WithElse else Stmt****| Assignment****WithElse ? If E then WithElse else WithElse****| Assignment**

Let derive the following using the rewritten grammar:

We have been using the term context- free without explaining why such rules are in fact “free of context”. The simple reason is that non-terminals appear by themselves to the left of the arrow in context-free rules:

A ? a

The rule A? a says that A may be replaced by a anywhere, regardless of where A
occurs. On the other hand, we could define a context as pair of strings b, g, such that a
rule would apply only if b occurs before and g occurs after the non-terminal A. We would
write this as

**b A g ? b a g**

Such a rule in which a ? e is called a context-sensitive grammar rule. We would write
this as

**b A g ? b a g**

Such a rule in which a ? e is called a context-sensitive grammar rule

There are two primary parsing techniques: top-down and bottom- up.

A top-down parsers starts at the root of the parse tree and grows towards leaves. At each node, the parser picks a production and tries to match the input. However, the parser may pick the wrong production in which case it will need to backtrack. Some grammars are backtrack- free.

A bottom- up parser starts at the leaves and grows toward root of the parse tree. As input is consumed, the parser encodes possibilities in an internal state. The bottom- up parser starts in a state valid for legal first tokens. Bottom-up parsers handle a large class of grammars