前后文无关文法和语言.ppt

第二章 前后文无关文法和语言,语言及其表示方法 文法的定义 由文法产生句子 有关定义和记号 语言的形式文法 句型的分析 文法和语言的乔姆斯基分类,重点和难点,重点： 本章中涉及的概念和术语的理解 文法和语言的形式定义 难点： 短语和句柄的识别 二义性文法的判定,2.1 语言及其表示方法,规定一种语言首先要规定它各种构造成分的形式，词汇、句子等的构造规则及表示法。 编译原理则应建立有关语言的数学化（形式化）模型，以便对程序语言进行研究。,定义1：相当大的地区内公众所懂得并使用的“话”，以及组成这些“话”的方法的统一体。 缺点：不够形式化和精确化 定义2：某一个字母表上的符号串的（句子）的集合。 缺点：缺乏语言句子的结构性组成描述， 缺乏判断任一符号串是否为合法句子判断机制。 因此，如果能刻画一个语言句子，就定义了该语言。,1、语言,1956年，chomsky建立文法的数学模型，对形式化语言和自动机理论的研究取得较大的成果。 1960年。P.Nuaur和J.Boukas首先用BNF成功对ALGOL语言的文法进行了描述，虽然对语义形式化描述不理想，但在程序设计语言的语法描述上有足够的能力。 至此，程序语言就有了形式化表述。,枚举（句子有限） 例：L=We are learning computer science,it is interesting 数学表示（句子无限） 例:1，1/2，1/3，1/n1/n|nN 制定有限条规则，用来产生所需描述语言中的句子全部，这些规则即文法。 建立一种算法能对于任给的符号串，判别是否为给定语言的合法句子自动机理论。,2、表示方法,语言可以看成在一个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合。,2.2 文法的定义,1、例： “我是大学生” 是汉语的一个句子。,句子=主语谓语 主语=代词名词 代词=我你他 名词=王明大学生工人英语 谓语=动词直接宾语 动词=是学习 直接宾语=代词名词,返回,=左端的规则由=右端的符号串代替： 句子 主语谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生,按照如下方式用它们导出句子：,“我大学生是”是否为?,sentence subject This | Computers | I verb-phrase | adverb never verb is | run | am | tell object the | a | noun university | world | cheese | lies This is a university. Computers run the world. I am the cheese. I never tell lies.,英语句子,2、文法的形式化表示,符号： 表示一个语法单位； =（ ）表示“定义为”； | 表示为“或” 。 文法：描述语言的形式结构的规则。 产生式 产生式左部 产生式右部,文法的一般构成： 一组终结符号：仅出现在产生式右部的符号 VT 一组非终结符号：至少在产生式左部出现过一次的符号VN 一个开始符号：特殊的非终结符，表示了定义语言中最感兴趣的语法范畴。 S； 一组规则：P G=VT，VN，S，P 例如,VN，VT和P是 非空有穷集； VN和VT不含公共的元素，即VN VT = ； 用V表示VNVT，称文法G的字母表或字汇表； 产生式是形如或 =的（ ，）有序对，其中是字母表V的一个非空符号串(V+)，是V中的一个符号串，可为空串(V*)。 称为产生式左部， 称作产生式右部。,说 明,2.3 由文法产生句子,1、推导 句子 主语谓语 代词谓语 我谓语 过程：文法的开始符号开始，每次把当前串的一个非终结符号用于之对应的产生式右部来代换，得到一个新符号串，称一步推导。 2、推导长度,文法的作用就是用有限条规则产生无限多句子。 某一文法产生的全部句子所组成的集合 该文法产生的语言。,一、基本定义 1、符号：可以相互区别的记号（元素）。 2、字母表：符号（元素）的非空有穷集合。 3、符号串：由字母表中的符号组成的任何有穷序列。 空符号串(没有符号的符号串)是上的符号串。 若x是上的符号串，a是的元素，则xa是上的符号串。 y是上的符号串，当且仅当它可以由1和2导出。 例如： =a,b ，a，b，aa，ab，aabba都是上的符号串,2.4 有关定义和记号,4、符号串s的头（前缀）：移走符号串s尾部的零个或多于零个符号得到的符号串。 如： b是符号串banana的一个前缀. banana是 banana前缀。 5、符号串s的尾（后缀）：删去符号串s头部的零个或多于零个符号得到的符号串。 如: nana是符号串banana的一个后缀. banana是 banana后缀。,6、符号串s的子串：从s中删去一个前缀和一个后缀得到的符号串。 如:ana是符号串banana的一个子串。,7、符号串s的真前缀，真后缀，真子串：任何非空符号串 x，是s的前缀，后缀或子串，并且 s x。 8、符号串的长度：符号串中符号的个数。符号串s的长度记为|s|。 的长度为0。,对于每个符号串s，s和两者都是符号串s的前缀，后缀和子串。,1、连接：符号串x、y的连接，是把y的符号写在x的符号之后得到的符号串xy。 如： x=ba，y=ck 则 xy=back 有a = a 2、方幂：符号串自身连接n次得到的符号串。 an 定义为 aaaa n个a a1=a, a2=aa a0=,二、符号串的运算,三、符号串集合,若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。,1、符号串集合乘积：两个符号串集合A和B的乘积定义为 AB =xy|xA且yB 例如：若 集合A=ab，cde， B = 0，1 则 AB =ab1，ab0，cde0，cde1 2、的闭包：上的一切符号串（包括）组成的集合。记为*,3、的正闭包：上的除外的所有符号串组成的集合。记为+,例：=a,b ，求*和。 *=,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab,*包含上的所有符号串， +包含上除空串外的任意符号串。,1、语言：由句子组成的集合，为一符号串集合。 即：字母表上的一个语言是上的一些符号串的集合，是*的一个子集。 L=S|S* 、都是语言 例如：字母表=a,b 集合 w|w*且w=anbn,n1为上的一个语言。 集合 w|w*且w=an,n1 为上的一个语言。,四、语言上的有关运算,2、语言“并”运算：语言L和M的并为 LM，是一个语言: w|w is in L or is in M 如： L1 =a,b,y,z ，M1 =1,28,9 L1M1=a,b, y,z，1,28,9 ,设L是（上的）一个语言，M是（上的）一个语言， 语言L和M的“并”，“交”，“差”，“连接”运算结果是一个语言。,3、语言L和M的连接运算：记为 LM(可简记为LM)。 LM=st |sL且 tM 如： L =a,b,y,z ，M =1,28,9 LM =a1,b1,y1,z1,a2,b2a9z9 特别的：有L = L=L。 L的n次连接Ln= LL.L,4、语言L的 闭包：记为 L*， L*= L0 L1 L2 . L0= ， Ln= L Ln-1=Ln-1 L(n1) 5、语言L的正 闭包：记为 L+， L+= L1 L2 L3 . L+= LL*= L*L L*= L+ 如： L1 =a,b,y,z M1 =1,28,9 （L1M1）=a,b, y,z，1,28,9 （L1M1）*=a,b, y,z，1,28,9,aa,1a,xyz, 6789st L1（L1M1）*=所有字母打头的字母和数字符号串,练习1：L=A,B,C,Z,a,b,cz D=0,1,2,3,4,5,6,7,8,9 计算：LD， LD， L4 ， L*， L(L D)*， D+,练习2：考虑一个文法G1: SbA AaA|a 它定义了一个什么语言呢？,从开始符S出发，我们可以推出如下句子： SbA ba SbA baA baa SbA baA baaa,可以写为：L(G1)=ban|n1,2.5 语言和文法的形式定义,一个上下文无关文法G定义为四元组(VN，VT，P，S ) 其中： VN：非终结符号(或语法实体，或变量)集；VT：终结符号集；P：产生式(也称规则)的集合； A 其中， (VN VT )* ， A VN VN，VT和P是 非空有穷集。 S：称作识别符号或开始符号的一个非终结符，它至少要在一条产生式中作为左部出现。S VN VN和VT不含公共的元素，即VN VT = 用V表示VN VT ，称为文法G的字母表或字汇表,1、上下文无关文法,例 文法G=（VN，VT，P，S） VN = S , VT = 0, 1 P= S0S1, S01 S为开始符号 对此产生式可进行推导产生句子。,2、推导,直接推导“” 是文法G的产生式，若有v,w满足：v=,w= , 其中V*,V* 则称v直接推导到w,记作 v w； 也称w直接归约到v 例：G： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1,例：G： S0S1， S01 S 0S1 00S11 000S111 00001111,S S 00S11 00S11,S 00001111 推导长度为4,若存在v =w0 w1 . wn=w (n0) 则记为v w，称作v推导出w，或w归约到v 若有v w 或 v=w， 则记为v w,推导的长度（长度为n的推导）,3、句型和句子,例：G： S0S1， S01 S 0S1 00S11 000S111 00001111 G的句型 S，0S1，00S11，000S111，00001111 G的句子 00001111，01,句型 有文法GS，若S x， xV*，则称x是文法G的句型。,句子 有文法GS，若S x，且xVT*，则称x是文法G的句子。,例：GE： EE+T|T TT*F|F F(E)|a 判断：a+a*a是否为该文法的句子,EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a,句子：用符号a，+，*，(和)构成的算术表达式,4、语言,由文法G生成的语言记为L(G)，它是文法G的一切句子的集合:,语言中的每个句子可以由上下文无关文法的开始符号产生。 例：G=（0，1，S，S，P） P: S0S1， S01 L(G)=0n1n|n1,L(G)=x|S x，S为文法的开始符号，且x VT*,G生成的每个串都在L(G)中，L(G)中的每个串确实能被G生成。 文法所产生的语言L(G)是无限语言，原因是所定义的文法中含有递归。,5、文法的递归性,递归、直接递归：如果文法中有形如AA的产生式，其中，不同时为，则称产生式A 是直接递归。,例：GE： EE+T|T TT*F|F F(E)|a,A A，直接递归 A A，递归 A 称为递归和直接递归的非终结符号,若存在 A A,则称A 是递归的。,左递归、右递归 =， 左递归 ，= 右递归,直接递归是递归的一种特殊情况，如果一个语言是无限的，则定义此语法的文法必然是递归的。,例：语言L=anbbn| n 1, 写出产生L的文法。,GS: S aAb A aAb|b,从语法定义的角度，递归定义是一种较好的方式，因为它不仅使文法形式简练，而且也给无限语言的有限表示提供了一种有效的方法。 然而左递归会影响某些语法分析方法实现，因此有时需要对文法进行等价改造，以便消除其中的左递归。,6、文法的等价性,若L（G1）=L（G2），则称文法G1和G2是等价的。 如文法G1A：A0R 与G2S：S0S1 等价 A01 S01 RA1,2.6 句型的分析,如何表示语言中的句子？任给的一个符号串是否为某一文法的句子（型）？需要进行句型分析。 自顶向下：从文法的开始符号，以给定的符号串为目标，试图推导出串。 自底向上：给定符号串出发，反复用文法中有关产生式的左部替换当前符号串中的相应子串，以期最后归约为文法开始符号。,例：GE： EE+T|T TT*F|F F(E)|a,E,判定a+a*a是否为文法的句子？,E+T,T+T,F+T,a+T,a+T*F,a+F*F,a+a*F,a+a*a,1、规范推导 规范句型,最左（最右）推导：推导的每一步，其中、是句型，都是对中的最左（右）非终结符进行替换。 规范推导： 最右推导称为规范推导。 规范句型：由规范推导所得的句型称为规范句型。 注意：文法中的每个句子都必定有最左(右)推导，但对于一个句型，则不一定。,GE：EE+T|T TT*F|F F(E)|a,对句型T+a+T的推导： E E+T T*F+T T*a+T,问题：对于推导中的每一步，S X,如果X 1| 2| 3| k，（，）V*，XVN，则面临选哪一个i去匹配当前串的问题。使用不当易引起回溯。,2、句型分析过程,自顶向下分析方法 从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。,例：文法G：S cAd A ab A a 识别输入串w=cabd是否为该文法的句子,自底向上分析方法 从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。,例：文法G： S cAd A ab A a 识别输入串w=cabd是否该文法的句子,S A A c a b d c a b d c a b d 归约过程构造的推导： cAd cabd S cAd,在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”。 归约的子串应是当前句型的句柄。,3、语法树和二义性,语法树：设G=( VN,VT,P,S)为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树： 每个结点都有一个标记，此标记是V的一个符号； 根的标记是S 若某结点至少有一个子孙，并且该结点标记为A，则AVN； 若某结点标记A，其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak定是P中的一个产生式,语法树-句型推导的直观表示,给定上下文无关文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之相关的语法树(推导树) 定理： G为上下文无关文法， 对于 ，有S =* ，当且仅当 文法G有以为结果的一棵语法树(推导树),例: GS: SaAS ASbA ASS Sa Aba,句子aabbaa的语法树（推导树）,叶子结点：树中没有子孙的结点。,S,a,A,S,S,b,A,a,a,b,a,推导过程中使用产生式的顺序,例: GS: SaAS ASbA|SS|ba Sa,SaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa,一棵语法树可表示一个句子的多种可能的不同推导过程，包括最左(最右)推导。 一个句子是否只对应唯一的一棵语法树? 一个句子是否只有唯一的一个最左(最右)推导?,例：GE: E i E E+E E E*E E (E),句型 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),改写文法，消除同时存在的左右递归。,4、短语和句柄,S A且 A ，则称是句型相对于非终结符A的短语,对于文法GS： 句型的短语,句型的直接短语 若有A ，则称是句型相对于非终结符A 的直接短语 句型的句柄 一个句型的最左直接短语称为该句型的句柄,i*i+i 的短语、直接短语和句柄,E E + T T F T * F i3 短语：i1* i2+ i3， i1* i2 ， F i2 i1 ， i2 ， i3 。 i1 直接短语： i1 ， i2 ， i3 。句柄：i1,例 ： GE： EE+T|T TT*F|F F(E)|i 句型：i*i+i,GS: SaAS Sa ASbA ASS Aba,句子aabbaa的最左推导，指出此句子的全部短语、各步直接推导所得句型的句柄、该句子的句柄,练 习,通过对产生式施加不同限制，Chomsky将文法分为四类： 0型文法：对任一产生式，有V+，V*; 1型文法：对任一产生式，有| (, V+)， 仅 S除外。 或者形如A 产生式, AVN ,V+, ,V* 2型文法：对任一产生式A，都有AVN V*; 3型文法：任一产生式的形式都为AB或A (右线性)， AB或A（左线性）其中AVN ，BVN ，aVT +,2.8 文法的类型,四种文法之间的逐级“包含”关系,0型文法,1型文法,2型文法,3型文法,A hierarchy of grammars,Type 0: free or unrestricted grammars These are the most general. Productions are of the form u v where both u and v are arbitrary strings of symbols in V, with u non-null. There are no restrictions on what appears on the left or right-hand side other than the left-hand side must be non-empty. Type 1: context-sensitive grammars Productions are of the form uXw uvw where u , v and w are arbitrary strings of symbols in V, with v non-null, and X a single nonterminal. In other words, X may be replaced by v but only when it is surrounded by u and w .,Type 2: context-free grammars Productions are of the form X v where v is an arbitrary string of symbols in V, and X is a single nonterminal. Wherever you find X, you can replace with v (regardless of context). Type 3: regular grammars Productions are of the form X a or X aY where X and Y are nonterminals and a is a terminal. That is the left-hand side must be a single nonterminal and the right-hand side can be either a single terminal by itself or with a single nonterminal. These grammars are the most limited in terms of