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.
∙ ::= ◦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 |
---|---|
Title of host publication | Intelligent Computer Mathematics - 12th International Conference, CICM 2019, Proceedings |
Subtitle of host publication | CICM 2019 |
Editors | Cezary Kaliszyk, Edwin Brady, Andrea Kohlhase, Claudio Sacerdoti Coen |
Publisher | Springer |
Pages | 187-204 |
Number of pages | 18 |
ISBN (Electronic) | 9783030232504 |
ISBN (Print) | 9783030232498 |
DOIs | |
Publication status | Published - 3 Jul 2019 |
Event | 12th Conference on Intelligent Computer Mathematics 2019 - Prague, Czech Republic Duration: 8 Jul 2019 → 12 Jul 2019 https://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) |
---|---|
Volume | 11617 LNAI |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 12th Conference on Intelligent Computer Mathematics 2019 |
---|---|
Abbreviated title | CICM 2019 |
Country/Territory | Czech Republic |
City | Prague |
Period | 8/07/19 → 12/07/19 |
Internet address |
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.Profiles
-
Joe Wells
- School of Mathematical & Computer Sciences - Senior Research Fellow
- School of Mathematical & Computer Sciences, Computer Science - Senior Research Fellow
Person: Academic (Research & Teaching)