Concept

Backus–Naur form

In computer science, Backus–Naur form (ˌbækəs_ˈnaʊər) or Backus normal form (BNF) is a metasyntax notation for context-free grammars, often used to describe the syntax of languages used in computing, such as computer programming languages, document formats, instruction sets and communication protocols. It is applied wherever exact descriptions of languages are needed: for instance, in official language specifications, in manuals, and in textbooks on programming language theory. Many extensions and variants of the original Backus–Naur notation are used; some are exactly defined, including extended Backus–Naur form (EBNF) and augmented Backus–Naur form (ABNF). A BNF specification is a set of derivation rules, written as ::= expression where: is a nonterminal (variable) and the expression consists of one or more sequences of either terminal or nonterminal symbols; means that the symbol on the left must be replaced with the expression on the right. more sequences [of symbols] are separated by the vertical bar "|", indicating a choice, the whole being a possible substitution for the symbol on the left. Symbols that never appear on a left side are terminals. On the other hand, symbols that appear on a left side are non-terminals and are always enclosed between the pair . As an example, consider this possible BNF for a U.S. postal address: ::=
::= |
::= "." | ::=
::= ","
::= "Sr." | "Jr." | | "" ::= | "" This translates into English as: A postal address consists of a name-part, followed by a street-address part, followed by a zip-code part. A name-part consists of either: a personal-part followed by a last name followed by an optional suffix (Jr.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related courses (1)
CS-320: Computer language processing
We teach the fundamental aspects of analyzing and interpreting computer languages, including the techniques to build compilers. You will build a working compiler from an elegant functional language in
Related lectures (19)
CYK Algorithm for Parsing General Grammars
Explores parsing general grammars using the CYK algorithm and Chomsky Normal Form.
Chomsky Normal Form Transformation
Covers the conversion to Chomsky Normal Form by removing unproductive and unreachable symbols.
Scala Syntax Summary
Summarizes Scala syntax, covering types, expressions, and definitions in EBNF.
Show more
Related publications (5)

Scala 3 syntax rewriting

Mark Tropin

We present syntax rewriting rules that translate Scala 2 code into Scala 3. Two major syntactic changes are introduced: new control structure syntax and significant indentation. We describe the design and the implementation of these rules and evaluate thei ...
2024

Towards Empathetic Open-Domain Chatbots

Yubo Xie

The research community of dialog generation has been interested in incorporating emotional information into the design of open-domain dialog systems ever since neural networks (sequence-to-sequence models in particular) were adopted for modeling dialogs. T ...
EPFL2022

RSP-QL Semantics: a Unifying Query Model to Explain Heterogeneity of RDF Stream Processing Systems

Jean Paul Calbimonte Perez

RDF and SPARQL are established standards for data interchange and querying on the Web. While they have been shown to be useful and applicable in many scenarios, they are not sufficiently adequate for dealing with streams of data and their intrinsic continu ...
2014
Show more
Related concepts (23)
Formal grammar
In formal language theory, a grammar (when the context is not given, often called a formal grammar for clarity) describes how to form strings from a language's alphabet 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. Formal language theory, the discipline that studies formal grammars and languages, is a branch of applied mathematics.
Yacc
Yacc (Yet Another Compiler-Compiler) is a computer program for the Unix operating system developed by Stephen C. Johnson. It is a Look Ahead Left-to-Right Rightmost Derivation (LALR) parser generator, generating a LALR parser (the part of a compiler that tries to make syntactic sense of the source code) based on a formal grammar, written in a notation similar to Backus–Naur Form (BNF). Yacc is supplied as a standard utility on BSD and AT&T Unix. GNU-based Linux distributions include Bison, a forward-compatible Yacc replacement.
Imperative programming
In computer science, imperative programming is a programming paradigm of software that uses statements that change a program's state. In much the same way that the imperative mood in natural languages expresses commands, an imperative program consists of commands for the computer to perform. Imperative programming focuses on describing how a program operates step by step, rather than on high-level descriptions of its expected results.
Show more

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.