Spread Knowledge

CS606 - Compiler Construction - Lecture Handout 12

User Rating:  / 0

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

Parse Trees

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

Parse Trees'


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

parse tree under leftmost

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

Ambiguous Grammars

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:

sentential form

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:

  1. Stmt ? If E then Stmt
  2. | If E then WithElse else Stmt
  3. | Assignment
  4. WithElse ? If E then WithElse else WithElse
  5. | Assignment

Let derive the following using the rewritten grammar:

rewritten grammar

Context-Free Grammars

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

Parsing Techniques

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

Top-down parsers

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.

Bottom-up parsers

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