Skip to main content

Grammar Ambiguity | Check Ambiguous Grammar

Grammar Ambiguity-

Before you go through this article, make sure that you have gone through the previous article on Ambiguous Grammar.
  • There exists no algorithm to check whether any given grammar is ambiguous or not.
  • This general decision problem is undecidable-
“Whether a grammar is ambiguous or not?”
  • This is because it can be shown that this problem is equivalent to Post Correspondence Problem.

General Approach To Check Grammar Ambiguity-

To check whether a given grammar is ambiguous or not, we follow the following steps-

Step-01:

We try finding a string from the Language of Grammar such that for the string there exists more than one-
  • parse tree
  • or derivation tree
  • or syntax tree
  • or leftmost derivation
  • or rightmost derivation

Step-02:

If there exists at least one such string, then the grammar is ambiguous otherwise unambiguous.

PROBLEMS BASED ON CHECKING WHETHER GRAMMAR IS AMBIGUOUS-

Problem-01:

Check whether the given grammar is ambiguous or not-
S → SS
S → a
S → b

Solution-

Let us consider a string w generated by the given grammar-
w = abba
Now, let us draw parse trees for this string w.



Since two different parse trees exist for string w, therefore the given grammar is ambiguous.

Problem-02:

Check whether the given grammar is ambiguous or not-
S → A / B
A → aAb / ab
B → abB / ∈

Solution-

Let us consider a string w generated by the given grammar-
w = ab
Now, let us draw parse trees for this string w.

Since two different parse trees exist for string w, therefore the given grammar is ambiguous.

Problem-03:

Check whether the given grammar is ambiguous or not-
S → AB / C
A → aAb / ab
B → cBd / cd
C → aCd / aDd
D → bDc / bc

Solution-

Let us consider a string w generated by the given grammar-
w = aabbccdd
Now, let us draw parse trees for this string w.

Since two different parse trees exist for string w, therefore the given grammar is ambiguous.

Problem-04:

Check whether the given grammar is ambiguous or not-
S → AB / aaB
A → a / Aa
B → b

Solution-

Let us consider a string w generated by the given grammar-
w = aab
Now, let us draw parse trees for this string w.

Since two different parse trees exist for string w, therefore the given grammar is ambiguous.

Problem-05:

Check whether the given grammar is ambiguous or not-
S → a / abSb / aAb
A → bS / aAAb

Solution-

Let us consider a string w generated by the given grammar-
w = abababb
Now, let us draw parse trees for this string w.


Since two different parse trees exist for string w, therefore the given grammar is ambiguous.

Problem-06:

Check whether the given grammar is ambiguous or not-
E → E + T / T
T → T x F / F
F → id

Solution-

  • There exists no string belonging to the language of grammar which has more than one parse tree.
  • Since a unique parse tree exists for all the strings, therefore the given grammar is unambiguous.

Problem-07:

Check whether the given grammar is ambiguous or not-
S → aSbS / bSaS / ∈

Solution-

Let us consider a string w generated by the given grammar-
w = abab
Now, let us draw parse trees for this string w.


Since two different parse trees exist for string w, therefore the given grammar is ambiguous.

Problem-08:

Check whether the given grammar is ambiguous or not-
R → R + R / R . R / R* / a / b

Solution-

Let us consider a string w generated by the given grammar-
w = ab + a
Now, let us draw parse trees for this string w.

Since two different parse trees exist for string w, therefore the given grammar is ambiguous

Comments

Post a Comment

Popular posts from this blog

Code Optimization | Code Optimization Techniques

Code Optimization- Code Optimization is an approach to enhance the performance of the code. The process of code optimization involves- Eliminating the unwanted code lines Rearranging the statements of the code Advantages- The optimized code has the following advantages- Optimized code has faster execution speed. Optimized code utilizes the memory efficiently. Optimized code gives better performance. Code Optimization Techniques- Important code optimization techniques are- Compile Time Evaluation Common sub-expression elimination Dead Code Elimination Code Movement Strength Reduction 1. Compile Time Evaluation- Two techniques that falls under compile time evaluation are- A) Constant Folding- In this technique, As the name suggests, it involves folding the constants. The expressions that contain the operands having constant values at compile time are evaluated. Those express...
Post a Comment
Read more

Elimination of Left Factoring

In left factoring, We make one production for each common prefixes. The common prefix may be a terminal or a non-terminal or a combination of both. Rest of the derivation is added by new productions. The grammar obtained after the process of left factoring is called as Left Factored Grammar . Example-   PRACTICE PROBLEMS BASED ON LEFT FACTORING- Problem-01: Do left factoring in the following grammar- S → iEtS / iEtSeS / a E → b Solution- The left factored grammar is- S → iEtSS’ / a S’ → eS / ∈ E → b Problem-02: Do left factoring in the following grammar- A → aAB / aBc / aAc Solution- Step-01: A → aA’ A’ → AB / Bc / Ac Again, this is a grammar with common prefixes. Step-02: A → aA’ A’ → AD / Bc D → B / c This is a left factored grammar. Problem-03: Do left factoring in the following grammar- S → bSSaaS / bSSaSb / bSb / a Solution- ...
Post a Comment
Read more

Testing a Program – An Example

Question: Write a set of test cases – specific set of data – to properly test a relatively Simple program. Create a set of test data for the program - data the program must handle correctly to be considered a successful program. Here’s a description of the program: “The program reads three integer values from an input dialog. The three values represent the lengths of the sides of a triangle. The program displays a message that states whether the triangle is scalene, isosceles, or equilateral”. Code: The function triangle takes three integer parameters that are interpreted as the lengths of the sides of a triangle. It returns whether the triangle is equilateral (three lengths equal), isosceles (two lengths equal), scalene (no lengths equal), or invalid (impossible lengths). Evaluate your test cases: Evaluate your set of test cases by using it to answer the following questions. Give yourself one point for each “YES” answer. Do you have a test case that represents a ...
Post a Comment
Read more