自然语言和形式语言.doc

自然语言和形式语言
自然语言（Natural Language）就是人类讲的语言，比如汉语、英语和法语。这类语言不是人为设计（虽然有人试图强加一些规则）而是自然进化的。形式语言（Formal Language）是为了特定应用而人为设计的语言。例如数学家用的数字和运算符号、化学家用的分子式等。编程语言也是一种形式语言，是专门设计用来表达计算过程的形式语言。
形式语言有严格的语法（Syntax）规则，例如，3+3=6是一个语法正确的数学等式，而3=+6$则不是，H2O是一个正确的分子式，而2Zz则不是。语法规则是由关于符号（Token）和结构（Structure）的规则所组成的。Token的概念相当于自然语言中的单词和标点、数学式中的数和运算符、化学分子式中的元素名和数字，例如3=+6$的问题之一在于$不是一个合法的数也不是一个事先定义好的运算符，而2Zz的问题之一在于没有一种元素的缩写是Zz。语法规则的第二个范畴是结构，也就是Token的排列方式。3=+6$还有一个结构上的错误，虽然加号和等号都是合法的运算符，但是不能在等号之后紧跟加号，而2Zz的另一个问题在于分子式中必须把下标写在化学元素名称之后而不是前面。关于Token的规则称为词法（Lexical）规则，而关于语句结构的规则称为语法（Grammar）规则[3]。
当阅读一个自然语言的句子或者一种形式语言的语句时，你不仅要搞清楚每个词（或Token）是什么意思，而且必须搞清楚整个句子的结构是什么样的（在自然语言中你只是没有意识到，但确实这样做了，尤其是在读外语时你肯定也意识到了）。这个分析句子结构的过程称为解析（Parse）。例如，当你听到“The other shoe fell.”这个句子时，你理解the other shoe是主语而fell是谓语动词，一旦解析完成，你就搞懂了句子的意思，如果知道shoe是什么东西，fall意味着什么，这句话是在什么上下文（Context）里说的，你还能理解这个句子主要暗示的内容，这些都属于语义（Semantic）的范畴。
虽然形式语言和自然语言有很多共同之处，包括Token、结构和语义，但是也有很多不一样的地方。
歧义性（Ambiguity）
自然语言充满歧义，人们通过上下文的线索和其它一些信息来解决这个问题。形式语言的设计要求是清晰的、毫无歧义的，这意味着每一个语句必须有确切的含义而不管上下文如何。
冗余性（Redundancy）
为了消除歧义减少误解，自然语言引入了相当多的冗余。结果是自然语言经常变得啰里啰嗦，而形式语言则更加紧凑，极少有冗余。
与字面意思的一致性
自然语言充斥着成语和隐喻（Metaphor），我在某种场合下说“The other shoe fell”，可能并不是说谁的鞋掉了。而形式语言中字面（Literal）意思基本上就是真实意思，也有些特殊情况，例如C语言的转义序列（Escape Sequence），但也都会明确规定哪些字面意思不是真实意思，它们所表示的真实意思又是什么。
说自然语言长大的人（实际上没有人例外），往往有一个适应形式语言的困难过程。某种意义上，形式语言和自然语言之间的不同正像诗歌和说明文的区别，当然，前者的区别比后者更明显：
诗歌
词语的发音和意思一样重要，全诗作为一个整体创造出一种效果或者表达出一种感情。歧义和非字面意思不仅是常见的而且是刻意使用的。
说明文
词语的字面意思显得更重要，而且结构能传达出更多的信息。诗歌只能看一个整体，而说明文更适合逐字句分析，但仍然充满歧义。
程序
计算机程序是毫无歧义的，字面和本意高度一致的，能够完全通过对Token和结构的分析加以理解。
现在给出一些关于阅读程序（包括其它形式语言）的建议。首先请记住形式语言远比自然语言紧凑，所以要多花点时间来读。其次，结构很重要，从上到下从左到右地读往往不是一个好办法，而应该学会在大脑里解析：识别Token，分解结构。最后，请记住细节的影响，诸如拼写错误和标点错误这些在自然语言中可以忽略的小毛病会把形式语言搞得面目全非。

[3] 很不幸，Syntax和Grammar通常都翻译成“语法”，这让初学者非常混乱，Syntax的含义其实包含了Lexical和Grammar，还包含一部分语义（Semantic），例如变量应先声明后使用。即使在英文的文献中Syntax和Grammar也常混用，有些时候Syntax不包括Lexical。不过也没什么影响，只要结合上下文去看就不会误解。本书中在容易引起混淆的地方通常直接用英文名称，例如Token没有十分好的翻译，直接用英文名称。
程序和编程语言 请点评
程序（Program）是一个精确说明如何进行计算的指令序列。这里的计算可以是一些数学上的计算，比如解方程或者求多项式的根，也可以是符号运算，一个简单的例子是查找和替换文档中的词，一个复杂的例子是搜索引擎。从根本上说，计算机是由数字电路组成的运算机器，只能对数字做运算，程序之所以能做符号运算是因为符号在计算机内部也是用数字来表示的。此外，程序还可以处理声音和图像，同样因为声音和图像在计算机内部是用数字来表示的，这些数字再通过专门的硬件设备转换成人可以听到、看到的声音和图像。
程序由一系列指令（Instruction）组成，指令是指示计算机做某种运算的命令，通常包括以下几类：
输入（Input）
从键盘、文件或者其它设备获取数据。
输出（Output）
把数据显示到屏幕，或者存入一个文件，或者发送到其它设备。
基本运算
执行最基本的数学运算（加减乘除）和数据存取，其实输入和输出也属于数据存取。
测试和分支（Branch）
测试某个条件，然后根据不同的测试结果执行不同的后续指令。
循环（Loop）
重复执行一系列操作。
对于程序来说，有上面这几类指令就足够了。你曾用过的任何一个程序，不管它有多么复杂，都是由上面这几类指令组成的。程序是那么的复杂，而编写程序可以用的指令却只有这么简单的几种，这中间巨大的落差就要由程序员去填了，所以编写程序理应是一件相当复杂的工作。编写程序可以说就是这样一个过程：把复杂的任务分解成子任务，把子任务再分解成更简单的任务，层层分解，直到最后简单得可以用以上指令来完成。
在不同的编程语言（Programming Language）中，以上几种指令具有不同的形式。通常“指令”这个词专指机器语言（Machine Language）或者汇编语言（Assembly Language）等低级语言（Low-level Language）中的指令，而在C语言、C++、Java、Python等高级语言（High-level Language）中通常称为语句（Statement）或表达式（Expression）[1]。举个例子，同样一个语句用C语言、汇编语言和机器语言表示如下：
表 1.1. 同一个语句的三种表示
C语言
a=b+1;
汇编语言
Mov -0xc(%ebp),%eax
add  $0x1,%eax
mov %eax,-0x8(%ebp)
机器语言
8b 45 f4
83 c0 01
89 45 f8
计算机只能对数字做运算，虽然高级语言中有大量的符号，但这些符号都是人为定义的，最终转换成计算机可以直接处理的机器语言仍然是数字，上表中的机器语言完全由十六进制数字组成。最早的程序员都是直接用机器语言编程，但是很麻烦，需要查大量的表格来确定每个数字表示什么意思，编写出来的程序很不直观，很容易出错，于是有了汇编语言，把机器语言中的一组一组数字用助记符（Mnemonic）来表示，直接用这些助记符写出汇编程序，然后让汇编器（Assembler）去查表把助记符替换成数字，也就把汇编语言翻译成了机器语言。从上面的例子可以看出，汇编语言和机器语言的指令是一一对应的，汇编语言有三条指令机器语言也有三条指令，汇编器就是做一个简单的替换工作，例如在第一条指令中，把movl ?(%ebp),%eax这种格式的指令替换成机器码8b 45，把指令中的-0xc替换成机器码f4（这是补码表示）。
从上面的例子还可以看出，C语言的语句和低级语言的指令之间不是简单的一一对应关系，一条a=b+1语句要翻译成三条汇编或机器指令，这个过程称为编译（Compile），由编译器（Compiler）来完成，显然编译器的功能比汇编器要复杂得多。用C语言编写的程序必须经过编译转成机器指令才能被计算机执行，运行编译器程序要消耗一些时间，这是一个小小的缺点，而优点则是不可胜数的。首先，用C语言编程更容易，写出来的代码更紧凑，可读性更强，也更容易改正。其次，C语言是可移植的（Portable）或者称为平台无关的（Platform Independent），平台这个词有很多种解释，可以指计算机体系结构（Architecture），也可以指操作系统（Operating System），也可以指两者的组合。不同的计算机体系结构有不同的指令集（Instruction Set），可以识别的机器指令格式是不同的，直接用某种计算机的汇编或机器指令写出来的程序只能在这种计算机上执行，然而各种计算机上都有C编译器，可以把C程序编译成该计算机自己的（Native）机器指令，这意味着用C语言写出来的程序只需要稍加修改甚至不用修改就可以在不同的计算机上编译执行。各种高级语言都具有C语言的这些优点，所以绝大部分程序是用高级语言编写的，只有和硬件关系密切的少数程序（例如驱动程序）才会用到低级语言。
总结一下编译执行的过程，首先你用文本编辑器写一个C程序，然后保存成一个文件，例如program.c（通常C程序的文件名后缀是.c），这称为源代码（Source Code），然后运行编译器对它进行编译，编译的过程并不执行程序，而是把源代码全部翻译成机器指令，再加上一些描述信息，生成一个新的文件，例如a.out，这称为目标代码（Object Code）或可执行代码（Executable）[2]，这个可执行代码才是计算机可以执行的程序。如下图所示：
图 1.1. 编译执行过程

有些高级语言以解释（Interpret）的方式执行，解释执行的过程和C语言的编译执行过程很不一样，例如写一个Python源代码，保存成program.py（通常Python程序的文件名后缀是.py），然后，并不需要生成目标代码，而是直接运行解释器（Interpreter）执行该源代码，解释器是一行一行地翻译源代码，边翻译边执行的。如下图所示：
图 1.2. 解释执行过程

编程语言仍在发展演化。以上介绍的机器语言称为第一代语言（1GL，1st Generation Programming Language），汇编语言称为第二代语言（2GL，2nd Generation Programming Language），C、C++、Java、Python等可以称为第三代语言（3GL，3rd Generation Programming Language）。目前已经有了4GL（4th Generation Programming Language）和5GL（5th Generation Programming Language）的概念，主要区别在于，4GL以后的语言主要不是通过输入、输出、基本运算、测试分支和循环这些基本指令来编程的，4GL以后的语言更多是在描述要做什么（Declarative）而不是描述具体一步一步怎么做（Imperative），具体一步一步怎么做完全交由编译器或解释器决定，例如SQL语言（SQL，Structured Query Language，结构化查询语言）就是这样的例子。
习题 请点评
1、解释执行的语言相比编译执行的语言有什么优缺点？
这是我们的第一个思考题。本书的思考题通常要求读者系统地总结当前小节的知识，结合以前的知识，并经过一定的推理，然后作答。本书强调的是基本概念，读者应该抓住概念的定义和概念之间的关系来总结，比如本节介绍了很多概念：程序由语句或指令组成，在高级语言写的程序中通常叫语句，在低级语言写的程序中通常叫指令，计算机只能执行低级语言中的指令，高级语言要执行就必须先翻译成低级语言，翻译的方法有两种－－编译和解释，虽然有这样的不便，但高级语言有一个好处是平台无关性。什么是平台？一种平台，就是一种体系结构，就是一种指令集，就是一种机器语言，这些都可看作是一一对应的，上文没有明确讲它们之间是一一对应的但读者应该能推理出这个结论，而高级语言和它们不是一一对应的，因此高级语言是平台无关的，概念之间像这样的数量对应关系尤其重要。那么编译和解释的过程有哪些不同？主要的不同在于什么时候翻译和什么时候执行。
现在回答这个思考题，根据编译和解释的不同原理，能否在执行效率和平台无关性等方面做一下比较？
希望读者掌握以概念为中心的阅读思考习惯，每读一节就总结一套概念之间的关系图画在书上空白处。如果读到后面某一节看到一个讲过的概念，但是记不清在哪一节讲过了，没关系，书后的索引可以帮你找到它是在哪一节定义的。

[1] 语句和表达式之间的划分在不同的编程语言中有不同的规定，例如赋值在C语言中是表达式，而在Python中就是语句。
[2] 可执行代码只是目标代码的一种，以后我们会详细介绍