© Copyright 2005 Peri Hankey - documentation license Gnu FDL - code license Gnu GPL - validate HTML
SourceForge.net Logo frequently asked questions

home the project

home is this yet another YACC?

home installation

home the language machine

home the metalanguage

home that hyphen

home why not BNF?

Backus-Naur-Form (BNF) in one variant or another is the standard way of writing grammar rules for the kind of grammar that maps directly to a tree structure. It's very well established - for many readers 'grammar' pretty much means 'BNF'. Why not simply use that?

The starting point for this whole exercise was David Hendry's realisation that if you take an unrestricted rule in a Chomsky-view grammar

 sequence-of-symbols-in-the-grammar => 
         sequence-of-symbols-getting-closer-to-a-sentence;

and write it the other way round as

 sequence-of-symbols-that-relate-to-the-input => 
         sequence-of-symbols-getting-closer-to-the-grammar;

or just

 sequence-of-symbols-to-recognise => 
         sequence-of-symbols-as-replacement;

(where '=>' means ' can be rewritten as') you get something that is in lots of ways just like a simple substitution macro:

 #define DO_IT_THIS_WAY(x) {if(sillytest(x)jump(window));}

Most macro notations have a fixed format and only recognise simple text. Rules in LM are like macro definitions with these differences:

So you can take BNF rules, unpack the alternatives to 'flatten' the rules so that

 this_or_that -> 'this' | 'that';

becomes

 this_or_that -> 'this';
 this_or_that -> 'that';

and then turn them the other way round, and you have BNF as written in LMN:

 'this' <- this_or_that;
 'that' <- this_or_that;

and now you can add the 'parameters':

 'this' <- this_or_that :"this";
 'that' <- this_or_that :"that";
 - this_or_that :Selector noun :Selected 
   <- selection :{ 'you chose ' Selector ' ' Selected '?' };

BNF of course deals with type 2 grammars that have only one symbol on the left-side (in BNF ordering). The mapping to tree structures obscures the importance of substitution in Chomksy's original idea, and once you think of it as a system of grammatical macro definitions, the BNF ordering feels wrong.

In fact, it is clear that looking at grammars the BNF way round is what makes many-to-many grammar rules feel incomprehensible, when in fact we use a restricted kind of many-to-many rule every time we write a #define or any other kind of textual substitution macro.

So you can write BNF rules in LMN (just flatten them and write them the other way round). But you can also do so much more that BNF begins to feel like the straightjacket it is.

home