Home/
 www.icosaedro.it 

 BNF Syntax Checker

Last update: 2009-06-22

bnf_chk validator and formatter for the EBNF (Extended Backus-Naur Form) syntax. bnf_chk is available for on-line tests and can be downloaded as source code.

Index

Features
EBNF Syntax
Try BNF_CHK on-line
Updates log
Download

Features

The program presented here lets you check the formal validity of a set of EBNF declarations. Given a text file containing the EBNF declarations, the program bnf_chk can:

The program parses a common EBNF syntax like this, describing integer and floating point numbers:

digit = "0".."9";
integer = ["+"|"-"] digit {digit};
real = integer "." digit {digit} [ "E" integer ];

These rules say that a digit is any character between 0 and 9, an integer number is a sequence of one or more digits with possibly a leading sign, and a real number is just like an integer with a fractional part and possibly a scale factor. These declarations can be reformatted with the command

$ bnf_chk --print-html --print-index numbers.txt

giving as output the HTML version that follows:

1. digit = "0".."9" ;
2. integer = [ "+" | "-" ] digit1 { digit1 } ;
3. real = integer2 "." digit1 { digit1 } [ "E" integer2 ] ;

The program is released as freeware.

EBNF Syntax

A file that BNF_CHK can parse must be a sequence of zero or more rules. The special character "#" starts a comment and all the characters up to the end of the line are ignored.

Rules. Every rule begins with its rule identifier, followed by an equal sign =, followed by an expression and terminated by semicolon:

identifier = expression ;

Rule identifiers. Any sequence of letters, digits and underscore starting with a letter or an underscore is a rule identifier (non-terminal symbol).

Expressions. An expression is one or more terms separated by a vertical bar:

term1 | term2 | term3

Terms. A term is a product of factors. Factors can be simply written in the order, no "product" symbol is required. Spaces are allowed to separate contiguous identifiers.

Factors. A factor can be:

Literal words of the language must be enclosed within double quotes. Only ASCII printable characters are allowed. The character double quote itself can be expressed through the special sequence \" (backslash, double quote) and the character backslash can be expressed as \\ (backslash, backslash). Commonly used escaped sequences "\a\b\n\r\t" are also allowed. Any other byte can be expressed in hexadecimal form as \xHH where HH are two hexadecimal digits.

The figure below illustrates some features of the EBNF syntax through syntax diagrams: the square boxes are the rules, while the arrows indicate the allowed paths between rules.


EBNF syntax diagrams

Algebraic syntax and syntax diagrams compared.


The EBNF syntax allowed by the program can be expressed in terms of the EBNF syntax itself as follows:

1. bnf_file = { rule2 } ;

2. rule = identifier3 "=" expression6 ";" ;

3. identifier = ( letter4 | "_" ) { letter4 | digit5 | "_" } ;

4. letter = "a".."z" | "A".."Z" ;

5. digit = "0".."9" ;

6. expression = term7 { "|" term7 } ;

7. term = factor8 { factor8 } ;

8. factor = identifier3 | literal9 | range10 | "(" expression6 ")" | "{" expression6 "}" | "[" expression6 "]" ;

9. literal = "\"" { char11 } "\"" ;

10. range = "\"" char11 "\"" ".." "\"" char11 "\"" ;

11. char = plain_char12 | escaped_char13 | hex_char14 ;

12. plain_char = "\x20".."\x7F" | "\x80".."\xFF" ;

13. escaped_char = "\\" ( "\"" | "\\" | "a" | "b" | "n" | "r" | "t" ) ;

14. hex_char = "\\x" hex15 hex15 ;

15. hex = "0".."9" | "a".."f" | "A".."F" ;

Try BNF_CHK on-line

You can try the program bnf_chk on-line at this WEB page:

www.icosaedro.it/bnf_chk/bnf_chk-on-line.html

You can choose between some examples of EBNF syntaxes, but you can try with your own EBNF syntax too.

Updates log

Version 1.4_20061107:
====================
- can display the source with line numbers
- can display a line of context along the error message
- new options: --print-source --print-context
- fixed: displays properly plain text when mixed with HTML text

Version 1.3_20061007:
====================
- commonly used escaped sequences "\a\b\n\r\t" now allowed in literal strings
- literal strings now rendered exactly as they were entered

Version 1.3_20060811:
====================
- Now available also as pure-C source for those who don't want to install M2.
- Literal strings now allow for hexadecimal encoded chars \xHH.
- Allows ASCII-extended charset.

Version 1.2_20050405:
====================
- Executable file: fixed buf in the str module of M2.
- The option --do-print-html now force all the output to be HTML.
- The options --version and --help do not stop the program any more.

Version 1.1_20040419:
====================
- Minor changes.

Version 1.0_20040402:
====================
- First public release.

Download

File Size Description
bnf_chk-windows-1.4_20061107.zip 68 KB Executable program tested on Microsoft Windows Vista. Users of Windows that intend simply to use the program, should download only this package.
bnf_chk-pure-c-1.4_20061107.tar.gz 27 KB This version of the program is the output of the M2-to-C cross compiler. To successfully generate the executable program you only need a C compiler like gcc under Linux or Unix.
bnf_chk-1.4_20061107.tar.gz 30 KB Original M2 source of BNF_CHK. Requires the M2 development system, available at www.icosaedro.it/m2.

The source program is also browsable throught the CVS server, from which you can also download the latest version of the program under development.


Umberto Salsi

Contact
Site map
Home/