BNF 表示法

学习目标

通过本集的学习，你将能够：

  • 理解 BNF 的基本概念和语法
  • 掌握扩展 BNF (EBNF) 的用法
  • 学会用 BNF 描述简单的编程语言

1. BNF 简介

1.1 什么是 BNF？

BNF (Backus-Naur Form) 是一种用于描述上下文无关文法的形式化表示法。它由 John Backus 和 Peter Naur 发明，用于描述 Algol 60 编程语言的语法。

BNF 的基本元素：
- 非终结符：用尖括号 <> 括起来
- 终结符：直接写出
- 产生式：::= 表示"定义为"
- 选择：| 表示"或"

1.2 BNF 的基本语法

简单算术表达式的 BNF：
<表达式> ::= <表达式> + <项> | <项>
<项>     ::= <项> * <因子> | <因子>
<因子>   ::= ( <表达式> ) | <标识符>
<标识符> ::= <字母> | <标识符><字母> | <标识符><数字>
<字母>   ::= a | b | c | ... | z | A | B | ... | Z
<数字>   ::= 0 | 1 | 2 | ... | 9

2. 扩展 BNF (EBNF)

2.1 EBNF 的引入

EBNF 扩展了 BNF，增加了一些方便的表示法：

EBNF 的扩展符号：
- {} : 零次或多次重复（克林星）
- [] : 可选部分（零次或一次）
- () : 分组

2.2 EBNF 示例

用 EBNF 重写算术表达式：
<表达式> ::= <项> { + <项> }
<项>     ::= <因子> { * <因子> }
<因子>   ::= ( <表达式> ) | <标识符>

标识符的 EBNF：
<标识符> ::= <字母> { <字母> | <数字> }

3. 用 BNF 描述简单语言

3.1 简单语句的 BNF

简单赋值语句：
<语句>     ::= <赋值语句> | <if语句> | <while语句>
<赋值语句> ::= <标识符> = <表达式> ;
<if语句>   ::= if ( <表达式> ) <语句> [ else <语句> ]
<while语句>::= while ( <表达式> ) <语句>

3.2 完整示例

一个简单编程语言的 BNF：
<程序>       ::= { <声明> } { <语句> }
<声明>       ::= <类型> <标识符> ;
<类型>       ::= int | float | bool
<语句>       ::= <赋值语句> | <if语句> | <while语句> | <块>
<块>         ::= { { <语句> } }
<赋值语句>   ::= <标识符> = <表达式> ;
<if语句>     ::= if ( <表达式> ) <语句> [ else <语句> ]
<while语句>  ::= while ( <表达式> ) <语句>
<表达式>     ::= <加法表达式> [ <关系运算符> <加法表达式> ]
<关系运算符> ::= < | <= | > | >= | == | !=
<加法表达式> ::= <项> { <加法运算符> <项> }
<加法运算符> ::= + | -
<项>         ::= <因子> { <乘法运算符> <因子> }
<乘法运算符> ::= * | /
<因子>       ::= <标识符> | <数字> | ( <表达式> )
<标识符>     ::= <字母> { <字母> | <数字> }
<字母>       ::= a | b | ... | z | A | B | ... | Z
<数字>       ::= 0 | 1 | ... | 9

4. 实用案例

4.1 案例1：描述 JSON 语法

简化的 JSON EBNF：
<JSON>      ::= <对象> | <数组>
<对象>      ::= { [ <成员> { , <成员> } ] }
<成员>      ::= <字符串> : <值>
<数组>      ::= [ [ <值> { , <值> } ] ]
<值>        ::= <字符串> | <数字> | <对象> | <数组> | true | false | null
<字符串>    ::= " { <字符> } "
<数字>      ::= [ - ] <整数> [ . <数字> ] [ e <整数> ]
<整数>      ::= <数字> { <数字> }

4.2 案例2：描述正则表达式

正则表达式的 EBNF：
<regex>     ::= <alt>
<alt>       ::= <concat> { | <concat> }
<concat>    ::= <repeat> { <repeat> }
<repeat>    ::= <primary> [ * | + | ? ]
<primary>   ::= <字符> | ( <regex> ) | [ <字符类> ]
<字符类>    ::= <字符范围> { <字符范围> }
<字符范围>  ::= <字符> [ - <字符> ]

5. 自测问题

  1. BNF 中的 ::= 表示什么？
  2. EBNF 中 {} 和 [] 分别表示什么？
  3. 非终结符和终结符在 BNF 中如何区分？
  4. 为什么需要 EBNF？
  5. 用 BNF 描述一个简单的 if-else 语句。

6. 下集预告

下一集我们将学习语言设计原则！

参考资料

  • 《编译原理》（龙书）
  • 《现代编译原理》（虎书）
« 上一篇 推导与语法树 下一篇 » 语言设计原则（上）
↑