BNF-Style Notation as It Is Actually Used

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

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 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
PublisherSpringer
Pages187-204
Number of pages18
ISBN (Electronic)9783030232504
ISBN (Print)9783030232498
DOIs
Publication statusPublished - 3 Jul 2019
Event12th Conference on Intelligent Computer Mathematics 2019 - Prague, Czech Republic
Duration: 8 Jul 201912 Jul 2019
https://www.cicm-conference.org/2019/cicm.php

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

Conference

Conference12th Conference on Intelligent Computer Mathematics 2019
Abbreviated titleCICM 2019
CountryCzech Republic
CityPrague
Period8/07/1912/07/19
Internet address

Fingerprint

Forms (concrete)
Notation
Formal logic
Production Rules
Computer science
Rewriting
Grammar
Strings
Interleaving
Arrangement
Computer Science
Express
Form
Style
Logic
Distinct
Series
Syntax

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Quinlan, D., Wells, J. B., & Kamareddine, F. (2019). BNF-Style Notation as It Is Actually Used. In C. Kaliszyk, E. Brady, A. Kohlhase, & C. Sacerdoti Coen (Eds.), Intelligent Computer Mathematics - 12th International Conference, CICM 2019, Proceedings: CICM 2019 (pp. 187-204). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11617 LNAI). Springer. https://doi.org/10.1007/978-3-030-23250-4_13
Quinlan, Dee ; Wells, Joseph Brian ; Kamareddine, Fairouz. / BNF-Style Notation as It Is Actually Used. Intelligent Computer Mathematics - 12th International Conference, CICM 2019, Proceedings: CICM 2019. editor / Cezary Kaliszyk ; Edwin Brady ; Andrea Kohlhase ; Claudio Sacerdoti Coen. Springer, 2019. pp. 187-204 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{4998a457b71e47cb917254bd2b3d7630,
title = "BNF-Style Notation as It Is Actually Used",
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.",
author = "Dee Quinlan and Wells, {Joseph Brian} and Fairouz Kamareddine",
year = "2019",
month = "7",
day = "3",
doi = "10.1007/978-3-030-23250-4_13",
language = "English",
isbn = "9783030232498",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "187--204",
editor = "Cezary Kaliszyk and Edwin Brady and Andrea Kohlhase and {Sacerdoti Coen}, Claudio",
booktitle = "Intelligent Computer Mathematics - 12th International Conference, CICM 2019, Proceedings",

}

Quinlan, D, Wells, JB & Kamareddine, F 2019, BNF-Style Notation as It Is Actually Used. in C Kaliszyk, E Brady, A Kohlhase & C Sacerdoti Coen (eds), Intelligent Computer Mathematics - 12th International Conference, CICM 2019, Proceedings: CICM 2019. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11617 LNAI, Springer, pp. 187-204, 12th Conference on Intelligent Computer Mathematics 2019, Prague, Czech Republic, 8/07/19. https://doi.org/10.1007/978-3-030-23250-4_13

BNF-Style Notation as It Is Actually Used. / Quinlan, Dee; Wells, Joseph Brian; Kamareddine, Fairouz.

Intelligent Computer Mathematics - 12th International Conference, CICM 2019, Proceedings: CICM 2019. ed. / Cezary Kaliszyk; Edwin Brady; Andrea Kohlhase; Claudio Sacerdoti Coen. Springer, 2019. p. 187-204 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11617 LNAI).

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

TY - GEN

T1 - BNF-Style Notation as It Is Actually Used

AU - Quinlan, Dee

AU - Wells, Joseph Brian

AU - Kamareddine, Fairouz

PY - 2019/7/3

Y1 - 2019/7/3

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85069226581&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-23250-4_13

DO - 10.1007/978-3-030-23250-4_13

M3 - Conference contribution

SN - 9783030232498

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 187

EP - 204

BT - Intelligent Computer Mathematics - 12th International Conference, CICM 2019, Proceedings

A2 - Kaliszyk, Cezary

A2 - Brady, Edwin

A2 - Kohlhase, Andrea

A2 - Sacerdoti Coen, Claudio

PB - Springer

ER -

Quinlan D, Wells JB, Kamareddine F. BNF-Style Notation as It Is Actually Used. In Kaliszyk C, Brady E, Kohlhase A, Sacerdoti Coen C, editors, Intelligent Computer Mathematics - 12th International Conference, CICM 2019, Proceedings: CICM 2019. Springer. 2019. p. 187-204. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-23250-4_13