Bnf

BNF

Backus–Naur form(BNF or Backus normal form)是一种用于描述编程语言或其他形式语言语法的符号。BNF 可以描述为上下文无关语法的元语法表示法。随着时间的推移，原始巴科斯-诺尔表示法的许多扩展和变体已经被创建。有些是精确定义的, 包括扩展巴科斯-诺尔形式(EBNF)和增强巴科斯-诺尔形式(ABNF)。

语法结构

BNF由三个部分组成: 一组非终结符号; 一组终结符号; 用符号序列替换非终结符号的规则。这些所谓的“推导规则”被写为

 <symbol> ::= __expression__

• <symbol>是一个非终结符变量, 始终包含在<>对之间。
• ::=表示左侧的符号必须替换为右侧的表达式。
• __expression__由一个或多个终结符或非终结符序列组成, 其中每个序列由竖线”|“分隔。表示一个选择, 整体可以替代左侧的符号。
• |表示选择。
• BNF允许递归定义, 即在规则中一个非终结符可以通过某种方式再次引用自己。

示例

简单示例

email示例: example@gmail.com, 可以用以下BNF规则匹配。

<digit>   ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<letter>  ::= "e" | "x" | "a" | "m" | "p" | "l" | "e" 

<username>   ::= <letter> | <digit>
<domain>     ::= <subdomain> "." <tld>
<subdomain>  ::= "gmail" | "foxmail"
<tld>        ::= "com" | "org"

<email>      ::= <username> "@" <domain>

自举

BNF 的语法本身可以用 BNF 表示

 <syntax>         ::= <rule> | <rule> <syntax>
 <rule>           ::= <opt-whitespace> "<" <rule-name> ">" <opt-whitespace> "::=" <opt-whitespace> <expression> <line-end>
 <opt-whitespace> ::= " " <opt-whitespace> | ""
 <expression>     ::= <list> | <list> <opt-whitespace> "|" <opt-whitespace> <expression>
 <line-end>       ::= <opt-whitespace> <EOL> | <line-end> <line-end>
 <list>           ::= <term> | <term> <opt-whitespace> <list>
 <term>           ::= <literal> | "<" <rule-name> ">"
 <literal>        ::= '"' <text1> '"' | "'" <text2> "'"
 <text1>          ::= "" | <character1> <text1>
 <text2>          ::= "" | <character2> <text2>
 <character>      ::= <letter> | <digit> | <symbol>
 <letter>         ::= "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" | "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"
 <symbol>         ::= "|" | " " | "!" | "#" | "$" | "%" | "&" | "(" | ")" | "*" | "+" | "," | "-" | "." | "/" | ":" | ";" | ">" | "=" | "<" | "?" | "@" | "[" | "\" | "]" | "^" | "_" | "`" | "{" | "}" | "~"
 <character1>     ::= <character> | "'"
 <character2>     ::= <character> | '"'
 <rule-name>      ::= <letter> | <rule-name> <rule-char>
 <rule-char>      ::= <letter> | <digit> | "-"

EBNF

基于BNF的扩展。

语法结构

• =用于定义语法规则的结构, 等价于BNF中的::=。
• ，是concatenation, 表示多个元素按顺序连接出现。例如，a , b 表示 a 后跟 b。
• ;或者.表示规则定义的结束。
• |、/、!、c表示在多个选项中选择一个。例子: a | b 表示 a 或 b。
• none or more的表达式可以通过大括号{}表示。
• none or once可以通过方括号[]表示。也就是说，方括号内设置的所有内容可能只出现一次, 或者根本不出现。
• ()用于将表达式分组，以明确优先级。
• "..."或者'...'用于表示终结符的具体字符串值。例如，"a" 表示具体的字符 a。
• (**)用于添加注释，不影响语法规则。例如，(* This is a comment *)。
• ?...?表示特殊的语法序列，通常与具体实现相关。
• -表示在规则中排除某些情况。例子：a - b 表示 a 但排除 b。

示例

简单示例

下列是一个计算器语法的规则, 支持加法、乘法、括号和数字。

(* 定义表达式 *)
expression = term , { ("+" | "-") , term } ;

(* 定义项 *)
term = factor , { ("*" | "/") , factor } ;

(* 定义因子 *)
factor = number | "(" , expression , ")" ;

(* 定义数字 *)
number = digit , { digit } ;

(* 定义数字字符 *)
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;

• expression: 一个表达式由一个term(项)开始, 后面可以跟零个或多个term, 中间用+或-连接。例如, 2+3*4是一个有效的表达式。
• term: 一个项由一个factor(因子)开始, 后面可以跟零个或多个 factor, 中间用*或/连接。例如, 3*4是一个有效的项。
• factor: 一个因子可以是一个 number(数字), 或者是一个括号内的 expression。例如，(2 + 3) 或 5 都是有效的因子。
• number: 一个数字由一个或多个digit(数字字符)组成。例如, 42 是一个有效的数字。
• digit: digit 定义了单个数字字符, 可以是0到9之间的任意字符。

对于输入 "2 + 3 * (4 - 5)"：

1. expression 是整个 "2 + 3 * (4 - 5)"。
2. term 是 "2" 和 "3 * (4 - 5)"。
3. factor 是 "2" 和 "(4 - 5)"。
4. number 是 "2", "3"，以及 "4" 和 "5"。

自举

letter = "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" | "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" ;

symbol = "[" | "]" | "{" | "}" | "(" | ")" | "<" | ">"
       | "'" | '"' | "=" | "|" | "." | "," | ";" | "-" 
       | "+" | "*" | "?" | "\n" | "\t" | "\r" | "\f" | "\b" ;

character = letter | digit | symbol | "_" | " " ;
identifier = letter , { letter | digit | "_" } ;

S = { " " | "\n" | "\t" | "\r" | "\f" | "\b" } ;

terminal = "'" , character - "'" , { character - "'" } , "'"
         | '"' , character - '"' , { character - '"' } , '"' ;

terminator = ";" | "." ;

term = "(" , S , rhs , S , ")"
     | "[" , S , rhs , S , "]"
     | "{" , S , rhs , S , "}"
     | terminal
     | identifier ;

factor = term , S , "?"
       | term , S , "*"
       | term , S , "+"
       | term , S , "-" , S , term
       | term , S ;

concatenation = ( S , factor , S , "," ? ) + ;
alternation = ( S , concatenation , S , "|" ? ) + ;

rhs = alternation ;
lhs = identifier ;

rule = lhs , S , "=" , S , rhs , S , terminator ;

grammar = ( S , rule , S ) * ;

相对于BNF的优势

• shecannotsee觉得是更加完善且准确的语法规则。

ABNF

RFC5234: https://datatracker.ietf.org/doc/html/rfc5234

RFC7405: https://datatracker.ietf.org/doc/html/rfc7405

基于BNF的增强。

语法结构

• rule是这样, 这里的 <name> 是规则的名称, <elements> 是该规则的定义内容, <crlf> 是行尾指示符, 即回车换行符。

  name = elements crlf
  

• 终结符(Terminals): 在ABNF中, 终结符通常是字符(可以是一个或者多个), 这些字符在某些上下文中可能通过特定的编码(如ASCII)进行映射。终结符可以用不同的数值表示方式: b表示二进制(binary); d表示十进制(decimal); x表示十六进制(hexadecimal)。

  CRLF = %d13.10
  

• rule是不区分大小写的非终结符, 定义由定义规则的符号序列、文档注释以及以回车符和换行符结尾组成。

• rule名称周围不需要尖括号(<和>)。然而, 在rule中仍然中可是使用其来辨别rule边界。

• 可以使用;来表示comment(注释)。

• 空格连接元素。例如为了匹配”aba”, 可以通过以下方式fu = %x61;a和bar = %x62;b, 然后通过mumble = fu bar fu。

• /表示匹配某一个规则, =/可以连续进行匹配。例如ruleset = alt1 / alt2、ruleset =/ alt3、ruleset =/ alt4 / alt5等价于ruleset = alt1 / alt2 / alt3 / alt4 / alt5, 也就是说结果是ruleset可以匹配alt1、alt2、alt3、alt4或alt5中的任何一个。

• 可以通过使用连字符 ( - ) 指定数值范围。例如OCTAL = %x30-37等价于OCTAL = "0" / "1" / "2" / "3" / "4" / "5" / "6" / "7"。

• 可以通过()修改匹配的优先级。例如为了匹配”abd”或”acd”，可以构造以下规则: group = a (b / c) d。

• 可变重复 : n*nRule 指示元素的重复。例如使用*element表示零个或多个元素, *1element表示零个或一个元素, 1*element表示一个或多个元素, 2*3element表示两个或三个元素。

• 具体重复: nRule指示元素的明确数量。例如使用2DIGIT获取两个数字，使用3DIGIT获取三个数字。

• 可选顺序: 通过[]来处理rule的可选性(也就是rule可以出现, 也可以不出现)。例如下列三者是等价的[fubar snafu]、*1(fubar snafu)、0*1(fubar snafu)。

• 运算符优先级从高到低:

  1. Strings, names formation 字符串、名称形成
  2. Comment 评论
  3. Value range 取值范围
  4. Repetition 重复
  5. Grouping, optional 分组，可选
  6. Concatenation 级联
  7. Alternative 选择

示例

简单示例

email示例: example@gmail.com, 可以用以下ABNF规则进行匹配。

; 电子邮件地址的定义

email = local-part "@" domain

local-part = 1*(alpha / digit / "." / "-" / "_")
domain = subdomain *( "." subdomain )
subdomain = 1*(alpha / digit) ; 子域名由一个或多个字母或数字组成

alpha = %x41-5A / %x61-7A  ; 大写和小写字母（A-Z，a-z）
digit = %x30-39             ; 十进制数字（0-9）