Ambiguous Grammar

In this class, We discuss Ambiguous Grammar.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of the derivation tree for Context-free grammar. Click Here.

Take an example and understand ambiguous grammar.

Example:

T = {a,b,+,*} list of input symbols or terminals.

The below grammar is our CFG.

S – S + S

S – S * S

S – a

S – b

Take an input string a+b*a

We can derive the input string in two different ways.

The below diagrams show the derivation trees of the input string a+b*a.

Ambiguous Grammar 1.1
First Derivative Tree

The first derivation tree is elaborated as a+(b*c).

Ambiguous Grammar 1.2
Second Derivative Tree

The second derivation tree is elaborated as (a+b)*a.

For the same input string, we have two different derivation trees.

The grammar that generates more than one derivation tree for a given input string we call ambiguous grammar.

Take a look at the above grammar.

From the above grammar, we are evaluating the expressions.

Evaluating expressions is one of the applications of context-free grammar.

We use this in compiler design.

Similarly, In compiler design, we check the mistakes in syntax. This is done using finite automata.

We study syntax analysis and expression evaluation in our compiler design course.