BNF与ABNF

| 分类 深入学习之编译原理  | 标签 编译原理  编译  语法  BNF  巴科斯范式  数学  ABNF  扩展巴科斯范式  java  json 

巴科斯范式(BNF)

BNF被用来形式化定义语言的语法,以使其规则没有歧义。(如C、Java都可以通过BNF进行描述)。事实上,BNF非常精确,围绕这些语法有很多数学理论,使得人们竟然可以机械地为基于BNF语法的语言构造解析器。(有些语法不能实现,但通常可以手工地通过转换成其他形式来实现)

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

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

在双引号外的字代表着语法部分:

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

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

FOR_STATEMENT ::= 
      "for" "(" ( variable_declaration | 
   ( expression ";" ) | ";")
       [ expression ] ";"
       [ expression ] ";"
       ")" statement

下面是Java的一个for语句例子

int i;
for (i = 0; i < 100; i++){
    for (int j = 0; j < i; j++)
        System.out.println(j);
}

扩展巴科斯范式(ABNF)

RFC2234定义了扩展的巴科斯范式(ABNF)。近年来在Internet的定义中ABNF被广泛使用。ABNF做了更多的改进

ABNF基于了BNF,但由它自己的语法和推导规则构成。这种元语言的发起原则是描述通信协议(双向规范)的语言的形式系统。它建档于RFC4234中通常充当IETF通信协议的定义语言

ABNF规定一组推导规则,写为:

规则 = 定义 ; 注释 CR LF

这里的规则是大小写敏感的非终止符,定义由定义这个规则的符号序列、一个文档注释组成,并结束于回车换行

规则名称是大小写不敏感的:<rulename><Rulename><RULENAME><rUlENamE>都是提及同一规则。规则名字由开始于一个字母的字母、数字和连字符组成。不要求用尖括号(“<”、”>”,如BNF那样)包围规则名字。但是他们可以用来界定规则名字,比如在冗文中识别出规则名字的时候。ABNF使用7位ASCII编码,在8位域中把高位置零

终结符由一个或多个数值字符指定。数值字符可以指定为跟随着基数(b=二进制,d=十进制,x=十六进制)的一个百分号“%”,随后是这个数值,或数值的串联(用“.”来指示)。例如回车可以指定为十进制的%d13或者十六进制%x0D、回车换行可以指定为%d13.10

文字正文通过使用包围在引号"中字符串来指定。这些字符串是大小写不敏感的,使用的字符集是US-ASCII。所以字符串”abc”将匹配”abc”、”Abc”、”aBc”、”abC”、”ABc”、”AbC”、”aBC”和”ABC”。对于大小写敏感匹配,必须定义明确的字符:要匹配”aBc”定义将是%d97 %d66 %d99

空白

空白被用来分隔定义的各个元素:要使空格被识别为分隔符则必须明确的包含它

串联

规则1 规则2

规则可以通过列出一序列的规则名字来定义。要匹配字符串"aba"可使用下列规则:

fu = %x61  ; a
bar = %x62 ; b
mumble = fu bar fu

选择

规则1 / 规则2

规则可通过反斜杠 / 分隔的多选一规则来定义。要接受规则<fu>或规则<bar>可构造如下规则:

fubar = fu / bar

递增规则

规则1 =/ 规则2

可通过使用在规则名字和定义之间的 =/ 来向一个规则增加补充选择。比如规则

ruleset = alt1 / alt2 / alt3 / alt4 / alt5

等价于

ruleset = alt1 / alt2
ruleset =/ alt3
ruleset =/ alt4 / alt5

值范围

%c##-##

数值范围可以通过连字符 - 来指定。比如规则

OCTAL = "0" / "1" / "2" / "3" / "4" / "5" / "6" / "7"

等价于

OCTAL = %x30-37

序列分组

(规则1 规则2)

元素可以放置在圆括号中来组合定义中的规则。要匹配"elem fubar snafu""elem tarfu snafu"可以构造下列规则

group = elem (fubar / tarfu) snafu

要匹配"elem fubar""tarfu snafu"可以构造下列规则

group = elem fubar / tarfu snafu
group = (elem fubar) / (tarfu snafu)

可变重复

n*n规则

要指示一个元素的重复可以使用形式 <a>*<b>元素。可选的 <a>给出要包括的元素的最小数目,缺省为0,。可选的 <b>给出包括的元素的最大数目,缺省为无穷

对零或多个元素使用 *元素,对1或多个元素使用 1*元素,对二或三个元素使用 2*3元素

特定重复

n 规则

要指示明确数目的元素可使用形式 <a>元素,它等价于 <a>*<a>元素

使用 2DIGIT得到两个数字,使用 3DIGIT得到三个数字

可选序列

[规则]

要指示可选元素下列构造是等价的:

[fubar snafu]
*1(fubar snafu)
0*1(fubar snafu)

注释

; 注释

分号 ; 开始一个注释并持续到此行的结束

操作符优先级

上述操作符由从最紧绑定到最松绑定的给出优先级:

  1. 字符串,名字形成(formation)
  2. 注释
  3. 值范围
  4. 重复
  5. 分组、可选
  6. 串联
  7. 选择

与串联一起使用选择操作符可能造成混淆,建议使用分组来做明确串联分组

核心规则

核心规则定义于ABNF标准中

规则 形式定义 意义
ALPHA %x41-5A / %x61-7A 大写和小写ASCII字母(A-Z a-z)
DIGIT %x30-39 数字(0-9)
HEXDIG DIGIT / “A” / “B” / “C” / “D” / “E” / “F” 十六进制数字(0-9 A-F a-f)
DQUOTE %x22 双引号
SP %x20 空格
HTAB %x09 水平tab
WSP SP / HTAB 空格和水平tab
LWSP *(WSP / CRLF WSP) 线性空白(晚于换行)
VCHAR %x21-7E 可见(打印)字符
CHAR %x01-7F 任何7位US-ASCII字符,不包括NUL
OCTEL 0x00-FF 8位数据
CTL %x00-1F / %x7F 控制字符
CR %x0D 回车
LF %x0A 换行
CRLF CR LF 互联网标准换行
BIT “0” / “1”  

JSON的语法描述(ABNF)

null/false/true

JSON-text = ws value ws
ws = *(%x20 / %x09 / %x0A / %x0D)
value = null / false / true
null = "null"
false = "false"
true = "true"

数值

number = ["-"] int [frac] [exp]
int = "0" / digit1-9 *digit
frac = "." 1*digit
exp = ("e" / "E") ["-" / "+"] 1*digit

字符串

string = quotation-mark *char quotation-mark
char = unescaped /
   escape (
      %x22 /                ; "  quotation mark   U+0022
      %x5C /                ; \  reverse solidus  U+005C
      %x2F /                ; /  solidus          U+002F
      %x62 /                ; b  backspace        U+0008
      %x66 /                ; f  form feed        U+000C
      %x6E /                ; n  line feed        U+000A
      %x72 /                ; r  carriage return  U+000D
      %x74 /                ; t  tab              U+0009
      %x75 4HEXDIG )        ; uXXXX               U+XXXX
escape = %x5C               ; \
quotation-mark = %x22       ; "
unescaped = %x20-21 / %x23-5B / %x5D-10FFFF

数组

array = %x5B ws [ value *( ws %x2C ws value) ] ws %x5D

对象

member = string ws %3A ws value
object = %x7B ws [ member *( ws %x2C ws member ) ] ws %x7D

参考资料




如果本篇文章对您有所帮助,您可以通过微信(左)或支付宝(右)对作者进行打赏!


上一篇     下一篇