BMF — Backtracking Model Form

Here is the actual top of BMF-grammar.bml from the 2000 archive — the file that defines the BMF grammar in BML:

{`// Name:     BMF.bml
// Author:   Urs C. Muff
// Date:     11-Apr-2000
// Platform: BML Virtual Machine
// Compiler: JBMF (R) Compiler

package BMF;
import BMF.primitive.*;

class BMF [public] : Application {
   const String DefaultBMFSyntax = "BMF.library.BMF";

   section [class, public] {
      String m_strDefaultConfigFile = "BMF.cfg";
      String m_strConfigFile = m_strDefaultConfigFile;
   }

   section [class, public] {
      bool m_bDebug = true;
   }

   section [public] {
      void Main( String[] hArgs ) { HandleArgs( hArgs ); }
   }
}`}
          

class BMF [public]: Application — BMF is a class in BML, inheriting from Application. section [class, public] is Smalltalk-style category-pane visibility expressed as BML syntax. The compiler that compiled this file is named in the header: JBMF (R) — the Java port. The system was already self-bootstrapped at the moment this comment was typed.

BMF is BNF augmented with execution. The notation reads like EBNF with a few specific moves that matter:

• ::= rule definition · | branch (OR-list, tried in order, backtracked)
• {... } zero-or-more · [... ] optional · < 'a'..'z' > character class
• item \\ separator separator-list (same as item { separator item })
• $tag:Element tag a sub-element so action code can lift it by name
• Rule( arg1, arg2 )::=... template rule — arguments bound at call-site, resolved at parse-time

With those moves, here is a fragment of BML's own grammar written in BMF — the same notation the parser is reading while parsing it. These rules are pulled directly from the 2000 thesis ( backtracking-model-languages.txt ):

{`// BML grammar fragment, written in BMF
// (Backtracking Model Form — the same form parsing this file)

Number     ::= < '0'..'9' > [ '.' < '0'..'9' > ];
Identifier ::= < 'a'..'z' | 'A'..'Z' | '_' >
                 { < 'a'..'z' | 'A'..'Z' | '_' | '0'..'9' > };

Expression ::= Term { ( "-" | "+" ) Term };
Term       ::= "(" Expression ")" | Number | Identifier;

// template rule — argument-passing, anticipating ANTLR
List( item, separator ) ::= item { separator item };
Other      ::= List( Identifier, "," );

// BML's own control flow, in BMF
If     ::= "if" "(" Expression ")" $then:Statement
             [ "else" $else:Statement ];

Select ::= LabelDecl "select" "(" Expression ")" SwitchBlock;
SwitchBlock ::= "{"
                  { ( "case" CaseExpr \\\\ "," ":" | "default" ":" )
                      Statement }
                "}";
CaseExpr    ::= Expression [ ".." Expression ];

For    ::= LabelDecl "for" "(" [ Expression ] ";"
                              [ Expression ] ";"
                              [ Expression ] ")" Statement;

// the backtracking statement — BMF's own discipline,
// expressed in the language it parses
Choice ::= "choice" CodeBlock \\\\ ",";

// binary types — read raw bytes with the same grammar machine
BinaryType ::= "binary" Identifier "["
                  "size"    "=" int ","
                  "mapping" "=" ( "signed" | "unsigned"
                                | "float"  | "double" | "no" )
               "]";`}
          

Read If closely: the two Statement occurrences carry tags $then and $else. When the rule matches, the action code attached to If can ask the parse stack for the entry tagged $then and get the then-branch's already-built object — no positional indexing, no second pass over the tree. The parse tree decorates itself as it grows.

Read Choice closely: BML's backtracking statement is "choice" CodeBlock \\ "," — a comma-separated list of code blocks. The grammar of the language carries the same backtracking discipline as the grammar engine that parses it. The parser, the assembly ( BMCPU ), and the language all unwind the same way.

The full self-description lives at companion/source-samples/BMF-grammar.bml — the BMF compiler driver, written in BML, compiled by JBMF, parsing files described by grammars written in BMF. Three layers of self-bootstrap, all visible in one file.