什么是BNF符号?
BNF是“Backus Naur Form”的缩写。John Backus和Peter Naur首次引入一种形式化符号来描述给定语言的语法(最早用于描述ALGOL 60 编程语言,参见[Naur60])。确切地说,早在UNESCO(联合国教科文组织)关于ALGOL 58的会议上提出的一篇报告中,Backus就引入了大部分BNF符号。虽然没有什么人读过这篇报告,但是在Peter Naur读这篇报告时,他发现Backus对ALGOL 58的解释方式和他的解释方式有一些不同之处,这使他感到很惊奇。首次设计ALGOL的所有参与者都开始发现了他的解释方式的一些弱点,所以他决定对于以后版本的ALGOL应该以一种类似的形式进行描述,以让所有参与者明白他们在对什么达成一致意见。他做了少量修改,使其几乎可以通用,在设计ALGOL 60的会议上他为ALGOL 60草拟了自己的BNF。看你如何看待是谁发明了BNF了,或者认为是Backus在1959年发明的,或者认为是Naur在1960年中发明。(关于那个时期编程语言历史的更多细节,参见1978年8月,《Communications of the ACM(美国计算机学会通讯)》,第21卷,第8期中介绍Backus获图灵奖的文章。这个注释是由来自Los Alamos Natl.实验室的William B. Clodius建议的)。
自从那以后,几乎每一个新编程语言书的作者都使用BNF来描述语言的语法规则。参见[Jensen 74]和[Wirth 82]中的例子。
以下摘自[Marcotty 86]:
BNF的元符号:
::= 表示“定义为 ”
| 表示“或者”
< > 尖括号用于括起类别名字。
尖括号将语法规则名字(也称为非终结符)同终结符区分开来,终结符想表达什么意思就怎么书写。定义非终结符的BNF规则的格式如下:
nonterminal ::= sequence_of_alternatives consisting of strings of
terminals or nonterminals separated by the meta-symbol |
(译注:包括由元符号“|”分隔的终结符字符串或者非终结符的一组可选项)
例如,迷你语言(mini-language)的BNF描述如下:
这表明迷你语言(mini-language)程序包含关键字“program”,后面跟声明序列,然后是关键字“begin”和语句序列,最后是关键字“end”和分号。
(摘录结束)
事实上,许多作者为了方便使用引入了一些小的BNF扩展:
l 可选项被括在元符号“[”和“]”中,例如:
::= | if then |
| | |
| [ else |
| | ] |
| end if ; |
l 重复项(零个或者多个)被括在元符号“{ ”和“}”中,例如:
::= { | }
(译注:表示标识符由字母开头,后面是一个或多个字母或数字)
这个规则跟如下递归规则相同:
l 仅一个字符的终结符用引号(")引起来,以和元符号区别开来,例如:
::= { ";" }
在最近一些教材中,通过对终结符使用粗体来区分终结符和非终结符,不允许在非终结符两边使用“<”和“>”。这大大提高了可读性。
前面的例子就变成了这样:
if_statement ::= | if boolean_expression then |
| | statement_sequence |
| [ else |
| | statement_sequence ] |
| end if ";" |
现在作为最后一个例子(可能读起来不是很容易!),给出用BNF表达的BNF定义:
syntax | ::= | { rule } |
rule | ::= | identifier "::=" expression |
expression | ::= | term { "|" term } |
term | ::= | factor { factor } |
factor | ::= | identifier | |
| quoted_symbol |
| "(" expression ")" | |
| "[" expression "]" | |
| "{" expression "}" |
identifier | ::= | letter { letter | digit } |
quoted_symbol ::= """ { any_character } """ |
BNF不仅对在书中描述语法规则是重要的,而且许多语法工具对BNF(及其变体)使用得也非常普遍。参见任何关于LEX和YACC书中的例子,LEX和YACC是标准UNIX解析器(parser)生成工具。如果你有机会接触Unix机器,你可能会在文档中的某章发现这些工具的介绍。
参考资料:
[Naur 60]
NAUR, Peter (ed.), "Revised Report on the Algorithmic Language ALGOL 60.", Communications of the ACM, Vol. 3 No.5, pp. 299-314, May 1960.
[Jensen 74]
JENSEN, Kathleen, WIRTH, Niklaus, "PASCAL user manual and report", Lecture notes in computer science ; vol. 18., Berlin [etc.] : Springer, 1974., 1974.
[Johnson 75]
S.C. Johnson, "Yacc: Yet Another Compiler Compiler", Computer Science Technical Report #32, Bell Laboratories, Murray Hill, NJ, 1975.
[Wirth 82]
WIRTH, Niklaus., Programming in Modula-2, Berlin, Heidelberg: Springer, 1982.
[Marcotty 86]
M. Marcotty & H. Ledgard, The World of Programming Languages, Springer-Verlag, Berlin 1986., pages 41 and following.
, CUI - University of Geneva(CUI -日内瓦大学)
原文链接