Definition:Backus-Naur Form/Rules of Formation
Jump to navigation
Jump to search
Definition
Let $\meta {word}$ be a metasymbol of an object language.
Let $\meta {word1}, \meta {word2}, \ldots, \meta {wordn}$ be letters of Backus-Naur form.
That is, $\meta {word1}, \ldots, \meta {wordn}$ may be either metasymbols of, or words in, the object language.
The rules of formation of Backus-Naur form specify two kinds of well-formed formulae:
- $\meta {word} \ ::= \ \meta {word1} \meta {word2} \cdots \meta {wordn}$
This means that $\meta {word}$ on the left hand side may be replaced by the specified sequence of $n$ words on the right hand side.
- $\meta {word} \ ::= \ \meta {word1} \ \mid \ \meta {word2} \ \mid \ \cdots \ \mid \ \meta {wordn}$
This means that $\meta {word}$ on the left hand side may be replaced by one of the $n$ words on the right hand side.