文法和语法.ppt

第2章文法和语言,文法和语言的形式定义文法的类型上下文无关文法及其语法树上下文无关文法的句型分析有关文法实用中的一些说明,2.1语言,语言是由句子组成的集合，是由一组记号所构成的集合。汉语-所有符合汉语语法的句子的全体英语-所有符合英语语法的句子的全体程序设计语言-所有该语言的程序的全体研究语言：每个句子构成的规律每个句子的含义每个句子和使用者的关系,研究程序设计语言：每个程序构成的规律 每个程序的含义 每个程序和使用者的关系语言研究的三个方面：语法 Syntax 语义 Semantics 语用 Pragmatics,语法-表示构成语言句子的各个记号之间的组合规律语义-表示按照各种表示方法所表示的各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）语用-表示在各个记号所出现的行为中，它们的来源、使用和影响。,如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。,2.2形式语言,以自然语言为例：,“我是大学生”是否是该语言的句子？,句子:=主语谓语主语:=代词|名词代词:=你|我|他名词:=王明|大学生|工人|英语谓语:=动词直接宾语动词:=是|学习直接宾语:=代词|名词,用 EBNF 描述一种语言：,文法,句子 主语谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生,句子:=主语谓语主语:=代词|名词代词:=你|我|他名词:=王明|大学生|工人|英语谓语:=动词直接宾语动词:=是|学习直接宾语:=代词|名词,句子:=主语谓语主语:=代词|名词代词:=你|我|他名词:=王明|大学生|工人|英语谓语:=动词直接宾语动词:=是|学习直接宾语:=代词|名词,下列是否是句子：我是大学生王明是大学生王明学习英语他学习英语你是工人,下列是否是句子：我大学生是大学生是王明英语学习王明大学生学习他工人是英语,2.3符号和符号串,字母表：元素的非空有穷集合。（符号集）符号：字母表中的元素。,例如：汉语的字母表中包括汉字、数字及标点符号等。PASCAL语言的字母表是由字母、数字、若干专用符号及BEGIN、IF之类的保留字组成。,符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。1.空符号串(没有符号的符号串)是上的符号串 2.若x是上的符号串,a是的元素,则xa是上的符号串 3.y是上的符号串,当且仅当它可以由1和2导出。例如：=a,b,a,b,aa,ab,aabba,都是上的符号串,例：=0,1,0,1,00,01,11,1001110等都是上的符号串.,例：=a,b,c上的符号串有：a,b,c,ab,ba,aaca,acaa等.,注意：符号串中的符号排列是有顺序的.可以用字母表示符号串，如 x=aaca,如果 z=xy 是一符号串，那么：x 是 z 的头，y 是 z 的尾；如果 x 非空，那么 y 是固有尾；如果 y 非空，那么 x 是固有头。,例：设 z=abc,那么z 的头是：,a,ab,abc（除 abc 外都是固有头）z 的尾是：,c,bc,abc（除 abc 外都是固有尾）,几种表示法（x,z是符号串,t是符号）：z=xx 是符号串 z 的头z=xx 在符号串z 中某处出现z=t符号 t 是 符号串 z 的第一个符号,符号串的运算符号串的长度：符号串中符号的个数.符号串s的长度记为|s|。的长度为0连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy例 x=ST,y=abu 则 xy=STabu|x|=2,|y|=3,|xy|=5 x=x=x,方幂：符号串x自身连接n次得到的符号串 xxxx(n个x)定义为 xn x0=,x1=x,x2=xx,x3=xxx x=AB,则 x0=,x1=AB,x2=ABAB,x3=ABABAB对于 n0,xn=xxn-1=xn-1x,符号串集合：若集合A中一切元素都是某字母表上的符号串，则称A为字母表上的符号串集合。两个符号串集合A和B的乘积定义为AB=xy|xA且yB若 集合A=a,b B=c,d则 AB=ac,ad,bc,bd A=A=A(x=x=x)使用*表示上的所有有穷长的串（包括）的集合。*称为的闭包。从*中除去得到的集合记为+。+称为的正闭包。,*=0 1 2 n+=1 2 n*=0+=*=*+=*-,例：设=0,1，则*=,0,1,00,01,10,11,000,001,010,例：设=a,b，则*=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,文法和语言的形式定义,规则（重写规则、产生式或生成式），是形如或=的（，）有序对，其中是某字母表V的正闭包V+中的一个符号，是V*中的一个符号。（V+，V*)称为规则的左部(或生成式的左部)。称为规则的右部(或生成式的右部)。,文法G定义为四元组（VN，VT，P，S）VN：非终结符集VT：终结符集P：产生式（规则）集合S：开始符号（识别符号）VN、VT 和 P 是非空有穷集。S 至少在一条规则中作为左部出现。VNVT=，SVNV=VNVT，称为文法G的字母表（字汇表）,2.4文法的定义,例3.1 文法G=（VN，VT，P，S）VN=S,VT=0,1 P=S0S1,S01 S为开始符号,例3.2 文法G=（VN，VT，P，S）VN=标识符，字母，数字VT=a,b,c,x,y,z,0,1,9P=a,z 0,9 S=,习惯上只将产生式写出。并有如下约定：第一条产生式的左部是开始符号用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符G可写成GS，其中S是开始符号,例3.1 文法G=（VN，VT，P，S）VN=S,VT=0,1 P=S0S1,S01 S为开始符号,可写成：G：S0S1 S01,或写成：GS：S0S1 S01,2.5推导的定义,一、直接推导“”是文法G的产生式，,V*，若有v,w满足：v=,w=,则说：v（应用规则）直接产生w或说：w是v的直接推导或说：w直接归约到v记作 v w,例：G：S0S1，S01直接推导：0S10011（v=0S1，w=0011，使用规则S01，=0，=1）S 0S1（v=S，w=0S1，使用规则S0S1，=，=）0S100S11（v=0S1，w=00S11，使用规则S0S1，=0，=1）,例 文法G=（VN，VT，P，S）VN=标识符，字母，数字VT=a,b,c,x,y,z,0,1,9P=a,z 0,9 S=,指出下面直接推导所使用的规则：abc abc5,例：G：S0S1，S010S1 00S11 000S111 00001111 即 0S1 00001111也记作 0S1 00001111,若存在v=w0 w1.wn=w,(n0)则称v推导出（产生）w（推导长度为n），或称w归约到v.记作 v w若有v w，或v=w，若存在v=w0 w1.wn=w,(n=0)则记为v w,+,+,+,*,+,*,*,二、,和,三、最左（最右）推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换最右推导被称为规范推导。由规范推导所得的句型称为规范句型,例:GS:SaASASbAASSSaAba,SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa,四、语法树,用于描述上下文无关文法的句型推导的直观方法。,例:GS:SaASASbAASSSaAba,S a A S S b A a a b a,句型aabbaa的语法树（推导树）,叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型的语法树。,五、短语、直接短语、句柄的定义：文法GS，是G的一个句型，如果：S A且A 则称是句型相对于非终结符A的短语。若有A 则称是句型相对于规则A的直接短语（或简单短语）。一个句型的最左直接短语称为该句型的句柄。,+,+,2.6文法的句型、句子的定义,一、句型设GS是一文法，如果符号串x是从识别符号推出来的，即S x，则称x是文法GS的句型。,*,*,二、句子x仅由终结符号组成（即S x，且xVT*），则称x是GS的句子。例：G：S0S1，S01S 0S1 00S11 000S111 00001111,*,三、语言的定义,由文法G生成的语言记为L(G),它是文法G的一切句子的集合:L(G)=x|S x，其中S为文法的开始符号，且x VT*例：G：S0S1，S01L(G)=0n1n|n1,*,例3.3 文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEee L（G）=anbnen|n1,S a S BE(SaSBE)a aBEBE(SaBE)aabEBE(aBab)aabBEE(EBBE)aabbEE(bBbb)aabbeE(bEbe)aabbee(eEee),G生成的每个串都在L(G)中L(G)中的每个串确实能被G生成,文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEee,S a S BE aaSBEBE aaaBEBEBE,四、文法的等价,若L（G1）=L（G2），则称文法G1和G2是等价的。如文法G1A：A0R 与G2S：S0S1 等价 A01 S01 RA1,2.7文法的类型,一、通过对产生式施加不同的限制，Chomsky将文法分为四种类型：1、0型文法：对任一产生式，都有(VNVT)+，(VNVT)*，|，仅仅 S除外2、1型文法（也称上下文有关文法）：对任一产生式，都有|，仅仅 S除外1A212(A在VN中，其他在V*中，),3、2型文法（也称上下文无关文法）：对任一产生式，都有VN，(VNVT)*A(A在VN中，在V*中，)4、3型文法（也叫正规文法）任一产生式的形式都为AaB或Aa，其中AVN，BVN，aVT,例：1型（上下文有关）文法 文法GS：SaSBESaBEEBBEaBabbBbbbEbeeEee,例：1型（上下文有关）文法 文法GS：SCDAbbA CaCABaaB CbCBBbbBADaD CBDbD DAabDL(G)=ww|wa,b*,例：2型（上下文无关）文法 文法GS：SaB|bAAa|aS|bAABb|bS|aBB 文法GS：S0A|1B|0A0A|1B|0SB1B|1|0,例：定义标识符的3型（正规）文法 文法GI：I lTI lT lTT dTT lT d,二、文法和语言,1、0型文法产生的语言称为0型语言2、1型文法或上下文有关文法（CSG）产生的语言称为1型语言或上下文有关语言（CSL）2、2型文法或上下文无关文法（CFG）产生的语言称为2型语言或上下文无关语言（CF L）3、3型文法或正则（正规）文法（RG）产生的语言称为3型语言正则（正规）语言（RL）,三、上下文无关文法及其语法树,上下文无关文法有足够的能力描述现今程序设计语言的语法结构1、算术表达式上下文无关文法表示,文法G=(E,+,*,i,(,),P,E P:E iE E+EE E*EE(E),ifthen|ifthenelse 3、赋值语句，条件语句，读语句,2、条件语句上下文无关文法表示,4、上下文无关文法的语法树,用于描述上下文无关文法的句型推导的直观方法,例:GS:SaASASbAASSSaAba,S a A S S b A a a b a,句型aabbaa的语法树（推导树）,叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型的语法树。,推导过程中施用产生式的顺序,例:GS:SaASASbAASSSaAba,S a A S S b A a a b a,句型aabbaa的语法树（推导树）,SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa,问题：一个句型是否对应唯一的一棵语法树？,例：GE:E iE E+EE E*EE(E),E E+E E*E i i i,E E*E i E+E i i,句型 i*i+i 的两个不同的最左推导：推导1：E E+E E*E+E i*E+E i*i+E i*i+i推导2：E E*E i*E i*E+E i*i+E i*i+i,五、二义文法,若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。产生某上下文无关语言的每一个文法都是二义的，则称此语言是先天二义的。,判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的。但可以为无二义性寻找一组充分条件。二义文法改造为无二义文法GE:E i GE：E T|E+T E E+E T F|T*F E E*E F（E）|i E(E)规定优先顺序和结合律,句型的分析,句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号。,分析算法可分为：自上而下分析法：从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的推导。自下而上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。两种方法反映了两种不同的语法树的构造过程,自上而下的语法分析,例：文法G：S cAd A ab A a识别输入串 w=cabd 是否该文法的句子,SSScAdcAd a b推导过程：S cAd cabd,自下而上的语法分析,例：文法G：S cAd A ab A a识别输入串 w=cabd 是否该文法的句子,SAA c a b d c a b d c a b d 规约过程：S cAd cabd,句型分析的有关问题,1）如何选择使用哪个产生式进行推导？假定要被代换的最左非终结符号是V，且有n条规则：VA1|A2|An，那么如何确定用哪个右部去替代V？2）如何识别可归约的串？在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”,E F T T F F i1*i2+i3短语：直接短语：句柄：,GE：EE+T|T TT*F|F F(E)|i句型：i*i+i,有关文法实用中的一些说明,有关文法的实用限制上下文无关文法中的规则,有关文法的实用限制,文法中不得含有有害规则和多余规则有害规则：形如UU的产生式。会引起文法的二义性多余规则：指文法中任何句子的推导都不会用到的规则1）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达的2）文法中某些非终结符，由它不能推出终结符号串来，称为不可终止的,对于文法GS，为了保证任一非终结符A在句子推导中出现，必须满足如下两个条件：1）A必须在某句型中出现。2）必须能从A推出终结符号串t来。即1）文法GS，对某两个符号串和：S A 2）A t,tVT*,*,+,化简文法,例：GS 1)SBe SBe2)BCe BAf3)BAf AAe 4)AAe Ae5)Ae 6)CCf7)Df,上下文无关文法中的规则,具有形式A的规则称为规则，其中AVN某些著作和讲义中限制这种规则的出现。因为规则会使有关文法的一些讨论和证明变得复杂两种定义的唯一差别是句子在不在语言中。,如果语言L有一个有穷的描述，则L也同样有一个有穷描述。并且可以证明，若L是上下文有关语言、上下文无关语言或正规语言，则L和L-分别是上下文有关语言、上下文无关语言和正规语言,定理3.1 文法G，P中的每一个产生式的形式均为A，其中AVN，(VN VT)*(即可能为)，则L(G)也能由这样一种文法产生：每一个产生式或者为A形式，其中AVN，(VN VT)+(即)，或者 S且 S不出现在任何产生式右边。,定理3.2G是上下文有关文法，则存在另一个上下文有关文法G1，L(G)=L(G1)，且G1的开始符号不出现在G1的任何产生式的右边。若G为上下文无关文法或正规文法，类似结论成立。,