www.icosaedro.it

BNF Syntax Validator and Formatter

Last update: 2024-03-12

bnf_chk validator and formatter for the EBNF (Extended Backus-Naur Form) syntax. Two implementations are also available:

bnf_chk application for on-line tests only, with several examples. Uses the M2 implementation running server-side. Recommended if you are new to this program.
JavaScript implementation which can be used on-line and can also be saved locally on your computer. Recommended if you want to use the program for your works.

Index

Features
EBNF Syntax
Try BNF_CHK on-line
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:

reports EBNF syntax errors
reports undeclared identifiers
reports identifiers declared twice
reports identifiers declared but not used
prints to standard output an HTML version of the declarations.

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 = [ "+" | "-" ] digit₁ { digit₁ } ;
3. real = integer₂ "." digit₁ { digit₁ } [ "E" integer₂ ] ;

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:

a rule name some_rule
a literal string enclosed between double-quotes "some text"
a range of characters "A".."Z"
an optional expression enclosed between square parentheses [expression]
an expression that can match zero or more times enclosed between curly braces {expression}
an expression enclosed between round parentheses just to alter the order of precedence between factors and terms (a|b|c).

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 new JavaScript implementation also supports UTF-16 characters encoded as "\uHHHH".

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.

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 = { rule₂ } ;
2. rule = identifier₃ "=" expression₆ ";" ;
3. identifier = ( letter₄ | "_" ) { letter₄ | digit₅ | "_" } ;
4. letter = "a".."z" | "A".."Z" ;
5. digit = "0".."9" ;
6. expression = term₇ { "|" term₇ } ;
7. term = factor₈ { factor₈ } ;
8. factor = identifier₃ | literal₉ | range₁₀ | "(" expression₆ ")" | "{" expression₆ "}" | "[" expression₆ "]" ;
9. literal = "\"" { char₁₁ } "\"" ;
10. range = "\"" char₁₁ "\"" ".." "\"" char₁₁ "\"" ;
11. char = plain_char₁₂ | escaped_char₁₃ | hex_char₁₄ ;
12. plain_char = " ".."\x7f" | "\x80".."\xff" | utf_16_char₁₅ ;
13. escaped_char = "\\" ( "\"" | "\\" | "a" | "b" | "n" | "r" | "t" ) ;
14. hex_char = "\\x" hex₁₆ hex₁₆ ;
# UTF-16 chars are supported only by the new JavaScript implementation:
15. utf_16_char = "\\u" hex₁₆ hex₁₆ hex₁₆ hex₁₆ ;
16. hex = "0".."9" | "a".."f" | "A".."F" ;

Try BNF_CHK on-line

Two implementations are available:

bnf_chk application for on-line tests only, with several examples. Uses the M2 implementation running server-side. Recommended if you are new to this program.
JavaScript implementation which can be used on-line and can also be saved locally on your computer. Recommended if you want to use the program for your works.

Here are some examples of BNF definitions:

Algebraic Expressions - Simple math expressions.
EBNF - The syntax of BNF_CHK.
E-mail - Internet e-mail message, RFC 5322.
Pascal Language
PHP Language

Download

This old implementation of the validator based on the M2 language is not maintained anymore and it's still here only for future reference. The new maintained implementation is made in JavaScript and it's available here.

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.

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

Comments

Contact

Site map

Home/

An abstract of the latest comments from the visitors of this page follows. Please, use the Comments link above to read all the messages or to add your contribute.

2011-09-19 by Guest
comments
comment sections (* comment *) gave fatal error[more...]

2009-12-21 by Umberto Salsi
Re: EBNF
Anonymous wrote: [...] I would to remember you all to read the specifications about my little program (click on the "Section index" link above) where the exact syntax the program accepts is clearly explained. About the repetition factor, the syntax 3*A can be easily converted to A A A without commas. [more...]

2009-12-11 by Guest
Re: EBNF
Anonymous wrote: [...] The syntax checker also does not understand the repetition syntax above, such as bb = 3 * aa, "B";[more...]

2009-03-05 by Guest
EBNF
It seems that your EBNF syntax checked does not understand ','. In EBNF it is called 'concatenate-symbol'. Eample from ISO 17977: bb = 3 * aa, "B"; cc = 3 * [aa], "C"; Your checker does not understand comma here.[more...]