《编译原理实践及应用》第2章文法基础.ppt

第二章 形式语言基本知识 本章要求 主要内容：符号串，文法的概念及分类，语言的定义过程 重点掌握：上下文无关文法、推导、句型、句子、语言，语法树、二义性文法、文法的语言生成过程 以C和PASCAL为例复习高级语言 1 语言的基本字符集的定义(字母, 数字, 界符) 2 单词集的定义 3 数据类型的定义 4 表达式的定义 5 语句的定义 6 程序定义 PASCAL和C的主要区别 2.1 程序语言定义的基本概念 1. 字母表：是元素的有穷非空集合Σ 2. 符号：字母表中的每个元素，因此字母表也称为符号集。 不同的语言可以有不同的字母表，例如英文的字母表中26个字母、数字及标点符号等。 PASCAL语言的字母表是由字母、数字、若干专用符号组成。 符号是该语言能识别的符号，字母表是该语言能识别的所有符号的全体（字符集）。 基本概念(续) 3. 符号串: 由字母表中的符号组成的任何有穷序列称为符号串，例如00 11 10 是字母表? =｛0，1｝上的符号串. 字母表A=｛a,b,c｝上的一些符号串有：a,b,c,ab,aaca等。 在符号串中，符号的顺序是很重要的，符号串ab就不同于ba,abca和aabc也不同。 符号串STR表示“由符号S、T和R，并按此顺序组成. 基本概念(续) 4. 符号串的运算 a. 字符串的连接： 字符串αβ称为字符串α和β的连接 符号串的长度 :符号串中符号的个数，例如: 某符号串中有m个符号,则称其长度为m，表示为｜x｜=m，如001110的长度是6。 空符号串: 即不包含任何符号的符号串，用ε表示，其长度为0， 即｜ε｜=0。 用Σ *表示Σ上所有的符号串的全体(长度为0，1，2，…)。 集合的运算 b. Σ*的子集U、V的积 ： UV = {αβ | α∈U β∈V }长度相加 即: 集合UV中的符号串是由U和V的符号串连接而成。 U = {aa,bb} V={00,11} 则UV=? c. 集合的方幂：n个相同符号连接 Vn =VVVV …. V 规定V0 = {ε} d. 闭包、正闭包的运算 2.2 上下文无关文法及其语言 文法是描述语言的语法结构的形式规则。是一种工具，它可用于严格定义句子的结构；用有穷的规则刻划无穷的集合 文法是被用来精确而无歧义地描述语言的句子的构成方式. 文法描述语言的时候不考虑语言的含义。 引 例 例1：有如下规则 句子?主语谓语 (?表示由…组成) 主语?代词|名词 代词?我 名词?大学生 谓语?动词直接宾语 动词?是 直接宾语?代词|名词 现要求根据如上规则得出句子：我是大学生 句子=主语谓语?= 代词谓语 =代词动词直接宾语=代词动词名词 =我是大学生 句子“我是大学生”也可以如下图示分析 在有规则的情况下，每一次用上述规则的右边去替换左边，得到“我是大学生”是符合上述规则的句子 上下文无关文法的形式定义 由四部分组成： 终结符号：是组成该语言的最基本的符号，是不可再分的基本符号,如保留字、标识符等。 非终结符号：规则中用尖括号括起来的符号，表示一些语法成分，可以推导出其他的语法成分,表示一定符号串的集合，是一个类，如表达式。 开始符号：规则中的一个特殊的非终结符号，语言中的句子都从它开始推导,如程序、句子 产生式：定义语法成分的规则，其中： 文法的形式定义(续) 一个文法G抽象地表示为四元组? G=（Vn,Vt,P,S）? 其中Vn表示非终结符号 Vt表示终结符号，Vn∪Vt=Ｖ(字母表)，Vn∩Vt=φ S是开始符号， P是产生式，形如：α?β(α∈V+且至少含有一个非终结符号，β∈V*) 上例中： G=（Vn,Vt,P,句子） Vn=（句子，主语，谓语，代词，动词，名词，直接宾语） Vt= (我，是，大学生) P = 产生式的形式为：A? α 上下文无关文法所定义的语法成分独立于它可能出现的环境，即不考虑上下文。 算术表达式的文法定义 变量是表达式 表达式 + 表达式是表达式 表达式 * 表达式是表达式 (表达式) 是 表达式 上下文无关文法产生句子的方法:从文法的开始符号出发,反复连续使用产生式,对左边的非终结符进行替换和展开 例：表达式定义规则 推导: 连续使用产生式右部去替换左部某个非终结符的过程,得到的连续序列称为一个推导。 直接推导：又称一步推导(用 符号=表示),就是用某条规则的右部去替换该规则的左部 几个概念的形式定义 直接推导: 如果α?β是文法 G=（Vn,Vt,P,S）的产生式，γ和δ是Ｖ*中的任意符号，若有符号串v,w满足：v=γαδ,w=γβδ,则说v直接产生w，(w是v的直接推导)记作：