查看“︁Backus–Naur 范式”︁的源代码

[[分类:形式语言]]
[[分类:形式语言实例]]
[[分类:语法分析]]
{{InfoBox
|name=巴科斯–诺尔范式
|eng_name=Backus–Naur form
|aliases=BNF,巴克斯–瑙尔范式,巴科斯范式,Backus normal form
}}
'''<ins>巴科斯</ins>–<ins>诺尔</ins>范式'''('''Backus–Naur form''')或'''巴科斯范式'''('''Backus normal form''')，缩写为 '''BNF''' ，指一种为[[上下文无关文法]]设计的形式元语言语法。计算机领域中， BNF 及其变体作为编程语言理论的正式描述、作为语言文档及交流协议中的描述，得到广泛使用。

== 形式语言定义 ==

定义形式语言的字母表和规则如下：

=== 字母表 ===

BNF 的字母表是以下集合的并集：
* 文法符号（终结符和非终结符的统称）集合
** 终结符的集合 <math>V_N</math> ，其中任意元素都是字面量。字面量形式上使用双引号包围，如 <syntaxhighlight inline lang="bnf">"abc"</syntaxhighlight> 等；特别地，允许出现空串 <syntaxhighlight inline lang="bnf">""</syntaxhighlight> ，当需要双引号字符时可以使用单引号包围以免产生混淆 <syntaxhighlight inline lang="bnf">'"'</syntaxhighlight> ；
*** 尽管一般不明确出现在定义中， [[转义#C 风格转义字符|C 风格转义字符]]也常常被使用在 BNF 中指定非显示字符。
** 非终结符的集合 <math>V_T</math> 。非终结符使用[[连字符式]]并用尖括号包围，如 <syntaxhighlight inline lang="bnf"><symbol></syntaxhighlight> 或 <syntaxhighlight inline lang="bnf"><a-symbol-with-a-long-name></syntaxhighlight> ；
* 辅助符号的集合，包括竖线 <syntaxhighlight inline lang="bnf">|</syntaxhighlight> 和推导符号 <syntaxhighlight inline lang="bnf">::=</syntaxhighlight> 。

=== 规则 ===

BNF 的公式由多个生成式组成，记生成式的集合为 <math>G</math> ，则 BNF 的公式为：
* <math>g,g_2,g_3,\cdots</math>，<math>g\in G</math>；

其中 <math>G</math> 为生成式集，是由符合以下形式的项构成的集合：
* <math>n ::= a_1 | a_2 | \cdots | a_r</math> ，其中 <math>n\in V_N, a_i\in A, r\in \mathbb{N}_+</math> ；

其中 <math>A</math> 为生成式选项集，是由符合以下形式的项构成的集合：
* <math>v_1 v_2 \cdots v_s</math> ，其中 <math>v_i\in V_N \cup V_T, s\in \mathbb{N}_+</math> 。

==== BNF 定义 ====

这里使用 BNF 描述其自身的形式。<ref>https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form</ref>

<syntaxhighlight lang="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> | "-"
</syntaxhighlight>

== 语义 ==

每一条生成式对应一条生成文法规则，推导符号左侧总是一个非终结符，意味着其可以替换为右侧的文法符号序列。
多个具有相同左侧的生成式在 BNF 中可以写成一条的形式，此时右侧为由竖线分隔的多个选项，表示选择这多个选项中的一个进行替换。
右侧每个选项由一个到多个文法符号组成。

== 改进 ==

由于 BNF 缺失一些常见结构的简洁表达，通常有几种不同的扩展更常使用，见[[扩展 Backus–Naur 范式]]和[[增强 Backus–Naur 范式]]。