编译原理 前后文无关文法和语言.ppt

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

1、第二章文法和语言在20世纪50年代，N.Chomsky首先对语言的描述问题进行了探讨。他提出了一种用来描述语言的数学系统，并以此定义了四类性质不同的语言，称为语言（文法）的Chomsky分类。人们把用一组数学符号和规则来描述语言的方式称为形式描述，把所用的数学符号和规则称为形式语言。目前，形式语言与自动机理论已成为计算机科学中的一个重要分支。本章将初步介绍形式语言中的某些基本概念和知识，重点是与编译技术密切相关的一些术语和概念，诸如文法、语言、句子、句型、短语、句柄以及句型分析等。本章内容2.1语言的概述2.2文法和语言的定义2.1语言的

2、概述什么是语言自然语言(NaturalLanguage)是人与人的通讯工具语义(Semantics):环境、背景知识、语气、二义性——难以形式化计算机语言(ComputerLanguage)计算机系统间、人机间通讯工具严格的语法(Grammar)、语义(Semantics)——易于形式化：严格语言是用来交换信息的工具——功能性描述2.1语言概述语言的描述方法——现状自然语言：自然、方便-非形式化数学语言（符号）：严格、准确-形式化形式化描述高度的抽象，严格的理论基础和方便的计算机表示。2.1语言概述语言——形式化的内容提取单词(Token

3、)：满足一定规则字符(Character)串句子(Sentence)：满足一定规则单词序列语言(Language)：满足一定条件的句子集合语言是字和组合字的规则——结构性描述例：一译开天第课今始编节上今天开始上第一节编译课程序设计语言——形式化的内容提取程序设计语言(ProgrammingLanguage)：组成程序的所有语句的集合程序(Program)：满足语法规则的语句序列语句(Sentence)：满足语法规则的单词序列单词(Token)：满足词法规则的字符串例变量=表达式if条件then语句while条件do语句call过程名(参数

4、表)2.1语言概述语言描述形式——文法语法——语句语句的组成规则描述方法：BNF（巴科斯范式：BackusNormalForm）范式、语法(描述)图词法——单词单词的组成规则描述方法：BNF范式、正规式2.1语言概述遗憾的是，对于自然语言来说，目前尚无能够完全刻划一语言全部句子的结构的方法。然而，对大多数程序设计语言来说，此问题已被解决。1960年，P.Naur&J.Backus（巴科斯--瑙尔）首先用BNF（Backus-Naur-Formal（范式））对ALGOL语言进行了描述。应指出，BNF成功地解决了程序设计语言的语法描述问题，但

5、描述其语义，还必须借助自然语言。复习：巴科斯范式（BNF--BackusNormalForm）通常，可用如下方式表示或定义一种语言：（1）若语言的句子有限时，可用枚举法。例如，只含两个句子的语言：{“Iamateacher”,“Youarestudents”};（2）制定有限条规则，用于产生所要描述的语言的全部句子（可无限多），这些规则构成了该语言的文法。（3）建立一种装置（算法或过程），它以某字母表上的符号串为输入，判别该符号串是否为所描述语言的句子。此装置称为自动机。巴科斯范式（BNF）例子：Thebigelephantatethe

6、peanut.(大象吃花生）Thelittleboyranquickly.(小男孩跑得快）Themanhasadog.(这人有一条狗）以上都是符合英语语法规则的句子，即它们是在英语语法规则中成立的句子。如何描述一个给定的句子在给定规则下是否成立呢？①〈句子〉∷=〈主语〉〈谓语〉②〈主语〉∷=〈冠词〉〈形容词〉〈名词〉③〈冠词〉∷=the④〈形容词〉∷=big⑤〈谓语〉∷=〈动词〉〈宾语〉⑥〈动词〉∷=ate⑦〈宾语〉∷=〈冠词〉〈名词〉⑧〈名词〉∷=elephant

7、peanut我们把这种描述语法规则方法称巴科斯范式，也称巴科斯

8、--瑙尔范式(BackusNormalForm)，简称BNF。那么上面叙述<句子>的语法规则可写为：步骤推导所用规则1<句子><主语>〈谓语〉①2<冠词>〈形容词〉〈名词〉〈谓语〉②3the〈形容词〉〈名词〉〈谓语〉③4thebig〈名词〉〈谓语〉④5thebigelephant〈谓语〉⑧6thebigelephant〈动词〉<宾语>⑤7thebigelephantate<宾语>⑥8thebigelephantate〈冠词〉<名词>⑦9thebigelephantatethe<名词>③10theb

9、igelephantatethepeanut⑧可见句子thebigelephantatethepeanut成立。当然我们还可以推导出其它的句子，如thebigpeanutatetheeleph