Ensemble Collections

Collections Home -> Planet Math Collection -> Backus-Naur form

TITLE	Backus-Naur form
SUBJECT	msc:68Q45, msc:68Q42
SUBJECT	mathematics
DESCRIPTION	The ... Backus-Naur form (or ... BNF as it is commonly denoted) is a convenient notation used to represent context-free grammars in an intuitive and more compact manner. In a Backus-Naur form, there are only four symbols that have special meaning: ... Given a context-free grammar ... , a non-terminal (a symbol in the alphabet <i>N</i>) is always enclosed in ... .<. and ... .>. (e.g. ... .<expression>.). A terminal (a symbol in the alphabet Sigma) is often represented as itself, though in the context of computer languages a terminal symbol is often enclosed in single quotes. A production ... in <i>P</i> is then represented as ... .<. ... non-terminal ... .> ::= . ... symbols ... The symbol ... .\|. is used in BNF to combine multiple productions in <i>P</i> into one rule. For instance, if ... , then <i>P</i> in BNF is ... .<. ... S ... .> ::= . ... A ... .\|. ... B ... Examples . ... Let ... , ... be the terminal and non-terminal alphabets of a formal grammar, and ... is the set of productions. Then ... is a context-free grammar. The BNF for <i>P</i> is ... For another example, let us transform the context-free grammar specified in the ContextFreeLanguage to BNF. For readability, we will call <i>S</i> ... expression , <i>A</i> ... term , <i>B</i> ... factor , <i>C</i> ... number , and <i>D</i> ... digit . The BNF for <i>P</i> is then ... Remark . As the syntaxes of most programming languages are context-free grammars (or very close to it), the Backus-Naur form can be used to specify these syntaxes. In fact, BNF was invented to specify the syntax of ALGOL 60.
PUBLISHER	PlanetMath
DATE	2009-07-31
TYPE	text
FORMAT	text/html
IDENTIFIER	planetmath:292
SOURCE	http://planetmath.org/encyclopedia/BackusNaurForm.html
LANGUAGE	en-us