Metasyntax

Last updated December 28, 2023

A metasyntax is a syntax used to define the syntax of a programming language or formal language. It describes the allowable structure and composition of phrases and sentences of a metalanguage, which is used to describe either a natural language or a computer programming language.^[1] Some of the widely used formal metalanguages for computer languages are Backus–Naur form (BNF), extended Backus–Naur form (EBNF), Wirth syntax notation (WSN), and augmented Backus–Naur form (ABNF).

Metalanguages have their own metasyntax each composed of terminal symbols, nonterminal symbols, and metasymbols. A terminal symbol, such as a word or a token, is a stand-alone structure in a language being defined. A nonterminal symbol represents a syntactic category, which defines one or more valid phrasal or sentence structure consisted of an n-element subset. Metasymbols provide syntactic information for denotational purposes in a given metasyntax. Terminals, nonterminals, and metasymbols do not apply across all metalanguages.

Typically, the metalanguage for token-level languages (formally called "regular languages") does not have nonterminals because nesting is not an issue in these regular languages. English, as a metalanguage for describing certain languages, does not contain metasymbols since all explanation could be done using English expression. There are only certain formal metalanguages used for describing recursive languages (formally called context-free languages) that have terminals, nonterminals, and metasymbols in their metasyntax.

Element of metasyntax

Terminals: a stand-alone syntactic structure. Terminals could be denoted by double quoting the name of the terminals.

e.g. "else" , "if", "then", "while"

Nonterminals: a symbolic representation defining a set of allowable syntactic structures that is composed of a subset of elements. Nonterminals could be denoted by angle bracketing the name of the nonterminals.

e.g. <int>, <char>, <boolean>

Metasymbol: a symbolic representation denoting syntactic information.

e.g. := , |, {}, (), [], *

Methods of phrase termination

Juxtaposition: e.g. A B
Alternation: e.g. A|B
Repetition: e.g. {A B}
Optional phrase: e.g. [A B]
Grouping: e.g. (A|B)

Specific metasyntax conventions

The standard convention

'Backus–Naur form' denotes nonterminal symbols by angle bracketing the name of the syntactic category, while it denotes terminal symbols by double quoting the terminal words. Terminals can never appear on the left-hand side of the metasymbol ::= in a derivation rule. The body of the definition on the right-hand side may be composed with several alternative forms with each alternative syntactic construct being separated by the metasymbol |. Each of these alternative construct may be either terminal or nonterminal.
'Extended Backus–Naur form' uses all facilities in BNF and introduces two more metasymbols for additional features. One of these two new features is applied to denote an optional phrase in a statement by square bracketing the optional phrase. The second feature is applied to denote a phrase that is to be repeated zero or more times by curly bracketing the phrase.
'Wirth syntax notation' uses all facilities in EBNF except that the nonterminals are not necessarily angle bracketed but are always defined on the right-hand side of = in its production rule. It also does not require every nonterminal to be explicitly defined. Nonterminals such as <text> and <opt-whitespace> are implicitly defined as ASCII-character and optional white space respectively.
'Augmented Backus–Naur form' denotes nonterminal symbols by starting a one-word-name with an alphabet as the name of the syntactic category. Angle brackets are not required. Terminal symbols are either denoted by double quoted words or denoted by the following numeric structure: a %, followed by b or x or d, followed by a numeric value or a concatenation of numeric values separated by .. Metasymbol - is placed between two numeric values to denote value range. As that of BNF, the terminals of ABNF never occurs on the left-hand-side of the metasymbol = in the derivation rule. Metasymbol / denotes alternations. White space is used to separate elements in the body of the definition. The metasyntax for repetition in ABNF has several forms. A * preceding an element denotes the element to be repeated zero or more times. Numeric value n1 followed by * followed by numeric value n2 followed by an element denotes the element to be repeated at least n1 times and at most n2 times. A single numeric value n preceding an element denotes the element to be repeated n times. Comments may be express after metasymbol ;. As in EBNF, square bracketing a phrase denotes the phrase to be optional.

Variations

The metasyntax convention of these formal metalanguages are not yet formalized. Many metasyntactic variations or extensions exist in the reference manual of various computer programming languages. One variation to the standard convention for denoting nonterminals and terminals is to remove metasymbols such as angle brackets and quotations and apply font types to the intended words. In Ada, for example, syntactic categories are denoted by applying lower case sans-serif font on the intended words or symbols. All terminal words or symbols, in Ada, consist of characters of code position between 16#20# and 16#7E# (inclusive). The definition for each character set is referred to the International Standard described by ISO/IEC 10646:2003. In C and Java, syntactic categories are denoted using italic font while terminal symbols are denoted by gothic font. In J, its metasyntax does not apply metasymbols to describe J's syntax at all. Rather, all syntactic explanations are done in a metalanguage very similar to English called Dictionary, which is uniquely documented for J.

Advantage of the extensions

The purpose of the new extensions is to provide a simpler and unambiguous metasyntax. In terms of simplicity, BNF's metanotation definitely does not help to make the metasyntax easier-to-read as the open-end and close-end metasymbols appear too abundantly. In terms of ambiguity, BNF's metanotation generates unnecessary complexity when quotation marks, apostrophes, less-than signs or greater-than signs come to serve as terminal symbols, which they often do. The extended metasyntax utilizes properties such as case, font, and code position of characters to reduce unnecessary aforementioned complexity. Moreover, some metalanguages use fonted separator categories to incorporate metasyntactic features for layout conventions, which are not formally supported by BNF.

Related Research Articles

ALGOL is a family of imperative computer programming languages originally developed in 1958. ALGOL heavily influenced many other languages and was the standard method for algorithm description used by the Association for Computing Machinery (ACM) in textbooks and academic sources for more than thirty years.

In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules can be applied to a nonterminal symbol regardless of its context. In particular, in a context-free grammar, each production rule is of the form

In formal language theory, a context-free grammar, G, is said to be in Chomsky normal form if all of its production rules are of the form:

In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules called a formal grammar.

In formal language theory, a context-free grammar is in Greibach normal form (GNF) if the right-hand sides of all production rules start with a terminal symbol, optionally followed by some variables. A non-strict form allows one exception to this format restriction for allowing the empty word to be a member of the described language. The normal form was established by Sheila Greibach and it bears her name.

A bracket is either of two tall fore- or back-facing punctuation marks commonly used to isolate a segment of text or data from its surroundings. They come in four main pairs of shapes, as given in the box to the right, which also gives their names, that vary between British and American English. "Brackets", without further qualification, are in British English the (…) marks and in American English the […] marks.

In computer science, augmented Backus–Naur form (ABNF) is a metalanguage based on Backus–Naur form (BNF), but consisting of its own syntax and derivation rules. The motive principle for ABNF is to describe a formal system of a language to be used as a bidirectional communications protocol. It is defined by Internet Standard 68, which as of December 2010 is RFC 5234, and it often serves as the definition language for IETF communication protocols.

In computer science, Backus-Naur form is a notation used to describe the syntax of programming languages or other formal languages. It was developed by John Backus and Peter Naur. BNF can be described as a metasyntax notation for context-free grammars. Backus-Naur form is applied wherever exact descriptions of languages are needed, such as in official language specifications, in manuals, and in textbooks on programming language theory. BNF can be used to describe document formats, instruction sets, and communication protocols.

In computer science, a compiler-compiler or compiler generator is a programming tool that creates a parser, interpreter, or compiler from some form of formal description of a programming language and machine.

In computer science, extended Backus–Naur form (EBNF) is a family of metasyntax notations, any of which can be used to express a context-free grammar. EBNF is used to make a formal description of a formal language such as a computer programming language. They are extensions of the basic Backus–Naur form (BNF) metasyntax notation.

In logic and linguistics, a metalanguage is a language used to describe another language, often called the object language. Expressions in a metalanguage are often distinguished from those in the object language by the use of italics, quotation marks, or writing on a separate line. The structure of sentences and phrases in a metalanguage can be described by a metasyntax. For example, to say that the word "noun" can be used as a noun in a sentence, one could write "noun" is a <noun>.

In linguistics and semiotics, a notation system is a system of graphics or symbols, characters and abbreviated expressions, used in artistic and scientific disciplines to represent technical facts and quantities by convention. Therefore, a notation is a collection of related symbols that are each given an arbitrary meaning, created to facilitate structured communication within a domain knowledge or field of study.

In computer programming, a statement is a syntactic unit of an imperative programming language that expresses some action to be carried out. A program written in such a language is formed by a sequence of one or more statements. A statement may have internal components.

In computer science, the syntax of a computer language is the rules that define the combinations of symbols that are considered to be correctly structured statements or expressions in that language. This applies both to programming languages, where the document represents source code, and to markup languages, where the document represents data.

In formal languages, terminal and nonterminal symbols are the lexical elements used in specifying the production rules constituting a formal grammar. Terminal symbols are the elementary symbols of the language defined as part of a formal grammar. Nonterminal symbols are replaced by groups of terminal symbols according to the production rules.

Wirth syntax notation (WSN) is a metasyntax, that is, a formal way to describe formal languages. Originally proposed by Niklaus Wirth in 1977 as an alternative to Backus–Naur form (BNF). It has several advantages over BNF in that it contains an explicit iteration construct, and it avoids the use of an explicit symbol for the empty string.

Translational Backus–Naur Form refers to Backus–Naur form, which is a formal grammar notation used to define the syntax of computer languages, such as Algol, Ada, C++, COBOL, Fortran, Java, Perl, Python, and many others. TBNF goes beyond BNF and extended BNF (EBNF) grammar notation because it not only defines the syntax of a language, but also defines the structure of the abstract syntax tree (AST) to be created in memory and the output intermediate code to be generated. Thus TBNF defines the complete translation process from input source code to intermediate code. Specification of the output intermediate code is optional, in which case you will still get automatic AST creation and have the ability to define its structure in the grammar.

Syntax diagrams are a way to represent a context-free grammar. They represent a graphical alternative to Backus–Naur form, EBNF, Augmented Backus–Naur form, and other text-based grammars as metalanguages. Early books using syntax diagrams include the "Pascal User Manual" written by Niklaus Wirth and the Burroughs CANDE Manual. In the compilation field, textual representations like BNF or its variants are usually preferred. BNF is text-based, and used by compiler writers and parser generators. Railroad diagrams are visual, and may be more readily understood by laypeople, sometimes incorporated into graphic design. The canonical source defining the JSON data interchange format provides yet another example of a popular modern usage of these diagrams.

A formal grammar describes how to form strings from an alphabet of a formal language that are valid according to the language's syntax. A grammar does not describe the meaning of the strings or what can be done with them in whatever context—only their form. A formal grammar is defined as a set of production rules for such strings in a formal language.

In computing, a compiler is a computer program that transforms source code written in a programming language or computer language, into another computer language. The most common reason for transforming source code is to create an executable program.

References

↑ Sellink, Alex, and Chris Verhoef. "Development, assessment, and reengineering of language descriptions." Software Maintenance and Reengineering, 2000. Proceedings of the Fourth European. IEEE, 2000.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Sellink, Alex, and Chris Verhoef. "Development, assessment, and reengineering of language descriptions." Software Maintenance and Reengineering, 2000. Proceedings of the Fourth European. IEEE, 2000.

[1]