一种语言通常由语法、语义、语用三个部分组成。其中，语法是本章关注的重点，语义与语用将在后续章节中阐述。语言的语法指的是构成语言句子的各个符号之间的组合规律。同样，程序设计语言的语法就是描述构成各种语句的单词的组合规律，它是判断程序合法性的标准之一，但不是唯一标准。读者必须注意，符合程序设计语言语法的程序未必是合法的，但不符合语法的程序必定是非法的。这主要是由于程序既要符合语言的语法，又要符合语言的语义。

程序设计语言的语法体系与该语言是否能得到普及发展有着密切的联系。同时，也是评价一门语言的主要标准。通常，一门程序设计语言是否能得到普及发展主要取决于这几个方面：程序设计思想、应用领域、复杂程度、可移植性、语言实现、经济及其他非语言因素等。

(1)程序设计思想。实践证明，某种激进的程序设计思想往往与实现这种思想的程序设计语言密不可分。当然，那些实现先进设计思想的程序设计语言也会随着该设计思想的流行而获得广泛应用。例如，Niklaus Wirth提出结构化程序设计思想，同时也实现了Pascal语言。Pascal语言是其设计思想的一种体现。可以毫不夸张地说，完全是IF、WHILE、FOR等语法结构的出现成就了Pascal、C语言风靡几十年的神话。

(2)应用领域。程序设计语言在其定义之初就应该明确其应用领域。不同的应用领域对于程序设计语言的功能要求是不尽相同的。当然，应用领域也影响了该程序设计语言的普及程度。例如，C语言的应用领域是系统软件设计，而在数据库相关设计中就很少使用C语言。HTML语言的应用领域是Web设计，它就不具备传统结构化程序设计语言的IF、WHILE等语句。脱离具体的应用领域评价程序设计语言是不科学的。不过，优秀的程序设计语言往往能在相关领域内脱颖而出。

(3)复杂程度。与其他方面的因素相比，程序设计语言的复杂程度似乎显得更为重要。使用者总是偏爱那些简单易学的语言。简单易学的程序设计语言可以一定程度上弥补功能或其他方面的不足，BASIC语言的成功就是最好的例证。无论是程序设计思想还是功能实现，BASIC语言都确实存在一定不足之处，但是它的简单易学却足以弥补这一切。实际上，现存的大多数语言都是由于其简单易学而得以从当年的“乱世”中传承至今。实践证明，在一门功能强大的复杂语言和一门功能相对稍弱的简单语言之间，人们往往更乐意选择后者。当然，这种弥补是有一个度的。通常，功能强大与简单易学是矛盾的。以失去功能为代价，一味地追求语言的简单易学并不可取。语言设计者必须准确把握这个度，否则可能适得其反。

(4)可移植性。在当今程序设计语言领域，关于可移植性的争论是比较激烈的。在软件复用被尤为重视之际，一门语言是否能跨平台使用直接决定了其是否能普及发展。在这个问题上，C++与Java之争的结果似乎已经证明了一切。

(5)语言实现。Fortran语言的成功可能就是归功于其优秀的编译器实现。早期Fortran编译器的设计宗旨就是生成特别高效的代码。Fortran语言的开发者为此投入了大量的时间与金钱，虽然以牺牲一定的语言功能（例如，Fortran不支持递归）为代价，但是他们最终实现了这一目标。正是出众的效率才使得功能、设计思想都不是特别优秀的Fortran语言能传承至今。当然，语言实现不局限于编译器，还包括一些环境支持工具（如IDE、项目管理工具等）。

(6)经济及其他非语言因素。经济及其他非语言因素也是决定一门程序设计语言能否普及的重要因素。例如，语言支持、惯性发展等。经济因素是比较重要的，实践证明，免费的产品总会比收费的产品更容易得到使用者的青睐。编译器、操作系统等都是如此，Pascal、C、Java等都是由于免费才让更多的程序员、专家认识了它们。Linux能与操作系统霸主Windows一争高下，一个重要原因也是免费。另外，强有力的语言支持是保证语言发展的一个因素。程序设计语言的设计与实现是一项费时耗力的长期工程，如果没有强有力的后盾支持（人力、财力），可能是无法完成的。例如，COBOL和PL/I的生存很大程度上与IBM的支持有关。Ada语言的成功就是因为它出生在美国国防部。今天，评论C#、Java是否成功可能为时过早，但是C#、Java的发展与微软、Sun的支持是分不开的。再者，语言的惯性发展也是人们选择语言时考虑的因素之一。先入为主的思想广泛存在，人们通常更喜欢选择在某些现存语言基础上扩展而得的语言，而不喜欢选择一些全新定义的语言。尤其在今天几大语言体系初现端倪之际，人们更希望选择自己熟悉的语言及其扩展形式。

以上各个因素可能贯穿了整个程序设计语言及其编译器设计的过程。其中，前面三个因素与程序设计语言的语法有着密切的联系。因此，程序设计语言的语法定义是至关重要的，它是评价一门程序设计语言的重要因素之一。程序设计语言的语法定义通常包括两个过程：建模、描述。

建模就是构造一门程序设计语言的语法体系，这个过程并非想象中的那样简单，它涉及许多程序设计语言的相关理论。笔者举个简单的例子：C语言只定义了“与”、“或”、“非”、“异或”四个逻辑运算符，然而，这四个逻辑运算符的不同组合却可以描述任何复杂逻辑关系，但是，无论缺少哪一个逻辑运算符都无法实现这一描述功能。这使得C语言能借助较少的语言结构实现更多的功能，保证语言结构尽可能不重复，这种特性被称为程序设计语言的正交性。然而，在建模过程中，保证程序设计语言的正交性有时并不是非常容易的，需要程序设计语言相关理论的支持。由于Neo Pascal语言只是Pascal语言的扩展，所以并不存在完整的建模过程。程序设计语言的定义与设计也不是编译技术讨论的范畴，故不再赘述。

描述即语法的形式描述。其重点就是讨论如何描述程序设计语言语法模型。实际上，语言语法的描述是一门独立的学科，即形式语言学。形式语言是一种元语言的形式，是一套形式化描述语言（主要指的就是语言的语法）的方法。读者只要将形式语言理解为一种描述语言的语言即可。关于语言语义的描述并不是形式语言的讨论范畴，将在第4～6章中说明。形式语言在自然语言研究中起步，却在计算机科学中得到了应用，如编译技术、计算复杂性、通信技术、图像处理、人工智能等领域。其中，最主要被应用于编译技术中。编译技术是一门与语言有关的学科，所以形式语言自然就成为编译技术讨论的范畴了。在编译技术中，形式语言主要用于描述程序设计语言的语法。下面，就谈谈形式语言与程序设计语言语法之间的联系。

虽然人们每时每刻都离不开语言，但是，在日常生活或工作中，语言的语法往往为人们所忽视。读者可以想象一下，在学习汉语时，是不是从汉语语法开始的呢？显然，答案是否定的。语言学家研究表明，人们学习与掌握一门新语言的最主要途径就是实践经验。也就是说，人们是通过大量实践运用一门语言，以达到熟能生巧的境界。学习程序设计语言同样如此，也是通过大量编程实践最终才能掌握一门程序设计语言的。如果没有真正接触到语言的形式描述，即使能熟练应用某些程序设计语言，那也只是处于对语言的感性认识阶段。包括大多数程序设计书籍在内的编程方面的资料都是使用自然语言形式描述程序设计语言语法及其语义的。正如读者所知的，自然语言是可能存在不同程度的二义性的。显然，这种模糊的、不确定的方式是无法精确定义一门程序设计语言的。正因如此，在20世纪50年代，美国的语言学家Noam Chomsky提出了“转换一生成语法”的概念，深入阐述了语法结构的相关理论，这就是“形式语言学”原型，它是具有里程碑意义的。

编译器设计是一门与程序设计语言有着密切联系的学科，因此，仅仅从感性的角度认识一门程序设计语言是不够的。当然，必须设计一种准确无误地描述程序设计语言的语法结构，这就是将形式语言应用于编译技术的初衷。通常，将这种严谨、简洁、易读的形式规则描述的语言结构模型称为文法(grammar)。

最著名的文法描述形式是由Backus在定义Algol 60语言时提出的Backus-Naur范式（Backus-Naur Form，简写为“BNF”）及其扩展形式（简写为“EBNF”）。实际上，EBNF与BNF还是存在细微差别的，而且EBNF应用比BNF更为广泛。不过，由于BNF太著名，人们并不严格区别EBNF与BNF，统称为BNF。有些书籍甚至己不再严格区别BNF与文法的概念，本书后续提及文法指的就是文法的BNF形式。当然，除了BNF之外，还有一些其他的文法描述形式。其中，较为常见的就是语法图，第1章中描述Pascal语法的图形工具就是语法图。BNF、语法图都只是文法的一种描述形式而己，但与自然语言描述方式相比，它们的优点就是不存在二义性。然而，BNF之所以更为著名，就是由于它能以一种简洁、灵活的方式描述语言的语法。下面，笔者给出一个BNF的实例。

例3-1 自然语言文法实例。

【文法3-1l】

文法3-1是一个简化的自然语言文法。通常，将其中的每一行称为一个产生式，而一个完整的文法可以由一个或多个产生式组成。每个产生式中有且只有一个箭头（有时，亦可记作“：：”），表示“定义为”。箭头将一个产生式分成左右两个部分，而整个产生式即表示将其左部定义为其右部。读者不难发现，产生式的右部可以由一个或多个符号（或称为项）组成。其中，有些符号是整个文法中某些产生式的左部（为了便于讲解，笔者将这些符号使用斜体表示），有些符号则不是。在BNF中，将斜体符号称为非终结符，也就是说，它可以用其他符号串来定义。实际上，非终结符就是一个语法变量，是符号的有序集合。而其他非斜体符号则称为终结符，它是语言的最基本符号，即不可再分割的原子符号。

文法3-1描述了一个简化的自然语言模型，也就是说文法3-1完全可以验证某个句子是否属于该语言模型。下面，尝试验证“你是可爱的男孩”是否为合法的句子。实际上，如果可以运用上述产生式推导出这个句子（就是从“句子”出发，反复把上述规则中“一”左边的符号替换成右边的符号的过程。关于推导的详细内容可参见3.1.2节。），则表明这个句子符合该文法的描述，即为合法的句子，否则为不合法的句子。事实上，“你是可爱的男孩”是一个合法的句子，推导过程如下：

从“句子”这个非终结符出发（通常，称为文法开始符），经过了多次推导，最终得到了“你是可爱的男孩”这个句子，表明它是合法的句子。回头再来看看到底什么是推导？一次推导就是将非终结符替换为合适的产生式右部符号串的过程，可以用“=>”表示推导操作。从文法开始符出发，可以通过推导得到的句子集合就是这个文法所描述的语言。例如，“我是帅气的男孩”、“你是美丽的女孩”都是文法3-1的合法句子，而“我是男孩帅气的”、“我帅气的男孩是”都不是文法3-1的合法句子。读者不难发现，文法描述的语言都是终结符的集合，不包含任何非终结符。对于任何包含非终结符的符号串都只是推导的一个步骤，并不是文法描述的句子。在形式语言学中，将包含非终结符的符号串称为句型，将不包含非终结符的符号串称为句子。

值得注意的是，文法3-1是一个简化的自然语言文法，因此，它所描述的语言并不是汉语的全集。实际上，完整的自然语言文法是非常复杂的。其形式化描述是自然语言理解领域的重要研究课题，这里不作讨论。程序设计语言的语法比自然语言简单得多，使用文法描述程序设计语言是完全可行的。

形式语言理论的开创者Chomsky按文法描述能力将文法分为四种类型，由高到低分别为：0型（短语文法）、1型（上下文相关文法）、2型（上下文无关文法）、3型（正规文法）。实际上，大多数程序设计语言的文法都是上下文无关文法，文法3-1也是一个上下文无关文法。因此，上下文无关文法是编译技术讨论的重点。至于其他类型的文法，读者可参考相关书籍，这里不再赘述。

上下文无关文法(context-free grammar)由终结符、非终结符、文法开始符和产生式组成。(www.daowen.com)

(1)终结符(terminal):语言的最基本符号，即不可再分割的原子符号。在程序设计语言中，终结符必定是词法分析所得到的单词。例如，关键字if、then等都是终结符。

(2)非终结符(nonterminal)：语法变量，它可以定义为一个符号串（由终结符和非终结符组成的符号串）。例如，文法3-1的“宾语”、“主语”等都是非终结符。

(3)文法开始符(start symbol):在一个完整的文法中，有且仅有一个非终结符可以被指定为文法开始符。

(4)产生式(production):是一种定义语法规则的形式。产生式的形式：非终结符一符号串。

通常，有些书把上下文无关文法表示为一个四元组：(V_T，V_n，S，P)，其中VT为终结符集合，V_n为非终结符集合，S(S∈V_n)为文法开始符，P为产生式集合。

为了便于描述，除特殊说明外，本书的文法将采用如下约定：

非终结符用斜体字表示。

终结符用正体字表示。

若无特殊说明，文法的第一个产生式的左部非终结符就是文法的开始符。

可以使用小写希腊字母表示文法符号串。

如果存在如下文法：

则可以简化写成如下形式：

我们将α¹、α²、……、α^k称为A的候选式。

例3-2 使用上述简写约定，文法3-1可以简写为：

【文法3-2】

语言的文法是研究程序设计语言的基础，也是编译器前端的重要理论基础之一。读者应该熟悉文法描述形式，这对于学习编译器与程序设计语言设计是至关重要的。编译器设计者可以不关心程序设计语言的建模过程，但必须关心建模的结果，即语言模型的形式化描述。下面，笔者借助一个实例来讨论如何运用文法描述程序设计语言的算术表达式。

例3-3 算术表达式的文法。

【文法3-3】

注意：var表示变量，const表示常量，它们都是终结符。

在初学一门程序设计语言时，最复杂的语法机制可能就是表达式了。就C语言而言，34种运算符及其15个优先级分类可能足以让初学者琢磨许久。表达式不但文法复杂（优先级）、运算符众多，而且还涉及类型系统等繁复的语义处理。虽然文法j-j是一个简化的算术表达式文法，但是它揭示了算术表达式乃至表达式的核心。文法j-j中包含了括号、单目运算符、双目运算符，同时，还涉及运算符的优先级。独立设计程序设计语言文法的机会未必很多，但理解文法所描述的语法规则是非常必要的。运用文法j-j验证表达式“3*5+(1-i)，，合法性的详细推导过程如下：

从文法开始符E经过21步推导可以得到表达式3*5+（1-i）’故此表达式是合法的。