Documentation
The BNF Parser² is described in: Václav Vacek, Generic BNF-driven parser, Bachelor's Thesis, Masaryk University, Brno, January 2008. Archived in is.muni.cz.
This thesis describes the bnfparser² C++ library. It is a generic runtime-generated parser capable of parsing any context-free language. The parser is primarily meant for verification and diagnosis of telecommunication protocols, but the usage is not restricted to that.
First, the possibility of using tools already available is discussed. The rest of the thesis is then fully devoted to bnfparser². The architecture of the library is described in detail; all the important steps and algorithms are given. This generally involves tranforming the user input into an internal form, generating the parser and parsing. After that, format of input and output, required settings, restrictions are described. Finally the furher improvements of the library are outlined.
The BNF Parser² uses a modification of Tomita's linear LR parsing algorithm.
The modification is described in: Elizabeth Scott, Adrian Johnstone, and Shamsa Sadaf Husain, Tomita-Style Generalised LR Parsers, Royal Holloway University of London, December 2000.
The original algorithm is described in: Masaru Tomita, An Efficient Augmented-Context-Free Parsing Algorithm, in Computational Linguistics, Volume 13, Numbers 1-2, January-June 1987.
References
Different variants and extensions of Backus-Naur Form (BNF) are described in
The standard notations based on BNF are described in
- RFC 733
- RFC 1035
- RFC 4234 as Augmented BNF (ABNF)
- ISO/IEC 14977:1996 as Extended BNF (EBNF)