Contents

Extended Backusnaur FormEdit

Extended Backus–Naur Form (EBNF) is a family of formal languages used to describe the syntax of programming languages and data formats. It extends the classic Backus–Naur Form (BNF) by adding notation that makes grammar definitions more compact and readable, enabling authors to express optional elements, repetitions, and alternatives without resorting to ad hoc notation. EBNF has become a standard tool in compiler design and language specifications, helping implementers and designers communicate precise syntax in a way that is both human-readable and machine-parseable. For context, EBNF maintains a tight relationship with Context-free grammar and can be used in conjunction with parser generators and other tooling that translate grammars into actual software.

The dominant use of EBNF is in the formal description of programming languages and data interchange formats. Many language specifications and standard documents adopt an EBNF-like style because it reduces clutter and clarifies the intent of the syntax. When readers encounter an EBNF grammar, they typically see a set of production rules where nonterminals are defined in terms of terminals and other nonterminals, with constructs for optionality, repetition, and grouping. This clarity contrasts with the more ancient BNF, which often required additional prose or multiple productions to convey the same idea. For readers exploring related notation, Augmented Backus–Naur Form is another widely used formalism, particularly in internet standards, and it offers its own set of extensions and conventions.

History

The original Backus–Naur Form was developed to describe the syntax of programming languages in a concise and machine-usable way. As language design matured, a need arose for a more expressive and readable notation, leading to the development of Extended Backus–Naur Form. Over time, numerous dialects and refinements emerged, embedded in language specifications such as those for Pascal and Ada in their early days, and later in many modern languages. An international standard effort, such as ISO/IEC 14977 (the specification of EBNF), helped codify common practice and terminology, while individual projects often tailor the notation to their own needs. The relationship between EBNF and other grammar formalisms, like BNF and ABNF, remains a point of reference for language architects and tool developers.

Syntax and constructs

EBNF introduces several constructs that improve readability and expressiveness compared with plain BNF. The following elements are commonly used, though exact syntax can vary between dialects:

  • Nonterminals and terminals: Nonterminals denote abstractions in the grammar, while terminals are concrete tokens from the input. Terminals are often written as literals in quotation marks, while nonterminals are named symbols.
  • Sequencing: A sequence of symbols (nonterminals and terminals) represents the required order of elements.
  • Alternatives: A choice between options is expressed using a vertical bar or an equivalent operator.
  • Optionality: Optional elements are enclosed in brackets to indicate that they may or may not appear.
  • Repetition: Repetition operators denote zero or more, or one or more occurrences of a subexpression, typically using braces or other grouping symbols.
  • Grouping: Parentheses are used to group subexpressions for precedence and clarity.
  • Termination: Productions typically end with a terminator such as a semicolon or a newline, depending on the dialect.
  • Comments: Grammars may include comments to aid readability.

A representative small grammar illustrating these features:

expression ::= term { ("+" | "-") term } ; term ::= factor { ("*" | "/") factor } ; factor ::= number | "(" expression ")" ; number ::= digit { digit } ; digit ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;

Notes: - The braces { ... } denote repetition (zero or more). - The brackets [ ... ] denote optional elements in some dialects. - Alternatives are shown with the vertical bar within the right-hand side. - Quoted literals represent terminals, and nonterminals are on the left-hand side of productions.

Different dialects may replace or extend these constructs. For example, some variants use a different symbol for the end of a production, or they place production rules in a more compact or more verbose layout. The core ideas—defining a language by composing smaller pieces of syntax—are common across dialects.

Applications

EBNF is widely used in the specification of programming languages, data formats, and communication protocols. Major languages and standards have adopted EBNF-like grammars to convey precise syntax to implementers. The approach supports clear separation between lexical analysis and parsing when used in conjunction with tokenization rules, aiding compiler and interpreter development. In practice, EBNF grammars serve as the bridge between human-readable language design and machine-usable parsers generated by tools.

Tooling and practice around EBNF include the use of parser generators and grammar editors. Popular parser-generator ecosystems and university curricula often rely on EBNF-style grammars to teach concepts such as left factoring, precedence, and associativity, while also illustrating how grammar design choices affect parseability and compiler performance. For standards and web protocols, ABNF is sometimes preferred, but the influence of EBNF-style readability remains evident across many specifications. See for example ABNF in related technical literature and standards documents.

Comparison with other grammar formalisms

  • BNF and EBNF: BNF provides a minimal set of constructs to describe syntax, while EBNF adds expressive conveniences like optionality and repetition, usually making grammars shorter and clearer. This makes EBNF a popular choice for language design, even when the same grammar could be expressed in BNF with more productions.
  • ABNF: ABNF is a close relative designed for internet protocols and data formats. It emphasizes certain repetition and notation conventions that align well with protocol specifications, but it differs from EBNF in its dialectal rules and operators.
  • Formal language theory: While grammars in the EBNF family describe context-free languages, they sit within the broader study of formal languages, automata, and parsing algorithms. Designers often balance readability with the constraints of a chosen parsing strategy (e.g., LL, LR) to ensure that generated parsers are efficient and deterministic.
  • Parser design and tooling: The choice of grammar notation interacts with the capabilities of parser generators (such as those used with ANTLR, YACC/Bison), and with hand-written parsers. EBNF’s readability can influence maintainability and correctness of the resulting parser.

Implementation considerations

When implementing a language from an EBNF grammar, developers consider several practical factors: - Ambiguity: Some grammars may be inherently ambiguous; ensuring unambiguous parsing often requires grammar restructuring and left factoring. - Parser type: The grammar’s form influences whether a top-down (LL) or bottom-up (LR) parser is most suitable, and may lead to grammar transformations to fit the parser’s capabilities. - Lexical analysis: Clear separation of lexical rules from syntax improves reliability; token definitions should be stable and consistent with the terminal symbols used in the grammar. - Dialect choice: Real-world grammars may be written in one EBNF dialect or another. Tools, documentation standards, and team conventions often dictate the chosen variant. - Standards conformance: When formalizing a standard, reference to an official specification such as ISO/IEC 14977 helps ensure portability and interoperability across implementations.

See also