Backus – Naur形式

不要与Boyce -Codd正常形式混淆。

在计算机科学中， Backus-Naur形式（ ）（BNF或Backus正常形式）是用于描述编程语言或其他形式语言的语法的符号。它是由约翰·贝克斯（John Backus）和彼得·诺（Peter Naur）开发的。 BNF可以描述为无上下文语法的Metasyntax符号。在需要在官方语言规格，手册中以及有关编程语言理论的教科书中，需要在任何地方进行精确描述语言的确切描述。 BNF可用于描述文档格式，指令集和通信协议。

使用了原始的Backus -Naur符号的许多扩展和变体；有些是完全定义的，包括延伸的backus -naur形式（EBNF）和增强的Backus -Naur形式（ABNF）。

概述

BNF规范是一组派生规则，写为

 <symbol> ::= __expression__

在哪里：

  • <symend>是一个非末端变量，始终封闭在对之间的<>之间。
  • ::=意味着必须将左侧的符号替换为右侧的表达式。
  • __ expression __由一个或多个终端或非末端符号的序列组成，其中每个序列都被垂直条“ |”隔开。指示选择，整个可能是左侧符号的可能替代。

例子

例如，以美国邮政地址为例：

 <postal-address> ::= <name-part> <street-address> <zip-part>
      <name-part> ::= <personal-part> <last-name> <opt-suffix-part> <EOL> | <personal-part> <name-part>
  <personal-part> ::= <first-name> | <initial> "."
 <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" <apt-num> | ""

这将英语转化为：

  • 邮政地址由名字组成，然后是街道地址部分，然后是邮政编码部分。
  • 名称部分由：个人部分组成：姓氏，然后是姓该规则说明了BNF中递归的使用，涵盖了使用多个名称和姓名姓名的人的情况）。
  • 个人部分由名字或最初的名字组成，然后是点。
  • 街道地址由房屋号码组成，然后是街道名称，然后是可选的公寓指定者，然后是一条终点。
  • Zip-part由一个城镇名称组成，然后是逗号，然后是州法规，然后是邮政编码，然后是一条末端。
  • Opt-Suffix-Part由后缀组成，例如“ Sr.”，“ Jr。”。或罗马名称，或一个空字符串（即没有）。
  • 选项数字由前缀“ apt”组成，然后是公寓号或一个空字符串（即没有）。

请注意，许多内容（例如名称，公寓号，邮政编码和罗马数字的格式）在此处未指定。如有必要，可以使用其他BNF规则来描述它们。

历史

使用重写规则来描述语言结构的想法可以追溯到至少帕尼尼（Pāṇini）的作品，帕尼尼（Pāṇini）是一位古老的印度梵语语法主义者，也是印度教的受人尊敬的学者，他生活在公元前6到4世纪之间的某个时候。他描述梵语单词结构的符号等效于Backus，并且具有许多相似的属性。

在西方社会中，语法长期以来一直被视为教学的主题，而不是科学研究。描述是非正式的，并针对实际使用。在20世纪上半叶，伦纳德·布卢姆菲尔德（Leonard Bloomfield）和泽利格·哈里斯（Zellig Harris）等语言学家开始尝试形式化语言的描述，包括短语结构。

同时，诸如Axel Thue （1914年）， Emil Post （1920年代至40年代）和Alan Turing （1936年）等数学家（1914年）等数学家（1914年）介绍和研究了字符串重写规则。诺姆·乔姆斯基（Noam Chomsky） ，在麻省理工学院（MIT）向信息理论的学生讲语言学，通过将本质上是Thue的形式主义作为描述自然语言语法的基础，将语言学和数学结合在一起。他还提出了生成规则（无上下文语法）和转型规则（1956年）之间的明确区别。

IBM的编程语言设计师John Backus提出了一种“元语言公式”的金属语言来描述新的编程语言IAL的语法，如今已被称为Algol 58 （1959）。他的符号首次在Algol 60报告中使用。

BNF是乔姆斯基无上下文语法的符号。 Backus熟悉乔姆斯基的作品。

正如Backus提出的那样，公式定义了“类”，其名称以角度括号为单位。例如，<ab>。这些名称中的每一个都表示一类基本符号。

阿尔戈尔的进一步发展导致了阿尔戈尔60 。在委员会的1963年报告中，彼得·诺尔（Peter Naur）称Backus符号Backus正常形式。唐纳德·诺斯（Donald Knuth）认为，BNF应该宁愿将其读成Backus -Naur形式，因为它“在常规意义上不是正常形式”，例如，与乔姆斯基的正常形式不同。鉴于Backus正常形式可能不准确，并且Pāṇini较早地独立开发了类似的符号，鉴于Backus正常形式可能不准确的事实，也曾经建议使用PāṇiniBackus形式。

彼得·诺尔（Peter Naur）在Algol 60报告中描述了BNF为元语言公式：

括号中包含的字符序列<>代表其值是符号序列的属性变量。标记“ :: =”和“ |” （后者俱有“或”的含义）是元语言连接。公式中的任何标记（不是变量或结缔组织）表示自己。公式中的标记或变量并置表示表示的序列的并置。

Algol 60报告中的另一个例子说明了BNF Metalanguage和Chomsky无上下文语法之间的主要区别。金属语言变量不需要定义其形成的规则。它们的形成可以简单地在<>括号内用自然语言描述。以下Algol 60 Report 2.3评论规范说明了这项工作的工作方式：

为了将文本包括在程序的符号之间

基本符号的顺序：等同于
;评论<任何不包含';'>的序列;;
开始评论<任何不包含'''>的序列;开始
结束<任何不包含“ end”或“”;'的序列或“ else”>结尾

在这里，等效性意味着，在字符串之外的任何发生，在右列中的同一行中显示的符号都可以替换左列中显示的三个结构中的任何一个，而不会对程序的动作产生任何影响。

诺尔将Backus的两个符号更改为常见的字符。这::=符号最初是:≡。这|符号最初是单词“或”（上面有一个栏）。

BNF与逻辑电路设计中使用并且在当时使用的规范形式布尔代数方程非常相似。 Backus是数学家，也是Fortran编程语言的设计师。布尔代数的研究通常是数学课程的一部分。 Backus和Naur都没有描述包含在< >作为非末端。 Chomsky的术语最初不是在描述BNF的。诺尔后来将它们描述为Algol课程材料的课程。在Algol 60的报告中，它们被称为属语言变量。除了偏移符号之外::=,|，以及包含的班级名称< >是所定义的语言的象征。中部符号::=被解释为“被定义为”。这|用于分开替代定义，并将其解释为“或”。偏移板< >是封闭类名称的定系数。 BNF被描述为彼得·诺尔（Peter Naur）和索尔·罗森（Saul Rosen）谈论Algol的一种属性语言。

1947年，索尔·罗森（Saul Rosen）参与了刚起步的计算机机械协会的活动，首先是语言委员会成为IAL集团的语言委员会，并最终导致了Algol。他是ACM通信的第一位执行编辑。 BNF首先被用作Algol 60报告中的Algol语言。这就是彼得·诺（Peter Naur）在1962年开发的Algol编程课程材料中的解释。IBM，Honeywell，Burroughs和Digital Equipment Corporation的早期Algol手册遵循了Algol 60的报告，该报告使用它作为Metalanguage。索尔·罗森（Saul Rosen）在他的书中将BNF描述为谈论阿尔戈尔的一种金属语言。它用作金属语言的一个例子是定义算术表达：

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

替代方案的第一个符号可能是定义的类，正如诺尔（Naur）所解释的那样，重复的功能是指定替代序列可以从先前的替代方案递归开始，并且可以重复多次。例如，上面<expr>被定义为<term>其次是任意数量的<addop> <term>.

在一些后来的金属语言中，例如Schorre的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>。班级是抽象。我们可以独立于其形成来谈论它。我们可以谈论术语，独立于其定义，在Expr中添加或减去。我们可以讨论一个术语是特定的数据类型，以及如何评估一个特定组合数据类型的ExpR，甚至可以将表达式重新排序到组数据类型和混合类型的评估结果。自然语言补充剂提供了编译器实施和编写Algol程序的语言类语义语义的具体细节。自然语言描述也进一步补充了语法。整数规则是用于描述语法的自然语言和金属语言的一个很好的例子：

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

上面的空白空间没有细节。就规则所示，我们可以在数字之间有空间。在自然语言中，我们通过解释数字序列可以在数字之间没有空间来补充BNF Metalanguage。英语只是可能的自然语言之一。 Algol报告的翻译有许多自然语言。

BNF的起源并不像对编程语言发展的影响那么重要。在发布Algol 60报告后，BNF的直接段是许多编译器组合系统的基础。

有些，例如由Edgar T. Irons开发的“ Algol 60的语法编译器”和由Brooker和Morris开发的“编译器建筑系统”，直接使用BNF。其他人，例如Schorre MetaCompilers，它将其纳入了一种编程语言，只有几个更改。<class name>成为符号标识符，放下封闭式<，>，并使用引用的字符串作为目标语言的符号。类似算术的分组提供了一种简化的，该简化使用分组是其唯一值的类进行了删除。元II算术表达规则显示了分组使用。放置在元II规则中的输出表达式用于以汇编语言输出代码和标签。元II中的规则等同于BNF中的类定义。 UNIX实用程序YACC基于BNF，代码生产类似于Meta II。 YACC最常用作解析器发生器，其根显然是BNF。

今天，BNF是仍在使用的最古老的与计算机相关的语言之一。

进一步的例子

BNF syntax diagram
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>分别用声明的规则的名称/标签或文字替代。

在上面的美国邮政地址示例中，整个块引号是<syntax>。线条的每一行或不间断分组是一条规则。例如一个规则以<name-part> ::=。该规则的另一部分（除线端）是一个表达式，该表达式由两个列表组成，由垂直条隔开|。这两个列表包括一些术语（分别为三个术语和两个术语）。此特定规则中的每个术语都是规则名称。

变体

EBNF

主要文章：扩展的Backus -Naur形式

BNF有许多变体和扩展，通常是为了简单性和简洁性，或者使其适应特定的应用程序。许多变体的一个共同特征是使用正则表达重复运算符，例如*和+。伸展的靠背形式（EBNF）是常见的。

另一个常见的扩展是在可选项目周围使用方括号。尽管原始Algol 60报告中不存在（而是在IBM的PL/I定义中引入了几年后），但该符号现在已被普遍认可。

abnf

主要文章： ABNF

增强的Backus -Naur形式（ABNF）和路由Backus -Naur形式（RBNF）是通常用于描述互联网工程工作组（IETF）协议的扩展。

解析表达语法建立在BNF和正则表达符号上，形成了替代形式的形式语法，该语法本质上是分析性的，而不是特征的生成性。

其他的

当今在线发现的许多BNF规格旨在是可读的，并且是非正式的。这些通常包括以下许多语法规则和扩展：

  • 封闭在方括号中的可选项目：[<item-x>].
  • 现有0次或更多次的项目被封闭在卷曲括号中或带有星号的后缀（*） 例如<word> ::= <letter> {<letter>}或者<word> ::= <letter> <letter>*分别。
  • 现有1次或更多次的项目带有加法（加）符号，+， 例如<word> ::= <letter>+.
  • 终端可能以粗体而不是斜体形式出现，而非末端则以纯文本而不是角括号为单位。
  • 在将项目分组的地方，它们被包裹在简单的括号中。

使用BNF或变体的软件

接受BNF（或超集）作为输入的软件

  • Antlr ，用Java编写的解析器发电机
  • 可可/r ，编译器发电机，接受EBNF中的属性语法
  • DMS软件重新设计工具包，任意语言的程序分析和转换系统
  • 黄金，BNF解析器发电机
  • RPA BNF解析器。在线（PHP）演示解析：JavaScript，XML
  • XACT X4MR系统，一种基于规则的专家系统，用于编程语言翻译
  • XPL Analyzer，一种接受一种语言的简化BNF的工具，并在XPL中生成该语言的解析器；它可以将其集成到提供的骨骼程序中，该程序可以通过该程序进行调试（共享贡献程序，在编译器生成器之前）
  • BNFPARSER 2 ，通用语法验证实用程序
  • BNF2XML，使用高级BNF匹配的带有XML标签的标记输入
  • Javacc ，Java编译器编译器TM（JavACC TM） - Java Parser Generator

类似的软件

  • GNU BISON ，GNU版本的YACC
  • YACC ，解析器发生器（最常用于Lex预处理器）
  • 球拍的解析器工具，LEX和YACC风格的解析（美丽的球拍版）
  • BI工具Qlik Sense使用BNF的变体进行脚本
  • BNF转换器（BNFC），在称为“标记的Backus -Naur形式”（LBNF）的变体上运行。在此变体中，给定非末端的每个生产都有一个标签，可以用作代表该非末端的代数数据类型的构造函数。转换器能够用几种语言生产抽象语法的类型和解析器，包括Haskell和Java

也可以看看