[工学]编译原理及实现 第02章 文法和语言ppt.pptVIP

《编译原理基础》 第二章 文法和语言 第二章 文法和语言 为完成编译工作，需解决两个问题： 如何确切地描述和定义一种程序设计语言 如何识别和分析这种语言 汉语词类划分体系 提要系统的词类划分如下： 词可分实词和虚词两大类。 实词表示实在意义，能够作短语或句子的成分，一般能够独立成句。实词包括名词、动词、形容词、数词、量词、代词。 虚词一般不表示实在的意义，它们的基本用途是表示语法关系。虚词包括副词、介词、连词、助词、叹词和拟声词。 “我是大学生”是汉语的一个句子。 〈句子〉∷=〈主语〉〈谓语〉 〈主语〉∷=〈代词〉｜〈名词〉 〈代词〉∷= 我｜你｜他 〈名词〉∷= 王明｜大学生｜工人｜英语 〈谓语〉∷=〈动词〉〈直接宾语〉 〈动词〉∷= 是｜学习 〈直接宾语〉∷=〈代词〉｜〈名词〉 有了一组规则以后，按照如下方式用它们导出句子： 开始去找∷=左端的带有〈句子〉的规则并把它由∷=右端的符号串代替，这个动作表示成： 2.1 字母表和符号串 任何一种语言都是由该语言的基本符号所组成的符号串集合的子集。 2.1.1 字母表 2.1.3 符号串及其集合的运算 2.2 文法 2.2.1 文法形式定义 2.2.1 文法形式定义 〔例2－1〕文法形式定义 〔例2－2〕 2.2.2 文法的EBNF表示 2.3 推导 2.3.1 直接推导 2.3.1 直接推导 2.3.2 推导 2.3.3 规范推导 2.4 句型和句子 例子： 例子： 2.4 句型和句子 判断下列句型是否为规范句型 2.5 语言 〔例2－4〕 例2.4，已知文法G[Z]为： 1)Z→aZb 2)Z→ab 或写成 Z→ aZb| ab 求该文法确定的语言。 练习：已知文法，推导语言 〔例2－5〕 例：{abna|n≥1},构造其文法 练习：已知语言，构造文法 2.6 递归规则与递归文法 2.6 递归规则与递归文法 例： 2.7 短语、简单短语和句柄 2.8 语法树 语法树：描述一个句子的语法结构 用语法树求短语、简单短语和句柄的方法是： 1）每个句型都有一棵语法树； 2）每棵语法树的叶（从左到右）组成一句型； 3）每个子树 的叶（从左到右）组成一短语； 4）每个简单子树 的叶（从左到右）组成一简单短语； 5）最左简单子树 的叶（从左到右）组成一句柄。 2.9 子树与短语 句型“123”的语法树如右图所示。 短语：1、1、2、12、3、123、123 简单短语：1、2、3 句柄（最左简单短语）：1 2.10 由树构造推导过程 2.10 由树构造推导过程 2.11 文法的二义性 如果一个文法所定义的句子中有某个句子或句型，它存在两棵不同的语法树，那么这个句子或句型是二义性的，该文法是二义性文法。 例 2.10 IF语句文法如下： 语句∷= IF布尔表达式THEN语句 |IF布尔表达式THEN语句ELSE语句 |其它 说明该文法是二义性文法。 解：假设有一个IF语句嵌套的句型为：IF布尔表达式THEN IF布尔表达式THEN语句ELSE 语句 方法一：添加语法的非形式规定 方法二：改写文法 2.12 有关文法的实用限制 实用限制就是从实用的观点出发，对文法做一些必要的限制。首先，文法不能是二义性的，这是一种对文法的实用限制。另外，还有下面列出的一些限制条件： 1) 不能有U∷=U这样的有害规则。 2) 不能有多余规则：一是推导中始终用不到的规则。二是一旦使用某规则后无法推出终结符号的规则。 检查有害规则比较容易，而要检查多余规则，则要检查文法中每一条规则左部的每个非终结符号U是否满足下述两个条件： 1) U必须在某个句型中出现，即有：Z=*xUy 2) 必须能够从U推导出终结符号串，即U=+t，t∈Vt* 不满足这两个条件的规则就是多余规则。 2.13 文法和语言分类 例如, 文法G[S] : S→aSBE, S→aBE, BE→bE, aB→ab, bB→bb, bE→be, eE→ee 作业 第2章 习题1～10 句型“123”的推导过程如下： S =D = DN = D3 = DN3 = D23 = N23 = 123 D S D D N N 3 N 2 1 文法G[S]： S→D D→DN|N N→0|1|2|3|4|5|6|7|8|9 由语法树构造推导 2 自下而上地修剪子树的末端结点，直至把整棵树剪掉（留根），每剪一次对应一次归约。 从句型开始，自右向左地逐步进行归约，建立推导序列。 文法G[S]： S→D D→DN|N N→0|1|2|3|4|5|6|7|8|9 句型