BNF 和EBNF的含义与用法
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？ 更多信息 附录 致谢
简介
关于本文
这是一篇针对
现在文章越来越长，但你不必担心，文章将会逐渐深入。如果你不想深入了解，你可以只看感兴趣的部分，从中寻找你的问题答案即可。
什么是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 +：是指可以出现多次。