浅析上下文无关文法

在编译器的分析部分,需要使用一种表示方法用于描述程序语言的语法,上下文无关文法是表示方法中的一种。

文法定义

组成要素

一个上下文无关文法由四个元素组成:

  • 一个终结符号集合,终结符号是文法中最基本的符号,可以将其理解为最小的符号,有时也称为词法单元
  • 一个非终结符号集合,又称「语法变量」,是终结符号的集合
  • 一个产生式集合,产生式用来表示某种构造的书写形式,由产生式头,箭头,产生式体组成,稍后会有详细介绍
  • 一个开始符号,此符号为非终结符号
产生式

以 JAVA 语句为例子,一个 if-else 的语句一般是以下形式:

1
if (expr) stmt else stmt

上述语句可以用一个产生式表示为:

1
stmt -> if (expr) stmt else stmt

这是一个语句的描述,其中 if,else 称为终结符号,可以由一个词法单元表示。expr,stmt 属于非终结符号,因为其可以由另一个产生式表示。

举个简单的例子,接下来通过上下文无关文法描述一个简单的语法–乘除过程 p:

1
2
3
4
p -> p * digit
p -> p / digit
p -> digit
digit -> 0|1|2|3|4|5|6|7|8|9