BNF-Style Notation as It Is Actually Used

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)
1840 Downloads (Pure)


The famous BNF grammar notation, as introduced and used in the Algol 60 report, was subsequently followed by numerous notational variants (EBNF, ABNF, RBNF, etc.), and later by a new formal “grammars” metalanguage used for discussing structured objects in Computer Science and Mathematical Logic. We refer to this latter offspring of BNF as MBNF (Math-BNF), and to aspects common to MBNF, BNF, and its notational variants as BNF-style. MBNF is sometimes called “abstract syntax”, but we avoid that name because MBNF is in fact a concrete form and there is a more abstract form. What all BNF-style notations share is the use of production rules like (P) below which state that “every instance of ∘i for i∈{1,...,n} is also an instance of ∙ ”.

∙ ::= ◦1 | · · · | ◦n                                                                                           (P)

However, MBNF is distinct from all variants of BNF in the entities and operations it allows. Instead of strings, MBNF builds arrangements of symbols that we call math-text and allows “syntax” to be built by interleaving MBNF production rules and other mathematical definitions that can contain chunks of math-text. The differences between BNF (or its variant forms) and MBNF have not been clearly presented before. (There is also no clear definition of MBNF anywhere but this is beyond the scope of this paper.)

This paper reviews BNF and some of its variant forms as well as MBNF, highlighting the differences between BNF (including its variant forms) and MBNF. We show via a series of detailed examples that MBNF, while superficially similar to BNF, differs substantially from BNF and its variants in how it is written, the operations it allows, and the sets of entities it defines. We also argue that the entities MBNF handles may extend far outside the scope of rewriting relations on strings and syntax trees derived from such rewriting sequences, which are often used to express the meaning of BNF and its notational variants.
Original languageEnglish
Title of host publicationIntelligent Computer Mathematics - 12th International Conference, CICM 2019, Proceedings
Subtitle of host publicationCICM 2019
EditorsCezary Kaliszyk, Edwin Brady, Andrea Kohlhase, Claudio Sacerdoti Coen
Number of pages18
ISBN (Electronic)9783030232504
ISBN (Print)9783030232498
Publication statusPublished - 3 Jul 2019
Event12th Conference on Intelligent Computer Mathematics 2019 - Prague, Czech Republic
Duration: 8 Jul 201912 Jul 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11617 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference12th Conference on Intelligent Computer Mathematics 2019
Abbreviated titleCICM 2019
Country/TerritoryCzech Republic
Internet address

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'BNF-Style Notation as It Is Actually Used'. Together they form a unique fingerprint.

Cite this