编译原理 形式语言

《编译原理 形式语言》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章形式语言概论形式语言理论什么是语言？“为相当大地区的公众所懂得并使用的‘话’，以及组成这些‘话’的方法的统一体”“某一字母表上符号串（句子）的集合”定义仍需精确化1）字母表2）语法3）语义形式语言理论由数学方法研究自然语言(如英语)和人工语言(如程序语言)之语法的理论,主要讨论了语言和文法的数学机制以及语言和文法的分类应用领域(一)形式语言理论(二)语言和文法的直观概念(三)字母表、串、语言(四)文法和语言的形式定义(五)文法的类型(六)上下文无关文法及语法树(七)句型的分析(八)有关文法实用中的一些说明(一)形式

2、语言理论(二)语言和文法的直观概念(三)字母表、串、语言(四)文法和语言的形式定义(五)文法的类型(六)上下文无关文法及语法树(七)句型的分析(八)有关文法实用中的一些说明(一)形式语言理论(二)语言和文法的直观概念(三)字母表、串、语言(四)文法和语言的形式定义(五)文法的类型(六)上下文无关文法及语法树(七)句型的分析(八)有关文法实用中的一些说明(二)语言和文法的直观概念（引例）我们从“产生语言”的角度出发,讨论文法和语言的形式定义语言生成——指制定出有限条规则，借助它们产生的句子的集合英语语言为例。并设每个句子都

3、是“主-谓-宾”结构文法——见右。其中，每个用<>括起来的部分是所要定义语言中的一个语法实体（称为语法单位、语法结构、语法范畴、语法变量等）。“::=”是用于定义语法结构的符号，其含义（并读作）“定义为”。文法也称为产生式(Production)①<句子>::=<主语短语><动词短语>②<主语短语>::=the<名词>③<动词短语>::=<动词><宾语短语>④<宾语短语>::=<冠词><名词>⑤<名词>::=monkey⑥<名词>::=banana⑦<动词>::=eat⑧<动词>::=has⑨<冠词>::=the⑩<冠词

4、>::=a(二)语言和文法的直观概念（引例）推导(derivation)——从语言最大的一个语法实体（本例中是<句子>）开始，反复用语法规则中“::=”右侧的符号串取代其左侧符号，直到所得的符号串中不再含有可被替换语法实体。每次替换称为一步（直接）推导，并用符号“”表示。例如首先用规则①进行第一步推导，可得到<主语短语><动词短语>，即<句子><主语短语><动词短语>所得符号串<主语短语><动词短语>含有两个语法实体，可对其中任一个（例如对<动词短语>）进行新的推导<句子><主语短语><动词短语><主语短语><动

5、词><宾语短语>重复上述过程，可得到一个推导序列（见下页）。推导所用所得的符号串步规则1①<句子><主语短语><动词短语>2③<主语短语><动词><宾语短语>3②the<名词><动词><宾语短语>4④the<名词><动词><冠词><名词>5⑤themonkey<动词><冠词><名词>6⑦themonkeyeat<冠词><名词>7⑩themonkeyeata<名词>8⑥themonkeyeatabanana推导序列推导长度用语法规则进行推导从<句子>出发，经8步推导得到一个英语句子,则称前面的推导为长度为8

6、的推导若不关心推导的中间过程，可将从一符号串到另一符号串的推导用记号规则的简化表示在前面的语法规则定义中，有些语法范畴（如<名词>、<动词>）有若干条不同的规则来定义它，为简明起见，我们可以将它们写在同一个左部语法范畴下，将其定义值用符号“

7、”（读作‘或’）隔开。如<名词>、<动词>、<冠词>的定义规则可简记为<名词>::=monkey

8、banana<动词>::=eat

9、has<冠词>::=the

10、a推导所用所得的符号串步规则1①<句子><主语短语><动词短语>2③<主语短语><动词><宾语短语>3②the<名词>

11、<动词><宾语短语>4④the<名词><动词><冠词><名词>5⑤themonkey<动词><冠词><名词>6⑦themonkeyeat<冠词><名词>7⑩themonkeyeata<名词>8⑥themonkeyeatabanana练习：请推导thebananaeatamonkey推导序列语法规则及其产生的语言前面的语法规则可以产生16个不同的句子，由这16个句子组成的集合，就是该规则所定义（或所产生）的语言应指出，所产生的句子中，有些句子的含义是荒谬的（如thebananaeatamonkey和thebana

12、naeatthebanana等）。然而，若不考虑语义，则我们就必须承认它们是语法上合法的句子。(二)语言和文法的直观概念程序设计语言的定义语言是一个记号系统。汉语--符合汉语语法的句子的全体英语--符合英语语法的句子的全体程序设计语言--该语言的程序的全体程序设计语言由语法和语义定义：语法：定义每个程序构成的规则语义