CODEWITHSUNDEEP
grammarcontext-free-grammarambiguous-grammar
CHANTAL MARIN BOURCERAAU
CHANTAL MARIN BOURCERAAU

Reputation: 1

How to show that a grammar with Bitwise operator is ambiguous using the expression a>>b^c

I am trying to solve this question but I really don't know how to get started. I would appreciate some help.

The bitwise operators for a language are shown in the table below alongside the grammar. The operators and the grammar rules are in order of precedence from highest to lowest. The characters a, b and c represent terminals in the language.

Grammar table:

Grammar table

  1. Show that the grammar is ambiguous using expression: a >> b ^ c
  2. Rewrite the grammar so that it is unambiguous.

Upvotes: 0

Views: 631

Answers (1)

Michael Dyck
Michael Dyck

Reputation: 2458

The Dragon Book says: "A grammar that produces more than one parse tree for some sentence is said to be ambiguous." So to show that a grammar is ambiguous, you need to show at least two parse trees for a single sentence generated by the grammar. In this case, the sentence to use is already given to you, so for Q1 you just need to find two different parse trees for a >> b ^ c. Shiping's comment gives you a big clue for that.

For Q2, where they ask you to "rewrite the grammar", I suspect the unspoken requirement is that the resulting grammar generate exactly the same language as the original. (So Shiping's suggestion to introduce parentheses to the language would not be accepted.) The general approach for doing this is to introduce a nonterminal for each precedence level in the precedence chart, and then modify the grammar rules to use the new nonterminals in such a way that the grammar can only generate parse trees that respect the precedence chart.

For example, look at the two trees you found for Q1. You should observe that one of them conforms to the precedence chart and one does not. You want a new grammar that allows the precedence-conforming tree but not the other.

As another clue, consider the difference between these two grammars:

E -> E + E
E -> E * E
E -> a | b

and

E -> E + T
T -> T * F
F -> a | b

Although they generate the same language, the first is ambiguous but the second is not.

Upvotes: 1

Related Questions