定义编程语言的语言

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

BNF范式

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

BNF范式的内容

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

name ::= expansion

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

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

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

BNF范式示例

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

1
2
3
4
5
6
7
8
9
10
<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 定义为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 ? ;

总结

EBNF 排除了 BNF 的一些缺陷:

  • BNF 为自身使用了符号 (<, >, |, ::=). 当它们出现在要定义的语言中的时候, BNF 不能不加以修改或解释的使用.

  • BNF-语法在一行中只表示一个规则.
    EBNF 解决了这些问题:

  • 终结符被严格的包围在引号 (“…” 或 ‘…’) 中. 给非终结符的尖括号 (“<…>”)可以省略.

  • 通常使用终止字符分号结束一个规则.

进一步还提供了定义重复次数, 排除法选择(比如除了引号的所有字符)和注释等的增强机制.

不管所有这些增强, EBNF 在能定义的语言的意义上不比 BNF 更强大. 在原理上用 EBNF 定义的任何文法都可以用 BNF 表达. 但是经常导致可观的更多规则的表示.

在某些场合任何扩展的 BNF 都被称为 EBNF.

参考文献

1. 扩展巴科斯范式 - 维基百科,自由的百科全书
2. 什么是BNF范式,什么又是EBNF范式? - 张旋 - 博客园