Ask Question

Consider the grammar:

S β†’ aSbS | bSaS | πœ–

  • Show that this grammar is ambiguous by constructing two different left most derivations for the sentence abab.
  • Construct the corresponding right most derivations for abab.
  • Construct the corresponding parse tree for abab.
  • What language does this grammar generate?
Added 2 years ago
Active
Viewed 1505
Compiler Design Computer Science & Engineering
Ans

 

Right most derivations for abab:

Case 1:

S → aSbS

  → aSb             (applying S → πœ–) 

  → abSaSb       (applying S → bSaS)

  → abSab         (applying S → πœ–)

  → abab            (applying S → πœ–)  

Case 2:

S → aSbS

  → aSbaSbS     (applying S → aSbS)

  → aSbaSb        (applying S → πœ–)

  → aSbab         (applying S → πœ–)

  → abab           (applying S → πœ–)

 



Subjects

Data Structures & Algorithm
57 questions
Database Management System
33 questions
Software Engineering
55 questions
Compiler Design
22 questions
Mobile computing
23 questions
Design and Analysis of Algorithm
12 questions
C Programming and Practices
37 questions
Computer Graphics and Multimedia
42 questions

Advertisements

Related Questions

Construct the three address code for the following expression and represent it in quarter of a triple and indirect triple format a equal to b + c into d - e
1 week ago . by Adithi Ashok Shetty

Consider the following grammar:

                         

Prove the above grammar is LL (1). Draw the parsing table. Now check whether the string β€œab” and β€œacbd” are the languages of the above grammar. (Derive each step with the help of a stack.)

 
2 years ago . by Super Admin

Write short notes on:

  • Back patching
  • Thompson’s construction
  • Constant folding and copy propagation
2 years ago . by Super Admin

What is activation record? Explain clearly the components of an activation record.
2 years ago . by Super Admin

MindStudy - a preparation hub for all the students. The goal is to make it easier for pupils to get better grades on exams.

Company

Legal Stuff

Help

Copyright © 2025 MindStudy

A product by Shunya Intelliware Solution
(Registered under MSME Uddyam)