编译原理ppt课件CHAPTER2(GrammarandLanguage).ppt

Chapter2Grammar and Language一教学目的一教学目的 掌握文法、语法树、推导、归约、句子、语言、规范推导与归 约、短语、简单短语、句柄、二义性定义，了解文法的分析过程、文法实用限制、语言分类等。二教学重点和难点二教学重点和难点重点掌握：1串和语言的概念。2文法和语言的定义。3文法和语言的分类。4分析树与句型。难点：1文法和语言的分类。2分析树与句型。2/17/20231Chapter2Grammar and Language 三教学内容三教学内容n串和语言（串和语言（Strings and Languages）n文法和语言的定义文法和语言的定义 （Definitions of Grammar and Language）n文法和语言的分类文法和语言的分类 （Classification of Grammar and Language）n分析树与句型分析树与句型 （Parse Tree and Sentential form）2/17/202322.1 2.1 串和语言串和语言n 字母表（字母表（alphabet）：）：n字母表是符号（symbols）的非空有穷集合，用表示n符号：可以相互区别的记号（元素）n不同的语言有不同的字母表n汉语汉字n英语26个英文字母2/17/202332.1 2.1 串和语言串和语言n符号串（符号串（String）：）：n符号串是由字母表中的符号所组成的有穷序列n在语言理论中，符号串又称为:句子（句子（sentence）、字（字（word）n例如：=a,b a,b,aa,ab,aabba都是上的符号串n是任何上的符号串2/17/202342.1 2.1 串和语言串和语言n符号串的长度n符号串中包含符号的个数n符号串 s 的长度记为|s|n例，对于字母表a,b,c，aab 是其上的一个符号串，|aab|=3n注意：空符号串，|=02/17/202352.1 2.1 串和语言串和语言n符号串的前缀（prefix）、后缀（suffix）、子串（substring）n后缀：删去符号串 s 头部的零个或多于零个符号得到的符号串n例如：nana是符号串banana的一个后缀n前缀：移走符号串 s 尾部的零个或多于零个符号得到的符号串n例如：b是符号串banana的一个前缀2/17/202362.1 2.1 串和语言串和语言n符号串的真（proper）前缀、真后缀和真子串非空n子串：从 s 中删去一个前缀和一个后缀得到的符号串n例如：ana是符号串banana的一个子串n*对于每个符号串s，s和两者都是符号串 s的前缀，后缀和子串2/17/202372.1 2.1 串和语言串和语言n 语言（语言（Language）：）：n某个字母表上的符号串的集合集合n例:汉语所有符合汉语语法的句子构成的集合 PASCAL语言所有合法的PASCAL程序构成的集合n注意：空集、和的不同2/17/202382.1 2.1 串和语言串和语言n符号串的运算：n连接（concatenation）：符号串x、y的连接，是把 y 的符号写在 x 的符号之后得到的符号串 xyn如 x=ab,y=cd 则 xy=abcd n注：=n方幂（exponentiation）：符号串自身连接n次得到的符号串nn 定义为 n个n1=,2=，注：0=2/17/202392.1 2.1 串和语言串和语言n语言的运算（operations on languages）：n语言是符号串的集合，集合的运算有并、交、差等n并运算 等同于集合的并运算2/17/2023102.1 2.1 串和语言串和语言n连接（乘积）n两个符号串集合 A 和 B 的乘积定义为：AB=xy|x A 且 y B n例如：集合A=ab,cde B=0,1 则 AB=ab1,ab0,cde0,cde1 nL=L=L nLLL=Ln L0=2/17/2023112.1 2.1 串和语言串和语言n*闭包（Kleene closure）nL*=L0L1L2L3 n+闭包（Positive closure）nL+=L1L2L3nL*=L+2/17/2023122.1 2.1 串和语言串和语言n注:后面通常是考虑字母表的*闭包和+闭包n例：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,2/17/2023132.1 2.1 串和语言串和语言n综合性的例子：P93 example 3.2n L=A,B,C,Z,a,b,c,zn D=0,1,9n把 L 和 D 两个字母表看作长度为1的符号串集合，即语言1.L D 2.LD 3.L4 4.L*5.L(L D)*6.D+2/17/2023142.2 2.2 文法和语言的定义文法和语言的定义n如何来描述一种语言？如何来描述一种语言？n如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示n如果语言是无穷的，找出语言的有穷表示。2/17/2023152.2 2.2 文法和语言的定义文法和语言的定义n语言的有穷表示有两个途经：n生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造。n识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，（要么永远继续下去。）n文法即是以生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造.2/17/2023162.2 2.2 文法和语言的定义文法和语言的定义n文法文法 G 定义为四元组（定义为四元组（VT，VN，S，P）：）：nVT：终结符（terminals）集，其中的元素一般用小写字母或数字表示（a,b,c0,1.），代表语言中不可再语言中不可再分的基本符号分的基本符号，如汉语中的汉字、PASCAL语言中的基本字nVN：非终结符（nonterminals）集，其中的元素一般用大写字母表示（A,B,C），或者用尖括号括起，代表语法单位语法单位，如汉语中的语句、段落，PASCAL语言中的语句、表达式、子程序等2/17/2023172.2 2.2 文法和语言的定义文法和语言的定义nS 是一个特殊的非终结符号，称为开始符号（start symbol）nS 至少要在一条产生式中作为左部出现nP是一个产生式（production）的集合n产生式（重写规则、生成式），是形如或=的（，）有序对，且V+，V*其中 V=（VTVN）n称为产生式的左部，不能为空n称为产生式的右部，可以为空（如：A ）2/17/2023182.2 2.2 文法和语言的定义文法和语言的定义例1：文法 G=（VT，VN，S，P）VN=S VT=0,1 P=S0S1,S01 n可以只写出产生式，通过产生式可以得到文法的其它部分n左部相同的产生式可以写在一起，如:S 0S1|012/17/2023192.2 2.2 文法和语言的定义文法和语言的定义例2：文法 G=（VT，VN，S，P）VN=，VT=a,b,c,x,y,z,0,1,9P=a,z 0,9 S=2/17/2023202.2 2.2 文法和语言的定义文法和语言的定义n推导（推导（derivation）与归约（）与归约（reduction）：）：n直接推导与直接归约n如果 A 是 G 的一条产生式，则称用代替A为一步直接推导直接推导，记为A=；称用A代替为一步直接归约直接归约，记为 0S1=00S11=000111，长度为3 记为：S 000111 S S2/17/2023222.2 2.2 文法和语言的定义文法和语言的定义n最左推导与最右推导n=是一步推导，（VTVN）*n最左推导(=lm)对 中的最左非终结符进行展开n最右推导(=rm)对 中的最右非终结符进行展开2/17/2023232.2 2.2 文法和语言的定义文法和语言的定义n例子：表达式文法 E E+T E T T T*F T F F （E）F a最左推导：E=lmT=lmT*F=lmF*F=lma*F=lma*a*最右推导又称为规范推导最右推导：E=rmT=rmT*F=rmT*a=rmF*a=rma*a2/17/2023242.2 2.2 文法和语言的定义文法和语言的定义n最右归约与最左归约n最左推导的逆过程是最右归约，即对最右边的可归约串进行归约 a*a=a*F=F*F=T*F=T=En最右推导的逆过程是最左归约，即对最左边的可归约串进行归约 a*a=F*a=T*a=T*F=T T=T*F=F*F=a*F=a*a 中，句型有：E、T、T*F、F*F、a*F、a*a句子是：a*a2/17/2023272.2 2.2 文法和语言的定义文法和语言的定义n语言的形式定义：语言的形式定义：n文法 G 推导出的所有句子组成的集合，称为语言语言，记为 L（G）nL（G）=|S ，VT*2/17/2023282.2 2.2 文法和语言的定义文法和语言的定义n例子：nG1：S A A 0A1 A 01 是由一个或多个 0 开头，后跟同样数目的 1 的符号串构成的集合（语言），可记为：L(G)=0n1n|n12/17/2023292.2 2.2 文法和语言的定义文法和语言的定义nG2：E idE E+EE E*EE （E）产生的是表达式的集合2/17/2023302.2 2.2 文法和语言的定义文法和语言的定义nG3：E E+T E T T T*F T F F （E）F id产生的也是表达式的集合2/17/2023312.2 2.2 文法和语言的定义文法和语言的定义n一个文法对应一个语言，但一个语言可能有若干个文法产生它，这若干个文法是等价的，称为 等价（等价（equivalent）文法）文法n例 G2 与 G32/17/2023322.3 2.3 文法和语言的分类文法和语言的分类n乔姆斯基（乔姆斯基（Chomsky）在）在1956年提出形式语言年提出形式语言理论，他将形式文法分为四类理论，他将形式文法分为四类(0,1,2,3)，对应四，对应四类形式语言类形式语言(0,1,2,3)n分类的方法是对文法的产生式进行不同的限制分类的方法是对文法的产生式进行不同的限制2/17/2023332.3 2.3 文法和语言的分类文法和语言的分类n0型文法|0，即 （）n1型（上下文有关）文法|（）n2型（上下文无关）文法 A VN，（VTVN）*（A）n3型（正规）文法nAa 或 AaB（右线性）nAa 或 ABa（左线性）2/17/2023342.3 2.3 文法和语言的分类文法和语言的分类例：例：1 1型（上下文有关）文法型（上下文有关）文法 文法文法G G：SCDSCD AbbA AbbACaCACaCABaaBBaaBCbCBCbCBBbbBBbbBADaDADaDCCBDbDBDbDDDAabDAabDL(G)=ww|wa,bL(G)=ww|wa,b*2/17/2023352.3 2.3 文法和语言的分类文法和语言的分类例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法G G1 1：SaB|bASaB|bAAa|aS|bAAAa|aS|bAABb|bS|aBBBb|bS|aBB 文法文法G G2 2：S0A|1B|0S0A|1B|0A0A|1B|0SA0A|1B|0SB1B|1|0B1B|1|02/17/2023362.3 2.3 文法和语言的分类文法和语言的分类例：例：3 3型（正规）文法型（正规）文法 文法文法G G：S0A|1B|0S0A|1B|0A0A|1B|0SA0A|1B|0SB1B|1|0B1B|1|02/17/2023372.3 2.3 文法和语言的分类文法和语言的分类n0型文法产生的语言称为0型语言n1型文法或上下文有关文法（CSG）产生的语言称为1型语言或上下文有关语言（CSL）n2型文法或上下文无关文法（CFL）产生的语言称为2型语言或上下文无关语言（CF L）n3型文法或正则（正规）文法（RG）产生的语言称为3型语言正则（正规）语言（RL）2/17/2023382.3 2.3 文法和语言的分类文法和语言的分类n四种文法（语言）之间的逐级“包含”关系2型文法型文法（语言）（语言）1型文法型文法（语言）（语言）0型文法（语言）型文法（语言）3型文法（语言）型文法（语言）2/17/2023392.3 2.3 文法和语言的分类文法和语言的分类n识别各类语言的数学模型（自动机）识别各类语言的数学模型（自动机）n图灵机（0型语言）n有界图灵机、线性有界自动机（1型语言）n下推自动机（2型语言）n有限自动机（3型语言）2/17/2023402.3 2.3 文法和语言的分类文法和语言的分类n上下文无关文法能够描述现今程序设计语言上下文无关文法能够描述现今程序设计语言的大部分语法结构的大部分语法结构n算术表达式n赋值语句n条件语句等2/17/2023412.3 2.3 文法和语言的分类文法和语言的分类n表达式文法：G=(+,*,i,(,),E,E,P)P:E idE E+EE E*EE (E)E表示算术表达式，id表示程序的“变量”，该文法定义了由变量，+，*，(和)组成的算术表达式的语法结构，即：变量是算术表达式；若E1和E2是算术表达式，则E1+E2，E1*E2和(E1)也是算术表达式。2/17/2023422.3 2.3 文法和语言的分类文法和语言的分类n描述一种简单赋值语句的产生式：赋值语句 i=En描述条件语句的产生式：条件语句 if条件then语句 if条件then语句else语句2/17/2023432.4 2.4 分析树与句型分析树与句型n分析树分析树是描述上下文无关文法句型推导的一种直观方法，也称为推导树2/17/2023442.4 2.4 分析树与句型分析树与句型n为句型推导构造分析树n例子：E=TnE E+T E TT T*FT F F （E）F a=T*F=F*F=a*FTT*FFaaE=a*a2/17/2023452.4 2.4 分析树与句型分析树与句型n分析树的特性：分析树的特性：n根标识为开始符号n内部结点标识为非终结符号n每一内部结点及其子结点对应一条产生式，该结点是产生式的左部，子结点从左至右排列构成产生式的右部n叶结点从左至右排列构成句型TT*FFaaE2/17/2023462.4 2.4 分析树与句型分析树与句型n分析树与句型推导的关系分析树与句型推导的关系n一次推导（不是一个句型）对应一棵分析树n一棵分析树可能对应若干个推导n例如下面的推导对应的也是上面那棵分析树 E=T=T*F=T*a=F*a=a*aTT*FFaaE2/17/2023472.4 2.4 分析树与句型分析树与句型n说明分析树没有严格反映推导的顺序n但是一棵分析树对应一个最左推导，也只能对应一个最右推导TT*FFaaE2/17/2023482.4 2.4 分析树与句型分析树与句型n句型的短语、直接短语和句柄（句型的短语、直接短语和句柄（handle）n如果S A和A ，则称是关于A的，句型的一个短语短语（子树的叶子）SA2/17/2023492.4 2.4 分析树与句型分析树与句型例：句型 F*a 的短语TT*FFaEF*a、F、a2/17/2023502.4 2.4 分析树与句型分析树与句型n如果S A和 A=，则称是关于 A的，句型的一个直接短语直接短语（只有父子两代的子树的叶子）SA2/17/2023512.4 2.4 分析树与句型分析树与句型例：句型 F*a 的直接短语TT*FFaEF、a2/17/2023522.4 2.4 分析树与句型分析树与句型n最左直接短语称为句柄句柄n最左性体现在分析树和句型中SA2/17/2023532.4 2.4 分析树与句型分析树与句型例：句型 F*a 的句柄TT*FFaEF2/17/2023542.4 2.4 分析树与句型分析树与句型n句型的素短语、最左素短语1、是关于A的，句型的一个短语2、至少含有一个终结符3、除自身外不含更小的带终结符的短语称是关于A的，句型的一个素短语素短语n句型最左边的素短语称为最左素短语最左素短语n问题:素短语是否总是在直接短语中?(否.反例:T+T+F)2/17/2023552.4 2.4 分析树与句型分析树与句型例：EE+TE+TFTT*Fan句型：T+T*F+an短语：T+T*F+a、T+T*F、T*F、T（左边）、an直接短语：T、T*F、an句柄：Tn素短语：T*F、an最左素短语：T*F2/17/2023562.4 2.4 分析树与句型分析树与句型n句子、文法和语言的二义性（句子、文法和语言的二义性（Ambiguity）n如果一个文法的句子有两棵或两棵以上的分析树，称此句子是二义句子是二义的n最左（右）推导与分析树一一对应，句子二义说明它有两个或以上最左（右）推导2/17/2023572.4 2.4 分析树与句型分析树与句型nE=E+E=id+E=id+E*E=id+id*E=id+id*idnE=E*E=E+E*E=id+E*E=id+id*E=id+id*idEE+Eid*EEididEE*Eid+EEidid例：nE id E E+E E E*E E （E）2/17/2023582.4 2.4 分析树与句型分析树与句型n如果一个文法有一个句子是二义的，此文法称为二义文法二义文法nE id E E+E E E*E E （E）2/17/2023592.4 2.4 分析树与句型分析树与句型n如果一个语言的所有文法都是二义的，称此语言是二义的语言是二义的n希望文法是无二义的，因为希望对于每一个句子进行唯一确定的分析2/17/2023602/17/202361