
自然语言和形式语言.doc
6页自然语言和形式语言自然语言(Natural Language)就是人类讲的语言,比如汉语、英语和法语这类语言不是人为设计(虽然有人试图强加一些规则)而是自然进化的形式语言(Formal Language)是为了特定应用而人为设计的语言例如数学家用的数字和运算符号、化学家用的分子式等编程语言也是一种形式语言,是专门设计用来表达计算过程的形式语言形式语言有严格的语法(Syntax)规则,例如,3+3=6 是一个语法正确的数学等式,而 3=+6$则不是,H 2O 是一个正确的分子式,而 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),%eaxadd $0x1,%eaxmov %eax,-0x8(%ebp)机器语言8b 45 f483 c0 0189 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、解释执行的语言相比编译执行的语言有什么优缺点?这是我们的第一个思考题。
本书的思考题通常要求读者系统地总结当前小节的知识,结合以前的知识,并经过一定的推理,然后。
