Derivations in BNF

Question

I get how to do a derivation of a BNF. My text books do a good job of explaining it (much better than the on-line lecture notes of many profs etc). Example below then my questions:

<program> => begin <stmt_list> end
<stmt_list> => <stmt>
                   | <stmt>; <stmt_list>
<stmt> => <var> = <expression>
<var> => A | B | C;
<exression> => <var> + <var>
                   |<var> - <var>
                   |<var>

Generates:

<proogam> => begin<stmt_list> end
      => begin<stmt>;<stmt_list> end
      => begin<var> = <expression>;<stmt_list>end
      => begin a = <expression>;<stmt_list>end
      => begin a =  <var> + <var>;<stmt_list>end
      => begin a = b + <var> ; <stmt_list>end
      => begin a = b + c ; <stmt_list> end
      => begin a = b + c; <var> = <expression>; <stmt_list>end
      => begin a = b + c; b  = <expression>; end
      => begin a = b + c; b = <var> + <var>;<stmt_list> end
      => begin a = b + c; b = c + <var>; <stmt_list> end
      => begin a = b + c; b = c + a; <stmt_list> end
      => begin a = b + c; b = c + a; <var> + <expression>
      => begin a = b + c; b = c + a; c = <expression>;
      => begin a = b + c; b = c + a; c = <var>;
      => begin a = b + c; b = c + a;  c = b;

I get the how mostly and I know the benefit of BNF. But regarding derivations, why do we do them token by token when it's quite obvious what the resultant code would be?

Also, with BNF derivation, when an OR is used in the syntax how do we translate this? Such as:

<if_stmt>  if (<logic_expr>) <stmt>| 
                   if (<logic_expr>) <stmt> else <stmt>

Answer 1

Because the resultant structure will not be obvious to a compiler. A compiler will move through the grammar, step by step, in a systematic fashion. In practice, there are techniques that can shortcut this but if we want to formally and rigorously reason about grammars, we want it to all be as explicit as possible.

This directly leads to the OR syntax. The if_stmt is either if (<logic_expr>) <stmt> or if (<logic_expr>) <stmt> else <stmt>. This means that we can then nest ifs within elses and so forth. Otherwise, they are two entirely different statements and like I said before, we want to be as explicit as possible with BNF grammars. Grammars for computers must be unambiguous. If we leave out steps or are careless with how we array our grammatical structures, we can wind up with ambiguous grammars in short order. This in-turn can lead to substantial compiler errors.

Example:

some_statment ::= statement_components
    | other_possible_configuration
    | another_possible_configuration
    | yet_another_configuration

In the above example, each pipe (properly a Sheffer Stroke) functions as a "guard" that acts kind of like a case statement in a programming language. You fall through the options until you reach one that matches and then that one gets selected (technically you do it backwards when parsing but I digress).