编译原理 第三章 文法和语言编译原理 第三章 文法和语言.docVIP

第章 文法和语言 课前索引 【课前思考】　◇ 高级语言有哪些一般特性？　◇ 你所见到的程序设计语言的手册或语言标准是怎样陈述语言的语法和语义的？　◇ 学习编译程序为什么要研究语言的描述问题？【学习目标】　　本章目的是为语言的语法描述寻求工具 　◇ 掌握对源程序给出精确无二义（严谨、简洁、易读）的语法描述手段之一---文法。　◇ 熟练使用文法定义程序设计语言的单词和语法成分　◇ 对形式语言的理论有一个初步基础【学习指南】　◇ 什麽是文法,什麽是它定义的语言？　◇ 在乔姆斯基（Chomsky）的文法类型中，我们为什麽关注上下文无关文法？　◇ 什么是语法分析？语法分析方法的分类？【难重点】　　关于文法和语言的概念是形式语言的理论基础，形式语言抽象地定义为一个数学系统。形式是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。这里介绍的语言的语法描述工具正是这样的系统。【知识结构】 3.1引言和预备知识一个程序设计语言是一个记号系统，如同自然语言一样，它的完整的定义应包括语法和语义两个方面。所谓一个语言的语法是指一组规则，用它可以形成和产生一个合适的程序。目前广泛使用的手段是上下文无关文法，即用上下文无关文法作为程序设计语言语法的描述工具。语法只是定义什么样的符号序列是合法的，与这些符号的含义毫无关系，比如对于一个PASCAL程序来说，一个上下文无关文法可以定义A∶=B+C是合乎语法的，而A∶=B+是不合乎语法的。但是，如果B是实型的，而C是布尔型的，或者B，C中任何一个变量没有事先说明，则A∶=B+C仍不是正确的程序，也就是说程序结构上的这种特点，类型匹配，变量作用域等是无法用上下文无关手段检查的，这些工作属于语义分析工作。我们常常把程序设计语言的语义分为两类：静态语义和动态语义。静态语义是一系列限定规则，并确定哪些合乎语法的程序是合适的；动态语义也称作运行语义或执行语义，表明程序要做些什么，要计算什么。　　阐明语法的一个工具是文法，这是形式语言理论的基本概念之一。本章将介绍文法和语言的概念，重点讨论上下文无关文法及其句型分析中的有关问题。 文法的直观概念　　在给出文法和语言的形式定义之前，我们先直观地认识一下文法的概念。　　当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。　　以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如：我是大学生是汉语的一个句子。汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用第2章所介绍的EBNF来表示这种句子的构成规则：　　〈句子〉∷=〈主语〉〈谓语〉　　〈主语〉∷=〈代词〉|〈名词〉　　〈代词〉∷= 我 | 你 | 他　　〈名词〉∷= 王明 | 大学生 | 工人 | 英语　　〈谓语〉∷=〈动词〉〈直接宾语〉　　〈动词〉∷= 是 | 学习　　〈直接宾语〉∷=〈代词〉|〈名词〉　　“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。这样的语言描述称为文法。 一旦有了一组规则以后，我们可以按照如下方式用它们去推导或产生句子。我们开始去找∷=左端的带有〈句子〉的规则并把它表示成∷=右端的符号串，这个动作如右页所示： 〈句子〉〈主语〉〈谓语〉，然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓语〉，再用相应的规则∷=右端代替之。比如，选取了〈主语〉，并采用规则〈主语〉∷=〈代词〉，那么得到：〈主语〉〈谓语〉〈代词〉〈谓语〉，重复做下去。得到句子我是大学生的全部动作过程是：　　〈句子〉〈主语〉〈谓语〉　　 　　　 〈代词〉〈谓语〉 　　　　 我〈谓语〉　　　　　 我〈动词〉〈直接宾语〉　　　　　 我是〈直接宾语〉　　　　　　 我是〈名词〉　　　　　　 我是大学生　　符号的含义是，使用一条规则，代替左边的某个符号，产生右端的符号串。 显然，按照上述办法，不仅生成我是大学生这样的句子，还可以生成王明是大学生，王明学习英语，我学习英语，他学习英语，你是工人，你学习王明等几十个句子。事实上，使用文法作为工具，不仅为了严格地定义句子的结构，也是为了用适当条数的规则把语言的全部句子描述出来，是以有穷的集合刻划无穷的集合的工具。 语言概述　　语言是由句子组成的集合，是由一组符号所构成的集合。　　汉语--所有符合汉语语法的句子的全体　　英语--所有符合英语语