Overview of BNF Syntax
BNF is used to formalize the syntax of a particular grammar. This
is a fancy way of saying that it is used to specify the structure of
an object. It is a way to formally describe the composition of an
object in terms of tokens (lexical/object/numerical). It was first
introduced in 1959 by John Backus and then again in 1960 by Peter
Naur. It was created to describe the Algol programming language, and
has been used ever since to describe most software programming
languages and other constructs. A short overview is shown below.
Symbol Meaning
<element> :: "Element is composed of"
ELEMENT Required element
[ELEMENT] The element may be absent or occur once.
{ELEMENT} One of the elements in the braces must occur.
{ELEMENT}* All elements in the braces may be absent or occur one or more
times.
{ELEMENT}+ All elements in the braces must occur one or more
times.
<element> A composite element
| "Or"
If a grammar is thought of to be comprised of elementary tokens, then
BNF is used to describe how those tokens must be ordered in order to
satisfy the grammatical requirement. For example, a file used to
store some type of database may be described in BNF as shown below.
<db> :: HEADER [UNITS] {<gds>|<cif>} {<property>}+ {<record>}* ENDDB
<gds> :: GDSTYPE [VERSION]
<cif> :: CIFTYPE [VERSION]
<property> :: PROPTYPE PROPVALUE
<record> :: RECTYPE [<body>] ENDREC
<body> :: VALUE [TRANSFORM]
In normal speak the above states that a database object <db>
consists of a HEADER token optionally followed by a UNITS token.
This is followed by either a <gds> or <cif> object.
After this, one or more <property> objects must occur, followed
by zero or more <record> objects. The ENDDB token terminates
the database object. Continuing through the definition, sub-objects
are specified.
Description of tests
So how does the JBNT API map to what we have above? Well like
this...
Symbol Maps To
ELEMENT BNFNoFallthruTest
[ELEMENT] BNFOptionalTest
{ELEMENT} BNFOneOfManyRequiredTest
{ELEMENT}* BNFOneOrMoreOptionalTest
{ELEMENT}+ BNFOneOrMoreRequiredTest
<element> BNFRequiredTest
| No mapping required
Each of the tests listed above all subclass BNFAbstractTest and
implement the BNFTestImplementer interface. The BNFNoFallthruTest
represents a terminal test. The
constructor for this object takes an int value that
specifies the test requirement. The test method of this
object takes an int value and compares it to the requirement.
It will return a BNFTestResult object that will have a completion
status of FINISHED, FAIL, or UNFINISHED as defined by the BNFTestResult object.
The remaining tests are complex tests. The constructors for these
objects take an array of BNFTestImplementer objects. For example, if
a BNFRequiredTest was defined with a constructor arg consisting of an
array of BNFNoFallthruTests, then successive calls to the test
method on the object would require that each of the child tests in
the constructor arg were fulfilled in order. Furthermore all the
child tests would have to be fullfilled. That is, the requirement
for the test to pass is that all of the child tests pass and
the entire group occurs at exactly once.
A summary of the features of each test.
Name
|
FAIL conditions
|
UNFINISHED Conditions
|
FINISHED conditions
|
BNFNoFallthruTest
|
Token != requirement
|
-
|
Token == requirement
|
BNFOptionalTest
|
-
|
If more tokens are required to determine the result of the
test.
|
The group of child tests occur one time and each child test's
requirement is met Or none of the child requirements occur
Or only a partial pass of the child requirements occur
In these latter two cases the series of unconsumed tokens are
returned in the BNFTestResult object as replayable tokens.
|
BNFRequiredTest
|
If the group of child tests doesn't occur, or if one or more
of the child test's requirements aren't met.
|
If more tokens are required to determine the result of the
test.
|
The group of child tests occur one or more times and each
child test's requirements is met.
|
BNFOneOrMoreOptionalTest
|
-
|
If more tokens are required to determine the result of the
test.
|
The group of child tests occur one or more times and each child test's
requirement is met Or none of the child requirements occur
Or only a partial pass of the child requirements occur
In these latter two cases the series of unconsumed tokens are
returned in the BNFTestResult object as replayable tokens.
|
BNFOneOfManyRequiredTest
|
If none of the child test's requirement fails to be
met.
|
If more tokens are required to determine the result of the
test.
|
If one of the child test's requirements are met.
|
BNFOneOrMoreRequiredTest
|
If the group of child tests doesn't occur one or more times,
or if the group of child tests does occur but one or more of the
child test's requirements aren't met.
|
If more tokens are required to determine the result of the
test.
|
The group of child tests complete at least once
|
Example
The database BNF syntax shown above would map to the following
java code. The for statement at the end uses the dbT
test instance to test if a stream of tokens meets the syntax
requirements defined by the test. The construction and initialization
of the token array occurs outside the scope of this snippet.
//...
int TRANSFORM = 0x00;
int VALUE = 0x01;
int ENDREC = 0x02;
int RECTYPE = 0x03;
int RECVALUE = 0x04;
int PROPTYPE = 0x05;
int PROPVALUE = 0x06;
int CIFTYPE = 0x07;
int GDSTYPE = 0x08;
int VERSION = 0x09;
int HEADER = 0x0A;
int UNITS = 0x0B;
int ENDDB = 0x0C;
BNFTestImplementor xfrmT = new BNFOptionalTest(new BNFTestImplementor[]{BNFNoFallthruTest(TRANSFORM)});
BNFTestImplementor valueT = new BNFNoFallthruTest(VALUE);
BNFTestImplementor[] bodyTests = {valueT, xfrmT};
BNFTestImplementor bodyT = new BNFOptionalTest(bodyTests);
BNFTestImplementor rectypeT = new BNFNoFallthruTest(RECTYPE);
BNFTestImplementor endrecT = new BNFNoFallthruTest(ENDREC);
BNFTestImplementor[] recordTests = {rectypeT, bodyT, endrecT};
BNFTestImplementor recordT = new BNFRequiredTest(recordTests);
BNFTestImplementor proptypeT = new BNFNoFallthruTest(PROPTYPE);
BNFTestImplementor propvalueT = new BNFNoFallthruTest(PROPVALUE);
BNFTestImplementor[] propertyTests = {proptypeT propvalueT};
BNFTestImplementor propertyT = new BNFRequiredTest(propertyTests);
BNFTestImplementor gdstypeT = new BNFNoFallthruTest(GDSTYPE);
BNFTestImplementor ciftypeT = new BNFNoFallthruTest(CIFTYPE);
BNFTestImplementor versionT = new BNFOptionalTest(new BNFTestImplementor[]{BNFNoFallthruTest(VERSION)});
BNFTestImplementor[] gdsTests = {gdstypeT versionT};
BNFTestImplementor[] cifTests = {ciftypeT versionT};
BNFTestImplementor gdsT = new BNFRequiredTest(gdsTests);
BNFTestImplementor cifT = new BNFRequiredTest(cifTests);
BNFTestImplementor recordG = new BNFOneOrMoreOptionalTest(
new BNFTestImplementor[] { recordT });
BNFTestImplementor propertyG = new BNFOneOrMoreRequiredTest(
new BNFTestImplementor[] { propertyT });
BNFTestImplementor typeG = new BNFOneOfManyRequiredTest(
new BNFTestImplementor[] { gdsT, cifT });
BNFTestImplementor enddbT = new BNFNoFallthruTest(ENDDB);
BNFTestImplementor unitsT = new BNFOptionalTest(new BNFTestImplementor[]{BNFNoFallthruTest(UNITS)});
BNFTestImplementor headerT = new BNFNoFallthruTest(HEADER);
BNFTestImplementor[] dbTests = {
headerT, unitsT, typeG, propertyG, recordG, enddbT };
BNFTestImplementor dbT = new BNFRequiredTest(dbTests);
for(int i = 0; i < tokens.length; i++){
if(dbT.test(tokens[i]).isFailed())
return false
}
return true;
//...
|