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 1474
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
21 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

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

Write short notes on: 

  • Peephole Optimization
  • Symbol Table
  • Cross Compiler
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)