0
$\begingroup$

To illustrate my confusion let's say I'm given this unambiguous grammar in BNF:

         S ::= T O x
         T ::= empty
         T ::= "if" E "then" T x "else" T
         O ::= empty
         O ::= "if" E "then" T O

Here is the corresponding derivation tree:

                                         S
                     ____________________|______________________
                    /                    |                      \
                   T                     O                       x
                   |         ____________|_________________
                 <empty>    / |  |             |           \
                           if E then           T            O
                                       ________|_______     |
                                      / |  |   | |  |  \ <empty>
                                     if E then T x else T
                                               |        |
                                            <empty>  <empty>

Why couldn't we have this:

                                         S
                     ____________________|______________________
                    /                    |                      \
                   T                     O                       x
                   |         ____________|_________________
                 <empty>    / |  |             |           \
                           if E then           T            O
                                       ________|_______     |
                                      / |  |   | |  |  \ <empty>
                                     if E then T x else T
                                               |        |
                                       ________|_______ \
                                      / |  |   | |  |  \ <empty>
                                     if E then T x else T  

Why is the first T <empty>? What are the rules that govern how you substitute the definitions in the graph.

$\endgroup$
  • $\begingroup$ Why do you think that grammar is unambiguous? $\endgroup$ – rici Oct 23 '19 at 21:15
  • $\begingroup$ It's just given as unambiguous. The problem question takes it for granted. $\endgroup$ – WindBreeze Oct 23 '19 at 21:19
  • $\begingroup$ Ok, that's fine. So why is it a problem that those parses exist? They parse different sentences, no? $\endgroup$ – rici Oct 23 '19 at 21:22
  • $\begingroup$ Isn't it the same T that has 2 definitions for example? Which one do you choose? Why?When? $\endgroup$ – WindBreeze Oct 23 '19 at 21:28
  • $\begingroup$ You choose the one which matches the sentence to be parsed :-) There are lots of different ways to figure out which one to choose, but the easiest practical algorithm is to try all possible options in parallel and abandon every possibility when you notice it can't natch any more. If you do that cleverly, you can parse any unambiguous grammar in quadratic time, and any grammar in cubic time. $\endgroup$ – rici Oct 23 '19 at 21:53
1
$\begingroup$

There's no particular reason why the first $T$ should be replaced by $empty$. The other replacement would have been equally acceptable. A grammar rule says "you can replace this string by this other" and no more. In other words, a grammar may generate several strings, depending on which of the grammar's replacement rules are called into play at any stage.

In answer to your last question, there are no rules to specify which substituition you use: the choice is up to you.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.