AI Glossary / Natural language and speech / Advanced

Backus-Naur form

Definition

Backus-Naur form, or BNF, is a notation for specifying a context-free grammar. It describes how strings can be built from terminal symbols by expanding named nonterminal symbols through production rules. A designated start symbol identifies the kind of complete expression being defined. BNF specifies permitted structure; meanings and operational behavior generally require additional rules.

What it means

A grammar is a precise description of allowable forms. Terminals are the symbols that remain in a completed string, while nonterminals stand for structures that still need expansion. A production states which sequences can replace a particular nonterminal.
This lets a language designer explain how small pieces combine into larger expressions, including recursively nested structures. It is useful for artificial languages and formal descriptions of some natural-language structures. A grammar's ability to generate a sentence does not establish that the sentence is sensible, factually correct or appropriate in context.

How it works

A common convention writes a production as <name> ::= expression. The left side names one nonterminal; the right side gives a sequence of terminals and nonterminals. A vertical bar separates alternatives. Quotation marks can distinguish literal terminals from notation, although exact conventions vary between specifications.
Starting from the start symbol, repeatedly replace nonterminals using applicable productions until only terminals remain. A parse tree records the hierarchical structure of these expansions. Different expansion orders do not necessarily mean different parse trees. Ambiguity occurs when one terminal string has more than one parse tree under the grammar.
BNF is a grammar notation, not a particular parsing algorithm. Extended BNF adds convenient constructs such as optionality and repetition, with conventions that must be checked. Likewise, a grammar notation resembling BNF may use parsing-expression semantics, where alternatives are ordered. Visual similarity alone does not establish identical behavior.

Three practical examples

• A configuration-language specification uses productions to describe valid declarations and nested blocks. Separate checks determine whether referenced settings exist and whether their values are acceptable for the application.
• A language-processing lesson uses a small grammar to represent noun phrases and verb phrases. The resulting parser illustrates structural analysis without claiming to cover all the variability of human language.
• A structured-output system checks whether generated expressions belong to a defined syntax. Passing that check establishes structural conformity, while task correctness requires further evaluation.

Think of it this way

Think of a construction manual that says which components can be assembled into each named structure. A completed assembly follows the permitted pattern, but the pattern does not automatically explain what the assembly should do. The grammar is the structural manual; interpretation supplies the intended meaning.

Worked example

Define a small arithmetic-expression grammar with start symbol <expr> and these productions:
<expr> ::= <expr> "+" <term> | <term>
<term> ::= <term> "*" <factor> | <factor>
<factor> ::= "1" | "2" | "3" | "(" <expr> ")"
The quotation marks identify terminal symbols and are not part of the generated expression. For this example, spaces in the presentation separate grammar items; they are not literal terminals. The permitted numeral tokens are exactly 1, 2 and 3.
To obtain 1+2*3, first expand <expr> as <expr> "+" <term>. The left <expr> becomes <term>, then <factor>, then "1". The right <term> expands as <term> "*" <factor>. Its left <term> becomes the factor "2", while its right <factor> becomes "3". The final terminal string is 1+2*3.
The structure groups the multiplication inside the right-hand term, giving 1+(2*3). If a separate interpretation assigns ordinary arithmetic meanings to these symbols, its value is seven. The grammar establishes the grouping; the arithmetic interpretation supplies the value.
The grammar also generates (1+2)*3, using a parenthesized expression as a factor in a multiplication. Under the same arithmetic interpretation, this has value nine. Parentheses therefore permit a different grouping without changing the production rules.
However, 12 is not generated. The grammar contains single-digit factors and operators, but no rule joining digits into a multi-digit numeral. Similarly, 1+*2 has no valid expansion. Adding support for multi-digit numbers requires changing the grammar or introducing an appropriate numeral token definition; it cannot be assumed from familiar arithmetic notation.

Illustrative case study

In a fictional calculator project, a team begins with the worked grammar. A reviewer enters 12+3 and expects acceptance because it looks like an ordinary arithmetic expression. The parser rejects it, consistently with the stated grammar.
The team realizes that its product requirement and grammar differ. It introduces an explicit numeral definition, documents how spaces are handled, and decides whether leading zeros are allowed. It also keeps numeric interpretation separate from syntax so that accepted input is evaluated according to stated rules.
A second reviewer proposes replacing the expression rules with <expr> ::= <expr> "+" <expr> | <expr> "*" <expr> | <factor>. This simpler-looking structure permits both relevant groupings of 1+2*3. The team retains the layered rules to express precedence clearly. The lesson is that shorter grammar text can change the language's structural interpretation.

Common misconceptions and mistakes

A grammar is not automatically unambiguous merely because its productions look precise. Also, a valid grammar may be unsuitable for a particular parser without transformation. The worked grammar uses left recursion, which a naive recursive-descent implementation would need to address.
Syntax acceptance does not establish semantic validity. In richer languages, type compatibility, declared names and application constraints often require additional analysis. Do not silently treat every notation called BNF as having the same optionality, repetition or alternative-selection conventions.

Business use

Formal grammar descriptions help teams agree on interfaces, configuration formats and structured inputs. Publish the start symbol, token definitions and notation conventions together. Test accepted and rejected examples against requirements, and explain which checks are structural and which concern meaning or permitted operations.

People also ask

Is BNF a programming language?

It is a notation for describing grammars.

Does BNF calculate expression values?

Not by itself.

Can a BNF grammar be recursive?

Yes; recursion describes structures such as nested expressions.

Check your understanding

Answer: What is the worked start symbol? <expr>.

Why is 12 rejected?

Answer: No production defines a multi-digit numeral.

What gives multiplication its tighter grouping here?

Answer: The separate expression, term and factor levels.

Related terms

• Context-free grammar
• Start symbol
• Parse tree
• Ambiguity
• Syntax
• Semantics
• production rule
• terminal
• nonterminal
• extended BNF

Learn next

Compare parse trees for ambiguous and precedence-based grammars, then examine how a parser implements the chosen rules.

More in Natural language and speech

• Auxiliary - An auxiliary is a grammatical word that helps express distinctions such as tense, aspect, voice, or modality in a predicate.
• Backoff - Backoff is a language-modeling strategy that uses a less specific estimate when the more specific context lacks sufficient evidence.
• Backtranslation - Backtranslation is a machine-translation training technique that turns target-language text into additional synthetic parallel data.
• Basic emotions - Basic emotions are a limited set of emotion categories proposed as fundamental within a particular theory of emotion.
• Beam width - Beam width is the maximum number of candidate partial solutions retained at a step of a beam-search procedure.
• Benchmarks - Benchmarks are specified tasks, data and evaluation procedures used to compare systems under shared conditions.

Sources

Artificial Intelligence: A Modern Approach glossary, Backus-Naur form (BNF). https://github.com/aimacode/aima-glossary/blob/master/glossary.md Python Language Reference, notation: an example of explicitly documented EBNF and PEG conventions, distinct from plain BNF alternatives. https://docs.python.org/3/reference/introduction.html#notation The arithmetic grammar and fictional calculator case are original teaching illustrations.

Previous: Backus - Gilbert method Next: Backward-chaining