1.1 语言、文法与递归
我们对语言这个概念再熟悉不过了，汉语和英语等都是自然语言。而C语言和C++语言，这些是编程语言，更专业的术语，这些是形式语言, 老外称之为Formal Language。Formal这个单词的原意是“正式的”，非常准确地表达了形式语言和自然语言的区别。C语言和C++这些语言之所以被称为形式语言，原因在于这些语言的产生过程是先有正式的语法结构，之后才由这些语法结构来产生语言。而汉语和英语则正好相反，原始人从树上刚走下来时，是不会先开会讨论一下语法结构的，最原始的呼喊经数万年的演化和交融，自然而然地形成了汉语和英语等自然语言。很多时侯，我们讲“自然而然地”，往往是因为我们对具体的形成过程也不太明了。数万年的语言发展，岂能那么一清二楚？若干年之后，广大语文老师们才聚在一起研究语法结构的问题。这种先上车后补票的行为，当然不够formal了。这也是为什么自然语言的识别，会成为人工智能领域的一个令人头大的问题；而C语言的识别从语言一诞生就能得到很好解决的原因之一。
计算机相关学科的人会在大二时学一门叫《离散数学》的课程，里面一个很重要的概念就是集合，这个曾引起第三次数学危机的名词，是个放之四海皆适用的名词。我们要讨论的语言，实际上也是个集合。如何表达一个集合？一般而言，有这么两种方法：一个是列举法，一个是描述法。对于个数有限的集合，可以用列举法一一列出；而对于无穷的集合，则多用描述法来表达。例如，S ＝ {张三、李四、王五} 构成了一个有限集合。而要表达偶数这样的无穷集合，我们则使用 E ＝ {x | x = 2n, n是正整数} 这样的描述法。既然我们要把C语言看成一个集合，那么每个合法的C源代码就是这个集合里的一个元素，合法的C源代码有无穷多个，那我们要用什么样的描述方法来表达C语言这个无穷集合？让我们不妨先看看下面这个比C语言简单得多的语言。
T ＝ {a, a+a, a+a+a, ……} (1-1)
我们不难发现，上述集合T是由若干个a相加构成，这是个无穷集合，省略号“……”的意思是“这个集合的元素太多了，我们列举不下，你自个儿研究已列出的元素，然后去找规律吧”。这种“你猜你猜你猜猜”的描述方法，显然不能让追求完美的我们感到满意。那我们就来探索一下有没有更好的表达方法。让我们先把集合T一分为二。
T ＝ {a, a+a, a+ a + a, ……}
＝ {a} U {a+a, a+a+a, ……}
我们仔细观察其中的{a+a,a+a+a,…..}，越看越觉得这个式子跟T有点相似。如果把{a+a,a+a+a,…}里的每个元素的前缀“a+”移到大括号之外，我们就有
T ＝ {a} U a+ {a,a+a,a+a+a,……}
＝ {a} U a+T
这是一个对集合T的递归定义。到此，我们把语言、集合和递归关联到了一起。稍微整理一下，我们把这个无穷集合T写为：
T --> a | a+T (1-2)
式子(1-2)告诉我们，T由a或者a+T构成。也可分成多行写，记为
T:
a
a + T
如果我们想到事物往往是有阴就有阳，有左就有右，有前就有后，我们就会尝试看看能不能作其他类似的变换。仔细观察(1-1)式的右部，我们还可以把“+a”作为后缀提取到大括号之后，于是又有了：
T ＝ {a} U {a,a+a,a+a+a,…. } +a
＝ {a} U T +a
稍作整理，就有了下式
T ---> a | T + a (1-3)
式子(1-2)和(1-3)的区别在于，前者的递归出现在a+T右侧，而后者的递归定义出现在T+a左侧，所以(1-2)式被称为右递归，(1-3)式被称为左递归。由这两个式子都能产生语言T，即可以生成以下集合中的各个元素：
{a,a+a,a+a+a, …..}
所以，形如(1-2)和(1-3)这样的式子就被称为产生式。有限的符号却精准地描述了无穷的
集合，这非常符合是老子在《道德经》所言的“一生二，二生三，三生万物”。让我们享受一下由产生式产生句子的过程。例如要判断字符串a + a是否是语言T中的一个合法的句子，即判断字符串a+a是否是集合T的一个元素，我们可以从T出发，作以下推导。下式(1-4)和(1-5)分别是以(1-2)和(1-3)作为产生式进行推导的结果。
T -----> a + T
-----> a + a (1-4)
T -----> T + a
-----> a + a (1-5)
每一步的推导都是用某个产生式的右侧来替换左侧。下图1-1就用一棵树来形象地表述了式(1-4)的推导过程。该树被称为分析树，parsingtree。我们可通过这棵树来分析字符串a+a是否为语言T的合法句子。对这棵树作进一步观察，可以发现，树中的有些结点可以向外生长，例如其中标为T的结点；而有些结点则不具备生长能力，例如其中标为a和+的结点。因此，我们称式(1-2)中的T为非终结符，而a和+为终结符。式(1-2)实际上是由两个产生式构成,它们共同刻画了语言T的特征，它们是关于如何生成语言T的法则，所以称之为文法grammar. 当然，严格地说，文法由终结符、非终结符、产生式和开始符号构成。开始符号即为我们要描述的集合对应的非终结符，此处即为T。由图1-1可以形象地看到，开始符号即为树根T，这是我们作推导起步的地方，也是语言中所有合法句子的始祖，所以称之为开始符号。实际上如果约定第一个产生式左侧的非终结符为文法的开始符号，则产生式就包含了文法的所有信息。以后的表述中，在不混淆的情况下，我们不去区分文法和产生式。
如果任给一个字符串，作为程序员的我们当然不希望每次都手工来判断它是否为合法的
句子，我们需要根据文法来写一个程序来帮我们做这些事情，这个程序被称为语法分析器。
下面让我们先引入一个稍为复杂一点的文法，稍后我们将介绍如何基于这个文法来写一个语法分析器。
Program -----> CompoundStatement
Statement --> IfStatement | WhileStatement｜CompoundStatement｜ExpressionStatement
IfStatement -----> if ( expression) Statement
IfStatement -----> if ( expression) Statement elseStatement
WhileStatement -----> while(expression) Statement
CompoundStatement -----> { StatementListopt}
StatementList -----> Statement | StatementList Statement
ExpressionStatement -----> id = Expression ;
ExpressionStatement -----> Declaration ;
Expression -----> AdditiveExpression
AdditiveExpression -----> MultiplicativeExpression
AdditiveExpression -----> AdditiveExpression + MultiplicativeExpression
AdditiveExpression -----> AdditiveExpression - MultiplicativeExpression
MultiplicativeExpression -----> PrimaryExpression
MultiplicativeExpression -----> MultiplicativeExpression * PrimaryExpression
MultiplicativeExpression -----> MultiplicativeExpression / PrimaryExpression
PrimaryExpression -----> id | num | (Expression)
Declaration -----> int Declarator
Declarator -----> * Declarator | PostfixDeclarator
PostfixDeclarator ---> DirectDeclarator | PostfixDeclarator [num]| PostfixDeclarator (void)
DirectDeclarator -----> id | (Declarator)
图1-2 文法Program
按照前面的约定，图1-2中的第一个产生式左侧的非终结符Program为文法的开始符号。让我们来看个例子，就能明白这个看起来似乎很复杂的文法究竟刻画了一个什么样的语言。
{
int (*f(int,int,int))[4];
int (*(*fp2)(int,int,int))(int);
if(c)
a = f;
else{
b = k;
}
while(c){
while(d){
if(e){
d = d - 1;
}
}
c = c - 1;
}
}
请于http://download.csdn.net/detail/sheisc/8325793下载ucc162.2.tar.gz，解压后的目录ucc\examples\sc中包含的代码，即为根据图1-2构造出来的语法分析程序。