BNF&EBNF

Posted on

BNF

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

在 BNF 中，双引号中的字(“word”)代表着这些字符本身。而 double_quote 用来代表双引号。

在双引号外的字（有可能有下划线）代表着语法部分。

< > : 内包含的为必选项。
　　[ ] : 内包含的为可选项。
　　{ } : 内包含的为可重复 0 至无数次的项。
　　| : 表示在其左右两边任选一项，相当于”OR”的意思。
　　::= : 是“被定义为”的意思
　　“…” : 术语符号
　　[…] : 选项，最多出现一次
　　{…} : 重复项，任意次数，包括 0 次
　　(…) : 分组
　　| : 并列选项，只能选一个
　　斜体字: 参数，在其它地方有解释

下面是是用 BNF 来定义的 Java 语言中的 For 语句的实例：

1
2
3
4
5
6
FOR_STATEMENT ::=
      "for" "(" ( variable_declaration |
  ( expression ";" ) | ";" )
      [ expression ] ";"
      [ expression ] ";"
      ")" statement

EBNF

扩展巴科斯-瑙尔范式(Extended Backus–Naur Form,EBNF)是一种用于描述计算机编程语言等正式语言的与上下文无关语法的元语法(metasyntax)符号表示法。简而言之，它是一种描述语言的语言。它是基本巴科斯范式(BNF)元语法符号表示法的一种扩展。

最初由尼克劳斯·维尔特开发，最常用的 EBNF 变体由标准是 ISO-14977 所定义。

EBNF 的基本语法形式如下，这个形式也被叫做 production：

1
左式(LeftHandSide) = 右式(RightHandSide).

左式也被叫做 非终端符号(non-terminal symbol)，而右式则描述了其的组成。

终端符号与非终端符号

  • 终端符号(Terminal symbols)：形成所描述的语言的最基本符号。所描述语言的标点符号(不是 EBNF 自己的)会被左右加引号(它们也是终端符号)，而其他终端符号会用粗体(这边因不方便加粗，就不加粗了)打印。
  • 非终端符号：是用于描述语法的变量，它必须被定义在一个 production 中。或说，它们必须出现在某个地方的 production 的左式中。

符号

约定

1 .使用了如下约定:

  • EBNF 的每个元标识符(meta-identifier)都被写为用连字符(“-“,hyphens)连接起来的一个或多个单词；
  • 以 “-symbol” 结束的元标识符是 EBNF 的终端符号。

2 .用普通字符表示的 EBNF 操作符按照优先级(顶部为最高优先级)排序为:

1
2
3
4
5
6
7
*repetition-symbol(重复符)
-except-symbol(除去符)
, concatenate-symbol(连接符)
| definition-separator-symbol
= defining-symbol(定义符)
; terminator-symbol(结束符)
. terminator-symbol(结束符)

3 .以下的括号对(bracket pairs)能够改变优先级，括号对间也有优先级(顶部为最高优先级):

1
2
3
4
5
6
7
'  first-quote-symbol            first-quote-symbol  '    (* 引用 *)
"  second-quote-symbol          second-quote-symbol  "    (* 引用 *)
(* start-comment-symbol          end-comment-symbol *)    (* 注释 *)
(  start-group-symbol              end-group-symbol  )    (* 分组 *)
[  start-option-symbol            end-option-symbol  ]    (* 可选 *)
{  start-repeat-symbol            end-repeat-symbol  }    (* 重复 *)
?  special-sequence-symbol   special-sequence-symbol ?    (* 特殊序列 *)

下例示范了怎么表达重复：

1
2
3
4
5
6
7
aa = "A";
bb = 3 * aa, "B";
cc = 3 * [aa], "C";
dd = {aa}, "D";
ee = aa, {aa}, "E";
ff = 3 * aa, 3 * [aa], "F";
gg = {3 * aa}, "D";

这些规则定义的终端字符串如下:

1
2
3
4
5
6
7
aa: A
bb: AAAB
cc: C AC AAC AAAC
dd: D AD AAD AAAD AAAAD etc.
ee: AE AAE AAAE AAAAE AAAAAE etc.
ff: AAAF AAAAF AAAAAF AAAAAAF
gg: D AAAD AAAAAAD etc.

扩展

除了标准的定义，在 FREESCALE 文档中还使用了以下约定：

  • 计数重复：任何由”{“和”}”括起来并后跟一个上标 x 的东西必须准确地重复出现 x 次。x 也可能是一个非终端字符。比如下例中，Stars 相当于四个星号：
    Stars = {“*”}4.
  • 字节数：见到任何紧跟着由一对中括号“[”和“]”括起来的数字 n 的标识符，都应该认为它是一个高位字节在前的二进制数，并且字节数为 n，如：
    Struct=RefNo FilePos[4].
  • 在一些例子中，我们会使用”<”和”>”括起来一些文本。这些文本是 元文本(meta–literal)，它们的位置应该被它们所描述的东西替代掉，如，对于 < any char >，它的位置可以插入任意字符。

示例

以下提供一些示例以直观的理解 EBNF。

1
2
3
4
digit excluding zero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
digit                = "0" | digit excluding zero ;
natural number = digit excluding zero, { digit } ;
integer = "0" | [ "-" ], natural number ;

digit excluding zero 可以是 1 到 9 任意一个字符，digit 则扩展为 0 到 9 任意一个字符。
natural number 可以是 1、2、…、10、…、12345、…，因为{}代表重复任意次，包括 0 次。
integer 则可以是 0 或者可能带个负号的自然数。

这是用 EBNF 描述的 EBNF 自身语法：

1
2
3
4
5
6
7
8
9
10
Production     = NonTerminal "=" Expression ".".
Expression     = Term {"|" Term}.
Term           = Factor {Factor}.
Factor         = NonTerminal
                 | Terminal
                 | "(" Expression ")"
                 | "[" Expression "]"
                 | "{" Expression "}".
Terminal       = Identifier | “"“ <any char> “"“.
NonTerminal    = Identifier.

非终端符号可以是任意你喜欢的名字，而终端符号则要不然是出现在被描述的语言中的标识符，要不然就是任何被引号括起来的字符序列。
然后 Factor(参数)可以是终端字符、非终端字符、三种括号中任意一种括起来的表达式。
Term(术语)由起码一个 Factor 组合而成……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(* a simple program syntax in EBNF − Wikipedia *)
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 ? ;

对应的语法正确的程序如下：

1
2
3
4
5
6
7
8
9
10
PROGRAM DEMO1
BEGIN
  A:=3;
  B:=45;
  H:=-100023;
  C:=A;
  D123:=B34A;
  BABOON:=GIRAFFE;
  TEXT:="Hello world!";
END.