Question

Ex#6: Prove the following grammar is ambiguous. <S> --> <A> <A> --> <A> + <A> <A>...

Ex#6: Prove the following grammar is ambiguous.
<S> --> <A>
<A> --> <A> + <A>
<A> --> <id>
<id> --> a | b | c

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1 

Let's generate a string a+b+c using given grammar.

Using left most derivations
<S> -> <A> -> <A>+<A> -> <A>+<A>+<A> -> <id>+<A>+<A> -> a+<A>+<A> -> a+<id>+<A> -> a+b+<A> -> a+b+<id> -> a+b+c

Using left most derivations
<S> -> <A> -> <A>+<A> -> <id>+<A> -> a+<A> -> a+<A>+<A> -> a+<id>+<A> -> a+b+<A> -> a+b+<id> -> a+b+c

since we can generate a+b+c with 2-different left most derivations, this grammar is ambiguous.
0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Ex#5: Given the following grammar for a simple assignment statements. <assign> --> <id> = <expr> <id>...
Ex#5: Given the following grammar for a simple assignment statements. <assign> --> <id> = <expr> <id> --> A | B | C <exp> --> <id> + <expr> | <id> * <expr> | (<expr>) | <id> Show a leftmost derivation and a parse tree of the following statement: A = A *(B + (C * A))
Show a leftmost derivation step by step (each step on a single line)           for the...
Show a leftmost derivation step by step (each step on a single line)           for the statement: A = A + B * C using the following grammar: <assign> --> <id> = <expr> <expr>    --> <id> + <expr> | <id> * <expr> |   <id> <id>         --> A | B | C Is this grammar ambiguous (Yes or No?) Justify your answer. Does this grammar enforce the precedence of the conventional operators  (Yes or No?)   Justify your answer.
Consider the following grammar. Nonterminals are lowercase and terminals are uppercase. s -> c A c...
Consider the following grammar. Nonterminals are lowercase and terminals are uppercase. s -> c A c -> c B | B Which of the following sentences is in the language generated by the grammar? a) BAA b) BBBA c) BBAAAAA d) none of the above
Construct the LR parsing table for the following grammar: S → b S b
Construct the LR parsing table for the following grammar: S → b S b
Construct the LR parsing table for the following grammar: S → a S a
Construct the LR parsing table for the following grammar: S → a S a
Construct the LR parsing table for the following grammar: S → b b
Construct the LR parsing table for the following grammar: S → b b
Given the grammar <expr> -> <term> {( + | - ) <term>} <term> -> <factor> {(...
Given the grammar <expr> -> <term> {( + | - ) <term>} <term> -> <factor> {( * | / ) <factor>} <factor> -> <exp> { ** <exp>} <exp> -> (<expr>) | <id> <id> = (A | B | C | D | E) leftmost derivation of A**B + (B * C)
Ex 2. Prove by contradiction the following claims. In each proof highlight what is the contradiction...
Ex 2. Prove by contradiction the following claims. In each proof highlight what is the contradiction (i.e. identify the proposition Q such that you have Q ∧ (∼Q)). Claim 1: The sum of a rational number and an irrational number is irrational. (Recall that x is said to be a rational number if there exist integers a and b, with b 6= 0 such that x = a b ). Claim 2: There is no smallest rational number strictly greater...
1. Put the following grammar into Chomsky Normal Form. Note that this grammar has no useless...
1. Put the following grammar into Chomsky Normal Form. Note that this grammar has no useless symbols. S → iSE | a E → eS | ε
The grammar below generates Boolean expressions in prefix notation: B → O B B | not...
The grammar below generates Boolean expressions in prefix notation: B → O B B | not B | id O → and | or a) Write an attribute grammar to translate Boolean expressions into fully parenthesized infix form. For example, expression and and a or b c d turns into the following fully parenthesized expression ((a and (b or c)) and d). b) Now write an attribute grammar to translate the Boolean expressions into parenthesized expressions in infix form without...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT