编译原理：文法和语言.ppt

第二章 文法和语言 2.1 文法的直观表示 2.2 符号和符号串 2.3 文法和语言的形式定义 2.4文法的类型 2.5 上下文无关文法及语法树 2.6 句型分析 2.7 文法的实用限制 第2章 文法和语言 【学习目标】 本章是为语言的语法描述寻求工具 ◇ 掌握对程序设计语言给出精确、无二义（严谨、易读）的语法描述的手段之一——文法。 ◇ 对形式语言的理论有一个初步基础 ◇ 根据文法的特点指导语法分析过程 2.1 文法的直观表示 文法：阐明语法的一个工具，也可以说是以有穷的集合刻画无穷的集合的一个工具。 语言：程序设计语言。 一、语言概述 语言是由符合语法的句子组成的集合。 汉语--所有符合汉语语法的句子的全体 英语--所有符合英语语法的句子的全体 程序设计语言--所有该语言的程序的全体 每个句子构成的规律——语法 研究语言 每个句子的含义 ——语义 每个句子和使用者的关系——语用 形式语言：只考虑语法而不考虑语义的符号语言。 每种语言具有两个可识别的特性 语言的形式 与该形式相关联的意义 “形式”指语言的所有规则，描述出现什么符号串 语言可以看成在一个基本符号集上定义的，按一定规则构成的基本符号串组成的所有集合。 形式语言理论是对符号串集合的表示法、结构及其特性的研究，是程序设计语言语法分析研究的基础。 表达语言时，一般无法穷尽语言的所有句子，常用规则加以描述 例：汉语句子的构成规则：　　〈句子〉∷=〈主语〉〈谓语〉　　〈主语〉∷=〈代词〉|〈名词〉　　〈代词〉∷= 我 | 你 | 他　　〈名词〉∷= 王明 | 大学生 | 工人 | 英语　　〈谓语〉∷=〈动词〉〈直接宾语〉　　〈动词〉∷= 是 | 学习　　〈直接宾语〉∷=〈代词〉|〈名词〉 推导：“我是大学生” 是汉语的一个句子〈句子〉? 〈主语〉 〈谓语〉 ? 〈代词〉〈谓语〉 ?我〈谓语〉 ?我〈动词〉〈直接宾语〉 ? 我是〈直接宾语〉 ?我是〈名词〉 ?我是大学生 2.2 符号与符号串 一、相关概念 程序设计语言是由程序构成的集合，程序是由基本符号按照一定的规则构成的集合。 1. 符号、字母表和符号串 基本符号：可以相互区别的基本元素，如字母，数字，标点符号。 字母表：基本符号的非空有穷集合，常用Σ表示。例： Σ ={0,1}， Σ={a, b, c, … , x,y, z} 符号串：由字母表中的符号构成的任何有穷序列称为符号串。符号串中的符号是有顺序的。 符号串s的头（前缀）和尾（后缀） ： 如果s=xy是一符号串，那么x是s的头，y是s的尾。若x是非空，则y是固有尾；若y非空，则x是固有头。 前缀：移走符号串s尾部的零个或多个符号得到的串。 如：设s=abc,那么s的前缀是ε，a，ab，abc 后缀：移走符号串s头部的零个或多个符号得到的串。 如：s =abc的后缀是ε，c，bc，abc，s的固有尾是ε，c，bc。 符号串s的子串： 从s中删去任何前缀或后缀得到的串. 如:bc是符号串abc的一个子串. 对符号串s， s和ε两者都是符号串s的前缀、后缀和子串。 符号串s的真前缀，真后缀，真子串： 任何非空符号串 x，是s的前缀，后缀或子串，并且 s ? x 2.符号串的运算 (1)符号串相等： 符号串x，y，如果两者诸符号依次相等，则两符号串相等。 (2)符号串的长度：符号串中包含符号的个数。 |abc|=3；| ? |=0； (3)符号串的连结： x=abc，y=def 则xy=abcdef；yx=defabc； xy yx ? x=x ? =x； (4)符号串集合的乘积： 设A、B为两个符号串集合，其乘积为AB={xy|x ?A，y?B}； 例：A={aa，bb}，B={cc，dd}，则 AB={aacc，aadd，bbcc，bbdd} {? }A=A {? }=A； (5)空集： 不含任何元素的集合称为空集。记为?； 对任何集合A：A ?= ?A= ?; 注意： ?? ? (6)符号串的方幂： x是字母表上的符号串，则x的幂运算为： x0= ? ; x1= x; x2= xx;… xn= xn-1x=x xn-1 (n0) xn表示n个x相连结。 eg：x=ok；则 x0= ?