1、第四章 程序语言的性质1语言的形式化模型n BNF为描述程序设计语言的属性提供了一种很好的手段，但并不是充分的手段。 BNF回答了程序看起来象什么，但没有回答程序是做什么的。n 形式化模型采用精确的数学模型来刻画研究对象，为研究、分析和操纵研究对象提供严谨的数学工具和手段。n 本章将介绍下列形式化模型：n 形式文法：乔姆斯基文法分级n 语言的语义 ： 属性文法 、 指称语义n 程序的验证24.1 语言的形式化性质n 乔姆斯基分级文法n 语言的能力3乔姆斯基分级文法n 文法n 由非终结符、终结符、开始（非终结）符、及产生式构成n 文法的类别n 3型文法：正则文法，定义词法的模型n 2型文法： B
2、NF文法，上下文无关文法n 1型文法：上下文有关文法n 0型文法：43型文法：正则文法n 为词法分析器提供模型。n 这类文法的大多数性质都是可判定的n 如，能产生什么样的串、给定串是否属于文法规定的语言、语言中的串是否有限等n 正则文法可以产生形如 an的串，其中 a为有限字符序列n 正则文法只能计数有限数n 常用于关键字或单词扫描52型文法 上下文无关文法n 产生式的形式为： X , 其中 可以是终结符和非终结符的任意序列n 同样，这类文法的大多数性质都是可判定的n 如，能产生什么样的串、给定串是否属于文法规定的语言、语言是否为空等n 可用来计数和比较两个项，产生形如 ancbn的串n 可以
3、用堆栈来实现n 可用来自动产生程序的语法分析树n 2型和 3型文法的相关问题都已基本上得到解决61型文法 上下文有关文法n 产生式的形式为： , 其中 任意非终结符串， 是终结符和非终结符的任意序列，但 中的符号个数应不多于 的符号个数n 从开始符开始导出的串的长度是递增的n 在生成串时，需要使用固定数量的存储空间，例如识别上下文无关文法无法识别的串 ancnbnn 上下文有关文法太复杂，很难用于程序设计语言n 人们对上下文有关文法的很多特征还不太清楚70型文法 非限定型文法n 对产生式的形式 没有任何限制n 可用来识别任意可计算的函数n 其大多数性质都是不可判定的返回8不可判定性n 不同类型
4、的文法越来越复杂，产生的语言也越来越复杂，但是否说明计算机解决问题的能力可以越来越强，没有限制？n 例如：能否编写一个 C语言程序来判断另一个 C语言程序能否结束？n 但这基本上是不可能的，这不是编程人员的问题，而是因为 计算机所基于的数学模型 本身的局限性而导致的。9图灵机n 一般来说，用一种语言编写的程序也可以用其他另一种语言来实现。n 那么是否存在某个程序，只能用某种语言来实现，而用其他语言就无法实现？n 如果没有，那么有哪些程序是其它程序设计语言无法表示的，为什么还需要那么多种不同的语言？n 如果我们将能够表示所有计算的语言都称为通用语言，那么是不是所有语言都是通用语言？如果是，是否存在更简单的通用语言？10
