Ambiguity in Context free Grammar

0
votes

Question

Show that the context-free grammar "S->SbS|ScS|a" is ambiguous by giving two parse trees for the string abaca.

I don't get how the string is ambiguous ? I was reading a book on compilers and self learning so i was doing this question in book and i am stumped.

Possible Solution

abaca         abaca
a(aba)aca     aba(aca)a

Can anyone confirm if my solution is correct and if not can someone please guide me.

1
grammarcontext-free-grammarambiguous-grammar
What you've shown aren't parse trees. You need to show how abaca can be parsed. There isn't one way to draw a parse tree, but generally something that shows either the syntax tree if you imagine it in memory, or a sequence of derivations (as in @Mephy's answer). – codenheim

1 Answers

2
votes

This is much easier to do with pen and paper. Among all the possibilities, I list three possibilities find by deriving the initial symbol S.

S -> SbS -> abS -> abScS -> abacS -> abaca
S -> ScS -> Sca -> SbSca -> abSca -> abaca
S -> SbS -> SbScS -> abScS -> abSca -> abaca

There are others, that's not hard to see. However, often it is easier to reduce the string (abaca) to the original symbol (S). Many compilers do this to avoid infinite recursion:

abaca <- Sbaca <- SbSca <- Sca <- ScS <- S
abaca <- abacS <- abScs <- abS <- SbS <- S

The way to do this is by hand is choosing a way (derivation or reduction), then go by trial-and-error the possible substitutions you can make according to the grammar, which will lead you to a tree. The nodes in the tree that lead to the goal (either the original symbol or the final string) are the correct nodes. And if there is more than one path, then it is ambiguous.

Now, each of these derivations, and the others, will produce a so-called Parse Tree. A parse tree represents the set of derivations that is able to produce the terminal string from the initial symbol. To better visualize the parse tree, I've found a tool in the web to draw these kinds of tree, you can find it here.

The format it uses is [NonTerminal terminal [NonTerminal terminal] terminal], pretty much a Lisp-like list with square-brackets instead of parenthesis. For example, the first derivation I built, S -> SbS -> abS -> abScs -> ... can be written as [S [S a] b [S [S a] c [S a]]], where [S [S ...] b [S ...]] represents the first derivation, then you expand the first [S ...] into [S a] by the second derivation and so on. Hope this tools helps you in your formal grammars learning!