Imported from previous forum
[ original email was from Jim Northey - jnorthey@jandj.com ]
We have had a few discussions on formalizing the FAST specification. Rolf mentioned BNF as an appropriate choice as opposed to UML. BNF grammars have been used for a long time to describe message formats.
Like all languages, even the formal ones, there are variants. I am leaning towards use of a combination of ABNF and EBNF.
ABNF is (Augmented Bachus-Naur Form) as specified in IETF RFC 2234 as it is spare in terms of symbol usage.
EBNF has notation similar to regular expression symbols: +?* and uses the | concatenation character as an or or selection operator. ABNF’s use of the / for selection (one of the following - this or that) is a bit less visual in this day and age.
There are also ISO standards - but was thinking we might want to keep ourselves in the flavor of the IETF Stuff.
Any thoughts or other recommendations?
I think BNF is sufficient for definition - UML or diagrammatic representation is not required.
Rolf also mentioned the possibility of using Relax/NG. I don’t know enough about it yet to be able to form an opinion. As it is based upon regular expressions - conceptually it could work.
Clearly the XML template specification can best be specified via XML Schema and/or Relax NG. For the past few years we have discussed generating a Relax NG schema for FIXML. With so much going on it has not gotten above the low priority nice to have list.
[ original email was from Matt Simpson - msimpson@cme.com ]
Jim - would you mind elaborating on how BNF could be used to formalize the FAST spec and provide some background on the method? thanks
[ original email was from Jim Northey - jnorthey@jandj.com ]
A BNF Grammar is a way to precisely define a computer programming language. The Wikipedia page rightfully refers to it as a meta syntax. The name is from two of the great computer scientists in the 50’s that invented it John Backus and Peter Naur. Backus was the father for of FORTRAN at IBM; Naur I believe was one of the key guys behind Algol 60 (with C.A.R. Hoare). Donald Knuth - another great- suggested appending Naur’s name to the grammar. They invented a grammar for specifying other languages. This approach now is used to define most languages. The grammar does not have to be, but is best used in conjunction with a compiler/compiler, such as (LEX/YACC) or SPARK or Bison or other commercial products, to read the grammar and actually generate a parser. There are different types of parsers that can be generated from a grammar -but that is outside the context of our purposes for the moment and is one layer of the onion too deep.
For quite a long time now in the telco and networking spaces the same formal grammars are used to describe message protocols. Such as the ISO/IEC specifications. The IETF adopted a variant of BNF for specifying Internet Protocols called ABNF (rfc2234). Grammars exist for XML and SGML, in addition to grammars for Java, C, C++, SQL, Perl, Awk, etc.
Please note that my example below is not likely consistent. And note there is more than one way to use a BNF grammar. So someone knowledgeable in grammars may disagree with the approach I used to represent this small off-the-cuff example. I do think that the examples does provide an idea of the usage and hopefully the value can be derived from this crude example.
Considering the FIX protocol, We could describe the FIX session layer message along the lines of:
:= …<application_message> +
:= %x01 // hexadecimal digit 0x01
:= “8” “=”
:= <ascii_digits>+ // There may be a way to extend our grammar to provide a functional definition for the calculation of body length and checksum for instance.
:= “FIX” (“4.0” | “4.1” | “4.2”) // or you could use digit rules
:= “FIX” <major_release> “.” <minor_release>
<major_release> := <ascii_digit>+ // The + means 1 or more, ? 0 or 1, * 0 or more - very familiar
<minor_release> := <ascii_digit>+
<ascii_digit> := “0” | “1” | “2” | “3” | “4” | “5” …
:= “=”
:= |
:= “0” … “4999” // This is a paraphrase - not exact syntax - got lazy :- “5000” … “9999” // ditto
:= | | | … // you get the idea
:= +
:= ‘a’ | ‘b’ | ‘d’ | … // you get the idea
<application_message> := | | …
For FAST it has more value in that we can define the encoding rules as well. You can specify bit strings as well. The ABNF from the IETF does this using %b11101 for instance.
Rolf may have suggested we see if we can use Relax NG for this purpose. For those unfamiliar - RelaxNG was developed by James Clark as a way of specifying XML syntaxes. RelaxNG is an alternative to XML Schema for defining the format (schema) of an XML document. As the BNF does have a certain relationship to regular expressions and Relax NG is based upon regular expressions - this indeed might be possible - but I have not spent a day working with Relax NG yet - So Rolf and David Rosenborg are running out in front of me in this area. I think it prudent we consider Rolf’s suggestion before moving forward.
The cool thing about this if done correctly - we can take any number of compiler-compilers and actually produce a parser from the specification to test the specification. A compilable, testable specification results. A compiler-compiler (such as YACC (ascii only I believe unfortunately)) reads a grammar and generates parser code from that grammar.
I worked with this stuff at AT&T - but it fell off the map through the years of disuse. Recently, when we were doing detailed reviews of the FIX specification at J&J we discussed a better approach - Rolf recommended BNF grammar - and I whole heartedly agreed. This is a best practice - far better than UML for specifying wire message syntaxes. I think we look at a BNF grammar and Relax NG as alternatives and move the specification into one of these forms.
I am motivated to move forward in doing this so I can better and definitively learn what is and isn’t FAST 1.0.
This is good stuff.
[ original email was from Jim Northey - jnorthey@jandj.com ]
Came up with a proposed grammar based upon the EBNF grammar that is used by the W3C to define XML with some useful extensions from ABNF, which is used to define SMTP and other Internet protocols by the IETF, plus a couple of other bells and whistles thrown in, including the ability to define macros or functions - similar to the way alot of Python compiler generators are implemented now. Seems to be useful in helping to tighten down the spec.
I put the language definition up on the MDOWG site in the publicly accessible file: http://fixprotocol.org/documents/2504/FIX_XBNF_GrammarProposal_20060407.doc
I am hoping that folks will rip to shreds.
Sound like an interesting idea.
Have you had a chance to test some more on FAST?
Thx,
Rolf
Came up with a proposed grammar based upon the EBNF grammar that is used by the W3C to define XML with some useful extensions from ABNF, which is used to define SMTP and other Internet protocols by the IETF, plus a couple of other bells and whistles thrown in, including the ability to define macros or functions - similar to the way alot of Python compiler generators are implemented now. Seems to be useful in helping to tighten down the spec.
I put the language definition up on the MDOWG site in the publicly accessible file: http://fixprotocol.org/documents/2504/FIX_XBNF_GrammarProposal_20060407.docI am hoping that folks will rip to shreds.
[ original email was from Jim Northey - jnorthey@jandj.com ]
Well I think my initial foray into formalization scared more folks. No one came back saying they were enlightened. We seem to be having some luck with UML static structure diagrams, both in presentations and within the SCP 1.0 proposal. The UML approach might work out okay. Haven’t given up entirely on XBNF, ABNF, or EBNF yet- just set in on the shelf for a little while until we get a FAST 1.1 specification (documentation release only) out the door.
Sound like an interesting idea. Have you had a chance to test some
more on FAST?Thx, Rolf
Came up with a proposed grammar based upon the EBNF grammar that is
used by the W3C to define XML with some useful extensions from ABNF,
which is used to define SMTP and other Internet protocols by the IETF,
plus a couple of other bells and whistles thrown in, including the
ability to define macros or functions - similar to the way alot of
Python compiler generators are implemented now. Seems to be useful in
helping to tighten down the spec. I put the language definition up on
the MDOWG site in the publicly accessible file: http://fixprotocol.or-
g/documents/2504/FIX_XBNF_GrammarProposal_20060407.docI am hoping that folks will rip to shreds.