Java Backus-Naur Test API (JBNT) 


Explore JBNT
> Overview
> Download
> Documentation
> Links
> Contact

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;
      //...
    






overview | download | documentation | links | contact |
©2004 Ohrasys Corporation. All rights reserved.