上下文无关文法及其分析树

上下文无关文法是程序设计语言所使用的语法。它的特点是同样的字符串在不同的语境下，意思不变。满足上下文无关文法的语言便于计算机识别和处理。我们已经介绍过，语言是语句的集合，而语句是通过产生式定义的。上下文无关文法要求产生式的左部有且仅有一个非终结符。

例如：考虑如下文法G，其非终结符集合为{L, D}，终结符集合为{0,1,2,…,9,+,-}，开始符号为L，产生式集合为

L→L+D|L−D|D

D→0|1|2|3|4|5|6|7|8|9

上面两个产生式中”|”表示“或”运算。产生式 L→L+D|L−D|D 是产生式集合

L→L+D

L→L−D

L→D

的缩写。
同样地产生式 D→0|1|2|3|4|5|6|7|8|9 是产生式集合

D→0

D→1

D→2

…

D→9

的缩写。

本例定义的文法是所有由‘+’和‘-’分割的数字序列组成的集合。

为了描述语法分析过程，需要引入分析树的概念。

分析树具有如下特性。

1. 根节点是开始字符。
2. 非叶子节点是非终结符（或者特殊的空串非终结符，见后文）。
3. 叶子节点是终结符。
4. 任何一个节点与它的子节点对应一个产生式。

例如：1+2-3的分析树如下。

整个分析过程如下

L→→D→3→L→L+D→D→2→L→D→D→1L−DL−3L+D−3L+2−3D+2−31+2−3.

如果一个语句能够构成一棵完整的分析树，则成为这个语句是合法的。事实上，语法分析的过程，就是构造分析树的过程。虽然我们在实现的时候，并不一定显示地构造这棵分析树。但是分析树的思想贯穿整个语法分析的始终。