《编译概述》PPT课件.ppt
2023/7/31,1,Chapter2Grammar and Language,串和语言（Strings and Languages）文法和语言的定义（Definitions of Grammar and Language）文法和语言的分类（Classification of Grammar and Language）分析树与句型（Parse Tree and Sentential form）,2023/7/31,2,2.1 串和语言,字母表（alphabet）：字母表是符号（symbols）的非空有穷集合，用表示符号：可以相互区别的记号（元素）,不同的语言有不同的字母表汉语汉字英语26个英文字母,2023/7/31,3,2.1 串和语言,符号串（String）：符号串是由字母表中的符号所组成的有穷序列,在语言理论中，符号串又称为:句子（sentence）、字（word）,例如：=a,b a,b,aa,ab,aabba都是上的符号串是任何上的符号串,2023/7/31,4,2.1 串和语言,符号串的长度符号串中包含符号的个数符号串 s 的长度记为|s|,例，对于字母表a,b,c，aab 是其上的一个符号串，|aab|=3注意：空符号串，|=0,2023/7/31,5,2.1 串和语言,符号串的前缀（prefix）、后缀（suffix）、子串（substring）,后缀：删去符号串 s 头部的零个或多于零个符号得到的符号串例如：nana是符号串banana的一个后缀,前缀：移走符号串 s 尾部的零个或多于零个符号得到的符号串例如：b是符号串banana的一个前缀,2023/7/31,6,2.1 串和语言,符号串的真（proper）前缀、真后缀和真子串非空,子串：从 s 中删去一个前缀和一个后缀得到的符号串例如：ana是符号串banana的一个子串*对于每个符号串s，s和两者都是符号串 s的前缀，后缀和子串,2023/7/31,7,2.1 串和语言,语言（Language）：某个字母表上的符号串的集合,例:汉语所有符合汉语语法的句子构成的集合 PASCAL语言所有合法的PASCAL程序构成的集合,注意：空集、和的不同,2023/7/31,8,2.1 串和语言,符号串的运算：连接（concatenation）：符号串x、y的连接，是把 y 的符号写在 x 的符号之后得到的符号串 xy,如 x=ab,y=cd 则 xy=abcd 注：=,方幂（exponentiation）：符号串自身连接n次得到的符号串,n 定义为 n个1=,2=，注：0=,2023/7/31,9,2.1 串和语言,语言的运算（operations on languages）：,语言是符号串的集合，集合的运算有并、交、差等,并运算 等同于集合的并运算,2023/7/31,10,2.1 串和语言,连接（乘积）两个符号串集合 A 和 B 的乘积定义为：AB=xy|x A 且 y B,例如：集合A=ab,cde B=0,1 则 AB=ab1,ab0,cde0,cde1,L=L=L LLL=Ln L0=,2023/7/31,11,2.1 串和语言,*闭包（Kleene closure）L*=L0L1L2L3,+闭包（Positive closure）L+=L1L2L3L*=L+,2023/7/31,12,2.1 串和语言,注:后面通常是考虑字母表的*闭包和+闭包例：=a,b*=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,2023/7/31,13,2.1 串和语言,综合性的例子：P93 example 3.2 L=A,B,C,Z,a,b,c,z D=0,1,9,把 L 和 D 两个字母表看作长度为1的符号串集合，即语言,1.L D 2.LD 3.L4 4.L*5.L(L D)*6.D+,2023/7/31,14,2.2 文法和语言的定义,如何来描述一种语言？,如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示,如果语言是无穷的，找出语言的有穷表示。,2023/7/31,15,2.2 文法和语言的定义,语言的有穷表示有两个途经：生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造。,识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，（要么永远继续下去。）,文法即是以生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造.,2023/7/31,16,2.2 文法和语言的定义,文法 G 定义为四元组（VT，VN，S，P）：,VT：终结符（terminals）集，其中的元素一般用小写字母或数字表示（a,b,c0,1.），代表语言中不可再分的基本符号，如汉语中的汉字、PASCAL语言中的基本字,VN：非终结符（nonterminals）集，其中的元素一般用大写字母表示（A,B,C），或者用尖括号括起，代表语法单位，如汉语中的语句、段落，PASCAL语言中的语句、表达式、子程序等,2023/7/31,17,2.2 文法和语言的定义,S 是一个特殊的非终结符号，称为开始符号（start symbol）S 至少要在一条产生式中作为左部出现,P是一个产生式（production）的集合产生式（重写规则、生成式），是形如或=的（，）有序对，且V+，V*其中 V=（VTVN）称为产生式的左部，不能为空称为产生式的右部，可以为空（如：A）,2023/7/31,18,2.2 文法和语言的定义,例1：文法 G=（VT，VN，S，P）VN=S VT=0,1 P=S0S1,S01,可以只写出产生式，通过产生式可以得到文法的其它部分,左部相同的产生式可以写在一起，如:S 0S1|01,2023/7/31,19,2.2 文法和语言的定义,例2：文法 G=（VT，VN，S，P）VN=，VT=a,b,c,x,y,z,0,1,9P=a,z 0,9 S=,2023/7/31,20,2.2 文法和语言的定义,推导（derivation）与归约（reduction）：,直接推导与直接归约如果 A 是 G 的一条产生式，则称用代替A为一步直接推导，记为A=；称用A代替为一步直接归约，记为=A,推导是用产生式的右部代替左部，归约是用产生式的左部代替右部，归约是推导的逆过程,2023/7/31,21,2.2 文法和语言的定义,推导的长度直接推导的次数，长度大于等于1的推导，长度大于等于0的推导,推导的例子：S=0S1=00S11=000111，长度为3 记为：S 000111 S S,2023/7/31,22,2.2 文法和语言的定义,最左推导与最右推导=是一步推导，（VTVN）*最左推导(=lm)对 中的最左非终结符进行展开最右推导(=rm)对 中的最右非终结符进行展开,2023/7/31,23,2.2 文法和语言的定义,例子：表达式文法 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*a,2023/7/31,24,2.2 文法和语言的定义,最右归约与最左归约最左推导的逆过程是最右归约，即对最右边的可归约串进行归约 a*a=a*F=F*F=T*F=T=E,最右推导的逆过程是最左归约，即对最左边的可归约串进行归约 a*a=F*a=T*a=T*F=T=E,*最左归约称为规范归约,2023/7/31,25,2.2 文法和语言的定义,句型（sentential form）与句子（sentence）：,句型：从文法的开始符号出发进行零步或多于零步的推导得到的文法符号串S,句型可以既包含终结符号又包含非终结符号，只包含终结符号的句型称为句子,句子是一种特殊的句型,2023/7/31,26,2.2 文法和语言的定义,例：在推导E=T=T*F=F*F=a*F=a*a 中，,句型有：E、T、T*F、F*F、a*F、a*a,句子是：a*a,2023/7/31,27,2.2 文法和语言的定义,语言的形式定义：,文法 G 推导出的所有句子组成的集合，称为语言，记为 L（G）,L（G）=|S，VT*,2023/7/31,28,2.2 文法和语言的定义,例子：G1：S A A 0A1 A 01,是由一个或多个 0 开头，后跟同样数目的 1 的符号串构成的集合（语言），,可记为：L(G)=0n1n|n1,2023/7/31,29,2.2 文法和语言的定义,G2：E idE E+EE E*EE（E）,产生的是表达式的集合,2023/7/31,30,2.2 文法和语言的定义,G3：E E+T E T T T*F T F F（E）F id,产生的也是表达式的集合,2023/7/31,31,2.2 文法和语言的定义,一个文法对应一个语言，但一个语言可能有若干个文法产生它，这若干个文法是等价的，称为 等价（equivalent）文法,例 G2 与 G3,2023/7/31,32,2.3 文法和语言的分类,乔姆斯基（Chomsky）在1956年提出形式语言理论，他将形式文法分为四类(0,1,2,3)，对应四类形式语言(0,1,2,3),分类的方法是对文法的产生式进行不同的限制,2023/7/31,33,2.3 文法和语言的分类,0型文法|0，即（）,1型（上下文有关）文法|（）,2型（上下文无关）文法 A VN，（VTVN）*（A）,3型（正规）文法Aa 或 AaB（右线性）Aa 或 ABa（左线性）,2023/7/31,34,2.3 文法和语言的分类,例：1型（上下文有关）文法 文法G：SCD AbbACaCABaaBCbCBBbbBADaDCBDbDDAabDL(G)=ww|wa,b*,2023/7/31,35,2.3 文法和语言的分类,例：2型（上下文无关）文法 文法G1：SaB|bAAa|aS|bAABb|bS|aBB 文法G2：S0A|1B|0A0A|1B|0SB1B|1|0,2023/7/31,36,2.3 文法和语言的分类,例：3型（正规）文法 文法G：S0A|1B|0A0A|1B|0SB1B|1|0,2023/7/31,37,2.3 文法和语言的分类,0型文法产生的语言称为0型语言,1型文法或上下文有关文法（CSG）产生的语言称为1型语言或上下文有关语言（CSL）,2型文法或上下文无关文法（CFL）产生的语言称为2型语言或上下文无关语言（CF L）,3型文法或正则（正规）文法（RG）产生的语言称为3型语言正则（正规）语言（RL）,2023/7/31,38,2.3 文法和语言的分类,四种文法（语言）之间的逐级“包含”关系,2型文法（语言）,1型文法（语言）,0型文法（语言）,3型文法（语言）,2023/7/31,39,2.3 文法和语言的分类,识别各类语言的数学模型（自动机）,图灵机（0型语言）,有界图灵机、线性有界自动机（1型语言）,下推自动机（2型语言）,有限自动机（3型语言）,2023/7/31,40,2.4 分析树与句型,上下文无关文法能够描述现今程序设计语言的大部分语法结构,算术表达式赋值语句条件语句等,2023/7/31,41,2.4 分析树与句型,表达式文法：G=(+,*,i,(,),E,E,P)P:E idE E+EE E*EE(E),E表示算术表达式，id表示程序的“变量”，该文法定义了由变量，+，*，(和)组成的算术表达式的语法结构，即：变量是算术表达式；若E1和E2是算术表达式，则E1+E2，E1*E2和(E1)也是算术表达式。,2023/7/31,42,2.4 分析树与句型,描述一种简单赋值语句的产生式：赋值语句 i=E,描述条件语句的产生式：条件语句 if条件then语句 if条件then语句else语句,2023/7/31,43,2.4 分析树与句型,分析树是描述上下文无关文法句型推导的一种直观方法，也称为推导树,2023/7/31,44,2.4 分析树与句型,为句型推导构造分析树例子：,E=T,E E+T E TT T*FT F F（E）F a,=T*F,=F*F,=a*F,T,T,*,F,F,a,a,E,=a*a,2023/7/31,45,2.4 分析树与句型,分析树的特性：,根标识为开始符号,内部结点标识为非终结符号,每一内部结点及其子结点对应一条产生式，该结点是产生式的左部，子结点从左至右排列构成产生式的右部,叶结点从左至右排列构成句型,T,T,*,F,F,a,a,E,2023/7/31,46,2.4 分析树与句型,分析树与句型推导的关系,一次推导（不是一个句型）对应一棵分析树,一棵分析树可能对应若干个推导,例如下面的推导对应的也是上面那棵分析树 E=T=T*F=T*a=F*a=a*a,T,T,*,F,F,a,a,E,2023/7/31,47,2.4 分析树与句型,说明分析树没有严格反映推导的顺序,但是一棵分析树对应一个最左推导，也只能对应一个最右推导,T,T,*,F,F,a,a,E,2023/7/31,48,2.4 分析树与句型,句型的短语、直接短语和句柄（handle）,如果S A和A，则称是关于A的，句型的一个短语（子树的叶子）,S,A,2023/7/31,49,2.4 分析树与句型,例：句型 F*a 的短语,T,T,*,F,F,a,E,F*a、F、a,2023/7/31,50,2.4 分析树与句型,如果S A和 A=，则称是关于 A的，句型的一个直接短语（只有父子两代的子树的叶子）,S,A,2023/7/31,51,2.4 分析树与句型,例：句型 F*a 的直接短语,T,T,*,F,F,a,E,F、a,2023/7/31,52,2.4 分析树与句型,最左直接短语称为句柄最左性体现在分析树和句型中,S,A,2023/7/31,53,2.4 分析树与句型,例：句型 F*a 的句柄,T,T,*,F,F,a,E,F,2023/7/31,54,2.4 分析树与句型,句型的素短语、最左素短语,1、是关于A的，句型的一个短语,2、至少含有一个终结符,3、除自身外不含更小的带终结符的短语,称是关于A的，句型的一个素短语,句型最左边的素短语称为最左素短语,2023/7/31,55,2.4 分析树与句型,例：,E,E,+,T,E,+,T,F,T,T,*,F,a,句型：T+T*F+a,短语：T+T*F+a、T+T*F、T*F、T（左边）、a,直接短语：T、T*F、a,句柄：T,素短语：T*F、a,最左素短语：T*F,2023/7/31,56,2.4 分析树与句型,句子、文法和语言的二义性（Ambiguity）,如果一个文法的句子有两棵或两棵以上的分析树，称此句子是二义的,最左（右）推导与分析树一一对应，句子二义说明它有两个或以上最左（右）推导,2023/7/31,57,2.4 分析树与句型,E=E+E=id+E=id+E*E=id+id*E=id+id*id,E=E*E=E+E*E=id+E*E=id+id*E=id+id*id,E,E,+,E,id,*,E,E,id,id,E,E,*,E,id,+,E,E,id,id,例：,E id E E+E E E*E E（E）,2023/7/31,58,2.4 分析树与句型,如果一个文法有一个句子是二义的，此文法称为二义文法,E id E E+E E E*E E（E）,2023/7/31,59,2.4 分析树与句型,如果一个语言的所有文法都是二义的，称此语言是二义的,希望文法是无二义的，因为希望对于每一个句子进行唯一确定的分析,2023/7/31,60,The End!,
