第二章 编译原理

《第二章 编译原理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章形式语言与自动机理论基础I“在不了解语言及自动机理论的技术和结果的情况下，就不能对计算机科学进行严肃的1研究”，J.Hopcroft如是说。“严肃”听起来比较吓人，只是，现在计算机的应用遍及日常生活的每一个角落，想不了解恐怕也不行，就像“出生越晚的人，需要记忆的历史事件越多”一样。2.1.文法和语言2.1.1.文法的直观描述在第一章中，我们讲过高级语言是人们模仿自然语言，采用一套形式规则来设计的人工语言。下面，我们就试着按这种方法来设计一种高级语言（注意：是自己设计的一种语言，可以是程序设计语言，也可以不是）。既然是模仿自然语言，就

2、需要借用自然语言中的符号表示以及熟悉的单词等。这里，我们不妨以英语为模仿对象，借用英语中的一些字母、单词及语法。例2.1文法的直观描述。第一步，从26个英文字母中选取以下9个字母作为我们要构造的人工语言的字母表。{a,c,e,h,m,o,s,t,u}第二步，用字母表中的这几个字母可以构造如下的一些单词。{a,cat,the,catches,mouse,came,⋯}2这些单词的构造规则：是所构造的单词应该是有实际意义的英文单词，是可以在英文字典里找得到的。第三步，借用英语中一些简单的语法把这些单词组词成句。有关的语法可以表示成下面的形式，

3、这里把它们也称为“规则”。（1）<句子>⟶<主语><谓语>（2）<主语>⟶<冠词><名词>（3）<谓语>⟶<动词><宾语>（4）<宾语>⟶<冠词><名词>（5）<名词>⟶cat

4、mouse（6）<冠词>⟶a

5、the（7）<动词>→catches

6、came以这些规则为基础，从第一条规则开始，不断地用这些规则的右部替换左部，直到把所有带尖括号的部分（即语法成分）都替换成单词为止。替换的方法有三种：（1）始终替换最左边的语法成分；（2）始终替换最右边的语法成分；（3）任意替换某一语法成分。2-1这里，采用第一种方法进行替换。例如：步骤推导所用规

7、则1.<句子>⟹<主语><谓语>(1)2.⟹<冠词><名词><谓语>(2)3.⟹the<名词><谓语>(6)4.⟹thecat<谓语>(5)5.⟹thecat<动词><宾语>(3)6.⟹thecatcatches<宾语>(7)7.⟹thecatcatches<冠词><名词>(4)8.⟹thecatcatchesa<名词>(6)9.⟹thecatcatchesamouse(5)1这种替换过程也可用“树”来表示，如图2.1所示。<句子><主语><谓语><冠词><名词><动词><宾语>thecatcatches<冠词><名词>amouse图2.

8、1替换过程的“树”表示在上述过程中，以字母表为基础构造了一些单词，然后又以单词为基础构造了一些句子。构造单词有相应的构词规则，即是在英文字典中可以找得到的单词。构造句子也有相应的语法规则。这种方式能够产生许多个句子，例如，采用类似的方法，可以构造如下的一些句子：（1）acatcatchesthemouse（2）themousecatchesacat2称这种方式为产生语言。“产生语言”，直观的理解：“说话”、“书写程序”。反过来，如果我们构造了一些单词，就需要根据英文字典判断这些单词是否合法；如果我们构造了一些句子，同样需要根据前述的语法规

9、则来判断句子是否是合法的，例如对于句子2-2thecatthemousecatches根据语法规则不难判断，这个句子是非法的。这种方式称为识别语言。“识别语言”，直观的理解：“听懂别人说的话”、“程序被机器执行，机器听懂了”。不过，在识别语言的过程中，不仅要看单词和句子是否符合构词规则和语法规则，同时还需要判断它所表达的意思即语义是否正确，例如对于句子（2），虽然其中的单词和句子分别符合构词规则和语法规则，但它的语义是不正确的。形式语言就是从这两个角度——产生语言和识别语言的角度，来对程序设计语言进行1形式化描述的，其中产生语言的构词规则

10、和语法规则称为文法，对语言的识别过程则是用自动机来实现的。2自1956年Chomsky建立形式语言以来，形式语言理论对计算机科学的发展产生了深刻的影响，特别是对计算机程序语言的设计、编译技术、计算复杂性等方面具有更大的作用。形式语言理论可以用统一的抽象方法来分析、研究程序设计语言。如果一个语言中含有有穷个句子，则称该语言是有穷的。有穷语言可用穷举法枚举全部句子。例如QQ中常用的表情就可以看成是一个语言集合，是可以用穷举法表示的有穷语言，如图2.2所示。图22QQ表情语言如果一个语言中含有无穷个句子，则称该语言是无穷的，例如，自然语言、QQ

11、表情语言的组合情形。形式语言理论为无穷语言的有穷表示提供了一种解决途径。在本节例子的每一步中，我们都会用到一些数学符号来表达或描述，下面就介绍一下一些常见的基本概念。2.1.2.字母表、字符串