πŸŽ“ Computer Science & Engineering Portal

Master Engineering Disciplines with Structured Notes

Comprehensive academic lecture notes, exam-oriented unit summaries, laboratory manuals, and previous year question papers designed strictly for university students.

πŸ“‘

University Syllabi

AKTU & AICTE aligned semester guidelines.

πŸ“

Exam Question Papers

Previous 5 years solved university papers.

πŸ’‘

Lab Manuals & Viva

Practical codes with outputs & interview Qs.

Core Subjects & Units Hub

Click on any specific unit to immediately view its lecture notes below

Viewing All Lectures

Unambiguous Grammar

Unambiguous Grammar

A grammar can be unambiguous if the grammar does not contain ambiguity that means if it does not contain more than one leftmost derivation or more than one rightmost derivation or more than one parse tree for the given input string.

To convert ambiguous grammar to unambiguous grammar, we will apply the following rules:

1. If the left associative operators (+, -, *, /) are used in the production rule, then apply left recursion in the production rule. Left recursion means that the leftmost symbol on the right side is the same as the non-terminal on the left side. For example,

X β†’ Xa  

2. If the right associative operates(^) is used in the production rule then apply right recursion in the production rule. Right recursion means that the rightmost symbol on the left side is the same as the non-terminal on the right side. For example,

X β†’ aX  

Example 1:

Consider a grammar G is given as follows:

S β†’ AB | aaB  

A β†’ a | Aa  

B β†’ b  

Determine whether the grammar G is ambiguous or not. If G is ambiguous, construct an unambiguous grammar equivalent to G.

Solution:

Let us derive the string "aab"

Unambiguous Grammar

As there are two different parse tree for deriving the same string, the given grammar is ambiguous.

Unambiguous grammar will be:

S β†’ AB  

A β†’ Aa | a  

B β†’ b  

Example 2:

Show that the given grammar is ambiguous. Also, find an equivalent unambiguous grammar.

S β†’ ABA  

A β†’ aA | Ξ΅  

B β†’ bB | Ξ΅  

Solution:

The given grammar is ambiguous because we can derive two different parse tree for string aa.

Unambiguous Grammar

The unambiguous grammar is:

S β†’ aXY | bYZ | Ξ΅  

Z β†’ aZ | a  

X β†’ aXY | a | Ξ΅  

Y β†’ bYZ | b | Ξ΅ 

Example 3:

Show that the given grammar is ambiguous. Also, find an equivalent unambiguous grammar.

E β†’ E + E  

E β†’ E * E  

E β†’ id  

Solution:

Let us derive the string "id + id * id"

Unambiguous Grammar

As there are two different parse tree for deriving the same string, the given grammar is ambiguous.

Unambiguous grammar will be:

E β†’ E + T  

E β†’ T  

T β†’ T * F  

T β†’ F  

F β†’ id  

Example 4:

Check that the given grammar is ambiguous or not. Also, find an equivalent unambiguous grammar.

S β†’ S + S  

S β†’ S * S  

S β†’ S ^ S  

S β†’ a  

Solution:

The given grammar is ambiguous because the derivation of string aab can be represented by the following string:

Unambiguous Grammar

Unambiguous grammar will be:

S β†’ S + A |  

A β†’ A * B | B  

B β†’ C ^ B | C  

C β†’ a  


Labels: ,

Discussion & Queries (<$I18NNumComments$>):

<$CommentPager$>
<$I18NAtCommentTimeWithPermalink$>, <$I18NCommentAuthorSaid$>

<$BlogCommentBody$>

<$BlogCommentDeleteIcon$>
 <$CommentPager$>