ch3文法和语言(张素琴).ppt

1,文法和语言的形式定义 文法的类型 上下文无关文法及其语法树 上下文无关文法的句型分析 有关文法实用中的一些说明,第三章 文法和语言 语言的词法和语法描述工具，用有穷规则描述语言的无穷句子。,3.1 文法的直观概念,采用巴克斯范式BNF，规则的集合来描述 元符号:=, ,|, , 例子p32 :=,2,高级语言都是由句子(程序)的集合组成 C语言是字母表上定义的，按照一定规则构成的字母表上基本符号串（C源程序）的集合。 字母表：是某语言基本符号的集合，如if是字母表中的一个元素，保留关键字、标示符、运算符、字母、数字和一些专用符号，如/*，；等。 符号串：字母表中符号组成的任何有穷序列。如字母表=0,1上的符号串001100,3.2 符号和符号串,符号串的头尾 z=xy是符号串，x是z的头，y是z的尾。 x非空，y是固有尾；y非空，x是固有头 例子z=abc,头,a,ab, abc z=x 符号串的方幂 x是符号串，将自身链接n次的符号串z=xxx=xn,设x=ab,则x0=,x1=ab, x2=abab,xn=xn-1x 符号串的集合 若集合A中所有元素都是某字母表上字符串。,4,符号串集合的乘积-笛卡尔乘积 集合A和B的乘积AB=xy|xA,y B A=a,b,B=c,d, AB=ac,ad,bc,bd , A=A=A 字母表集合的闭包* 定义在字母表上的所有有穷长字符串的集合。 *=0 1 2 n =0 + 正闭包 +=1 2 n =* 例子：=0,1， *=,0,1,00,01,10,11,000,无穷 +=0,1,00,01,10,11,000,5,6,3.3文法和语言的形式定义,如何来描述一种语言？ 如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示 如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经： 生成方式 （文法）：语言中的每个句子可以用严格 定义的规则来构造。 识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”；若不属于，要么能停止并回答“不是”，要么永远继续下去。,7,语言中的每个句子可以用严格定义的规则来构造。,规则：也称重写规则、产生式或生成式，是形如或 =的( ，)有序对，其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。 称为规则的左部， 称作规则的右部。 文法的定义 推导的概念 句型、句子和语言的定义,8,文法定义,文法G定义为四元组(VN，VT，P，S )其中 VN:非终结符号(或语法实体，或变量)集； VT:终结符号集； P: 规则的集合； VN，VT和P是 非空有穷集。 S:称作识别符号或开始符号的一个非终结符，它至少要在一条产生式中作为左部出现。 VN和VT不含公共的元素，即VN VT = 用V表示VN VT ，称为文法G的字母表或字汇表,9,文法的定义,例 文法G=（VN，VT，P，S） VN = S , VT = 0, 1 P= S0S1, S01 S为开始符号,例 文法G=（VN，VT，P，S） VN =标识符，字母，数字 VT =a,b,c,x,y,z,0,1,9 P= a z 0 9 S=,11,文法的写法 元符号: , = ,| , 习惯 大写字母表示非终结符 小写字母表示终结符,(1) G：SaAb Aab AaAb A,(2) GS： Aab AaAb A SaSb (3) GS:Aab |aAb | SaSb,描述文法的规则成为巴克斯范式BNF。也可以用语法图来表示。见第2章p13-15.,12,推导的定义,直接推导“” 是文法G的产生式，若有v,w满足：v=,w= , 其中V*,V* 则称v直接推导到w,记作 v w 也称w直接归约到v 例：G： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1,13,推导,. ( . ) . . ( ) VAR;BEGIN READ()END. VAR A;BEGIN READ( ) END. ( A) VAR A;BEGIN READ( ) END. VAR A;BEGIN READ( A) END. ( A),14,推导的定义,若存在v =w0 w1 . wn=w,(n0) 则记为v =+ w，称作v推导出w，或w归约到v 若有v =+ w 或 v=w， 则记为v =* w,15,例：G： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1 00S11 000S111 00001111 S =+ 00001111 S =* S 00S11 =* 00S11,16,句型、句子的定义,句型 有文法GS，若S =* x，则称x是文法G的句型。 句子 有文法GS，若S =* x，且xVT*，则称x是文法G的句子。 例：G： S0S1， S01 S 0S1 00S11 000S111 00001111 G的句型S,0S1 ,00S11 ,000S111,00001111 G的句子00001111, 01,17,句型、句子,例：GE： EE+T|T TT*F|F F(E)|a EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a 句子：用符号a，+，*，(和)构成的算术表达式,18,语言的定义,由文法G生成的语言记为L(G),它是文法G的一切句子的集合: L(G)=x|S =* x，其中S为文法的开始符号，且x VT* 例：G： S0S1， S01 L(G)=0n1n|n1,例 文法GS： （1）SaSBE （2）SaBE （3）EBBE （4）aBab （5）bBbb （6）bEbe （7）eEee L（G）= anbnen | n1 G生成的每个串都在L(G)中 L(G)中的每个串确实能被G生成,20,文法的等价,若L（G1）=L（G2），则称文法G1和G2是等价的。 如文法G1A：ADB 与G2S：S0S1 等价 ADE S01 EAB D0 B1,21,3.4文法的类型,通过对产生式施加不同的限制，Chomsky将文法分为四种类型： 0型文法：对任一产生式，都有(VNVT)+， (VNVT)* 1型文法：对任一产生式，都有|， 仅仅 S除外 2型文法：对任一产生式，都有VN 3型文法：任一产生式的形式都为AaB或Aa，其中AVN ，BVN ，aVT *,22,文法的类型,例：1型（上下文有关）文法 文法GS： SCD AbbA CaCA BaaB CbCB BbbB ADaD Ca BDbD Db AabD,23,文法的类型,例：2型（上下文无关）文法 文法GS： SAB ABS|0 BSA|1,24,3型文法,GS： S0A|1B|0 A0A|1B|0S B1B|1|0,GI： I lT I l T lT T dT T l T d,25,文法的类型,0型文法,四类文法之间的逐级“包含”关系,3型文法,26,文法和语言,0型文法产生的语言称为0型语言 1型文法或上下文有关文法（ CSG ）产生的语言称为1型语言或上下文有关语言（CSL） 2型文法或上下文无关文法（ CFG ）产生的语言称为2型语言或上下文无关语言（ CF L ） 3型文法或正则（正规）文法（ RG ）产生的语言称为3型语言正则（正规）语言（ RL ）,27,文法和语言,四种文法之间的关系 是将产生式做进一步限制而定义的。 语言之间的关系依次：有不是上下文有关语言的0型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语言。,28,形式语言理论,文法和识别系统间的关系:,0型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的 1型文法（上下文有关文法）：产生式的形式为1A212，即只有A出现在1和2的上下文中时，才允许取代A。其识别系统是线性界限自动机。,29,2型文法（上下文无关文法CFG）：产生式的形式为A，取代A时与A的上下文无关。其识别系统是不确定的下推自动机。 描述语法的构成。 3型文法（正规文法RG）：文法G= (VN,VT,P,S),其中P中的产生式的形式为AB或者A，其中A和B是非终结符号，VT* 。 产生的语言是有穷自动机（FA）所接受的集合。,复习,规则、文法、推导、句型、句子、语言 文法的等价性 文法分类 最有用的文法是上下文无关文法和正规文法,30,31,3.5上下文无关文法及其语法树,上下文无关文法(2型文法)有足够的能力描述程序设计语言的语法结构。 语法树-句型推导的直观表示。,32,语法树-句型推导的直观表示,GE： EE+T|T TT*F|F F(E)|a EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*a EE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a,33,规范推导 规范句型,最左（最右）推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换 最右推导被称为规范推导。 由规范推导所得的句型称为规范句型,34,语法树,设G=( VN,VT,P,S)为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树(推导树)(派生树）： 1. 每个结点都有一个标记，此标记是V的一个符号 2. 根的标记是S 3. 若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定AVN 4. 如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式 语法树的结果： 从左到右读出叶子的标记而构成句型。树称为该句型的语法树。,35,上下文无关文法的语法树,句型aabbaa的可能推导序列和语法树,例: 3.7文法GS: SaAS ASbA ASS Sa Aba,S a A S S b A a a b a,SaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa,36,语法树-句型推导的直观表示,给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树(推导树) 定理： G为上下文无关文法， 对于，有S =* ，当且仅当 文法G有以为结果的一棵语法树(推导树),37,一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导。 一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左(最右)推导呢?,38,例：GE: E i E E+E E E*E E (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,39,二义文法,若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的; 或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的,40,文法的二义性和语言的二义性:,文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G，其中G是二义的，但是却有L(G)=L(G)，也就是说，这两个文法所产生的语言是相同的。 二义文法改造为无二义文法: GE:E i GE： E T|E+T E E+E T F|T*F E E*E F （E）|i E (E) 引入非终结符T和F 规定算符优先性和结合性 如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。,41,3.6（上下文无关文法）句型的分析,句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。 在语言的编译实现中，把完成句型分析的程序称为(语法)分析程序或识别程序。分析算法又称识别算法。 从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。,42,句型的语法分析算法分类,自上而下分析法： 从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导，或者说，为输入串寻找一个最左推导。 自下而上分析法： 从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。,43,两种方法反映了两种语法树的构造过程,自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串。 自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树。,44,自上而下的语法分析,例：文法G： S cAd A ab A a 识别输入串w=cabd是否为该文法的句子,S S S c A d c A d a b 推导过程：S cAd cAd cabd,45,自下而上的语法分析,例：文法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,46,自上而下的语法分析存在的问题： 例子：(1)S cAd (2) A ab (3) A a 识别输入串w=cad是否为该文法的句子,若S cAd 后选择(2)扩展A，S cAd cabd 将会？ w的第二个符号可以与叶子结点a得以匹配，但第三个符号却不能与下一叶子结点d匹配，宣告分析失败。原因是在分析中对定义A的规则选择是不正确的。,S c A d a b 这时应该回朔，把A为根的子树剪掉，再试探用产生式（3）,47,自下而上的语法分析 (1)S cAd (2) A ab (3)A a 识别输入串w=cabd是否为该文法的句子,对串cabd的分析中，如果选择a用产生式(3)将a归约到了A，那么在c A b d 中无法找到一个可归约串了，最终就达不到归约到S的结果，因而也无从知道cabd是一个句子。,c a b d c A b d a,48,句型分析的有关问题,1)在自上而下的分析方法中如何选择使用哪个产生式进行推导？ 假定要被代换的最左非终结符号是B，且有n条规则：BA1|A2|An，那么如何确定用哪个右部去替代B？LL(1)文法不用回溯。确定和不确定？ 2)自下而上的分析方法中如何识别可归约的串？ 在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”。如句柄, 素短语,刻画“可归约串”-句柄、素短语,文法GS 句型的短语 S * A且 A + ，则称是句型相对于非终结符A的短语 句型的直接短语 若有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 最左素短语：i1,GE：EE+T|T TT*F|F F(E)|i 句型：i*i+i,自下而上的语法分析 在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”,(1) 选择“可归约串”是最左素短语（至少含有一个终结符的最左边的短语，且这个短语不包含别的短语） (2) 选择“可归约串”是句型的句柄称为规范归约,GE：EE+T|T TT*F|F F(E)|i,(1)句型 i*i+i 的自下而上分析，总是归约当前句型的句柄形成的规范推导序列： EE+TE+FE+iT+iT*F+iT*i+iF*i+i i*i+i (2) 句型 i*i+i 的另一种自下而上分析总是归约当前句型的最左素短语形成的推导： ET+FT+iF*F+iF*i+i i*i+i,GE：EE+T|T TT*F|F F(E)|i,E E + T T F T * F i3 F i2 句型F*i2+i3的最左素短语：i2 归约为F 句型F*F+i3的最左素短语：F*F归约为T 句型T+i最左素短语i3归约为F;句型T+F最左素短语T+F归约为E,54,3.7文法实用中的一些说明,3.7.1有关文法的实用限制-化简文法 文法中不含有有害规则和多余规则 有害规则：形如UU的产生式。会引起文法的二义性 多余规则：指文法中任何句子的推导都不会用到的规则 文法中不含有不可到达和不可终止的非终结符 1）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达。 2）文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止。,55,对于文法GS，为了保证任一非终结符A在句子推导中出现，必须满足如下两个条件： (1) A必须在某句型中出现 即有S =* A，其中，属于V* (2) 必须能够从A推出终结符号串t来 即A =* t，其中tVT*,56,例子 化简文法：GS ： 1) SBe 2) BCe D为不可到达 3) BAf C为不可终止 4) AAe 5) Ae 6) CCf 7) Df 产生式 2），6），7）为多余规则应去掉。,57,3.7.2上下文无关文法中的规则,上下文无关文法中规则具有形式A，为规则 有时需要限制。 两种定义的唯一差别是句子在不在语言中 可以证明，若L是上下文有关语言、上下文无关语言或正规语言，则L和L-分别是上下文有关语言、上下文无关语言和正规语言。,58,练习,1. 写一文法，使其语言是偶正整数的集合。 要求： 允许0打头 (2) 不允许0打头 2.证明下述文法G表达式是二义的。 表达式=a|(表达式)|表达式运算符表达式 运算符=+|-|*|/ 3. 令文法GE为： ET|E+T|E-T TF|T*F|T/F F(E)|i 证明E+T*F是它的一个句型,59,练习,4.请 给出生成下述语言的上下文无关文法： （1） anbnambm| n，m=0 (2) 1n0m 1m0n| n，m=0 5.请 给出生成下述语言的三型文法： (1) anbm|n,m=1 (2)anbmck|n,m,k=0 6.请 给出下述文法所对应的正规式： S0A|1B A1S|1 B0S|0,