CODEWITHSUNDEEP
grammarcontext-free-grammarambiguous-grammar
name
name

Reputation: 419

How can I show that this grammar is ambiguous?

I want to prove that this grammar is ambiguous, but I'm not sure how I am supposed to do that. Do I have to use parse trees? 

  S -> if E then S | if E then S else S | begin S L | print E
  L -> end | ; S L
  E -> i

Upvotes: 2

Views: 832

Answers (2)

philipxy
philipxy

Reputation: 15156

You can show it is ambiguous if you can find a string that parses more than one way:

if i then ( if i then print i   else print i ; )
if i then ( if i then print i ) else print i ;

This happens to be the classic "dangling else" ambiguity. Googling your tag(s), title & grammar gives other hits.

However, if you don't happen to guess at an ambiguous string then googling your tag(s) & title:

how can i prove that this grammar is ambiguous?

There is no easy method for proving a context-free grammar ambiguous -- in fact, the question is undecidable, by reduction to the Post correspondence problem.

Upvotes: 1

Jurgen Vinju
Jurgen Vinju

Reputation: 6696

You can put the grammar into a parser generator which supports all context-free grammars, a context-free general parser generator. Generate the parser, then parse a string which you think is ambiguous and find out by looking at the output of the parser.

A context-free general parser generator generates parsers which produce all derivations in polynomial time. Examples of such parser generators include SDF2, Rascal, DMS, Elkhound, ART. There is also a backtracking version of yacc (btyacc) but I don't think it does it in polynomial time. Usually the output is encoded as a graph where alternative trees for sub-sentences are encoded with a nested set of alternative trees.

Upvotes: 0

Related Questions