巴科斯范式（Backus-Naur Form）

巴科斯范式是一种描述形式语言语法的元语言记号,用来精确地定义上下文无关文法。它由计算机科学家约翰·巴科斯（John Backus）在描述某编程语言语法时提出,后经彼得·瑙尔（Peter Naur）改进,因而得名。它是形式化语言规范的奠基性工具之一。

概述

巴科斯范式通过一组产生式规则来表达语法。每条规则把一个非终结符定义为由终结符和其他非终结符组成的序列或若干可选形式。非终结符代表可继续展开的语法类别,终结符则是语言中实际出现的最小符号。整个文法由这些规则递归地组织起来,能够刻画出语言中所有合法句子的结构。

核心特点

• 以产生式规则为基本单位,左侧为待定义的非终结符,右侧为其展开形式。
• 用竖线表示多种可选的产生形式。
• 通过递归规则表达嵌套与重复的语法结构。
• 只描述语法而不涉及语义,即只规定形式是否合法,不解释其含义。

应用场景

巴科斯范式被广泛用于编程语言的官方规范中,以无歧义的方式定义语言的语法。它是编译原理教学的基础内容,也是自动生成语法分析器的输入格式。许多协议、配置文件格式和查询语言的规范同样采用这种记号。其扩展形式引入了表示可选、重复的简便符号,使文法描述更为紧凑,应用更加广泛。

常见问题

问:巴科斯范式和扩展巴科斯范式有何区别?答:扩展形式在基本范式之上增加了表示可选项、重复项和分组的记号,减少了对递归的依赖,书写更简洁直观,但表达能力本质上相当。

问:巴科斯范式能描述所有语言吗?答:它对应上下文无关文法,能描述大多数编程语言的语法结构,但无法表达上下文相关的约束,例如变量必须先声明后使用这类规则通常留给语义分析阶段处理。