巴科斯范式（Backus–Naur Form）介绍

简介

巴科斯范式（Backus Normal Form简称为BNF），又称为巴科斯-诺尔范式，是一种上下文无关的语言，广泛地使用于程序设计语言、指令集、通信协议的语法表示中。在各种文献中，还存在巴科斯范式的一些变体，如扩展巴科斯范式（ENBF）或扩充巴科斯范式。

上下文无关语言

 我们假定您已了解正则语言——一种通过有限状态机或正则表达式表达的语言，这种语言是字符串集的子集。我们现在来介绍另一种语言——上下文无关语言。任何的正则语言都是一种上下文无关语言。

大部分程序语言可被定义为上下文无关语言。要定义上下文无关语言，我们需要使用上下文无关语法，上下文无关语法的一个例子是巴科斯范式。

巴科斯范式

巴科斯范式是一种上下文无关语法，它使用一系列符号和表达式来创建字符串生成规则。一个简单的BNF生成规则类似如下：

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

上述文法代表任意一个0到9的任意一个数字。这里的尖括号“<>”是非终结符，如果一个非终结符出现在生成规则的右边，这意味着会有另一条生成规则来解释代替它的位置。考虑如下生成规则：

<fullname>::=<title><name><name>

这里<fullname>由<title>、<name>和另一个<name>字符串构成。例如，我们可以定义如下生成规则来代替<title>：

<title>::=Mr|Mrs|Ms|Miss|Dr

在这条规则中，Mr、Mrs、Ms、Miss和Dr均是终结符，它们是title的实际值，符号“|”在这里代表元字符，含义是“或”。这条规则的具体含义<title>可被解释为Mr或Mrs或Ms或Miss或Dr中的一个。

当你在表达式右侧看到非终结符时，就一定有一条生成规则，该非终结符是在左侧的。这个一直持续到任一非终结符都出现在某一条生成规则的左侧为止。让我们来看另一组生成规则：

　　<addition> ::= <number>+<number>
    <number> ::= <sign><integer>|<integer>
    <integer> ::= <digit>|<digit><integer>
    <digit>::=0|1|2|3|4|5|6|7|8|9
    <sign> ::= +|-

上述生成规则表示由任意两个整数相加得到的表达式。

巴科斯范式生成规则中的递归