《文法和语言》PPT课件.ppt

第二章 文法和语言,学习目标:掌握：自上而下与自下而上的分析思想理解：文法的形式定义，推导，归约，句型，句子，语言，上下文无关文法，规范句型，语法树，短语，直接短语，句柄了解：文法的类型，文法实用中的限制，文法的二义性,2.1语言和文法的直观概念2.2符号和符号串2.3文法和语言的形式定义2.4文法的类型2.5上下文无关文法及其语法树2.6句型的分析,2.1 语言和文法的直观概念,程序设计语言的直观定义程序设计语言是一个记号系统，它的定义包括语法和语义。语法(syntax)定义:是一组规则，用它可以形成和产生一个合适的程序描述工具:文法作用:定义什么样的符号序列是合法的，与符号的含义无关。,语义(semantics)分类:静态语义：一系列限定规则，确定哪些合乎语法的程序是合适的动态语义：表明程序要做什么描述工具:指称语义,操作语义等作用:检查类型匹配，变量作用域等,文法的直观概念,如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，要找出语言的有穷表示。有两个途经：生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，要么永远继续下去。,文法：是语言语法的描述工具，实现用有穷的规则把语言的无穷句子集描述出来。,例:“我是大学生”是汉语的一个句子汉语句子的构成规则表示如下：句子=主语谓语主语=代词名词代词=我你他名词=王明大学生工人英语谓语=动词直接宾语动词=是学习直接宾语=代词名词,例:“(34-3)*42”是一个表达式表达式的构成规则表示如下：Exp=Exp op Exp|(Exp)|NumberOp=+|*,由规则推导句子,方法:用一条规则=的右端符号串代替:=的左端.表示:用“=”表示推导,含义是,使用一条规则,代替=左边的某个符号,产生=右端的符号串.,例如:句子“我是大学生”的推导过程如下：句子 主语谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生,文法的作用严格定义句子的结构，是判断句子结构合法与否的依据用有穷的规则把无穷的句子集合描述出来,2.2 符号和符号串,字母表定义:元素的非空有穷集合例：=01=ab,c元素也称为符号，字母表也称符号集。程序语言的字母表由字母数字和若干专用符号组成。,符号串定义:由字母表中的符号组成的任何有穷序列例：0,00,10是字母表=01上的符号串 a,ab,aaca是=ab，c上的符号串在符号串中，符号是有顺序的，顺序不同,代表不同的符号串，如:ab和ba不同不含任何符号的符号串称为空串，用表示注意:并不等于空集合 符号串长度:符号串中含有符号的个数如:|abc|=3|=0,符号串的运算符号串的连接：设x、y是符号串,它们的连接是把y的符号写在 x的符号之后得到的符号串xy例如 x=ST，y=abu 则 xy=STabu 显然x=x=x符号串的方幂：把符号串a自身连接n次得到的符号串an=aaaa例如 a1=a a2=aa a0=,符号串集合：定义:若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。符号串集合的乘积：符号串集合A和B的乘积定义为:AB=xy|xA且yB，即AB是由A中的串x和B中的串y连接而成的串xy组成的集合。若集合A=ab,cde B=0,1 则 AB=ab0,ab1,cde0,cde1显然A=A=A,符号串集合的方幂:设A是符号串的集合，则称Ai为符号串集A的方幂，其中i是非负整数。具体定义如下:A0=A1=A,A2=A AAK=AA.A(k个),集合的闭包闭包集合的闭包*定义如下：*=0 1 2 3例：设有字母表=0，1则*=012=,0,1,00,01,10,11,000,即*表示上所有有穷长的串的集合。,正闭包+=1 2 3称为的正闭包。+表示上的除外的所有用穷长串的集合*=0+=*=*,字母表上的一个语言是上的一些符号串的集合 即是*的一个子集例如：=a,b*=,a,b,aa,ab,ba,bb,aaa,aab,集合ab,aabb,aaabbb,anbn,或w|w*且w=anbn,n1为字母表上的一个语言。集合a,aa,aaa,或w|w*且w=an,n1为字母表上的一个语言是一个语言即 是一个语言。,2.3文法和语言的形式定义,1文法的定义2文法的简化表示法3推导与归约4句型、句子、语言的定义5文法的等价,1文法的定义,产生式（规则）产生式是一个有序对(,)，通常写作（或:=）文法定义:文法G(Grammar)定义为四元组（VN，VT，P，S）VN(Nonternimal)：非终结符集VT(Terminal)：终结符集P(Production)：产生式（规则）集合S(Start Symbol)：开始符号或识别符号,说明:V=VNVT，V称为文法G的字母表P中产生式形如：,其中V+且至少含一个非终结符，V*VN,VT和P是非空有穷集VNVT=S是一个非终结符，且至少要在一条产生式的左部出现,汉语句子的构成规则表示如下：句子=主语谓语主语=代词名词代词=我你他名词=王明大学生工人英语谓语=动词直接宾语动词=是学习直接宾语=代词名词,例1：文法G=(VN,VT,P,S)其中VN=S，VT=0，1，P=S-0S1,S-01，开始符为S例2：文法G=(VN,VT,P,S)VN=标识符，字母，数字，VT=a,b,c,x,y,z,0,1,9P=，a,z，0,9，S=,2文法的简化表示法,简化:通常不用将文法的四元组表示出来，只写出产生式约定：第一条产生式的左部是开始符号或用GS表示S是开始符号用大写字母（或用尖括号括起来）表示非终结符用小写字母表示终结符左部相同的产生式A-,A-可以记为A-|，其中“|”是“或”的意思，,分别称为侯选式,例如:文法GS：S-A|SA|SDA-a|b|zD-0|1|9,3.推导(Derivation)与归约(Reduction),直接推导和直接归约：是文法G的产生式，若有v，w满足：v=,w=,其中,V*则称v直接推导到w,也称w直接归约到v,记作 v w直接推导就是用产生式的右部替换产生式的左部的过程直接归约就是用产生式的左部替换产生式的右部的过程,例 文法G：S0S1，S01 有直接推导：0S1 00S11（S0S1）00S11 000S111（S0S1）000S111 00001111（S01）S 0S1（S0S1）,推导和归约若存在v=w0 w1.wn=w,(n0)则称v推导出w，或w归约到v,记为v=+w若有v=+w，或v=w，则记作v=*w,例 文法G：S0S1，S01 S 0S1 00S11 000S111 00001111 S=+00001111S=*00001111 S=*S,规范推导如果在推导的任何一步，都是对中的最左（最右）非终结符进行替换,则称这种推导为最左(最右)推导最右推导被称为规范推导,例如:句子“我是大学生”的推导过程如下：句子 主语谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生,例 文法G：EE+T|T TTF|F F（E）|i“i+ii”的推导过程如下：最左推导：E=E+T=T+T=F+T=i+T=i+TF=i+FF=i+iF=i+ii最右推导：E=E+T=E+TF=E+Ti=E+Fi=E+ii=T+ii=F+ii=i+ii,4句型、句子、语言的定义,句型和句子设有文法GS，若符号串x是从开始符推导出来的,即S=*x，则称x是文法G的句型若x仅由终结符组成,即S=*x，且xVT*，则称x是文法G的句子由规范推导所得的句型称为规范句型例 文法GS：S0S1，S01S 0S1 00S11 000S111 00001111S,0S1,00S11,000S111,00001111都是G的句型00001111是G的句子,提问,以下哪个符号串是文法的句子,语言的定义由文法G生成的语言记为L(G),它是文法G的一切句子的集合,即 L(G)=x|S=*x，其中S为文法的开始符号，且x VT*例 文法G：S0S1，S01S0S1 00S11 03S13 0n-1S1n-1 0n1nL(G)=0n1n|n1,根据文法，可以通过推导得到该文法相应的语言；例：GE：EE+T|TTTF|FF(E)|aEE+T T+T F+T a+T a+TF a+FF a+aF a+aa表示一切能用符号a，+，(和)构成的算术表达式有了语言的要求，也可以为该语言设计文法例：若语言由0、1符号串组成，串中0和1的个数相同，构造其文法为：A 0B|1CB 1|1A|0BBC 0|0A|1CC,提问根据文法，可以通过推导得到该文法相应的语言；S S+a|a有了语言的要求，也可以为该语言设计文法L(G)=a,(a),(a),(a),5文法的等价,若L（G1）=L（G2），则称文法G1和G2是等价的。例如 文法G1A：A0R A01 RA1 G2S：S0S1 S01所定义的语言都是0n1n两文法等价,2.4 文法的类型,通过对产生式施加不同的限制，Noam Chomsky将文法分为 四种类型：0型文法(短语文法)：对任一产生式，都有(VNVT)*且至少含有一个非终结符，(VNVT)*,1型文法(上下文有关)：它是0型文法的特例，设文法G=(VN,VT,P,S)，对P中的任一产生式，都有|，仅仅 S除外例 文法GS：S-aSBAAA-ABBA-BAS-abBbA-bbBA-AA1型文法产生式的一般形式是A，,V*，AVN,V，它表示当A的上文为且下文为时可把A替换成，因此称1型文法为上下文有关文法。,2型文法（上下文无关文法）：它是1型文法的特例，对任一产生式，都有VN，(VNVT)*例 文法GS：SABABS|0BSA|12型文法产生式的一般形式是:A，它表示不管A的上下文如何即可把A替换成，因此被称为上下文无关文法。产生式A称为规则通常程序设计语言的文法，可用2型文法来描述，因此我们重点研究2型文法。,3型文法(正规文法)：它是2型文法的特例，任一产生式的形式都为AaB或Aa，其中A，BVN，aVT例如 文法GS：S0A|1B|0A0A|1B|0SB1B|1|0在程序设计语言中，3型文法通常用来描述单词的结构。,四种文法之间的逐级“包含”关系,2.5上下文无关文法及其语法树,1上下文无关文法(Context-Free Grammar)上下文无关文法有足够的能力描述现今程序设计语言的语法结构例：算术表达式：Ei|E+E|E*E|（E）-i:=E-if then|if then else 所以我们只关心上下文无关文法形成的语言的句子的分析和分析方法,2.语法树(推导树Parse Tree)作用:直观地描述上下文无关文法的句型推导过程。给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树,例：文法G：EE+T|TTTF|F F（E）|i句型T+TF的推导过程与语法树,E=E+T,E=E+T,=E+TF,=T+TF,=T+T,=T+TF,从语法树中看不出句型中的符号被替代的顺序,从左到右读出叶子结点得到的符号串，为文法的句型。也把该语法树称为该句型的语法树。,语法树定义:给定文法G=(VN,VT,P,S)，若一棵树满足下列4个条件，则称此树为G的语法树：每个结点都有一个标记，此标记是V的一个符号根的标记是S若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定AVN如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2Ak一定是P中的一个产生式,语法树和推导的关系句型的每个推导都产生相应的一棵语法树一个句型的不同推导产生相同的语法树每棵语法树对应唯一的最左推导或最右推导通常，一个句型有唯一的语法树、最左推导和最右推导，它们代表了句型的语法结构，但是一个句型可以有多个不同的推导，它不能代表句型的语法结构,3.文法的二义性(Ambiguity),通常，一个句型对应一棵语法树，它表示该句型的不同推导过程,句型“T+T F”对应的语法树：,文法G：EE+E|EE|（E）|i句子 ii+i 对应的语法树,两个不同的最左推导：推导1：E E+E EE+E iE+E ii+E ii+i推导2：E EE iE iE+E ii+E ii+i,二义性:如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的二义性文法存在某个句子,它有两个不同的最左（右）推导对于一个程序设计语言来说，希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。,构造无二义性文法,文法G：EE+E|EE|（E）|i,文法G：E-T|E+TT-F|TFF-(E)|i,句子 ii+i 对应的语法树,2.6句型的分析,任务:句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。对于程序设计语言来说，句型分析就是一个识别输入符号串是否为语法上正确的程序的过程。,从左到右的分析算法，即总是从左到右地识别输入符号串.句型分析算法采用从左到右的分析算法句型的分析算法分类自上而下分析法(Top-Down parsing)自下而上分析法(Bottom-Up parsing),2.6.1自上而下的分析方法,定义:从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。语法树的构造：将文法的开始符号作为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。,例 文法G：S cAd A ab A a识别输入串w=cabd是否为该文法的句子,S,推导过程：,=cabd,S,=cAd,自上而下方法的主要问题对输入串cabd自上而下构造语法树的另一过程,不成功，不成功的原因是选错产生式Aa,自上而下分析的主要问题是选择产生式:假定要被代换的最左非终结符号是B，且有n条规则：BA1|A2|An，那么如何确定用哪个右部去替代B？,S,2.6.2自下而上的分析方法,定义:从输入符号串开始，利用文法的产生式逐步进行归约，试图归约到文法的开始符号。语法树的构造：从输入符号串开始，以它作为语法树的末端结点符号串，自底向上的构造语法树，使文法开始符正好是该语法树的根。如果最终根结点是开始符，则输入符号串是语言的一个句子，否则不是。,例 文法G：S cAd A ab A a识别输入串w=cabd是否为该文法的句子,归约过程：,用“|-”表示归约，下划线部分为被归约符号,cabd,|-cAd,|-S,自下而上分析的主要问题对输入串cabd的两种归约过程（1）cabd|-cAd|-S 归约到开始符（2）cabd|-cAbd 不能归约到开始符在自下而上的分析方法中，每一步都是从当前串中选择一个子串加以归约，该子串暂称“可归约串”。如何确定“可归约串”是自下而上分析的主要问题。,不同的确定“可归约串”的方法，形成了不同的自下而上分析方法在一种“规范归约”方法中，“可归约串”被称为“句柄”,短语，直接短语和句柄定义:设是文法GS中的一个句型，如果有S=*A且A=+，则称是句型相对于非终结符A的短语,特别的如有A=，则称是句型相对于规则A的直接短语。,一个句型的最左直接短语称为该句型的句柄(Handle)。,对定义的分析：在短语的定义中包括了三个条件：是文法的一个句型；S=*A;A=+。,这三个条件都必须满足。(1)(2)说明、A都必须是句型(2)(3)说明，将中的归约称A后，得到的A一定要是句型。假如符号串，将其归约成A后得到的符号串不能由开始符号推出，则不是短语。,例：文法GE:EE+T|TTTF|F F(E)|i的一个句型 是TF+i，相应的语法树见右图：,因为E=*Ti且T=TF，所以T F是句型相对于T的短语，且是相对于 T-T F的直接短语因为E=*T F+F且F=i，所以i是句型相对于F的短语，且是相对于F-i的直接短语因为E=*E且E=+T F+i，所以T F+i是句型相对于E的短语T F是最左直接短语，即句柄,文法GE:EE+T|TTTF|FF（E）|i的一个句型 是TF+i,虽然F+i是句型TF+i的一部分，但不是短语，因为尽管有E=+F+i，但是不存在从文法开始符E=*TE的推导,短语与语法树从句型的语法树上很容易找出句型的短语语法树中每棵子树的末端结点构成相对于子树根的短语 例：文法GE的句型T*F+i语法树：,五棵子树对应三个短语T*F，i，T*F+i,两层子树的末端结点构成直接短语 两棵两层子树对应两个直接短语：T*F，i位于最左边的两层子树的末端结点构成句柄：T*F,本章小结,本章出现的概念较多，应重点理解文法，语言，推导，句型句子及句柄等概念。本章的内容是学习语法分析的基础,作业,P3411.一个上下文无关文法生成句子abbaa的推导树如下：(1)给出该句子相应的最左推导，最右推导。(2)给出该文法的产生式集合P可能有哪些元素？(3)找出该句子的所有短语，简单短语，句柄。,作业,P3515 分以下两种情形，各写一个文法，使其语言是十进制非负偶数的集合：（1）允许0打头；（2）不允许0打头。,