# BNF-Style Notation as It Is Actually Used

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

2 Citations (Scopus)

## Abstract

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 language English Intelligent Computer Mathematics - 12th International Conference, CICM 2019, Proceedings CICM 2019 Cezary Kaliszyk, Edwin Brady, Andrea Kohlhase, Claudio Sacerdoti Coen Springer 187-204 18 9783030232504 9783030232498 https://doi.org/10.1007/978-3-030-23250-4_13 Published - 3 Jul 2019 12th Conference on Intelligent Computer Mathematics 2019 - Prague, Czech RepublicDuration: 8 Jul 2019 → 12 Jul 2019https://www.cicm-conference.org/2019/cicm.php

### Publication series

Name Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 11617 LNAI 0302-9743 1611-3349

### Conference

Conference 12th Conference on Intelligent Computer Mathematics 2019 CICM 2019 Czech Republic Prague 8/07/19 → 12/07/19 https://www.cicm-conference.org/2019/cicm.php

## ASJC Scopus subject areas

• Theoretical Computer Science
• General Computer Science

## Fingerprint

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