Context-free languages revision notes

What BNF does

Backus–Naur Form (BNF) describes the syntax of a language by using production rules. A production rule states how one named part of the language may be formed. A non-terminal represents a category that can be expanded, while a terminal is an actual symbol or word that appears in the final string. The symbol ::= can be read as “is defined as”, and | means “or”.

For example:

text <digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" <number> ::= <digit> | <digit> <number>

The first rule allows <digit> to be any one digit. The second rule allows a number to contain one digit, or a digit followed by another <number>. Because <number> can refer to itself, the rule can describe numbers of different lengths.

Checking syntax with BNF

To check whether a string is valid, begin with the start symbol and repeatedly replace non-terminals using the available production rules. If the process produces exactly the proposed string, the string conforms to the BNF. If a required symbol cannot be produced, or extra symbols remain, the string is not valid according to those rules.

Using the rules above, 507 can be derived as follows:

text <number> <digit> <number> "5" <number> "5" <digit> <number> "5" "0" <number> "5" "0" <digit> "5" "0" "7"

The derivation finishes with the exact string 507, so it is valid. A string such as 50A is not valid because the rules provide no production that allows A as a digit.

Recursion and nesting

BNF can contain recursive production rules. For example:

text <item> ::= "x" | "(" <item> ")"

This describes x, (x), ((x)), and so on. The rule can therefore represent arbitrary nesting: an item can contain another item, which can contain another item.

A simple expression grammar could be written as:

text <expression> ::= <number> | "(" <expression> ")"

The structure is important: the opening and closing parentheses must occur as matching pairs around a valid expression.

Syntax diagrams

A syntax diagram represents the same kind of information graphically. A path through the diagram shows the order in which symbols may occur. A choice in the diagram corresponds to alternatives in BNF, and a loop corresponds to repetition. When checking a string, follow a valid path from the start to the end. If the whole string can be consumed by one valid path, it conforms to the diagram.

Why BNF can express more than regular expressions

Regular expressions are suitable for patterns that do not require arbitrary nested structure. BNF can use recursion to describe structures whose depth is not fixed in advance. For example, the rule <item> ::= "x" | "(" <item> ")" permits any number of correctly nested pairs of parentheses. A regular expression cannot represent arbitrary matching and nesting of this kind. Therefore, BNF can represent some languages that cannot be represented using regular expressions.

Common errors

• Treating | as meaning that both alternatives must be used; it means one alternative is selected.
• Forgetting that every terminal in the proposed string must be generated.
• Stopping a derivation while non-terminals remain.
• Accepting unmatched parentheses when the production requires a matching pair.
• Assuming that a repeated pattern in a regular expression can always represent recursive nesting.
• Writing a production rule without making clear which symbols are alternatives and which must occur in sequence.