# Confused about substitution in grammar in certain cases

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.

• Why do you think that grammar is unambiguous?
– rici
Oct 23, 2019 at 21:15
• It's just given as unambiguous. The problem question takes it for granted. Oct 23, 2019 at 21:19
• Ok, that's fine. So why is it a problem that those parses exist? They parse different sentences, no?
– rici
Oct 23, 2019 at 21:22
• Isn't it the same T that has 2 definitions for example? Which one do you choose? Why?When? Oct 23, 2019 at 21:28
• 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.
– rici
Oct 23, 2019 at 21:53

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.