BNF

By: Lars Marius Garshol
原文参见：http://www.garshol.priv.no/download/text/bnf.html
（本文是上述作者文章的翻译，原文版权归作者所有）
(译者：Sunnybill)
BNF 和EBNF的含义与用法 1
简介
      关于本文
      什么是BNF?
工作原理
      基本原理
      一个实例
EBNF及其用途
      一个EBNF语法实例
      BNF和EBNF的使用
          一般用法
         如何使用形式语法
解析
    最简单的方法
          自上而下的解析(LL)
          一个LL分析实例
          一个LL转换实例
      稍难的方法
          自底而上的解析(LR)
     LL还是LR？
      更多信息
附录
      致谢

简介
关于本文
      这是一篇针对<[e-mail] > 16.Jun.98年6月16日发布在comp.text.sgml 的信息而写的一篇解释BNF的短文，有些粗略，不详之处可与作者联系，作者将会尽量解释。
现在文章越来越长，但你不必担心，文章将会逐渐深入。如果你不想深入了解，你可以只看感兴趣的部分，从中寻找你的问题答案即可。


什么是BNF?
      Backus-Naur符号（就是众所周知的BNF或Backus-Naur Form）是描述语言的形式化的数学方法，由John Backus (也许是Peter Naur)开发，用于描述Algol 60编程语言的语法。
      最初的时候是许多标记（图例），是John Backus 在数学家Emil Post早期工作的基础上开发的，Peter Naur 在Algol 60中采用了它，并进行了稍许改进,从而使其出名，因此Naur把BNF叫做Backus Normal Form，而其他人则把它叫成Backus-Naur Form。
      BNF被用来形式化定义语言的语法，以使其规则没有歧义。事实上，BNF非常精确，围绕这些语法有很多数学理论，使得人们竟然可以机械地为基于BNF语法的语言构造解析器。（有些语法不能实现，但通常可以手工地通过转换成其他形式来实现）。
      实现这个功能的程序叫做编译器，最有名的是YACC,当然，还有很多很多。


工作原理
基本原理
      BNF类似一种数学游戏：从一个符号开始（叫做起始标志，实例中常用S表示），然后给出替换前面符号的规则。BNF语法定义的语言只不过是一个字符串集合，你可以按照下述规则书写，这些规则叫做书写规范（生产式规则），形式如下：
      symbol := alternative1 | alternative2 ...
      每条规则申明:=左侧的符号必须被右侧的某一个可选项代替。替换项用“|”分割（有时用“::=”替换“:=”，但意思是一样的）。替换项通常有两个符号和终结符构成。之所以叫做终结符是因为没有针对他们的书写规范，他们是书写过程的终止（符号通常被叫做非终止符，也有人叫非终端）。
      BNF语法的另一个变化是把终止符（终端）放在引号中，把他们与符号区别开来。有些BNF语法用符号明确地标明允许使用空格的地方，而有的语法则把它留给读者推测。
      BNF中有一个特殊符号“@”，表示符号可以去掉。如果用@替换符号，只需要将符号去掉。这非常有用，因为如果不利用这个技巧，有时很难终止替换过程。
      因此，一个语法描述的语言就是用书写规则（生产式规则）写的字符串的集合。如果一个字符串无法用这些规则写出，那么，该字符串在这个语言中就被禁用。


一个实例
      下面是BNF语法的一个实例：
      S      := '-' FN |      FN
      FN := DL |      DL '.' DL
      DL := D | D DL
      D      := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
      这里的各种符号都是缩写的：S是开始符，FN产生一个分数，DL是一串数字列表，D是各个数字。
该语法描述的语言的有效句子都是数字，可能是分数，也可能是负数。要写一个数字，首先以S符号开头：
      S
      然后，用S的结果替换它。上例中，我们可以选择在数字前面不加“-”号而仅仅使用FN，并用FN替换S：
      FN
      接着用FN的结果替换FN。我们想写一个分数，所以选择产生两个中间带“.”的十进制数的列表，然后，我们接着在每一行用一个符号的结果替换一个符号，像下面的例子：
      DL . DL
      D . DL
      3 . DL
      3 . D DL
      3 . D D
      3 . 1 D
      3 . 1 4
      这里我们写了一个分数3.14。如何写-5，读者可自己练习。要彻底搞明白，还需要研究语法，知道您弄明白为什么按照上述规则不能写出3..14。


EBNF及其用途
      在DL中，我们已经用到了递归（如DL能产生新的DL）来表达许多数字D的情况。这有点不太灵活，使BNF难以阅读。扩展BNF（EBNF）通过引入下列操作符解决了这个问题：
          l ?：意思是操作符左边的符号（或括号中的一组符号）是可选项（可以出现0到多次）。
          l *：是指可以重复多次。
          l +：是指可以出现多次。


一个EBNF语法实例
      上面的例子用EBNF可以写成：
      S := '-'? D+ ('.' D+)?
      D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
      提示：EBNF在定义语言方面并不比BNF更强大，只是更方便。凡是用EBNF写的东西都可以转换成BNF的形式。


BNF和EBNF的使用
一般用法
      多数编程语言标准都使用一些EBNF变量来定义语言的语法。这有两个好处：一是在语言的语法上没有争议，而是易于编译器的编写，因为编译器的解析器可以用类似YACC这样的“编译器编译器”自动产生。
      EBNF也用于许多其他标准，如定义协议格式，数据格式和XML,SGML这样的标记语言。（HTML没有按照语法定义，而是用SGML DTD这样的高级语法定义的。）
      在BNF web club（http://cuiwww.unige.ch/db-research/Enseignement/analyseinfo/BNFweb.html ）上可以查到BNF的一个语法集。


如何使用形式语法
      现在，我们已经了解什么是BNF和EBNF以及它们的用途了，但还不知道为什么它们很有用以及如何利用它们。
      形式语法最明显的用法已经提到过了：一旦为语言制定了形式语法，就完全定义了这个语言。对于那些东西可以用于语言，那些东西不可以就不会有歧义了。这非常有用因为用普通语言描述的语法不仅冗长，而且会产生对不同的解释。
      另一个好处是：形式语法是数学产物，可以被计算机理解。实际上有许多程序可以用(E)BNF语法输入，并自动为给定语法的解析器提供处理代码。实际上，这是设计编译器的常见做法：用带有语法输入的所谓“编译器编译器”产生编程语言的解析器代码。
      当然，编译器除了做语法检查之外还做许多其他检查，他们也产生代码。这些都没有在(E)BNF中描述，因此编译器编译器通常有针对一种语法中不同代码的代码块连接（也叫做操作）的特殊语法。
最有名的编译器编译器是YACC(Yet Another Complier Complier)，产生C代码，其他的编译器还有针对C++，JAVA，Python等等其他语言的。


解析
最简单的方法
自上而下的解析(LL)
      按照现有语法解析代码的最简单方法是叫做LL解析（自上而下解析）。它是这样工作的：对每一段代码找出代码开始的非终端标记（叫做初始集）。
      然后，在解析时只需要从起始符开始比较不同代码段（符号）初始集和第一个输入的符号，判断代码段用的是哪个起始符作为开始的（用到了那些符号）。只有不存在一个符号的两个初始集含有相同的终止符时才可以这样。否则，就不能通过输入的第一个终止符选择哪个开始符（符号）了。
      LL语法通常按数字分类，比如LL(1), LL(0)等等。括号中的数字是在语法中的任何一点选择适当符号时需要同时考虑的最大终端数。因此 LL(0)根本不需要检查终端（终止符），总能够选择适当的终止符。这种情况只发生在所有符号只有一个替换符的情形，而如果只有一个替换符意味着语言只有一个字符串。也就是说LL(0)没有意义。
      最常有也是做有用的LL语法是联络LL(1)，通过检查输入的第一个终止符总能够选择适当的替换符。而LL(2)需要检查两个符号，以此类推。


一个LL分析实例
      为了说明，我们就实例语法做一个初始集分析。对符号D这非常容易：所有的替换符号跟它们的初始集（它们产生的）一样是一个数字，D符号把由10个数字组成的集合作为初始集。这意味着至少有一个LL(1)语法，因为这时我们需要一个终端来选择适当的替换符。
      对DL就会有些麻烦。两个替换符都以D开头，因此都有相同的初始机。这意味着不能够通过检查输入的第一个终止符来选择适当的替换符。但我们可以通过欺骗轻松地克服这个困难：如果输入的第二个终止符不是数字，我们就用第一个替换符，如果两个都是数字，就用第二个替换符。也就是说，这至少是LL(2)语法。
      这里其实把事情简化了。DL的替换符并没有告诉我们D @的替换符中的第一个终止符后哪个终止符是被允许的，因为我们需要知道在DL后面哪个终止符被允许。这个终止符集叫做符号的后续集（follow set of the symbol），这里是“.”，是输入的结尾。
      FN符号更糟糕，因为两个替换符都是以数字作为其初始集。检查第二个也终止符没有用，因为在数字列表（DL）中的最后一个数字的后面需要查看第一个终止符，而我们需要读取所有的数字后才能知道有多少数字。由于有多少数字并无限制，这就不是一个对于任意k的LL(k)语法。
或许有些奇怪，S符号很简单。第一个替换项“-”是它的初始集，第二个全部是数字。也就是说，解析时从S符号开始查看输入项来决定使用哪个替换项。如果第一个终端是“-”，就用第一个替换项“-”；否则就用第二个。只有FN和DL替换想会引起麻烦。


一个LL转换实例
      其实也没有必要失望。多数非LL(k)语法可以容易地转换成了LL(1)语法。这样我们需要转换两个符号：FN和DL。
      FN的问题是两个替换项都以DL开头，但第二个后接一个“.”和另外一个初始DL后面的DL。这很好解决：我们把FN变成只有以一个DL开头的替换项后跟一个FP(分数部分)，FP可以是空或是”.”后跟一个DL。变成下面这样：
      FN := DL FP
      FP := @ | '.' DL
      现在FN没有问题了，因为只有一个替换项，FP也没有问题，因为两个替换项有不同的初设集。分别是输入的结尾和“.”。
      DL是块硬骨头，因为主要问题出在递归，而且是复合的，需要从DL中得到一个D。解决方案是给DL一个单独的替换项，一个D后接一个DR（其余的数字）。这时DR就有两个替换项：D和DR或@。第一个替换项以所有的数字为初始集，第二个含有“.”和输入的结尾作为其初始集，从而解决问题。
这样就彻底转换成LL(1)语法了：
      S      := '-' FN | FN
      FN := DL FP
      FP := @ | '.' DL
      DL := D DR
      DR := D DR | @
      D      := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'


稍难的方法
自底而上的解析(LR)
      一个稍难的方法是移动替换法或叫自底而上解析。这个技术采集所有输入直道发现能够还原成符号的输入。这听起来好像很困难，所以需要给个例子加以说明。我们解析“3.14”看看如何从该语法中产生。我们从读取输入“3”开始：
      3
      然后，我们查看能否还原成产生它的符号。实际上我们能，它是从符号D产生的，我们用D替换3。这时我们注意到D可以从DL产生，所以用DL替换D。（这个语法有不确定性，我们可以一直还原到FN，但是是错误的。简单起见我们这里跳过错误的步骤，但清晰的语法将不会允许这样的错误发生），之后我们从输入中读取“.”并试图还原它，但是失败了。
      D
      DL
      DL .
      他不能还原成其它的东西，所以我们继续读取其它输入“1”，并把它还原成D，在读取下一个输入“4”, “4”也可以还原成D，再还原成DL，然后，“D DL”序列可以进一步还原成DL。
      DL .
      DL . 1
      DL . D
      DL . D 4
      DL . D D
      DL . D DL
      DL . DL
      看一下语法就会发现FN恰好能够还原“DL.DL”序列，于是将其还原。FN是从S产生的，所以FN可以还原成S，到此为止就完成了解析。
      DL . DL
      FN
      S
      也许你注意到我们可以先在做还原，也可以等到有多个符号在做不同的还原。这种移位还原解析算法有许多复杂变化，按照复杂程度和功能分为LR(0)、 SLR、LALR和LR(1)。LR(1)需要太大的解析表，所以LALR是最常用的算法，而SR(0)和SLR对多数编成语言都不够强大。
LALR 和LR(1)实在太复杂了，这里没法讨论，但你已经了解了其基本思想。


LL还是LR？
      这个问题已经被人回答了，这里引用他的新消息：
      希望不要引发争议，首先，当Frank看到这个时不要打我（我老板就是Frank DeRmer，LALR解析的创始人…）。
（借用一下Fischer&LeBlanc's "Crafting a Compiler"的摘要）
      简单性Simplicity        - - LL
      通用性Generality        - - LALR
      操作Actions           - - LL
      错误恢复Error repair      - - LL
      表大小Table sizes       - - LL
      解析速度Parsing speed - - comparable (me: and tool-dependent)
简单性- - LL 占优
==========
      LL解析器更简单，如果要调试一个解析器，考虑递归下降解析器（编写LL解析器的常用方法）要比LALR解析器的表简单多了。
通用性 - - LALR 占优
==========
      在规范定义的简易性，LALR轻松取胜。LL和LALR的最大不同是LL语法必须用左因子法则和消除左递归。
      提取左因子是必须的，因为LL解析器需要基于固定的输入数选择替换。
      左回归是有问题的，因为规则前导标记总是统一规则的前导标记。这将导致无穷递归。
      参考以下连接了解LALR转换成LL语法的方法：
  http://www.jguru.com/thetick/articles/lalrtoll.html
      许多语言已经有了LALR语法，但还需要翻译。如果语言没有这样的语法，写一个LL语法也不是什么难事。
操作性 - - LL 占优
=======
      在LL解析器中可以把操作放在任何地方而不会引起冲突。
错误修复 - - LL 占优
============
      LL解析器具有丰富的环境信息（上下文信息），对修复错误很有帮助而非报告所无。
表大小 - - LL
===========
      假设你编写一个表驱动LL解析器，它的表只有其他的一半大小。（平心而论，有很多方法优化LALR表，使其变小）
解析速度 – 比较(我的观点：视工具而定)
--Scott Stanchfield in article <[e-mail] > on comp.lang.java.softwaretools Mon, 07 Jul 1997.


更多信息
      John Aycock用Python开发了一个非常好而且简单易用的解析框架叫做SPARK ,用可读性非常强的论文描述。 
      编译器和解析器方面权威工作是'The Dragon Book'，也叫Compilers : Principles, Techniques, and Tools，作者Aho, Sethi and Ullman。请注意这是一本高级的数学书。
      在线的免费资料较好的是这本：http://www.cs.vu.nl/~dick/PTAPG.html 。
      Frank Boumphrey的another EBNF tutorial，（http://www.hypermedic.com/style/xml/ebnf.htm ）
Henry Baker的an article about parsing in Common Lisp（http://home.pipeline.com/~hbaker1/Prag-Parse.html       ）呈现的是一个简单、高效而且十分方便的解析框架。方法类似于编译器编译器，但它依赖于一个十分强大的Common Lisp宏系统。
      定义BNF语法的句法规则在RFC 2234（http://www.ietf.org/rfc/rfc2234.txt ）中可以找到，the ISO 14977 standard中也有。


附录
致谢
Thanks to:
• Jelks Cabaniss, for encouraging me to turn the news article into a web article, and for providing very useful criticism of the article once it appeared in web form.
• C. M. Sperberg-McQueen for extra historical information about the name of BNF.
• Scott Stanchfield for writing the great comparison of LALR and LL. I have asked for permission to quote this, but have received no reply, unfortunately.
• James Huddleston for correcting me on John Backus' name.