巴科斯-瑙尔范式(BNF)

定义

巴科斯-瑙尔范式(Backus-Naur Form,BNF)是描述上下文无关文法的形式化记法,由 John Backus 提出、Peter Naur 在 ALGOL 60 报告中完善并推广,此后成为编程语言语法规范的标准表达方式。

记法

文法由一组产生式构成,形如 <expr> ::= <expr> "+" <term> | <term>;尖括号包裹非终结符,引号或裸字面量为终结符,竖线表示可选分支,规则可递归引用。

扩展

EBNF(扩展 BNF)增加了重复 {}、可选 [] 与分组 () 等便捷记号,被 ISO 标准化;ABNF(增强 BNF)由 IETF 用于 RFC 中协议语法定义,如 HTTP、URI 的规范。

意义

BNF 让语言语法第一次拥有了精确、可机读的定义,直接催生了解析器生成器(Yacc 等以 BNF 风格文法为输入),也是编译原理教学的基本工具。