《文法和语言》PPT课件

《《文法和语言》PPT课件》由会员分享，可在线阅读，更多相关《《文法和语言》PPT课件（76页珍藏版）》请在装配图网上搜索。

1、1第三章第三章 文法和语言文法和语言本章目的为语言的语法描述寻求工具本章目的为语言的语法描述寻求工具,以便：以便：y对源程序给出精确无二义的语法描述。（严谨、对源程序给出精确无二义的语法描述。（严谨、简洁、易读）简洁、易读）y根据语言文法的特点来指导语法分析的过程根据语言文法的特点来指导语法分析的过程y从描述语言的文法可以自动构造出可用的分析从描述语言的文法可以自动构造出可用的分析程序程序y制导语义翻译制导语义翻译2文法和语言文法和语言z预备知识预备知识z文法和语言的形式定义文法和语言的形式定义z文法的类型文法的类型z上下文无关文法及其语法树上下文无关文法及其语法树z上下文无关文法的句型分析上

2、下文无关文法的句型分析z有关文法实用中的一些说明有关文法实用中的一些说明z有关文法的一些关系3预备知识预备知识 -语言概述语言概述z语言是由句子组成的集合，是由一组记号语言是由句子组成的集合，是由一组记号所构成的集合。所构成的集合。z汉语汉语-所有符合汉语语法的句子的全体所有符合汉语语法的句子的全体z英语英语-所有符合英语语法的句子的全体所有符合英语语法的句子的全体z程序设计语言程序设计语言-所有该语言的程序的全体所有该语言的程序的全体z 每个句子构成的规律每个句子构成的规律z研究语言研究语言 每个句子的含义每个句子的含义z 每个句子和使用者的关系每个句子和使用者的关系4预备知识预备知识 -语

3、言概述语言概述研究程序设计语言研究程序设计语言 每个程序构成的规律每个程序构成的规律 每个程序的含义每个程序的含义 每个程序和使用者的关系每个程序和使用者的关系语言研究的三个方面语言研究的三个方面 语法语法 Syntax 语义语义 Semantics 语用语用 Pragmatics5预备知识预备知识 -语言概述语言概述语法语法-表示构成语言句子的各个记号之间的表示构成语言句子的各个记号之间的组合规律组合规律语义语义-表示按照各种表示方法所表示的各个表示按照各种表示方法所表示的各个记号的特定含义。（各个记号和记号所表记号的特定含义。（各个记号和记号所表示的对象之间的关系）示的对象之间的关系）语用

4、语用-表示在各个记号所出现的行为中，它表示在各个记号所出现的行为中，它们的来源、使用和影响。们的来源、使用和影响。6预备知识预备知识 -语言概述语言概述z每种语言具有两个可识别的特性，即语言每种语言具有两个可识别的特性，即语言的形式和该形式相关联的意义。的形式和该形式相关联的意义。z语言的实例若在语法上是正确的，其相关语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看，其一是该联的意义可以从两个观点来看，其一是该句子的创立者所想要表示的意义，另一是句子的创立者所想要表示的意义，另一是接收者所检验到的意义。这两个意义并非接收者所检验到的意义。这两个意义并非总是一样的，前者称为语言的语

5、义，后者总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。利用这两方面意义间的差异。7预备知识预备知识 -形式形式语言语言z如果不考虑语义和语用，即只从语法这一侧如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。言。形式语言抽象地定义为一个数学系统。“形式形式”是指这样的事实：语言的所有规则是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。形式只以什麽符号串能出现的方式来陈述。形式语言理论是对符号

6、串集合的表示法、结构及语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研其特性的研究。是程序设计语言语法分析研究的基础。究的基础。8预备知识预备知识 -有关定义和记号有关定义和记号z符号：可以相互区别的记号（元素）。符号：可以相互区别的记号（元素）。z字母表字母表：符号（元素）的非空有穷集合。：符号（元素）的非空有穷集合。z符号串：由字母表符号串：由字母表(没有没有符号的符号串符号的符号串)是是 x是是 上的符号串上的符号串,a是是 的元素的元素,则则xa是是 上的上的符号串符号串 3.y是是 上的符号串上的符号串,当且仅当它可以由当且仅当它可以由1和和2导出。导出。

7、例如：例如：=a,b =a,b ,a,b,aa,ab,aabba,a,b,aa,ab,aabba都都是是 上的符号串上的符号串9预备知识预备知识 -有关定义和记号有关定义和记号z符号串符号串s的前缀：移走符号串的前缀：移走符号串s尾部的零个或尾部的零个或多于零个符号得到的符号串多于零个符号得到的符号串.如：如：b是符号串是符号串banana的一个前缀的一个前缀.z符号串符号串s的后缀：删去符号串的后缀：删去符号串s头部的零个或头部的零个或多于零个符号得到的符号串多于零个符号得到的符号串.如如:nana是符号串是符号串banana的一个后缀的一个后缀.z符号串符号串s的子串：从的子串：从s中删去

8、一个前缀和一个中删去一个前缀和一个后缀得到的符号串后缀得到的符号串.如如:ana是符号串是符号串banana的一个子串的一个子串.10z对于每个符号串对于每个符号串s，s和和两者都两者都是符号串是符号串s的的前缀，后缀和子串。前缀，后缀和子串。z符号串符号串s的真前缀，真后缀，真子串：任何非的真前缀，真后缀，真子串：任何非空符号串空符号串 x,相应地，是相应地，是s的前缀，后缀或子串，的前缀，后缀或子串，并且并且 s x z符号串的运算符号串的运算ys的长度记为的长度记为|s|。的长度为的长度为0y连接：符号串连接：符号串x x、y y的连接的连接,是把是把y y的符号写在的符号写在x x的符

9、的符号之后得到的符号串号之后得到的符号串xy xy 如如 x=ab,y=cd x=ab,y=cd 则则 xy=abcd xy=abcd 有有a=a a=a y方幂：符号串自身连接方幂：符号串自身连接n n次得到的符号串次得到的符号串 a an n 定义为定义为 aaaa naaaa n个个a aa a1 1=a,a=a,a2 2=aa=aa则则a a0 0=11z符号串集合：若集合符号串集合：若集合A中所有元素都是某字中所有元素都是某字母表母表 上的符号串，则称上的符号串，则称A为字母表为字母表 上的符上的符号串集合。号串集合。z两个符号串集合两个符号串集合A和和B的乘积定义为的乘积定义为 A

10、B=xy|xxy|x A A且且y y B B 若若 集合集合A=ab,cdeab,cde B=0,10,1 则则 AB=ab1,ab0,cde0,cde1ab1,ab0,cde0,cde1 z使用使用 *表示表示 上的一切符号串（包括上的一切符号串（包括）组成的集合。组成的集合。*称为称为的闭包的闭包。z 上的上的除除外外的所有符号串组成的集合记为的所有符号串组成的集合记为+。+称为称为的正闭包的正闭包。12z例：例：=a,b=a,b *=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,

11、=a,b,aa,ab,ba,bb,aaa,aab,z.2*.32*13z语言：字母表语言：字母表 上上的一个语言是的一个语言是 上的一些符号上的一些符号串的集合串的集合 (上上的每个语言是的每个语言是*的一个子集的一个子集)。例如：例如：=a,b=a,b*=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab,集合集合ab,aabb,aaabbb,aab,aabb,aaabbb,an nb bn n,或或w|ww|w*且且w=aw=an nb bn n,n,n11为为字母表字母表 上上的一的一个语言。个语言。集合集合a,aa,aaa,a,aa,a

12、aa,或或w|ww|w*且且w=aw=an n,n,n1 1 为为字母表字母表 上上的一的一个语言。个语言。是一个语言。是一个语言。即即 是一个语言。是一个语言。14语言语言上上的运算的运算z设设L是（是（上的）一个语言上的）一个语言,M是（是（上的）一个语上的）一个语言言,z语言语言L和和M的并，交，差，补的并，交，差，补是一个语言。是一个语言。如如语言语言L和和M的并为的并为 L M，是一个语言是一个语言:w|w w|w is in L or is in M is in L or is in M 如：如：L1=a,b,y,z M1=1,28,9 =a,b,y,z M1=1,28,9 L1

13、M1=a,b,y,z1=a,b,y,z，1,28,9 1,28,9 z语言语言L和和M的连接的连接是一个语言，记是一个语言，记为为 LM LM=st|sst|sL且且 t tM 如：如：L1M1=a1,b1,y1,z1,a2,b2a9z9 =a1,b1,y1,z1,a2,b2a9z9 有有L =L=L。L的的n次连接次连接Ln=LL.L 15语言语言上上的运算的运算z语言语言L的的 闭包闭包记记为为 L*，L*=L0 L1 L2 .L0=，Ln=L Ln-1=Ln-1 L,n 1z语言语言L的正的正 闭包闭包记记为为 L+，L+=L1 L2 L3.L+=LL*=L*L L*=L+如：如：L1=

14、a,b,y,z M1=1,28,9 =a,b,y,z M1=1,28,9 （L1 M1 1）=a,b,y,z=a,b,y,z，1,28,91,28,9 （L1 M1 1）*=a,b,y,z=a,b,y,z，1,28,91,28,9，aa,1a,xyz,6789st.L1（L1 M1 1）*=所有字母打头的字母和数字符所有字母打头的字母和数字符号串号串 16语言的描述语言的描述z如何来描述一种语言？如何来描述一种语言？y如果语言是有穷的（只含有有穷多个句子），可如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示以将句子逐一列出来表示y如果语言是无穷的，找出语言的有穷表示。两个如果语

15、言是无穷的，找出语言的有穷表示。两个途经：途经：生成方式生成方式（文法）：语言中的每个句子可以用严（文法）：语言中的每个句子可以用严格定义的规则来构造。格定义的规则来构造。识别方式（自动机）：用一个过程，当输入的一任识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止意串属于语言时，该过程经有限次计算后就会停止并回答并回答“是是”，若不属于，要麽能停止并回答，若不属于，要麽能停止并回答“不不是是”，（要麽永远继续下去。），（要麽永远继续下去。）17文法文法 数学系统数学系统z一个形式数学系统一个形式数学系统可由下列基本成分来刻可由下列基本成分来刻画：一组基本

16、符号，一组形成规则，一组画：一组基本符号，一组形成规则，一组公理，一组推理规则。公理，一组推理规则。18文法和语言的形式定义文法和语言的形式定义z文法的定义文法的定义z推导的定义推导的定义z句型、句子、语言的定义句型、句子、语言的定义19文法的定义文法的定义z文法文法G定义为四元组（定义为四元组（VN，VT，P，S）yVN：非终结符集：非终结符集yVT：终结符集：终结符集yP：产生式（规则）集合：产生式（规则）集合yS：开始符号：开始符号VNVT=，SSVNV=V=VNVT，称为文法，称为文法G G的文法的文法符号集合符号集合20规则的定义规则的定义z规则（重写规则、产生式或生成式），是规则（

17、重写规则、产生式或生成式），是形如形如或或=的（的（，）有序对，）有序对，且且VV+，VV*。z 称为规则的左部称为规则的左部(或生成式或生成式的左部的左部)。z 称为规则的右部称为规则的右部(或生成式或生成式的右部的右部)。21文法的定义文法的定义z例例3.1 文法文法G=（VN，VT，P，S）VN=S,VT=0,1 P=S0S1,S01 S为开始符号为开始符号22文法的定义文法的定义z习惯上只将产生式写出。并有如下约定：习惯上只将产生式写出。并有如下约定：y第一条产生式的左部是开始符号第一条产生式的左部是开始符号y用尖括号括起的是非终结符，否则为终结符。用尖括号括起的是非终结符，否则为终结

18、符。或者大写字母表示非终结符，小写字母表示终结或者大写字母表示非终结符，小写字母表示终结符符yG可写成可写成GS，S是开始符号是开始符号G：SaaAb Aabab AaaAb A GS：Aabab AaaAb A SaaSb 缩写形式 GS：Aabab|a aAb|SaaSb注意：元元符号和源符号23例例3.2 文法文法G=（VN，VT，P，S）VN=标识符，字母，数字标识符，字母，数字VT=a,b,c,x,y,z,0,1,9P=a,zz 0,0,99 S=24推导的定义推导的定义z直接推导直接推导“”是文法是文法G G的产生式，若有的产生式，若有v,wv,w满足：满足：v=,w=,v=,w=

19、,其中其中VV*,V,V*则称则称v v直接推导到直接推导到w,w,记作记作 v v w w 或或w w直接归约到直接归约到v v例：例：G G：S0S1，S01 S 0S1 00S11 000S111 00001111 .VAR;BEGIN READ()END.VAR A;BEGIN READ(A)END.25推导的定义推导的定义z若存在若存在v w0 w1.wn=w,(n0)z则称则称v w，v推导出推导出w，或，或w归约到归约到vz若有若有v w，或，或v=w，z则记为则记为v w*26文法的句型、句子的定义文法的句型、句子的定义z句型句型y有文法有文法G，若，若S x，则称，则称x是文

20、法是文法G的句型。的句型。z句子句子y有文法有文法G，若，若S x，且，且xVVT T*，则称，则称x是文是文法法G的句子。的句子。例：例：G G：S0S1，S01S 0S1 00S11 000S111 00001111*27y例：例：GE E：EE+T|TEE+T|T TT TT*F|FF|F F(E)|a F(E)|aE EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a表示一切能用符号表示一切能用符号a，+，*，(和和)构成的算术表构成的算术表达式达式28文法，语言的定义文法，语言的定义z由文法由文法G生成的语言记为生成的语言记为L(G),它是文法它是文法G

21、的一切句子的集合的一切句子的集合:L(G)=x|S x，其中，其中S为文法的开始符为文法的开始符号，且号，且x VVT T*例：例：G G：S0S1，S01L(G)=0n1n|n1*29z例例3.3 文法文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEee L（G）=anbnen|n1 30 S a S BE (SaSBE)a aBEBE (SaBE)aabEBE(aBab)aabBEE(EBBE)aabbEE（bBbb)aabbeE（bEbe)aabbee（eEee)zG生成的每个串都在生成的每个串都在L(G)中中L(G)中的每个串确

22、实能被中的每个串确实能被G生成生成31z已知语言描述，写出文法已知语言描述，写出文法y例：若语言由例：若语言由0、1符号串组成，串中符号串组成，串中0和和1的的个数相同，构造其文法。个数相同，构造其文法。A 0B|1CB 1|1A|0BBC 0|0A|1CCz已知文法，写出语言描述已知文法，写出语言描述y例：例：GE E：EE+T|TEE+T|T TT TT*F|FF|F F(E)|a F(E)|a32语法语法 SyntaxSyntax 语义语义 SemanticsSemantics z偶正整数的集合0,2,4,2n,z dd.0(2，4，6，8)33文法的等价文法的等价z若若L（G1）=L（

23、G2），则称文法），则称文法G1和和G2是是等价的。等价的。如文法如文法G G1AA：A0R A0R 与与G G2SS：S0S1 S0S1 等价等价 A01 S01A01 S01 RA1 RA134文法的类型文法的类型z通过对产生式施加不同的限制，通过对产生式施加不同的限制，Chomsky将文法分为四种类型：将文法分为四种类型：y0型文法：对任一产生式型文法：对任一产生式，都有，都有(V(VN NVVT T)+，(V(VN NVVT T)*y1 1型文法：型文法：对任一产生式对任一产生式，都有，都有|，仅仅仅仅 SS除外除外y2 2型文法：型文法：对任一产生式对任一产生式，都有，都有VVN N

24、 ，(V(VN NVVT T)*y3 3型文法：型文法：任一产生式任一产生式的形式都为的形式都为AaBAaB或或AaAa，其中，其中AVAVN N ，BVBVN N ，aVaVT T35文法的类型文法的类型z例：例：1 1型（上下文有关）文法型（上下文有关）文法 文法文法GS：SaSBESaBEEBBEaBabbBbbbEbeeEee36文法的类型文法的类型z例：例：1 1型（上下文有关）文法型（上下文有关）文法 文法文法GSGS：SCDSCDAbbAAbbA CaCA CaCABaaBBaaB CbCB CbCBBbbBBbbBADaDADaD C CBDbDBDbD D DAabDAabD

25、L(G)=ww|wa,bL(G)=ww|wa,b*37文法的类型文法的类型z例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法GS：SaB|bAaB|bAAa|aS|bAAa|aS|bAABb|bS|aBBb|bS|aBB 文法文法GS：S0A|1B|00A|1B|0A0A|1B|0S0A|1B|0SB1B|1|01B|1|038文法的类型文法的类型z例：定义标识符的例：定义标识符的3 3型（正规）文法型（正规）文法 文法文法GI：I lT lTI l lT lT lTT dT dTT l lT d d39文法和语言文法和语言y0型文法产生的语言称为型文法产生的语言称为0型语言型

26、语言y1 1型文法或上下文有关文法（型文法或上下文有关文法（CSG ）产生的语产生的语言称为言称为1 1型语言型语言或上下文有关或上下文有关语言（语言（CSL）y2 2型文法或上下文无关文法（型文法或上下文无关文法（CFL ）产生的语产生的语言称为言称为2型语言型语言或上下文无关或上下文无关语言（语言（CF L）y3 3型文法或正则（正规）文法（型文法或正则（正规）文法（RG）产生的语产生的语言称为言称为3型语言型语言正则（正规）正则（正规）语言（语言（RL）40文法和语言文法和语言z四种文法之间的关系四种文法之间的关系 是将产生式做进一步是将产生式做进一步限制而定义的。限制而定义的。语言之间

27、的关系依次：有不是上下文有关语言之间的关系依次：有不是上下文有关语言的语言的0型语言，有不是上下文无关语言的型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语型语言，有不是正则语言的上下文无关语言。言。41文法和识别系统文法和识别系统z0型文法（短语文法）的能力相当于图灵机，型文法（短语文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何可以表征任何递归可枚举集，而且任何0型型语言都是递归可枚举的语言都是递归可枚举的z1型文法（上下文有关文法）：产生式的形型文法（上下文有关文法）：产生式的形式为式为1 1AA2 21 12 2，即只有，即只有A A出现在出现在1 1和

28、和2 2的上下文中时，才允许的上下文中时，才允许取代取代A A。其。其识别系统是线性界限自动机。识别系统是线性界限自动机。42 带带 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1 an 有限控制器有限控制器磁头磁头图灵机图灵机43文法的类型文法的类型z2型文法（上下文无关文法、型文法（上下文无关文法、CFG）：产生）：产生式的形式为式的形式为AA，取代取代A A时与时与A A的上下文的上下文无关。其识别系统是不确定的下推自动机。无关。其识别系统是不确定的下推自动机。z3型文法（正规文法、右线性文法）：产生型文法（正规文法、右线性文法）：产生的语言是有穷自动机（的语言是有穷自动

29、机（FA）所接受的集合）所接受的集合44上下文无关文法及其语法树上下文无关文法及其语法树z上下文无关文法有足够的能力描述现今程上下文无关文法有足够的能力描述现今程序设计语言的语法结构序设计语言的语法结构y算术表达式算术表达式y语句语句x赋值语句赋值语句x条件语句条件语句x读语句读语句x45算术表达式算术表达式上下文无关文法表示上下文无关文法表示z文法文法G=(E,+,G=(E,+,*,I,(,),P,E,I,(,),P,E P:P:E iE iE E+EE E+EE EE E*E EE (E)E (E)46条件语句条件语句上下文无关文法表示上下文无关文法表示 ififthenthen|if|i

30、fthenthenelse else 47上下文无关文法的语法树上下文无关文法的语法树z用于描述上下文无关文法的用于描述上下文无关文法的句型推导句型推导的直的直观方法观方法 例例:GS:SaASASbAASSSaAba S a A S S b A a a b a句型句型aabbaa的语法树（推导树）的语法树（推导树）叶子结点：树中没有子孙的结点。叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记，所得的句从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型为推导树的结果。也把该推导树称为该句型的语法树。型的语法树。48上下文无关文法的语法树上下文无关文法的语法

31、树z给定文法给定文法G，对于，对于G的任何句型都能构造与的任何句型都能构造与之关联的语法树（推导树）。这棵树满足之关联的语法树（推导树）。这棵树满足下列下列4个条件：个条件：1、每个结点都有一个、每个结点都有一个V中的符号作标记中的符号作标记2、根的标记是开始符号、根的标记是开始符号S3、若一结点、若一结点n至少有一个它自己除外的子孙，至少有一个它自己除外的子孙，并且并且n有标记有标记A，则，则AVVN N4、如果结点、如果结点n的直接子孙，从左到右的次序是的直接子孙，从左到右的次序是结点结点n1,n2,nk，其标记分别为，其标记分别为A1,A2,Ak，那么那么AA1A2,Ak一定是一定是P中

32、的一个产生式中的一个产生式49上下文无关文法的语法树上下文无关文法的语法树z定理：定理：G为上下文无关文法，为上下文无关文法，对于对于，有，有S ，当且仅当，当且仅当文法文法G有以有以为结果的一棵推导树。为结果的一棵推导树。*50上下文无关文法的语法树上下文无关文法的语法树z推导过程中施用产生式的推导过程中施用产生式的顺序顺序 例例:GS:SaASASbAASSSaAba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa51z最左（最右）推导：在推导的

33、任何一步最左（最右）推导：在推导的任何一步，其中，其中、是句型，都是对是句型，都是对中中的最左（右）非终结符进行替换的最左（右）非终结符进行替换z最右推导被称为规范推导。最右推导被称为规范推导。z由规范推导所得的句型称为规范句型由规范推导所得的句型称为规范句型52z问题：一个句型是否对应唯一的一棵语法问题：一个句型是否对应唯一的一棵语法树？树？53z例：例：GE:GE:E iE iE E+EE E+EE EE E*E EE (E)E (E)E E E+E E+E E E*E i E i i i i i E E E E*E E i E+E i E+E i i i i句型句型 i*i+i 的两个不

34、同的最左推导：的两个不同的最左推导：推导推导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+i54二义文法二义文法z若一个文法存在某个句子对应两棵不同的若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是语法树，则称这个文法是二义二义的。的。或者，若一个文法存在某个句子有两个不或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是同的最左（右）推导，则称这个文法是二二义义的。的。z产生某上下文无关语言的每一个文法都是产生某上下文无关语言的每一个文法都是二义的，则称此语言是二义的，则称此语言是先天

35、二义先天二义的。的。55二义文法二义文法z判定任给的一个上下文无关文法是否二义，判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的。但可语言，这两个问题是递归不可解的。但可以为无二义性寻找一组充分条件。以为无二义性寻找一组充分条件。z二义文法改造为无二义文法二义文法改造为无二义文法GE:E i GEGE:E i GE：E T|E+TE T|E+T E E+E T F|T E E+E T F|T*F F E E E E*E F E F （E E）|i|i E (E)E (E)规定优先顺序和结合律规定优先顺序

36、和结合律56句型的分析句型的分析z句型分析句型分析就是识别一个符号串是否为某文就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。法的句型，是某个推导的构造过程。z在语言的编译实现中，把完成句型分析的在语言的编译实现中，把完成句型分析的程序称为程序称为分析程序分析程序或或识别程序识别程序。分析算法。分析算法又称又称识别算法识别算法。z从左到右的分析算法从左到右的分析算法，即总是从左到右地，即总是从左到右地识别输入符号串，首先识别符号串中的最识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号。左符号，进而依次识别右边的一个符号。57句型的分析句型的分析z分析算法可分为

37、：分析算法可分为：z自上而下分析法自上而下分析法：从文法的开始符号出发，反复使用各种产从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的推导。生式，寻找与输入符号匹配的推导。z自下而上分析法自下而上分析法：从输入符号串开始，逐步进行归约，直至从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。归约到文法的开始符号。z两种方法反映了两种不同的语法树的构造两种方法反映了两种不同的语法树的构造过程过程58自上而下的语法分析自上而下的语法分析z例：文法例：文法G：S cAd A ab A a识别输入串识别输入串w=cabd是否该文法的句子是否该文法的句子SSScAdcAd a b推导

38、过程：推导过程：S cAd cabd59自下而上的语法分析自下而上的语法分析z例：文法例：文法G：S cAd A ab A a识别输入串识别输入串w=cabd是否该文法的句子是否该文法的句子SAA c a b d c a b d c a b d 规约过程：规约过程：S cAd cabd60句型分析的有关问题句型分析的有关问题1）如何选择使用哪个产生式进行推导？）如何选择使用哪个产生式进行推导？假定要被代换的最左非终结符号是假定要被代换的最左非终结符号是V，且有，且有n条规则：条规则：VA1|A2|An，那么如何确定，那么如何确定用哪个右部去替代用哪个右部去替代V？2）如何识别可归约的串？）如何

39、识别可归约的串？在自下而上的分析方法中，在分析程序工在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中选择一个子作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串串，将它归约到某个非终结符号，该子串称为称为“可归约串可归约串”61句型分析句型分析z短语、直接短语、句柄的定义：文法短语、直接短语、句柄的定义：文法GS，zS A且且A b则称则称b是句型是句型b相对相对于非终结符于非终结符A的短语。若有的短语。若有A b则称则称b是是句型句型b相对于该规则相对于该规则A b的直接短语。的直接短语。一个句型的最左直接短语称为该句型的句一个句型的最左直接短语称为该句型

40、的句柄。柄。*62句型分析句型分析 E F T T F F i1 *i2 +i3短语：短语：直接短语：直接短语：句柄：句柄：GEGE：EE+T|TEE+T|T TT TT*F|FF|F F(E)|i F(E)|i句型：句型：i i*i+ii+i63有关文法实用中的一些说明有关文法实用中的一些说明z有关文法的实用限制有关文法的实用限制z上下文无关文法中的上下文无关文法中的规则规则64有关文法的实用限制有关文法的实用限制z文法中不得含有文法中不得含有有害规则有害规则和和多余规则多余规则y有害规则：形如有害规则：形如UU的产生式。会引起文法的产生式。会引起文法的二义性的二义性y多余规则：指文法中任何

41、句子的推导都不会用多余规则：指文法中任何句子的推导都不会用到的规则到的规则x1）文法中某些非终结符不在任何规则的右部出现，）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达该非终结符称为不可到达x2）文法中某些非终结符，由它不能推出终结符号）文法中某些非终结符，由它不能推出终结符号串来，称为不可终止的串来，称为不可终止的65有关文法的实用限制有关文法的实用限制z对于文法对于文法GS，为了保证任一非终结符，为了保证任一非终结符A在句子推导中出现，必须满足如下两个条在句子推导中出现，必须满足如下两个条件：件：1）A必须在某句型中出现。必须在某句型中出现。2）必须能从必须能从A推出终

42、结符号串推出终结符号串t来。来。即即1）文法）文法GS，对，对 某两个符号串某两个符号串和和：S A 2 2）A t,tVA t,tVT T*66化简文法化简文法z例：例：GS 1)SBe SBe2)BCe BAf3)BAf AAe 4)AAe Ae5)Ae 6)CCf7)Df67上下文无关文法中的上下文无关文法中的规则规则z具有形式具有形式A的规则称为的规则称为规则，其中规则，其中AVNz某些著作和讲义中限制这种规则的出现。某些著作和讲义中限制这种规则的出现。因为因为规则会使有关文法的一些讨论和证规则会使有关文法的一些讨论和证明变得复杂明变得复杂z两种定义的唯一差别是两种定义的唯一差别是句子

43、在不在语言句子在不在语言中。中。68上下文无关文法中的上下文无关文法中的规则规则z如果语言如果语言L有一个有穷的描述，则有一个有穷的描述，则L也同样有一个有穷描述。并且可以证明，也同样有一个有穷描述。并且可以证明，若若L L是上下文有关语言、上下文无关语言或是上下文有关语言、上下文无关语言或正规语言，则正规语言，则L和和L-分别是上下分别是上下文有关语言、上下文无关语言和正规语言文有关语言、上下文无关语言和正规语言69上下文无关文法中的上下文无关文法中的规则规则z定理定理3.1 3.1 文法文法G G，任一，任一P P中的产生式中的产生式A，都有都有AVN，(VN VT)*,(,(即即可能为可

44、能为)，则，则L(G)L(G)也能这样一种文法产生，任一也能这样一种文法产生，任一产生式产生式A，只有如下两种形式：，只有如下两种形式：AVN，(VN VT)+,(,(即即)或者或者 SS且且 S S不出现在任何产生式右边不出现在任何产生式右边70上下文无关文法中的上下文无关文法中的规则规则z定理定理3.23.2G G是上下文有关文法，则存在另一个上下文是上下文有关文法，则存在另一个上下文有关文法有关文法G G1 1，L(G)=L(GL(G)=L(G1 1)，且，且G G1 1的开始符号的开始符号不出现在不出现在G G1 1的任何产生式的右边。的任何产生式的右边。若若G G为上下文无关文法或正

45、规文法，类似结为上下文无关文法或正规文法，类似结论成立。论成立。71 有关文法的一些关系z一般来说，一个集合上的（二目）关系就是某一性质，此性质对集合中的任意两个有序符号来说，或者满足，或者不满足。所定义的符号和 是符号串之间的两个关系。z我们习惯采用中缀表示法表示关系，即如果在集合中的两个元素c和d之间满足某一关系，我们就记作cRd。*72R+，R*z集合A上的一关系R,a,b,c是A的元素。若 cRc,称RaRb能得到 bRa 则称R为对称的。若由aRb和 bRc能得到 aRc 则称R为传递的。z给定任一关系R，我们定义一个新的关系 R+，称为R的传递闭包。aR1b aRb aR+b c:

46、aRc且 cRi-1b,i1 R*，称为R的自反传递闭包73FIRSTFIRST集和集和FOLLOWFOLLOW集集z设设G=(G=(VN,VT,S,P),S,P)是上下文无关文法是上下文无关文法zFIRSTFIRST（）=a|=a|a a,aV,aVT T,VV*若若 则规定则规定FRISTFRIST（）。）。zFOLLOWFOLLOW（A A）=a=a S S A A 且且a a FRISTFRIST（），），V V*，VV+若若S u A S u A ,且且 ，则，则#FOLLOW(A)#FOLLOW(A)。*74zX X V V,则则FIRST(X)=X.FIRST(X)=X.z V

47、VN N,且有产生式且有产生式X Xaa，则把，则把a a加入到加入到FIRST(X)FIRST(X)中中;若若X X也是一条产生式也是一条产生式,则把则把 也也加到加到FIRST(X)FIRST(X)中中.zX XYY是一个产生式且是一个产生式且Y Y V VN N,则把则把FIRST(Y)FIRST(Y)中中的所有非的所有非 元元素都加到素都加到FIRST(X)FIRST(X)中中;若若X X Y Y1 1Y Y2 2YYK K 是一个产生式是一个产生式,Y,Y1 1,Y,Y2 2,Y,Y(i-1)(i-1)都是非都是非终结符终结符,而且对于任何而且对于任何j,1j,1j j ii-1,F

48、IRST(Y-1,FIRST(Yj j)都含有都含有(即即Y Y1 1.Y.Y(i-1)(i-1),),则把则把FIRST(YFIRST(Yj j)中中的所有非的所有非 元素都加到元素都加到FIRST(X)FIRST(X)中中;特别是特别是,若若所有的所有的FIRST(YFIRST(Yj j,j=1,2,K)j=1,2,K)均含有均含有,则把则把 加到加到FRIST(X)FRIST(X)中中.*75FOLLOWFOLLOWzS,S,置置#于于FOLLOW(S)FOLLOW(S)中中;z B B 是一个产生式是一个产生式,则把则把 FIRST()FIRST()加至加至FOLLOW(B)FOLLOW(B)中中;z B B是一个产生式是一个产生式,或或BB是是 一个产生式而一个产生式而 (即即FIRST()FIRST()），），则把则把FOLLOWFOLLOW（A A），加至），加至FOLLOWFOLLOW（B B）中）中*76作业z3。8练习 题5，8，9，14，16z验证L(G)L(G)是匹配的括号串 G:S(S)S|(S)S|