Context Free Grammar - Derivation We have the following grammar with the start symbol : + | - -> * | / < factor> | | ->0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 91. Show a leftmost derivation for the expression "6*4 / 2-0 +9"; show every step.2. Show a rightmost derivation for the above expression; show every step.3. Show the parse trees for the above expression's leftmost derivation and rightmost derivation.4. Show a new grammar that removes the ambiguity and makes "+" and "-" left-associative.Show the parse tree for "6 * 4 / 2-0 + 9" in your new grammar. Provide proper reasoningas to why this is the only parse tree possible for your grammar (making it unambiguous).5. Show a new grammar that removes the ambiguity and makes "+" and "-"right-associative.Show the parse tree for "6*4 / 2-0 + 9" in your new grammar. Provide proper reasoningas to why this is the only parse tree possible for your grammar (making it unambiguous).

Answered: We have the following grammar with the…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Concept explainers

Question

Context Free Grammar - Derivation

We have the following grammar with the start symbol <expr>:
<expr>
<factor> + <factor> | <factor> - <factor> <expr>
<factor> -> <factor> * <factor> | <factor> / < factor> | <expr> | <digit>
<digit> ->0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
1. Show a leftmost derivation for the expression "6*4 / 2-0 +9"; show every step.
2. Show a rightmost derivation for the above expression; show every step.
3. Show the parse trees for the above expression's leftmost derivation and rightmost derivation.
4. Show a new grammar that removes the ambiguity and makes "+" and "-" left-associative.
Show the parse tree for "6 * 4 / 2-0 + 9" in your new grammar. Provide proper reasoning
as to why this is the only parse tree possible for your grammar (making it unambiguous).
5. Show a new grammar that removes the ambiguity and makes "+" and "-"right-associative.
Show the parse tree for "6*4 / 2-0 + 9" in your new grammar. Provide proper reasoning
as to why this is the only parse tree possible for your grammar (making it unambiguous).

Expert Solution

Step 1: Overview

We are given a grammar and its productions, based on the grammar we have questions .

First we will find the leftmost derivation for the given expression, then we will find the rightmost derivation for the same expression. At the end we will draw the parse tree for the expression.

note:

As per our guidelines we are suppose to answer three subparts of a question, you can post again as a separate question. I have provided answers for 1,2 and 3 and have uploaded images for the solution. I hope it helps.

Step by step

Solved in 4 steps with 3 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions