Lecture No. 12

Dated: 20-03-2025

Parse Trees

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

Left most deviation. Evaluation order \(x - (2 * y)\).

Right most deviation. Evaluation order \((x - 2) * y\).

Precedence

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:

1 Goal   -> expr
2 expr   -> expr + term   \
3        |  expr - term    |- Level One
4        |  term          /
5 term   -> term . factor \
6        |  term / factor  |- Level Two
7        |  factor        /
8 factor -> number
9        |  id

Rule	Sentential Form
-	Goal
1	Expr
3	expr – term
5	expr – term. factor
9	expr – term. <id,y>
7	expr – factor. <id,y>
8	expr – <num,2>. <id,y>
4	term – <num,2>. <id,y>
7	factor – <num,2>. <id,y>
9	<id,x> – <num,2>. <id,y>

Evaluation order \(x - (2 * y)\).

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.

The following sentential form has two deviations.
if \(E_1\) then if \(E_2\) then \(S\) else \(S_2\).

if E1 then
    if E2 then S1
else S2

if E1 then
    if E2 then S1
    else S2

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

Context Free Grammars

The rules in context free grammar are called context free because the non-terminals occur by themselves to the left of the arrow.

Example

\[A \to a\]

This rules says that where ever there is an \(A\), it can be replaced by \(a\).

Context Sensitive Grammar Rule

On the other hand

\[\beta A \gamma \to \beta a \gamma\]

This rules defines a context as pair of strings¹ \(\beta A \gamma\).
Such a rule in which \(a \to \epsilon\) is called context sensitive grammar rule.

Parsing Techniques

Top down

A top-down parser 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.
It works for some grammars.

Bottom up

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.

References

---

1. Read more about fundamentals. ↩

2. Read more about parsers and tokens. ↩↩