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>


<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>

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.


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).

  • Great. So if I was writing the derivation for my if then or if then else example above how would I write it? Would I do the if then part first, then underneath it write the if then else part? If you would not mind could you give me an example? – Andrew S Mar 24 '14 at 2:29
  • So if I were to write a derivation of your some_statement would I pick only one of the three options or all three in turn? – Andrew S Mar 24 '14 at 3:25
  • Exclusive. Otherwise it'd be an ambiguous grammar. – World Engineer Mar 24 '14 at 4:07

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.