这种形式的定义就叫做产生式。出现在→左侧符号E称作非终结符(nonterminal symbol),代表可以继续产生新符号的“文法变量”。 符号→表示非终结符可以“产生”的东西。而上述产生式中的蓝色id、+、(等符号,是具有固定意义的单词,它们不再会产生新的东西,称作终结符(terminal symbol)。注意,非终结符可以出现在产生式的右侧,这就是具有递归性质文法的来源。产生式经过一系列的推导,就能够生成各种完全由终结符组成的句子。比如,我们演示一下表达式(a + b) + c的推导过程:
E => E + E => (E) + E => (E + E) + E => (a + E) + E => (a + b) + E => (a + b) + c
推导过程中的=>代表将当前句型中的一个非终结符替换成产生式右侧的内容。以上推导过程中,我们每次都将句型中最左边一个非终结符展开,所以这种推导称为最左推导。当然也有最右推导,不同之处就算是每次将句型中最右边的非终结符展开:
E => E + E => E + c => (E) + c => (E + E) + c => (E + b) + c => (a + b) + c
可见,同一个结果可以具有多种不同的推导过程。使用最左推导时,句型的左侧逐渐变得只有终结符;而最右推导正好相反,推导过程中句型的右侧逐渐变得只有终结符,最终结果都是整个句子变为终结符。所有符合文法定义的句子,都可以用文法的产生式推导出来。
我们语法分析的目的是解析输入的单词流(a + b) + c,得到它的语法分析树。先来看看语法分析树是什么样的。还是以(a + b) + c为例,语法分析树是这样的:
语法分析树的每一个节点都是一个非终结符或者终结符,其中终结符都是树的叶子结点(没有子节点),而非终结符都是有子节点的。一旦我们得到了语法分析树,就可以很容易地进行后续的语义分析,比如这个表达式的语义是“先将a和b代表的变量相加,再把所得的结果与c代表的变量相加”。那么语法分析树是怎么得到的呢,其实刚才的产生式推导过程,就可以顺便建立语法分析树,只要在展开非终结符的同时,在语法分析树中相应的节点下加入非终结展开的结果即可生成。下面我们用动画演示上述产生式通过最左推导和最右推导产生(a + b) + c语法分析树的过程:
我们刚才举的例子中,表达式(a + b) + c只能有一种语法分析树。但另外一些语法分析的输入,可能存在多种语法分析树, 这称为歧义。刚才的文法其实就是有歧义的(在哪里?请大家思考一下),但为了更清楚地表达歧义的危害,我们再举一个新的例子,它在前面例子中增加了乘法:
E → id
E → E + E
E → E * E
E → ( E )
如果用上述产生式推导出表达式a * b + c,就有两种可能的最左推导:
最左推导1:E => E + E => E * E + E => a * E + E => a * b + E => a * b + c
最左推导2:E => E * E => a * E => a * E + E => a * b + E => a * b + c
这两种推导的语法树是不一样的: