Define left most, right most derivation and ambiguity. Define left most, right most derivation and ambiguity.

Left most derivative: If at each step in a derivation a production is applied to the left most variable, then the derivation is said to be left most derivative.

Right most derivation: If at each step in a derivation a production is applied to the right most variable, then the derivation is said to be right most derivation.

Example:

S → aAS | a

A → Sba | SS | ba

Left most:

S → aAS

→ aSbAS

→ aabAS

→ aabbaS

→ aabbaa

Right most:

S → aAS

→ aAa

→ aSbAa

→ aSbbaa

→ aabbaa

Ambiguity or, Ambiguous Grammar: Ambiguous grammar is a context free grammar G such that some word has two parse trees. Some word has more than one right most derivation in an ambiguous grammar.

Example: Let we have the grammar G with the following production rules.

E → E + E / E * E / id

We can show that grammar,

E → id + id * id is ambiguous

Here, we have two different left most derivations.

E → E + E

→ id + E

→ id + E * E

→ id + id * E

→id + id * id

E → E * E

→ E + E * E