1、2022-8-6计算机语言的发展计算机语言的发展计算机语言的发展计算机语言的发展主要内容主要内容5.1 形式语言形式语言5.2 计算机语言的发展计算机语言的发展计算机语言的发展5.1 形式语言形式语言 计算机语言是一种形式化语言计算机语言是一种形式化语言 为什么要用形式化语言？为什么要用形式化语言？形式语言是以数学和数理逻辑为基础的科学语形式语言是以数学和数理逻辑为基础的科学语言，其语言符号具有单一性、无歧义性和明确言，其语言符号具有单一性、无歧义性和明确性特点性特点 自然语言具有歧义性，其语法结构不够严格、自然语言具有歧义性，其语法结构不够严格、不够统一不够统一 自然语言是某一社会发展中形成
2、的一种民族语言自然语言是某一社会发展中形成的一种民族语言 要用计算机对语言进行处理，则必须解决要用计算机对语言进行处理，则必须解决语言的歧义性问题语言的歧义性问题计算机语言的发展自然语言的歧义性实例自然语言的歧义性实例 例：他的发理得好。例：他的发理得好。这个例子至少有两种不同的解释：这个例子至少有两种不同的解释：他的理发水平高。他的理发水平高。理发师理他的发理得好。理发师理他的发理得好。计算机语言的发展形式语言的基本特点形式语言的基本特点 有一组初始的、专门的符号。有一组初始的、专门的符号。有一组精确定义的符号串转换规则（即形式有一组精确定义的符号串转换规则（即形式语言语法）。语言语法）。形
3、式语言语法中不包含语义。形式语言语法中不包含语义。在一个给定的形式语言中，可以根据需要，通过赋值在一个给定的形式语言中，可以根据需要，通过赋值或模型对其进行严格的语义解释，从而构成形式语言或模型对其进行严格的语义解释，从而构成形式语言的语义的语义 在形式语言中，不允许出现根据形成规则无法确在形式语言中，不允许出现根据形成规则无法确定的符号串定的符号串计算机语言的发展形式语言实例形式语言实例 例：语言例：语言W定义为：定义为：初始符号集：初始符号集：a，b，c，d，e。形成规则：上述符号组成的有限符号串中，能组形成规则：上述符号组成的有限符号串中，能组成一英语单词的为一公式；否则不是。成一英语单
4、词的为一公式；否则不是。问：问：W是否为一形式语言？是否为一形式语言？答：不是，因为根据形成规则，无法精确地答：不是，因为根据形成规则，无法精确地定义转换规则。原因：形成规则（语法）中定义转换规则。原因：形成规则（语法）中包含了语义。包含了语义。计算机语言的发展形式语言实例形式语言实例 例：语言例：语言W定义为：定义为：初始符号集：初始符号集：a，b，c，d，e，(，)，+，。形成规则：上述符号组成的有限符号串中，能组形成规则：上述符号组成的有限符号串中，能组成表达式的为一公式；否则不是。成表达式的为一公式；否则不是。问：问：W是否为一形式语言？是否为一形式语言？答：不是，因为根据形成规则，无
5、法精确地答：不是，因为根据形成规则，无法精确地定义转换规则。原因：形成规则（语法）中定义转换规则。原因：形成规则（语法）中包含了语义包含了语义计算机语言的发展形式语言实例形式语言实例 例：语言例：语言W定义为：定义为：初始符号集：初始符号集：a，b，c，d，e，(，)，+，。形成规则：上述符号组成的有限符号串中，凡以符号形成规则：上述符号组成的有限符号串中，凡以符号“(”开头且以开头且以“)”结尾的符号串为一公式。结尾的符号串为一公式。问：问：W是否为一形式语言？是否为一形式语言？答：不是，因为根据形成规则，无法对不是以符号答：不是，因为根据形成规则，无法对不是以符号“(”开头且以开头且以“)
6、”结尾的符号串进行判定。例如，结尾的符号串进行判定。例如，(a+b)c。计算机语言的发展形式语言实例形式语言实例 例：语言例：语言W定义为：定义为：初始符号集：初始符号集：a，b，c，d，e，(，)，+，。形成规则：上述符号组成的有限符号串中，凡以形成规则：上述符号组成的有限符号串中，凡以符号符号“(”开头且以开头且以“)”结尾的符号串为一公式；结尾的符号串为一公式；否则不是。否则不是。问：问：W是否为一形式语言？是否为一形式语言？答：是。答：是。计算机语言的发展5.2 计算机语言的发展计算机语言的发展 计算机语言经历了从机器语言、汇编语言、计算机语言经历了从机器语言、汇编语言、高级语言、应用
7、语言到自然语言的发展阶段。高级语言、应用语言到自然语言的发展阶段。计算机语言的发展算法的机器语言描述算法的机器语言描述 例如：用机器指令对例如：用机器指令对“2+6”进行计算的算法进行计算的算法描述描述1011000000000110 /将将“6”送到寄存器送到寄存器AL中，数字中，数字“6”放在指令后八位放在指令后八位0000010000000010 /将数将数“2”与寄存器与寄存器AL中的内容相加，结果仍存在中的内容相加，结果仍存在AL中中101000100101000000000000 /把把AL中的中的内容送到地址为内容送到地址为5的单元中的单元中计算机语言的发展算法的汇编语言描述算法
8、的汇编语言描述 例如：用汇编语言对例如：用汇编语言对“2+6”进行计算的算法进行计算的算法描述描述MOV AL，6ADD AL，2MOV VC，AL 汇编语言语句与特定的机器指令有一一对应汇编语言语句与特定的机器指令有一一对应的关系，经汇编程序（汇编语言用户的虚拟的关系，经汇编程序（汇编语言用户的虚拟机）翻译为机器指令后才能运行机）翻译为机器指令后才能运行计算机语言的发展算法的高级语言描述算法的高级语言描述 例如：用高级语言对例如：用高级语言对“2+6”进行计算的算法进行计算的算法描述描述2+6 高级语言的语句与特定机器的指令无关高级语言的语句与特定机器的指令无关 高级语言程序经编译程序（高级
9、语言用户的虚拟高级语言程序经编译程序（高级语言用户的虚拟机）翻译成汇编语言，然后经汇编程序（汇编语机）翻译成汇编语言，然后经汇编程序（汇编语言用户的虚拟机）翻译为机器指令后才能运行言用户的虚拟机）翻译为机器指令后才能运行计算机语言的发展算法的应用语言描述算法的应用语言描述 用应用语言编程，用户只需告知系统用应用语言编程，用户只需告知系统“做什做什么么”，而无需说明，而无需说明“怎么做怎么做”如：如：SQL 这类语言提供了功能强大的非过程化问题定义手这类语言提供了功能强大的非过程化问题定义手段段 用应用语言编写的程序一般经应用程序包用应用语言编写的程序一般经应用程序包（应用语言用户的虚拟机）翻译
10、成高级语言（应用语言用户的虚拟机）翻译成高级语言程序后，再逐级向下实现程序后，再逐级向下实现计算机语言的发展基于虚拟机的计算机层次结构基于虚拟机的计算机层次结构计算机语言的发展基于虚拟机的计算机层次结构基于虚拟机的计算机层次结构计算机语言的发展自然语言的计算机处理自然语言的计算机处理 自然语言的计算机处理可以分为以下四个层次：自然语言的计算机处理可以分为以下四个层次：第一层次是文字和语音，即基本语言信息的构成第一层次是文字和语音，即基本语言信息的构成；第二层次是语法，即语言的形态结构；第二层次是语法，即语言的形态结构；第三层次是语义，即语言与它所指的对象之间的关系；第三层次是语义，即语言与它所
11、指的对象之间的关系；第四层次是语用，即语言与它的使用者之间的关系。第四层次是语用，即语言与它的使用者之间的关系。目前，自然语言的输入问题已基本解决。要使计算目前，自然语言的输入问题已基本解决。要使计算机对自然语言进行处理，关键是要解决自然语言语机对自然语言进行处理，关键是要解决自然语言语法和语义的形式化问题。法和语义的形式化问题。计算机语言的发展自然语言的形式化问题自然语言的形式化问题 自然语言能否形式化？自然语言能否形式化？人具有创造和理解正确句子的能力。这种语言人具有创造和理解正确句子的能力。这种语言“创造性创造性”过程，其实就是由有限数量的词，根过程，其实就是由有限数量的词，根据一定的规
12、则产生正确句子的过程。进一步而言，据一定的规则产生正确句子的过程。进一步而言，其实质也就是一个字符串到另一个字符串的变换其实质也就是一个字符串到另一个字符串的变换过程。显然，语言过程。显然，语言“创造性创造性”过程的本质与计算过程的本质与计算过程的本质是一致的。过程的本质是一致的。因此，可以将自然语言也看作是一种计算，从而因此，可以将自然语言也看作是一种计算，从而自然语言能否实现形式化的争论也就不存在了。自然语言能否实现形式化的争论也就不存在了。计算机语言的发展自然语言的形式化方法自然语言的形式化方法 自然语言的形式语法可表示为：自然语言的形式语法可表示为：G0=，其中，其中，Vn为非终结符号
13、的有限集合；为非终结符号的有限集合；Vt为终结符号的有限集合；为终结符号的有限集合；P0为生成式（或称产生式）的有限集合，即形式为生成式（或称产生式）的有限集合，即形式规则；规则；S为开始符号为开始符号计算机语言的发展自然语言的形式化实例自然语言的形式化实例 设自然语言的形式语法中，设自然语言的形式语法中，Vn=S，NP，VP，N，V，Vt=我，他，学，教，英语，汉语，希望我，他，学，教，英语，汉语，希望，P0=SNP VP，NP N，VP V NP，VP V S，N 我，我，N 他，他，V 学，学，V 教，教，V 希望，希望，N 英语，英语，N 汉语汉语，其中，其中，S表示句子；表示句子；N
14、P表示名词短语表示名词短语 VP表示动词短语表示动词短语 N表示名词表示名词 V表示动词表示动词 S NP VP表示句子由名词短语和动词短语组成表示句子由名词短语和动词短语组成 NP N表示名词短语由名词构成表示名词短语由名词构成计算机语言的发展句子的派生过程举例句子的派生过程举例计算机语言的发展相关图灵奖获得者相关图灵奖获得者 约翰约翰巴克斯巴克斯 1977年图灵奖获得者，年图灵奖获得者，FORTRAN和和BNF的发明的发明者者 肯尼思肯尼思艾弗森艾弗森 1979年图灵奖获得者，大器晚成的科学家，年图灵奖获得者，大器晚成的科学家，APL的发明人的发明人 查尔斯查尔斯霍尔霍尔 1980年图灵奖
15、获得者，从年图灵奖获得者，从QUICKSORT、CASE到程序设计语言的公理化到程序设计语言的公理化计算机语言的发展相关图灵奖获得者相关图灵奖获得者 罗宾罗宾米尔纳米尔纳 1991年图灵奖狄得者，标准元语言年图灵奖狄得者，标准元语言ML的开发者的开发者 彼得彼得诺尔诺尔 2005年图灵奖获得者，从天文学家到计算机科学年图灵奖获得者，从天文学家到计算机科学家，家，BNF改良家改良家 弗朗西丝弗朗西丝爱伦爱伦 2006年图灵奖获得者，编译器优化理论与实践的年图灵奖获得者，编译器优化理论与实践的先驱先驱计算机语言的发展罗宾罗宾米尔纳米尔纳（1934?）计算机语言的发展彼得彼得诺尔诺尔（1928?）计
16、算机语言的发展弗朗西丝弗朗西丝爱伦爱伦（1932?）计算机语言的发展讨论讨论 计算机发展趋势是什么？计算机发展趋势是什么？（巨型化、微型化、网络化、多媒体化、智能（巨型化、微型化、网络化、多媒体化、智能化）化）计算机语言的发展思考题思考题 什么是形式语言？试举例说明。什么是形式语言？试举例说明。什么是机器语言？什么是汇编语言？什么是机器语言？什么是汇编语言？如何用虚拟机的观点来划分计算机的层次结如何用虚拟机的观点来划分计算机的层次结构？构？自然语言的计算机处理分为哪自然语言的计算机处理分为哪4个层次？个层次？为什么说自然语言的为什么说自然语言的“创造性创造性”过程的本质过程的本质与计算过程的本质是一致的？与计算过程的本质是一致的？2022-8-6计算机语言的发展
