前后文无关文法和语言(姚版).ppt

1,第二章 前后文无关文法和语言,语言文法概述文法和语言的形式定义文法的类型上下文无关文法及其语法树句型的分析有关文法实用中的一些说明,本章目的,为语言的语法描述寻求工具。通过该工具，可以：掌握对源程序给精确无二义（严谨、简洁、易读）的语法描述手段之一-文法。根据语言文法的特点来指导语法分析的过程从描述语言的文法可以自动构造出可用的分析程序制导语义翻译,本章难重点,关于文法和语言的概念是形式语言的理论基础，形式语言抽象地定义为一个数学系统。形式是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。这里介绍的语言的语法描述工具正是这样的系统。,文法及语言的表示,当我们表述一种语言时，无非是说明这种语言的句子（句子：一定字符集（称字母表）上的一字符串），如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构（也就是各种属性的单词所允许的排列规则），比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用EBNF来表示这种句子的构成规则：,“我是大学生”。是汉语的一个句子,句子=主语谓语主语=代词名词代词=我你他名词=王明大学生工人英语谓语=动词直接宾语动词=是学习直接宾语=代词名词,“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。,英语句子,sentence subject This|Computers|Iverb-phrase|adverb neververb is|run|am|tellobject the|a|noun university|world|cheese|liesThis is a university.Computers run the world.I am the cheese.I never tell lies.,语言概述,语言是由句子组成的集合，是由一组记号所构成的集合。汉语-所有符合汉语语法的句子的全体英语-所有符合英语语法的句子的全体程序设计语言-所有该语言的程序的全体 语法：每个句子构成的规律研究语言 语义：每个句子的含义 语用：每个句子和使用者的关系,研究程序设计语言 语法：每个程序构成的规律 语义：每个程序的含义1、语法-表示构成语言句子的各个记号之间的组合规律。语法包括：词法规则和语法规则 例如：C语法规定了构成条件语句的各个记号的组合规律为：第一个单词（记号）必须是”if”，然后是单词”(”、表达式，.。2、语义-表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）对一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义。离开语义，语言只不过是一堆符号的集合。所谓一个语言的语义是这样的一组规则，使用它可以定义一个程序的意义。这些规则称为语义规则。阐明语义要比阐明语法难的多，现在还没有一种形式系统描述语义。,例如：我们根据C语法可以判断出声明语句”int i=999;”是正确的，但是无法判断出声明语句”int i=9999999;”是错误的，因为该语句的语法没有错误（即单词的排列顺序是对的），其错误是因为数值9999999超过了整型变量的最大允许值。这个错误就需要语义检查才能发现。如果不考虑语义，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。,有关定义和记号,符号：可以相互区别的记号（元素）。字母表：符号（元素）的非空有穷集合。符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。1.空符号串(没有符号的符号串)是上的符号串 2.若x是上的符号串,a是的元素,则xa是上的符号串 3.y是上的符号串,当且仅当它可以由1和2导出。例如：=a,b,a,b,aa,ab,aabba都是上的符号串,符号串s的头（前缀）：移走符号串s尾部的零个或多于零个符号得到的符号串.如：b是符号串banana的一个前缀.符号串s的尾（后缀）：删去符号串s头部的零个或多于零个符号得到的符号串.如:nana是符号串banana的一个后缀.符号串s的子串：从s中删去一个前缀和一个后缀得到的符号串.如:ana是符号串banana的一个子串.,符号串的运算符号串的长度：符号串中符号的个数.符号串s的长度记为|s|。的长度为0连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy 如 x=ab,y=cd 则 xy=abcd 有a=a 方幂：符号串自身连接n次得到的符号串 an 定义为 aaaa n个a a1=a,a2=aa则a0=符号串集合：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。,两个符号串集合A和B的乘积定义为 AB=xy|xA且yB若集合A=ab,cde，B=0,1 则 AB=ab1,ab0,cde0,cde1使用*表示上的一切符号串（包括）组成的集合。*称为的闭包。上的除外的所有符号串组成的集合记为+。+称为的正闭包。,例：=a,b*=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,语言是由句子组成的集合，是由一组符号所构成的集合。换言之,字母表上的一个语言是上的一些符号串的集合(字母表上的每个语言是*的一个子集)。例如：字母表=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 为字母表上的一个语言。是一个语言。即 是一个语言。,文法和语言的形式定义,如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：-生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造。-识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，（要么永远继续下去。）,文法是程序语言的生成系统，而自动机则是程序语言的识别系统；用文法可以精确地定义一个语言，并依据该文法构造出识别这个语言的自动机。因此，文法对程序语言和编译程序的构造具有重要意义，如程序语言的词法可用正规文法描述，语法可用上下文无关文法描述，而语义则要借助于上下文有关文法描述。下面给出文法的定义.进而在文法的定义的基础上,给出推导的概念,句型、句子和语言的定义.,文法和语言的形式定义,文法的定义推导的定义句型、句子、语言的定义,文法的定义,文法G定义为四元组（VN，VT，P，S）VN：非终结符集 VT：终结符集 P：产生式（规则）集合 S：开始符号VNVT=，SVNV=VNVT，称为文法G的文法符号集合,文法G定义为四元组(VN，VT，P，S)，其中 VN为非终结符号(或语法实体，或变量)集；VT为终结符号集；P为产生式(也称规则)的集合；VN，VT和P是非空有穷集。S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。VN和VT不含公共的元素，即VN VT=用V表示VN VT，称为文法G的字母表或字汇表,规则的定义,规则（重写规则、产生式或生成式），是形如或=的（，）有序对，且V+，V*。称为规则的左部(或生成式的左部)。称为规则的右部(或生成式的右部)。,文法的定义,例：文法G=（VN，VT，P，S）VN=S,VT=0,1 P=S0S1,S01 S为开始符号,终结符号是指语言不可再分的基本符号，通常是一个语言的字母表；终结符代表了语法的最小元素，是一种个体记号。非终结符号也称语法变量，它代表语法实体或语法范畴；非终结符代表一个一定的语法概念，因此，一个非终结符是一个类、一个集合。例如，在程序语言中，可以把变量、常数、“+”、“*”等看作是终结符，而像“算术表达式”这个非终结符则代表着一定算术式组成的类，如i*(i+i)、i+i+i等；也即每个非终结符代表着由一些终结符和非终结符且满足一定规则的符号串组成的集合。,文法开始符号是一个特殊的非终结符，它代表文法所定义的语言中我们最终感兴趣的语法实体，即语言的目标，而其它语法实体只是构造语言目标的中间变量；如表达式文法的语言目标是表达式，而程序语言的目标通常为程序。产生式(也称产生规则或规则)是定义语法实体的一种书写规则。一个语法实体的相关规则可能不止一个。例如，有：P1 P2 Pn 为书写方便，可将这些有相同左部的产生式合并为一个，即缩写成 P12n 其中，每个i(i=1,2,n)称为P的一个候选式，直竖“”读为“或”，它与“”一样是用来描述文法的元语言符号(即不属于的字符)。,例 文法G=（VN，VT，P，S）VN=标识符，字母，数字 VT=a,b,c,x,y,z,0,1,9 P=a,z 0,9 S=,例:试构造产生标识符的文法。解答首先，标识符是以字母开头的字母数字串，我们用L表示“字母”类非终结符，用D表示“数字”类非终结符，而用T表示“字母或数字”类非终结符，则有：Labz D019 TLD 其次，如果用S表示“字母数字串”类，则T是一字母或数字，ST也是字母数字串，即有 STST 其中，产生式STST是一种左递归形式，由它可以产生一串T。,最后，作为“标识符”的非终结符I，它或者是一单个字母，或者为一字母后跟字母数字串，即 ILLS 因此，产生标识符的文法GI为：G=(a,b,z,0,9,I,S,T,L,D,P,I)P:ILLS STST TLD Labz D019,例:写一文法，使其语言是奇数集合，但不允许出现以0打头的奇数。解答根据题意，我们可以将奇数划分为如图21所示的三个部分，即最高位允许出现19，用非终结符B表示；中间部分可以出现任意多位数字09，每一位用非终结符D表示；最低位只允许出现1、3、5、7、9等奇数，用A表示。,图21 奇数划分示意,由于中间部分可出现任意位，所以另引入了一个非终结符M，它包括最高位和中间位部分。假定开始符为N，则可得到文法GN为：G=(0,1,9,N,A,M,B,D,P,N)P:NAMA/*一位数字多位数字*/MBMD/*仅两位数字(无中间位)多于两位数字*/A13579 B123456789 D0B,推导,推导把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替。亦即：从识别符号开始，不断将当前符号串中的非终结符号替换为该符号的某个规则的右部。直到当前的符号串中所有的符号都是终结符号为止。,“我是大学生”的推导过程,开始先找=左端的带有句子的规则并把它由=右端的符号串代替，这个动作表示成：句子 主语谓语 然后在得到的串主语谓语中，选取主语或谓语，再用相应规则的=右端代替之。比如，选取了主语，并采用规则主语=代词，那么得到：主语谓语 代词谓语，重复做下去.句子：“我是大学生”的全部动作过程是：句子 主语谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生,实际上，推导过程就是对所要分析的句子进行断句（语法分析）的过程。例如，句子“我是大学生”如果符合句子的规则，则其在语法结构上必然是由两部分组成的：前一部分是主语，后一部分是谓语；又因为主语是由代词或名词组成的，所以符合上述文法的句子的前缀必是代词或名词。这样，如果所要识别的字符串的第一个单词不是或，则该句子不符合文法；否则，继续判断其后续子串是否符合谓语的语法.,推导的定义,直接推导“”是文法G的产生式，若有v,w满足：v=,w=,其中V*,V*则称v直接推导到w,记作 v w 或w直接归约到v其中“”表示直接推导出，是应用产生规则进行推导的记号。注意“”与“”不同，“”是产生式中的定义记号。直接推导是对文法符号串A中的非终结符A用相应的产生式A的右部来替换，从而得到。我们给出推导的说明如下：,例：G：S0S1，S01 S 0S1 00S11 000S111 00001111 句子 主语谓语 代词谓语 我谓语我动词直接宾语 我是直接宾语 我是名词 我是大学生,(1)如果1可直接推出2，2可直接推出3，n-1可直接推出n，即存在一个自1至n的推导序列：123n(n0)，则我们称1可推导出n，记为1 n，它表示从1出发经过一步或若干步可推导出n。(2)如果记1 1，则表示从1出发，经过0步或者若干步可推导出n；也即1 n意味着或者1 n，或者1 n。,+,*,+,*,推导的定义,例如，对下面的文法GE：EE+EE*E(E)i(3.1)其中，惟一的非终结符E可以看成是代表一类算术表达式。我们可以从E出发进行一系列的推导，如表达式i+i*i的推导如下：EE+EE+E*E E+E*iE+i*ii+i*i,文法的句型、句子的定义,句型：有文法G，若S=x，则称x是文法G的句型。句子：有文法G，若S=x，且xVT*，则称x是文法G的句子。由定义可知，仅含终结符的句型是一个句子。开始符S本身只能是文法的一个句型而不可能是一个句子；此外，上面推导出的i+i*i是文法GE的一个句子(当然也是一个句型)，而E+E、E+E*E、E+E*i和E+i*i都是文法GE的句型。例：G：S0S1，S01S 0S1 00S11 000S111 00001111G的句型S,0S1,00S11,000S111,00001111G的句子00001111,01,*,*,例：GE：EE+T|T TT*F|F F(E)|aEE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a句子：用符号a，+，*，(和)构成的算术表达式,文法，语言的定义,由文法G生成的语言记为L(G),它是文法G的一切句子的集合:L(G)=x|S=x，其中S为文法的开始符号，且xVT*例：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,S a S BE(SaSBE)a aBEBE(SaBE)aabEBE(aBab)aabBEE(EBBE)aabbEE（bBbb)aabbeE（bEbe)aabbee（eEee)G生成的每个串都在L(G)中L(G)中的每个串确实能被G生成,使用产生式(1)n-1次，得到推导序列：S=an-1S(BE)n-1，然后使用产生式(2)一次，得到：S=an-1S(BE)n-1 an(BE)n。然后从an(BE)n继续推导，总是对EB使用产生式(3)的右部进行替换，而最终在得到的串中，所有的B都先于所有的E。例如，若n=3,aaaBEBEBE aaaBBEEBE aaaBBEBEE aaaBBBEEE。即有：S=*anBnEn接着，使用产生式(4)一次，得到S=anbBn-1En，然后使用产生式(5)n-1次得到：S=anbnEn，最后使用产生式(6)一次，使用产生式(7)n-1次，得到：S=anbnen 也能证明，对于n1，串anbnen是唯一形式的终结符号串,*,*,*,*,*,已知语言描述，写出文法例：若语言由0、1符号串组成，串中0和1的个数相同，构造其文法。A 0B|1CB 1|1A|0BBC 0|0A|1CC已知文法，写出语言描述例：GE：EE+T|T TT*F|F F(E)|a,文法的等价,若L(G1)=L(G2)，则称文法G1和G2是等价的。如文法G1A：A0R 与G2S：S0S1 等价 A01 S01 RA1,文法的类型,语言学家NoamChomsky于1956年首先建立了形式语言的描述，定义了四类文法及相应的形式语言，并分别与相应的识别系统相联系，它对程序语言的设计、编译方法、计算复杂性等方面都产生了重大影响。,1、0型文法与0型语言(对应图灵机)如果文法G的每一个产生式具有下列形式：其中，V*VNV*(注：V=VNVT)，即至少含有一个非终结符；V*；则称文法G为0型文法或短语文法，记为PSG。0型文法相应的语言称为0型语言或称递归可枚举集，它的识别系统是图灵(Turing)机。,2、1型文法与1型语言(对应线性界限自动机，自然语言)文法G的每一个产生式，均在0型文法的基础上增加了字符长度上满足的限制，则称文法G为1型文法或上下文有关文法，记为CSG。1型文法相应的语言称为1型语言或上下文有关语言，它的识别系统是线性界限自动机。1型文法的另一种定义方法是文法G的每一个产生式具有下列形式：A 其中，、V*，AVN，V+；显然它满足前述定义的长度限制，但它更明确地表达了上下文有关的特性，即A必须在、的上下文环境中才能被所替换。,3、2型文法与2型语言(对应下推自动机，程序设计语言)文法G的每一个产生式具有下列形式：A 其中，AVN，V*，则称文法G为2型文法或上下文无关文法，记为CFG。2型文法相应的语言称为2型语言或上下文无关语言，它的识别系统是下推自动机。,4、3型文法与3型语言(对应有限自动机)文法G的每个产生式具有下列形式：Aa或AaB 其中，A、BVN，aVT*，则文法G称为3型文法、正规文法或右线性文法，记为RG。3型文法相应的语言为3型语言或正规语言，它的识别系统是有限自动机。3型文法还可以呈左线性形式：Aa或ABa,例：1型（上下文有关）文法 文法GS：SCDAbbA CaCABaaB CbCBBbbB ADaD C BDbD D AabD,例：2型（上下文无关）文法 文法GS：SAB ABS|0 BSA|1,例：3型（正规）文法,GS：S0A|1B|0 A0A|1B|0S B1B|1|0,GI：I lTI lT lTT dTT lT d,四类文法的关系与区别 由四类文法的定义可知，从0型文法到3型文法逐渐增加限制。13型文法都属于0型文法，2、3型文法均属于1型文法，3型文法属于2型文法。四类文法的区别如下：(1)1型文法中不允许有形如“A”的产生式存在，而2、3型文法则允许形如“A”的产生式存在；(2)0、1型文法的产生式左部存在含有终结符号的符号串或两个以上的非终结符，而2型和3型文法的产生式左部只允许是单个的非终结符号。,0型文法,四种文法之间的逐级“包含”关系,3型文法,上下文无关文法及其语法树,上下文无关文法有足够的能力描述程序设计语言的语法结构语法树-句型推导的直观表示,例文法G=(E,+,*,i,(,),P,E)其中P为：Ei,EE+E,EE*E,E(E)E表示算术表达式,i表示程序的“变量”，该文法定义了由变量，+，*,(和)组成的算术表达式的语法结构，即：变量是算术表达式；若E1和E2是算术表达式，则E1+E2，E1*E2和(E1)也是算术表达式描述一种简单赋值语句的产生式：赋值语句i=E描述条件语句的产生式：条件语句if条件then语句 if条件then语句else语句,句型、推导,GE EE+T|T TT*F|F F(E)|aEE+T T+T F+T a+T a+T*Fa+F*F a+a*F a+a*a（对所给句子a+a*a推导序列中的每一步推导都是对句型中的最左非终结符用相应产生式的右部进行替换）EE+T E+T*F E+T*a E+F*a E+a*aT+a*a F+a*a a+a*a（对所给句子a+a*a推导序列中的每一步推导都是对句型中的最右非终结符用相应产生式的右部进行替换）EE+T T+T T+T*F F+T*F F+F*Fa+F*F a+F*a a+a*a（推导序列中的每一步推导没有固定的替换规律）,规范推导,最左（最右）推导：在推导的任何一步,其中、是句型，都是对中的最左（右）非终结符进行替换最右推导被称为规范推导。由规范推导所得的句型称为规范句型,语法树,对程序语言来说，有两个问题需要解决：其一是判别程序在语法上是否正确；其二是句子的识别或分析。在编译方法中，为了便于识别或分析句子而引入了语法树这一重要的辅助工具。语法树以图示化的形式把句子分解成各个组成部分来描述或分析句子的语法结构，这种图示化的表示与所定义的文法规则完全一致，但更为直观和完整。,对文法G=(VT,VN,S,)，满足下列条件的树称为GS的语法树：(1)每个结点用GS的一个终结符或非终结符标记；(2)根结点用文法开始符S标记；(3)内部结点(指非树叶结点)一定是非终结符，如果某内部结点A有n个分支，它的所有子结点从左至右依次标记为x1、x2、xn，则Ax1x2xn一定是文法GS的一条产生式；(4)如果某结点标记为，则它必为叶结点且是其父结点的惟一子结点。,相应于一个句型的语法树是以文法的开始符S作为根结点的，并随着推导逐步展开；当某个非终结符被它对应的产生式右部的某个候选式所替换时，这个非终结符所对应的结点就产生出下一代新结点，即候选式中从左至右的每一个符号都依次顺序对应一个新结点，且每个新结点与其父结点之间都有一条连线(树枝)。在一棵语法树生长过程中的任何时刻，所有那些没有后代的树叶结点自左至右排列起来就是一个句型。,构造语法树,图2-2 句子i+i*i的语法树,GE：EE+T|T TT*F|F F(E)|aEE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a,E EE+T E+T T E E+T T F,上下文无关文法的语法树的用处,用于描述上下文无关文法句型推导的直观方法,例:GS:SaASASbAASSSaAba,S a A S S b A a a b a,句型aabbaa的语法树（推导树）,叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记连接成的文法符号串，为GS的句型。也把该推导树称为该句型的语法树。,上下文无关文法的语法树,推导过程中施用产生式的顺序,例:GS:SaASASbAASSSaAba,S a A S S b A a a b a,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,在构造语法树时可以发现，一个句型的最左推导及最右推导只是决定先生长左子树还是先生长右子树，句型推导结束时相应的语法树也随之完成，这时已不能看出是先生长左子树还是先生长右子树，所呈现的只是已经长成的这个句子或句型的语法树，这与使用文法规则进行推导是有差异的，即使用文法规则的推导过程是有先后之分的。,二义文法,文法GS的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。例如，对文法GE，句子i+i*i存在着两种最左推导或最右推导，所形成的两棵不同的语法树如图23所示。,图23 句子i+i*i的两棵不同语法树,再如，条件语句的文法GS为：GS:Sif B S Sif B S else S SA/*A指其它语句*/其中，VN=B,S,A，VT=if,else，则句型if B if B S else S所对应的两棵不同语法树见图24。因此，文法GS是二义性文法。,图24 句型 if B if B S else S 的两棵不同语法树,哪一个是正确的则取决于将单个else部分与第1个或第2个if语句结合：第1个分析树将else部分与第1个if语句结合；第2个分析树将它与第2个if语句结合。这种二义性称作悬挂else问题。可生成带有两个不同分析树的串的文法称作二义性文法。由于这个文法并不能准确地指出程序的语法结构，所以它是分析程序表示的一个严重问题。,解决二义性的基本方法,有两个解决二义性的基本方法。其一是：设置一个规则，该规则可在每个二义性情况下指出哪一个分析树（或语法树）是正确的。这样的规则称作消除二义性规则。这样的规则的用处在于：它无需修改文法（可能会很复杂）就可消除二义性；它的缺点在于语言的语法结构再也不能由文法单独提供了。例如，我们强制规定else与最近的一个if匹配。另一种方法是通过重写文法而消除二义性，将文法改变成一个强制正确分析树的构造的格式，这样就可以解决二义性了。,例如，可以把文法改写成下面无二义的文法。stmt matched _stmt|unmatched_stmt matched_stmtif expr then matched_stmt else matched_stmt|other unmatched_stmt if expr then stmt|if expr then matched_stmt else unmatched_stmt 注意，unmatched_stmt的第二个产生式的右部if expr then matched_stmt else unmatched_stmt的matched_stmt 和unmatched_stmt是不能对调的，否则仍然是二义的。,为什么文法中要保留二义性,我们总希望一个文法是无二义性的，这样，句子的分析可以按惟一确定的方式进行。但是，文法的二义性是不可判定的，即不存在一种算法，能够在有限步内判定一个文法是否为二义性的。有时候，二义性文法也可带来一定的好处，如语法分析中二义性文法的应用，从而使文法保持了简洁性。定义语言语法的文法有二义并不可怕，只要有消除二义性的规则就可以了。,句型的分析,句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。,句型的分析算法分类,自上而下分析法：从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。自下而上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。,两种方法反映了两种语法树的构造过程。,自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上地构造语法树,自上而下的语法分析,例：文法G：S cAd A ab A a识别输入串w=cabd是否为该文法的句子,SSScAdcAd a b推导过程：S cAd cAd cabd,自下而上的语法分析,例：文法G：S cAd A ab A a识别输入串w=cabd是否该文法的句子,SAA c a b d c a b d c a b d 规约过程构造的推导：cAd cabd S cAd,(1)S cAd(2)A ab(3)A a识别输入串w=cabd是否为该文法的句子自上而下的语法分析,若S cAd 后选择(3)扩展A，S cAd cad那将会？w的第二个符号可以与叶子结点a得以匹配，但第三个符号却不能与下一叶子结点d匹配，宣告分析失败（其意味着，识别程序不能为串cad构造语法树，即cad不是句子）-显然是错误的结论。导致失败的原因是在分析中对A的选择不是正确的。,S c A d a,(1)S cAd(2)A ab(3)A a识别输入串w=cabd是否为该文法的句子自下而上的语法分析,对串cabd的分析中，如果不是选择ab用产生式(2),而是选择a用产生式(3)将a归约到了A，那么最终就达不到归约到S的结果，因而也无从知道cabd是一个句子,c a b d c A b d a,句型分析的有关问题,1）在自上而下的分析方法中如何选择使用哪个产生式进行推导？假定要被代换的最左非终结符号是B，且有n条规则：BA1|A2|An，那么如何确定用哪个右部去替代B？2）在自下而上的分析方法中如何识别可归约串？在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”,刻画“可归约串”,文法GS句型的短语S=A且 A=，则称是句型相对于非终结符A的短语句型的直接短语若有A，则称是句型相对于非终结符A 的直接短语句型的句柄一个句型的最左直接短语称为该句型的句柄,*,+,一个有用的定理,定义：由某一结点及其所属分支组成的部分树称为原树的一颗子树。只有单层分支的子树称为简单子树。定理：1.每个句型都有一颗语法树，每个语法树的叶组成一句型。2.每棵子树的叶组成短语，每颗简单子树的叶组成简单短语，最左简单子树的叶组成句柄。3.用语法树可证明每个句子都有一规范推导。,例：i*i+i 的短语、直接短语和句柄,E E+T T FT*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,句型:(T+i)*i+F,短语：1.(T+i)*i+F 2.(T+i)*i 3.(T+i)4.T+i 5.T 6.第一个i 7.第二个i 8.F,简单短语：T,第一个i,第二个i,F,句柄：T,左递归规则,GS:SSa Sb L=ban|n0W=baa S S a S a b,直接左递归 若 P P|、V*且不以P开头一般左递归 若 P=*P SAa ASb,本章小结,1.本章出现的概念较多,应重点理解文法,推导,句型句子及语言的定义等概念.语法分析有关内容在后面章节会详细讨论.2.文法作为程序语言的语法的描述工具,它用规则只能陈述的是:语言的所有句子以什麽样的符号串能出现.请记住文法和语言的形式定义中的“形式”的含义只涉及语言的语法不涉及语言的语义.3.本章内容是形式语言理论的一部分.形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。,考察本章知识点最典型的题目是 1.已知文法GA，写出它定义的语言描述 如：GA:A 0B|1C B 1|1A|0BB C 0|0A|1CC答案:GA定义的语言由0、1符号串组成，串中0和1的个数相同.2.给出语言描述，构造文法.如：构造一文法,其定义的语言是由算符+,*,(,)和运算对象a构成的算术表达式的集合.答案1:GE EE+T|T TT*F|F F(E)|a答案2:GE EE+E|E*E|(E)|a,相关术语的回顾（英文版）,上下文无关文法A context free grammar(grammar for short)consists of terminals,nonterminals,a start symbol,and productions.Terminals are the basic symbols from which strings are formed.Nonterminals are syntactic variables that denote sets of strings that help define the language generated by the grammar.In a grammar,one nonterminal is distinguished as the start symbol,and the set of strings it denotes is the language defined by the grammar.The productions of a grammar specify the manner in which the terminals and nonterminals can be combined to form string.,句型句子和语言,Given a grammar G with start symbol S,we can use the=*relation to define L(G),the language generated by G.Strings in L(G)may contain only terminal symbols of G.We say a string of terminals w is in L(G)if and only if S=*w.The string w is called a sentence of G.If S=*,wher may contain nonterminals then we say that is a sentential form of G,验证文法生成的语言,A proof that a grammar G generates a language L has two parts:we must show that every string generated by G is in L,and coversely that every string in L can indeed be generated by G.,语法树和推导,A parse tree may be viewed as a graphical representation for a derivation that filt out the choice regarding replacement order.The leaves of the parse tree are labeled by nonterminals or terminals and,read from left to right,they constitute a sentential form,called the yield or frontier of the tree.,句型分析，语法分析,Parsing is the process of determing if a string of token can be generated by a grammar.Most parsing methods fall into one of two classes,called the top-down and bottom-up methods.These terms refer to the order in which nodes in the parse tree are constructed.In the former,construction starts at the root and proceeds towards the leaves,while,in the later,construction starts at the leaves and proceeds towards the root.,二义性,A grammar that produces more than one parse tree for some setence is said to be ambiguous.Put another way,an ambiguous grammar is one that produces more than one leftmost or more than rightmost derivation for th