|
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: $$\verb.<.\qquad \verb.>.\qquad \verb.::=.\qquad \verb.|.$$ Given a context-free grammar $(\Sigma,N,P,S)$ , a non-terminal (a symbol in the alphabet $N$ ) 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 $({non-terminal}\to {symbols})$ in $P$ is then represented as
<non-terminal> ::= symbols
The symbol | is used in BNF to combine multiple productions in $P$ into one rule. For instance, if $P := \left\{S\to A, S\to B\right\}$ , then $P$ in BNF is
<S> ::= A | B
Examples.
- Let $\Sigma=\lbrace a,b,c\rbrace$ , $N=\lbrace S,T,U\rbrace$ be the terminal and non-terminal alphabets of a formal grammar, and $$P=\lbrace S\to aSb, S\to TU, S\to c, T\to cUc, T\to ac, U\to bT, U\to cb\rbrace$$ is the set of productions. Then $(\Sigma,N,P,S)$ is a context-free grammar. The BNF for $P$ is \begin{eqnarray*} \verb.<.\textit{S}\verb.>.&\verb.:=.& \textit{a}\verb.<.\textit{S}\verb.>.\textit{b}\verb. | <.\textit{T}\verb.><.\textit{U}\verb.> | .\textit{c}\\ \verb.<.\textit{T}\verb.>.&\verb.:=.& \textit{c}\verb.<.\textit{U}\verb.>.\textit{c} \verb. | .\textit{ac}\\ \verb.<.\textit{U}\verb.>.&\verb.:=.& \textit{b}\verb.<.\textit{T}\verb.> | .\textit{cb} \end{eqnarray*}
- For another example, let us transform the context-free grammar specified in the parent entry to BNF. For readability, we will call $S$ expression, $A$ term, $B$ factor, $C$ number, and $D$ digit. The BNF for $P$ is then
\begin{eqnarray} \verb.<.expression\verb.>. & \verb.::=. & \verb.<.term\verb.>.\, \verb.|.\,\verb.<.expression\verb.>.\,\verb.+.\,\verb.<.term\verb.>.\, \verb.|.\,\verb.<.expression\verb.>.\,\verb.-.\,\verb.<.term\verb.>. \nonumber \\ \verb.<.term\verb.>. & \verb.::=. & \verb.<.factor\verb.>.\, \verb.|.\,\verb.<.term\verb.>.\,\verb.*.\,\verb.<.factor\verb.>.\, \verb.|.\,\verb.<.term\verb.>.\,\verb./.\,\verb.<.factor\verb.>. \nonumber \\ \verb.<.factor\verb.>. & \verb.::=. & \verb.<.number\verb.>.\,\verb.|.\, \verb.(<.expression\verb.>). \nonumber \\ \verb.<.number\verb.>. & \verb.::=. & \verb.<.digit\verb.>.\,\verb.|.\, \verb.<.number\verb.>.\,\verb.<.digit\verb.>. \nonumber \\ \verb.<.digit\verb.>. & \verb.::=. & \verb.0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9.\label{b} \end{eqnarray}
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.
|