BNF范式和EBNF范式详解

定义编程语言的语言

编程语言, 协议规范, 查询语言, 文件格式, 模式语言, 内存布局, 配置文件, 标记语言, 格式化语言和元语言等等塑造了我们计算的方式. 那么, 是什么塑造了这些语言呢?

BNF范式

BNF范式(BNF: Backus-Naur Form 的缩写)即巴科斯范式, 是由 John Backus 和 Peter Naur 首先引入的用来描述计算机语言语法的符号集.
现在, 几乎每一位新编程语言书籍的作者都使用巴科斯范式来定义编程语言的语法规则.

BNF范式的内容

BNF范式中的每个标准语法都具有以下结构:

name ::= expansion

其中 ::== 符号表示为 “可扩展为” 或 “可替换为”, “可定义为”.
在某些文本中, name 也称为非终止符, 一般为语言中某些抽象的概念.

BNF范式中的每个 name 都用尖括号<>括起来, 无论它出现在语法中的何处.
expansion 是包含终止符和非终止符的表达式, 通过排序和选择连接在一起.
终止符是像 + 或 function 这样的字符, 或者是一类字符 (如 integer), 一般为可以直接出现在语言中的符号.

竖线| 表示选择, 表示在其左右两边任选一项, 相当于 “or” .
双引号”” 表示为其原本含义.

BNF范式示例

在BNF中, 经典的表达式语法是:

<expr> ::= <term> + <expr>
        |  <term>

<term> ::= <factor> * <term>
        |  <factor>

<factor> ::= ( <expr> )
          |  <const>

<const> ::= integer

C语言的声明语句可以用BNF这样描述:

1	<声明语句> ::= <类型><标识符>; \| <类型><标识符>[<数字>];

这一句中 <声明语句> 这个非终结符(语言中某些抽象的概念)被定义成了两种形式(上面用 | 隔开的两部分), 同时在这里引入了三个终结符(可以直接出现在语言中的符号): 分号; , 左方括号[ , 右方括号 ].

EBNF范式

EBNF范式(Extended Backus-Naur form), 是对BNF范式的扩展.

EBNF范式的内容

虽然EBNF是对BNF的扩展, 但并非所有扩展都是严格意义上的超集, 因为有些更改了规则定义关系: 将 ::= 更改为 = , 而另一些则删除了非终止符的尖括号(所以可以不必使用尖括号).

比EBNF范式之间的微小语法差异更重要的是扩展中允许的附加操作.

使用了在标准中提议为正规表示的下列字符:

用途	符号表示
定义	= \| ::=
串接	,
终止	;
分隔	\|
可选	[ … ]
重复	{ … }
分组	( … )
双引号	“ … “
单引号	‘ … ‘
注释	(* … *)
特殊序列	? … ?
除外	-

EBNF范式示例

以BNF风格定义为:

1	<signed number> = <sign> , <number> \| <number> ;

可以在EBNF中表示为:

1	<signed number> = [ <sign> , ] <number> ;

只允许赋值的简单编程语言可以用 EBNF 定义为:

program = 'PROGRAM' , white space , identifier , white space ,
           'BEGIN' , white space ,
           { assignment , ";" , white space } ,
           'END.' ;
identifier = alphabetic character , [ { alphabetic character | digit } ] ;
number = [ "-" ] , digit , [ { digit } ] ;
string = '"' , { all characters − '"' } , '"' ;
assignment = identifier , ":=" , ( number | identifier | string ) ;
alphabetic character = "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" ;
white space = ? white space characters ? ;
all characters = ? all visible characters ? ;