中国石油大学,编译原理第03章、文法和语言.ppt

教学目标： 本章是编译原理课程的理论基础，要求掌握形式语言的基本术语和概念。 掌握文法和语言的定义，文法的二义性的判断方法及句型的分析方法。 熟练使用文法定义程序设计语言的单词和语法成分。 对形式语言的理论有一个初步认识。 1 第三章 文法和语言 2 本章目的 ——为语言的语法描述寻求工具 工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读） 形式工具——形式语言，抽象地定义为一个数学系统。 “形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。 3 本章知识点(内容) 引言和预备知识 文法和语言的形式定义 文法的类型 上下文无关文法及其语法树 上下文无关文法的句型分析 有关文法实用中的一些说明 4 3.1 文法的直观概念和语言概述 当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。 以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构。 5 “我是大学生”。是汉语的一个句子 〈句子〉∷=〈主语〉〈谓语〉 〈主语〉∷=〈代词〉｜〈名词〉 〈代词〉∷=我｜你｜他 〈名词〉∷=王明｜大学生｜工人｜英语 〈谓语〉∷=〈动词〉〈直接宾语〉 〈动词〉∷=是｜学习 〈直接宾语〉∷=〈代词〉｜〈名词〉 有了一组规则以后， 不断地用∷=的右边代替左边，就可以导出句子。 6 汉语描述规则 有了这组规则以后，可按如下方式导出句子： 先找∷=左端的带有句子的规则，并将它用∷=右端的符号串代替，于是表示成： 句子  主语 谓语 然后在得到的串主语 谓语中，选取主语或谓语 ，再用相应规则的∷=右端代替之。比如，选取了主语 ，并采用规则主语 ∷=代词 ，那么得到： 主语 谓语  代词 谓语 7 汉语描述规则导出过程 依此类推，句子“我是大学生”的全部导出过程是： 句子 主语谓语  代词谓语  我谓语  我动词直接宾语  我是直接宾语  我是名词  我是大学生 8 “我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。 这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。 这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。 9 符号和∷=符号 这里“”读作“导出”或“派生出”，含义是使用一条规则，代替左端的某个符号，产生右端的符号串。 而“::=”（通常又简记为“→”）读作“定义为”或“由…组成”，而每一条规则又称作是产生式或重写式。这样的一种描述形式就称作是BNF（Backus Normal Form，巴科斯范式）。 10 C语言中的赋值表达式 赋值表达式 → 左部=右部 左部 → 标识符 右部 → 表达式 表达式 → 表达式算符表达式 表达式 → 标识符|常数 标识符 → 字母(字母|数字)n 字母 → A|B |C |D |E |F |G |H |a |J |K |L |M |N |O |P |Q |R |S |T |U |V |W |X |Y |Z |a |b |c |d |e |f |g |h |a |j |k |l |m |n |o |p |q |r |s |t |u |v |w |x |y |z 数字 → 0 |1 |2 |3 |4 |5 |6 |7 |8 |9 算符 → + |- |* |/ 文法的BNF表示 11 语 言 概 述 语言是由句子组成的集合，是由一组符号所构成的集合。 汉语--所有符合汉语语法的句子的全体 英语--所有符合英语语法的句子的全体 程序设计语言--所有该语言的程序的全体 语法 Syntax 语言研究的三个方面 语义 Semantics 语用 Pragmatics 12 如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。 形式语言抽象地定义为一个数学系统。 “形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。 形式语言理论是对符号串集合的表示法、结构及其特性的研究。 是程序设计语言语法分析研究的基础。 13 3.2 有关定义和记号的回顾符号和符号串 符号：可以相互区别的记号（元素）。 字母表：符号（元素）的非空有穷集合（符号集）。 符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。 1.空符号串