巴科斯范式

使用重写规则来描述语言结构的想法至少可以追溯到Pāṇini（古代印度梵语语法学家和印度教的一位受人尊敬的学者，生活在公元前7世纪到4世纪的某个时候）的工作。^[1][2]他描述梵文单词结构符号的标记在能力上等同于巴科斯的标记，并且两者具有许多相似的性质。

在西方社会，语法长期以来被认为是一门教学科目，而不是科学研究；描述是非正式的，针对实际使用。在20世纪上半叶，伦纳德·布龙菲尔德和泽尔利·哈里斯等语言学家开始尝试将语言描述形式化，包括短语结构。

同时，阿克塞尔·图厄（1914年）、埃米尔·波斯特（1920-40年代）和阿兰·图灵（1936年）等数学家引入并研究了作为形式逻辑系统的字符串重写规则。诺姆·乔姆斯基讲授麻省理工学院信息论专业的语言学，他把语言学和数学结合起来，把本质上是Thue的形式主义作为描述自然语言句法的基础。他还明确区分了生成规则（上下文无关语法）和转换规则（1956）。^[3][4]

约翰·巴科斯是国际商用机器（IBM）公司的编程语言设计师，他提出了一种“元语言公式”的元语言来描述新的编程语言IAL的语法，现在被称为ALGOL 58 （1959）。他的标记首次出现在ALGOL 60报告中。

BNF是乔姆斯基上下文无关文法的一种符号。显然，巴克斯熟悉乔姆斯基的工作。^[5]

正如巴克斯所提议的，公式定义了名称被括在尖括号中的“类”。例如，< ab >。其中的每一个名称都表示一类基本符号。^[6]

随着ALGOL的进一步发展，ALGOL60诞生了。在委员会1963年的报告中，彼得·诺尔称巴克斯符号为巴克斯范式。高德纳 （Donald Knuth）认为BNF应该理解为巴克斯-瑙尔范式，因为它“不是传统意义上的范式”，^[7]正如它与乔姆斯基范式不同。Pāṇini·巴克斯形式这个名字也曾被提出，因为事实上，扩展巴克斯范式可能不准确，而pāṇini早些时候独立地发展了一个类似的标记。^[8]

彼得·诺尔在ALGOL 60报告中将BNF描述为元语言公式。方括号<>中包含的字符序列代表元语言变量，其值是符号序列。标记“::=”和“|”（后者的意思是“或”）是元语言连接词。公式中的任何不是变量或连接词的标记都表示它自己。公式中标记或变量的并置表示它们所表示的序列的并置。^[9]

ALGOL 60报告的另一个例子说明了BNF元语言和乔姆斯基上下文无关语法之间的一个主要区别。元语言变量不需要定义它们形成的规则。它们的形成可以在<>括号内用自然语言简单描述。下面的ALGOL 60报告第2.3节注释规范举例说明了其工作原理：

为了在程序的符号中包含文本，下列“注释”约定如下：

这里的等价性是指，在字符串之外的任何情况下，左边列中显示的三个结构中的任何一个都可以被右边列中同一行中显示的符号替换，而不会对程序的操作产生任何影响。

诺尔把巴克斯的两个符号变成了常用的字符。“::=”符号最初是“:”。“|”符号最初是单词“or”（上面有条杠）。^[10]巴克斯在为国际商用机器公司（IBM）工作时会有一个保密协议，如果它来自一个国际商用机器公司（IBM）的专有项目，他就不能谈论他的消息来源。BNF非常类似于当时用于逻辑电路设计的规范形式布尔代数方程。巴克斯是数学家和FORTRAN编程语言的设计者。布尔代数的研究通常是数学的一部分。我们所知道的是，巴克斯和诺尔都没有将< >中包含的名称描述为非终结符号。乔姆斯基术语最初并不用于描述BNF。诺尔后来将它们描述为ALGOL课程材料中的类。^[6]在ALGOL 60报告中，它们被称为元语言变量。除了元符号::=，|，和<，>中包含的类名之外的任何东西都是所定义语言的符号。元符号::=应解释为“定义为”。|用于分隔替代定义，并被解释为“或”。元符号<，>是包含类名的分隔符。彼得·诺尔和索尔·罗森把BNF描述为谈论ALGOL语言的一种元语言。^[6]1947年，索尔·罗森参与了新兴的ACM计算机学会的活动，首先是语言委员会，后来成为国际语言学会（IAL）的成员，并最终成立了ALGOL。他是ACM通讯的第一任总编辑。我们所知道的是，在ALGOL 60报告中，BNF首先被用作一种元语言来谈论ALGOL语言。这就是彼得·诺尔在1962年开发的ALGOL程序设计课程材料中的解释。^[6] 由国际商用机器（IBM）公司、霍尼韦尔公司、巴勒斯公司和数字设备公司编写的早期ALGOL手册遵循ALGOL 60报告，使用ALGOL 60作为一种原语言。索尔·罗森在他的著作中^[11] 描述BNF是一种谈论ALGOL语言的元语言。它用作元语言的一个例子是定义一个算术表达式：

<expr> ::= <term>|<expr><addop><term>

替代的第一个符号可以是被定义的类，如Naur所解释的，重复具有指定替代序列可以递归地从先前的替代开始并且可以重复任意次数的功能。^[6] 例如，上面 <expr> 被定义为 <term> ，接下来是任意数量的 <addop> <term>。

在后来的一些元语言中，如朔尔的META II，BNF递归重复结构被序列运算符和使用引用字符串定义的目标语言符号所取代。去掉 < 和 > 括号。添加数学分组 （ ） 。 <expr> 规则将在META II中显示为：

EXPR = TERM $('+' TERM .OUT('ADD') | '-' TERM .OUT('SUB'));

这些变化使得META II及其衍生编程语言能够定义和扩展它们自己的元语言。 这样做就失去了使用自然语言描述、元语言变量、语言结构描述的能力。许多派生的元语言都是受BNF启发的。参见META II、TREE-META和元编译程序（Metacompiler）。

BNF类描述了一种语言结构的形成，其中的形成被定义为一种模式或形成该模式的动作。类名expr在自然语言中被描述为 <term> ，接下来是一个序列 <addop> <term>。类是一个抽象概念，我们可以独立于它的形成来谈论它。我们可以把term，不管它的定义如何，说成是在expr中加或减。我们可以把term说成是一种特定的数据类型，以及如何使用特定的数据类型组合来评估expr。或者甚至将表达式重新排序以将数据类型和混合类型的评估结果分组。自然语言补充提供了语言类语义的具体细节，供编译器实现和编写ALGOL程序的程序员使用。自然语言描述也进一步补充了语法。整数规则是用来描述语法的自然语言和元语言的一个很好的例子：

<integer> ::= <digit>|<integer><digit>

上面没有关于空白的细节。根据规则，数字之间可以有空格。在自然语言中，我们通过解释数字序列之间不能有空格来补充BNF元语言。英语只是可能的自然语言之一。ALGOL报告的翻译有许多自然语言版本。

BNF的起源不如它对编程语言开发的影响重要。在ALGOL 60报告发表后不久，BNF是许多编译器-编译器系统的基础。有些直接使用BNF，如埃德加·艾恩斯（Edgar T. Irons）开发的“ALGOL 60语法导向编译器”和布鲁克和莫里斯开发的“编译器构建系统”。其他人把它改成了编程语言。朔尔元编译器只做了几处改动就把它变成了一种编程语言。 <class name> 成为了符号标识符，去掉了封闭符<，>并使用引用字符串作为目标语言的符号。像分组这样的算法提供了简化，使用分组是唯一值的类消除了简化。META II 算法表达式规则显示了分组使用。META II规则中的输出表达式用于以汇编语言输出代码和标签。META II中的规则相当于BNF中的类定义。Unix实用程序yacc基于BNF，代码生成类似于META II。yacc最常用作解析器生成器，它的根显然是BNF。如今，BNF是仍在使用的最古老的计算机相关语言之一。

BNF规范是一组派生规则，编写如下：

 <symbol> ::= __expression__

其中<symbol>^[6] 是一个非终结符，并且__expression__ 由一个或多个符号序列组成；更多的序列用竖线“|”隔开，表示一个选择，整个序列可能是左边符号的替代。永远不会出现在左侧的符号是终端。另一方面，出现在左侧的符号是非终结符，并且总是包含在对<>之间。^[6]

“::=”表示左边的符号必须用右边的表达式替换。

例如，考虑美国邮政地址的这种可能的BNF：

 <postal-address> ::= <name-part> <street-address> <zip-part>

      <name-part> ::= <personal-part> <last-name> <opt-suffix-part> <EOL> 
                    | <personal-part> <name-part>

  <personal-part> ::= <initial> "." | <first-name>

 <street-address> ::= <house-num> <street-name> <opt-apt-num> <EOL>

       <zip-part> ::= <town-name> "," <state-code> <ZIP-code> <EOL>

<opt-suffix-part> ::= "Sr." | "Jr." | <roman-numeral> | ""
    <opt-apt-num> ::= <apt-num> | ""

翻译成中文就是：

• 邮政地址由名称部分、街道地址部分、邮政编码部分组成。
• 姓名部分由以下两个部分组成：个人部分，后跟姓氏，然后是一个可选后缀（Jr、Sr或王朝编号）和行尾，或者个人部分，后跟姓名部分（此规则说明了递归在BNFs中的使用，涵盖了使用多个名字和中间名以及首字母的人的情况）。
• 个人部分由名字或首字母加一个点组成。
• 街道地址由门牌号、街道名称、可选的公寓说明符和行尾组成。
• 邮政编码由城镇名称、逗号、州代码、邮政编码和行尾组成。
• 可选后缀部分由后缀组成，如“Sr”，“Jr”，或罗马数字，或空字符串（即无）。
• opt-apt-num由公寓号或空字符串（即无）组成。

请注意，许多东西（例如名字、公寓说明符、邮政编码和罗马数字）在这里没有指定。如有必要，可以使用附加的BNF规则来描述它们。

BNF的语法本身可以用如下的BNF来表示：

 <syntax>         ::= <rule> | <rule> <syntax>
 <rule>           ::= <opt-whitespace> "<" <rule-name> ">" <opt-whitespace> "::=" <opt-whitespace> <expression> <line-end>
 <opt-whitespace> ::= " " <opt-whitespace> | ""
 <expression>     ::= <list> | <list> <opt-whitespace> "|" <opt-whitespace> <expression>
 <line-end>       ::= <opt-whitespace> <EOL> | <line-end> <line-end>
 <list>           ::= <term> | <term> <opt-whitespace> <list>
 <term>           ::= <literal> | "<" <rule-name> ">"
 <literal>        ::= '"' <text1> '"' | "'" <text2> "'"
 <text1>          ::= "" | <character1> <text1>
 <text2>          ::= '' | <character2> <text2>
 <character>      ::= <letter> | <digit> | <symbol>
 <letter>         ::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z"
 <digit>          ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
 <symbol>         ::=  "|" | " " | "!" | "#" | "$" | "%" | "&" | "(" | ")" | "*" | "+" | "," | "-" | "." | "/" | ":" | ";" | ">" | "=" | "<" | "?" | "@" | "[" | "\" | "]" | "^" | "_" | "`" | "{" | "}" | "~"
 <character1>     ::= <character> | "'"
 <character2>     ::= <character> | '"'
 <rule-name>      ::= <letter> | <rule-name> <rule-char>
 <rule-char>      ::= <letter> | <digit> | "-"

请注意""是空字符串。

原始BNF没有使用引号，如 <literal> 规则所示。这假设没有空格是正确解释规则所必需的。

<EOL> 表示适当的行尾说明符（在ASCII中，回车、换行符或两者都有，具体取决于操作系统）。 <rule-name> 和 <text> 分别用声明的规则名称/标签或文字文本替换。

在上面的美国邮政地址示例中，整个块引用是一种语法。 每一行或连续的行分组是一个规则；例如，一条规则以 <name-part> ::=开头。该规则的另一部分（除了行尾）是一个表达式，它由两个由符号|分隔的列表组成 。 这两个列表由一些术语组成（分别为三个术语和两个术语）。 这个特定规则中的每个术语都是一个规则名。

BNF有许多变体和扩展，通常是为了简单明了，或者是为了适应特定的应用。许多变体的一个共同特征是使用正则表达式重复运算符，例如 * 和 +。扩展的巴克斯-瑙尔范式（EBNF）是一种常见的形式。

另一个常见的扩展是在可选项目周围使用方括号。虽然在最初的ALGOL 60报告中没有出现（而是几年后在IBM的PL/I定义中引入），但这种符号现在已被普遍认可。

增强巴克斯-瑙尔范式（ABNF）和路由巴克斯-瑙尔范式（RBNF）^[12]是常用于描述因特网工程任务组（IETF）协议的扩展。

解析表达式语法建立在BNF和正则表达式标记的基础上，形成了另一类形式语法，它本质上是分析性的，而不是生成性的。

现今在网上找到的许多BNF规范都是可读的，而且是非正规的。这些通常包括以下许多语法规则和扩展：

• 方括号内的可选项目： [<item-x>]。
• 存在0次或更多次的项被括在大括号中或以星号作为后缀（*）。例如分别是 <word> ::= <letter> {<letter>} 或者 <word> ::= <letter> <letter>* 。
• 存在1次或多次的项以加号， +作为后缀。
• 终端可以用粗体而不是斜体显示，非终端可以用纯文本而不是尖括号显示。
• 在项目分组的地方，它们用简单的括号括起来。

5.1 使用BNF的软件

• ANTLR，另一个用Java编写的解析器生成器。
• BNF转换器（BNFC^[13]），在一种叫做“标记的巴克斯-瑙尔范式”（LBNF）的变体中运行。在这个变体中，给定非终端的每个产生式都被赋予一个标签，该标签可以用作表示该非终端符号的代数数据类型的构造器。转换器能够为抽象语法生成类型和分析器，包括Haskell和Java。
• Coco/R，在EBNF中接受属性语法的编译器生成器。
• DMS软件重组工具包（DMS Software Reengineering Toolkit），面向任意语言的程序分析和转换系统。
• 黄金BNF解析器。
• GNU bison，yacc的GNU版本。
• RPA BNF解析器。^[14] 在线（PHP）演示解析：JavaScript，XML。
• XACT X4MR系统^[15] 一个基于规则的编程语言翻译专家系统。
• XPL分析器，一个接受一种语言的简化BNF并在XPL中为该语言生成一个解析器的工具；它可以被集成到所提供的框架程序中，通过该程序可以调试该语言^[16] （一个SHARE共享程序，在之前的《A Compiler Generator》书中就已提到，ISBN 978-0-13-155077-3）。
• Yacc，解析器生成器（与Lex预处理器一起使用）。
• bnfparser²,^[17] 一个通用语法验证实用程序。
• bnf2xml，^[18] 使用高级BNF匹配的带有xml标记的标记输入。
• JavaCC，^[19] Java编译器编译器TM（JavaCC TM）-Java解析器生成器。
• Racket的解析工具，lex和yacc风格的解析（Racket的美化版本）。