Search code examples
syntaxcompiler-constructioncontext-free-grammarambiguousparse-tree

Show that the following grammar is ambiguous

this grammar was in my midterm exam but I couldn't find two different parse tree it ask to show that it's ambiguous

K -> QK | ε
Q -> Qa | aQb | ab

if I didn't see that it has left recursive I was going to write that is not ambiguous, thank you.

Solution 
  • K -> QK -> QQK -> QQ
  -> abQ -> abaQb -> abaQab
  -> abaabab

K -> QK -> QQK -> QQQK -> QQQ
  -> QaQQ -> abaQQ -> abaabQ
  -> abaabab

    Edit to add some commentary: I'm not sure there's a good way to solve these. Look for rules that can "do the same thing" (like deriving longer strings), and start there. In this case, the issue is that we can add Q in multiple ways. You can try working backwards as well: imagine strings in the language and how they would be finished in the grammar. If you're looking for the shortest counter examples possible, this is helpful since the ambiguity will typically happen fairly late in these strings.