搜索
1内容提要:•上下文无关文法•算符优先分析法•递归下降分析法语法分析的任务:把单词符号作为基本单位,分析程序是否为合法的程序.2第一节上下文无关文法上下文无关文法是这样一种文法:它定义的语法单位,独立于该语法单位可能出现的环境,不必考虑上下文关系.自然语言不是上下文无关文法;程序语言是上下文无关文法;1.上下文无关文法定义上下文无关文法G是一个四元式:G=(VT,VN,S,P)3VT:是一个非空有限单词集,每个元素称为终结符号.VN:是一个非空有限集,每个元素为非终结符号,代表了一种语法单位.且VT∩VN=φ.例如:表达式,短语,语句等S:是一个非终结符号,称为开始符号,S∈VN.S是文法G的最高层次的语法单位.在程序语言中,S代表了程序这一语法概念.P:是一个非空有限集,每个元素称为一条产生式;一条产生式定义了一个非终结符.产生式形式如下:Pi→αi(Pi∈VN,αi∈(VT∪VN)*)称Pi定义为αi.42文法的几点约定a)若Pi→αi1Pi→αi2Pi→αik则简写为:Pi→αi1|αi2|......|αikb)用英文大写字母串代表非终结符;英文小写字母串代表终结符;希腊字母αβ等代表由VT,VN组成的符号串;即:α,β∈(VT∪VN)*.c)一个文法,可以仅用开始符号及产生式代替.例如:表达式的文法可以定义如下:E→E+E|E-E|E*E|E/E|(E)|iE为文法的开始符号,+-*/()为终结符.53文法G与语言L(G)的关系及术语从文法初始符开始,反复用产生式右部替换左部的非终结符,直到推出的符号串全部由终结符组成.得到G所定义的各种句子.例如:E=E+E=E*E+E=i*E+E=i*i+E=i*i+i定义:若αBβ,经产生式B→λ替换后得到αλβ,称αBβ直接推出αλβ.{α,λ,β∈(VT∪VN)*},用=表示直接推出.若存在α1=α2=α3........=αn,称α1可推出αn;α1=αn表示经一步或若干步α1可推出αn.α1=αn表示经零步或若干步α1可推出αn.定义:设S是G的开始符号,若S=α,{α∈(VT∪VN)*},则称α是G的一个句型;若α∈VT*,则称α是G的一个句子.(**各概念举例)+**6定义:文法G所产生的句子的全体,为G所描述的语言,记为L(G)={α|S=α,α∈VT*}+文法G正规式VG:描述句子结构;V:描述单词结构;L(G):G的全体句子;L(V):V的全体单词.一个句型到另一个句型的推导有两种方式:最左推导和最右推导:最左推导是指每次直接推导,对句型的最左非终结符实行替换;最右推导是指每次直接推导,对句型的最右非终结符实行替换.74语法树与文法的二义性语法树可以表示句型的推导及句型的层次结构.语法树是一棵倒立树,根结点表示了文法的初始符号,每进行一步推导,树的叶结点构成的有序序列构成一个句型.例如:E=E+E=E*E+E=i*E+E=i*i+E=i*i+i可表示为:语法树可以表示同一句型的多种推导,是多种推导的共性抽象.但未必代表了同一句型的所有推导:E=E*E=E*E+E=i*E+E=i*i+E=i*i+iEEE+EE*iii语法树EEE*EE+iii8定义:若文法G的某个句型存在两个不同的语法树表示,称该文法是二义文法.因此,文法E是二义文法.二义性导致了i*i+i的两种不同运算结果:(i*i)+i以及i*(i+i).编译中应避免二义文法.E文法的二义性是因为没有规定*,+运算符的优先顺序,改进E后,得到:E→T|E+TT→F|T*FF→(E)|iE为表达式,T为项,F为因子该文法对于句子i*i+i的各种推导,对应的语法树是唯一的.EET+TFT*iFiFi95乔姆斯基文法分类定义:若G=(VT,VN,S,P)的每一个产生式型如:•α→βα,β∈(VT∪VN)*,且α至少含有一个非终结符,称G为0型文法;•α→βα,β∈(VT∪VN)*,α至少含有一个非终结符,且满足|α|≤|β|,称G为1型文法;•A→βA∈VN,β∈(VT∪VN)*,称G为2型文法(上下文无关文法);•A→αB或A→α,A,B∈VN,α∈VT*,称G为3型文法(正则文法).10第二节语法分析概述语法分析的任务:把单词符号作为基本单位,根据文法,分析源程序(字串)是否为合法的程序.1语法分析方法自下而上分析法自上而下分析法自下而上是指:根据文法,对输入字串进行归约,若能正确地归约为文法的初始符号,则表示输入字串是合法的.典型方法是算符优先分析法.自上而下是指:从文法的初始符号进行推导,若能推导出与输入字串相同的句子,则表示输入字串是合法的.典型方法是递归下降分析法.112归约栈自下而上分析的基本技术是采用归约栈,如下图所示:a1a2......an归约栈字串把输入符号依次移入栈内,当栈顶符号串形成某产生式的右部时,就归约为产生式左部非终结符;继续移入输入字串,直到栈中归约为文法初始符号S.这种方法也称为移进归约法.12例如:G:S→aAcBe分析句子abbcde是否A→b|Ab为合法的句子B→dbbcdeabcdeabbcdeaAcdeaAcdeaAbdeaAceaAcdeaAcBaAcBeS移入移入移入移入移入移入归约归约归约归约经分析,判定该句子是合法的句子.13定义:栈顶形成的某产生式候选称为归约串.在上例中,当栈中为aAb时,存在两个归约串:b及Ab,它们都可以归约为A.若使用b进行归约,栈中得到aAA,导致最终不能归约为S,因此,判定输入字串非法.这是一种错误归约,原因在于栈中同时存在多个归约串,而只有一个归约串的选择是正确的,如Ab.把Ab称为可归约串,而b为非可归约串.移进归约的关键问题,就是在栈中如何寻找可归约串.一旦能确定可归约串,句子分析的难点就迎刃而解.143分析树分析树也是一棵倒立的树,用于描述归约过程.分析树是从叶结点开始建立的,每进行一次归约,就生成相应的节点.例如,上例中的归约过程可描述为如下分析树:SaAcBeAbbd分析树1234该归约树与句子abbcde的语法树是一样的.154规范归约简介规范归约是一种较常用的自下而上分析方法.该方法实质上是最右推导的逆过程.例如:最右推导:S=aAcBe=aAcde=aAbcde=abbcde规范归约:abbcde=aAbcde=aAcde=aAcBe=S规范归约采用句柄来刻画可归约串.定义:设S为文法G的开始符号,若SαAδ且Aβ其中α,δ,β∈(VT∪VN)*=*=+则称β为句型αβδ相对于A的短语;若A→β则称β为句型αβδ相对于A的直接短语;一个句型的最左直接短语,称为句柄.16例如:设句型为aAbcde该句型有两个直接短语:Ab,dS=aAcBe=aAcdeA→Ab所以Ab为直接短语;S=aAcBe=aAbcBeB→d所以d为直接短语;注意:b不是句型aAbcde的直接短语;因此,该句型的句柄为AbcdeaAb若输入串是合法的,那么栈中内容与栈外内容的连接正好为S的一个句型.当栈顶出现句柄时就进行归约.17规范归约分析算法:(1)在栈底放入#,在输入串尾附上#;(2)逐个移入输入符号,当栈顶形成句柄时,进行归约;(3)重复(2)直到输入串已全部进栈,仅剩#,若栈中归约为#S,表示分析成功,输入串为合法的句子,否则为非法句子.这里,虽然指出对句柄进行归约,但并没有指出如何在栈中确定句柄,这是第四章的内容.##S18第三节算符优先分析法算符优先分析法是一种简单实用的自下而上分析方法,本节将详细介绍该方法,包括介绍什么是算符优先文法,优先关系表构造,可归约串的刻画与寻找方法,算符优先分析算法等内容.1算符优先文法定义1:若一个文法G的任何产生式右部,都不含两个相继出现的非终结符,则称G为算符文法.19定义2:设G是一个算符文法,任何相继出现的终结符对之间存在如下三种归约优先顺序:1)ab当且仅当G中含有型如P→......ab......或P→......aQb......的产生式;2)ab当且仅当G中含有型如P→......aR......,且Rb......或RQb......;3)ab当且仅当G中含有型如P→......Rb......,且R......a或R......aQ.优先关系可以用矩阵表示,称为优先关系表.···=+=+=+=+20定义3:若文法G的任何相继终结符对至多只满足以上关系之一,称该文法为算符优先文法.2优先关系表的构造给定一个算符优先文法,求各终结符对间的优先关系.定义:FIRSTVT(P)={a|Pa......,或PQa......}LASTVT(P)={a|P......a,或P......aQ}=+=+=+=+对每个非终结符求出这两个集合后,可按如下规则求出各终结符对之间的优先关系:1)对每一条产生式,若存在型如P→......ab......或P→......aQb......,则令ab;该关系表示ab同时归约.·212)对每一条产生式,若存在型如P→......aQ......的产生式,对所有b∈FIRSTVT(Q),令ab;该关系表示b应先于a归约为Q.·3)对每一条产生式,若存在型如P→......Qb......的产生式,对所有a∈LASTVT(Q),令ab;该关系表示a应先于b归约为Q.·示例:设文法G为:E→E+T|TT→T*F|FF→(E)|i根据定义1,这是一个算符文法.22对每个非终结符,求出:FIRSTVT(F)={(,i}LASTVT(F)={),i}FIRSTVT(T)={*,(,i}LASTVT(T)={*,),i}FIRSTVT(E)={+,*,(,i}LASTVT(E)={+,*,),i}优先关系表如下:+*()i+*(=i)i根据定义3,该文法是算符优先文法233可归约串在算符优先分析法中,用最左素短语描述可归约串.定义:素短语是一个短语,它至少含有一个终结符,且除自身之外不含更小的素短语.一个句型的最左素短语即为可归约串.例如:设文法G为:E→E+T|T句型为:F*F+iT→T*F|FF→(E)|i根据短语的定义,F*F+i有如下四个短语:其中,素短语有:F*F,i两个,最左素短语为:F*FEEEF*F+iEE+iEF*FEF*F+TTiET*F+iTF=*=*=*=*=+=+=+=+244寻找最左素短语根据定义,算符优先文法的句型必为如下形式:N1a1N2a2..............NmamNm+1其中ai∈VtNi∈VnNi可有可无.定理:一个算符优先文法G的任何句型的最左素短语,为满足如下条件的最左子串:最左素短语=Niai..............NjajNj+1且满足ai-1aiaiai+1........ajajaj+1·····因此,可以在归约栈中,通过比较优先关系,寻找最左素短语.255算符优先分析算法1)置栈底及输入串尾为#,并设#VT,VT#;栈顶终结符为θ,输入字为a;2)若θa或θa且a≠#,则a移入栈中.重复2);若θa,则在栈中寻找最左素短语,归约为N,重复2);若θ=a=#,且栈中为#N,则分析成功;否则,输入串为非法字串.·····26示例:设文法G为:E→E+T|TT→T*F|FF→(E)|i+*()i+*(=i)i优先关系表如右,分析表达式i+i*i是否为合法的表达式i+i*i##+i*i##i+i*i##Ni*i##N+移入归约移入移入27*i##N+i*i##N+Ni##N+N*归约移入移入##N+N*i归约##N+N*N归约##N+N归约##N为合法句子算符优先分析过程中,产生式以及非终结符名已不再起作用,只有优先关系表决定了分析过程.28课程设计二——赋值语句的解释程序设计实验目的：了解掌握算符优先分析的基本方法、内容；学会科学思考并解决问题，提高程序设计能力。实验内容与要求：用算符优先分