语法分析自底向上分析技术

5.1引言5.2算符优先分析技术5.3LR(k)分析技术本章小结第五章语法分析----自底向上分析技术5.1引言5.1.1自底向上分析技术及识别算法5.1.2讨论的前提5.1.3基本实现方法第五章语法分析----自底向上分析技术5.1引言5.1.1自底向上分析技术及识别算法基本思想是:从输入符号串出发，在每一分析步对相应句型中的某个简单短语进行归约。如果最终能归约到识别符号，则该输入符号串是相应文法的句子，否则就不是。当句型分析过程中每个分析步都对最左的简单短语进行直接归约时，自底向上分析技术的两个基本问题可以更确切地叙述为：如何找出句柄及把此句柄直接归约为哪个非终结符号。第五章语法分析----自底向上分析技术5.1引言5.1.1自底向上分析技术及识别算法5.1.2讨论的前提识别过程是从左到右、自底向上地进行的，一般都将采用规范归约；除了特别指明的以外，每一步总是对句柄——最左的简单短语进行直接归约。第五章语法分析----自底向上分析技术5.1.3基本实现方法采用自底向上分析技术时，通常以移入-归约法为基础。一般地，动作共有4类，即移入、归约、接受与报错。移入：读入下一个输入符号并把它下推进栈；归约：当栈顶的(部分)符号串形成一个句柄时，对此句柄进行直接归约；接受：当识别程序发现栈中除了栈底标志符号#外仅有识别符号，而输入也已到达右端#，则接受；报错：当识别程序察觉一个错误，因此输入符号串不是句子而无法继续识别工作时，调用一个出错处理子程序进行处理或停止。第五章语法分析----自底向上分析技术步骤栈输入动作规则（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）（11）##i#E#E*#E*i#E*E#E#E+#E+i#E+E#Ei*i+i#*i+i#*i+i#i+i#+i#+i#+i#i####移入归约移入移入归约归约移入移入归约归约接受E∷=iE∷=iE∷=E*EE∷=iE∷=E+E例5.1设有文法G[E]：E∷=E+E|E*E|(E)|i自底向上分析技术的步骤:1)找出句柄u;2)找出规则U∷=u；3)把u直接归约成U。分析技术不同,寻找句柄的方法也不同。第五章语法分析----自底向上分析技术5.2算符优先分析技术一、算符优先分析技术的引进二、算符文法三、算符优先关系与算符优先文法四、算符优先文法句型的识别五、实际应用中的算符优先分析技术第五章语法分析----自底向上分析技术一、算符优先分析技术的引进对算术表达式，运算符完全决定了运算次序，运算对象完全不起作用。因此，将文法中的终结符号看作运算符；非终结符号看作运算对象。算符优先分析技术：只在终结符号之间引进优先关系，并利用优先关系找出句柄（最左质短语）。第五章语法分析----自底向上分析技术5.2算符优先分析技术一、算符优先分析技术的引进二、算符文法定义5.1如果文法G中没有形如U∷=…VW…的规则，其中U、V、W∈VN，则该文法G称为算符文法，缩写为OG。第五章语法分析----自底向上分析技术5.2算符优先分析技术一、算符优先分析技术的引进二、算符文法三、算符优先关系与算符优先文法算符优先关系算符优先文法第五章语法分析----自底向上分析技术5.2简单优先分析技术5.2.1算符优先分析技术的引进5.2.2算符文法算符优先关系算符优先文法第五章语法分析----自底向上分析技术定义5.2设文法G是一个算符文法，Tj与Ti是两个任意的终结符号，而U,V,W∈VN，定义算符优先关系如下：Tj=Ti当且仅当文法G中存在形如U∷=…TjTi…或U∷=…TjVTi…的规则；Tj＜Ti当且仅当文法G中存在形如U∷=…TjV…的规则，其中V=Ti…或V=WTi…；Tj＞Ti当且仅当文法G中存在形如U∷=…VTi…的规则，其中V=…Tj或V=…TjW。例设有文法G[Z]:Z∷=EE∷=T|E+TT∷=F|T*FF∷=(E)|i++++i+*()i+*(=)5.2算符优先分析技术一、算符优先分析技术的引进二、算符文法三、算符优先关系与算符优先文法算符优先关系算符优先文法第五章语法分析----自底向上分析技术定义5.5设有算符文法G，如果在它的任意两个终结符号之间，算符优先关系=、＜与＞至多只有一种关系成立，则称该文法G为算符优先文法，缩写为OPG。例1文法G[Z]:Z∷=EE∷=T|E+TT∷=F|T*FF∷=(E)|i例2文法G[E]：E∷=E+E|E*E|(E)|i5.2简单优先分析技术5.2.1算符优先分析技术的引进5.2.2算符文法四、算符优先文法句型的识别质短语算符优先识别算法第五章语法分析----自底向上分析技术定义5.6设有算符文法G[Z]，(句型的)质短语定义为这样一个短语：它至少包含一个终结符号，且除它自身外不再包含其他质短语。例1文法G[Z]:Z∷=EE∷=T|E+TT∷=F|T*FF∷=(E)|i（考虑句型T+T*F+i)定理5.3一个算符优先文法句型[N1]T1[N2]…[Nn]Tn[Nn+1]的最左质短语是满足条件：Tj－1Tj=Tj+1=…=Ti－1=TiTi+1的最左子符号串[Ｎj]Tj[Nj+1]…[Ni]Ti[Ni+1]，其中的Nk(k=1,2,…，n+1)可能有也可能无。四、算符优先文法句型的识别质短语算符优先识别算法例文法G[Z]:Z∷=EE∷=T|E+TT∷=F|T*FF∷=(E)|i设有输入符号串i+(i+i)*i，试识别它是否是文法的句子。第五章语法分析----自底向上分析技术第五章语法分析----自底向上分析技术五、实际应用中的算符优先分析技术算符优先分析技术由于它的简单直观、所需存储容量小、且速度快而被广泛应用于识别各类表达式，把while、do与if之类界限符也看作运算符(称作广义运算符)，给它们优先数，则算符优先分析技术可扩充到整个语言的处理。对于C等实际的程序设计语言，只需对文法稍加修改便可应用算符优先分析技术。算符优先分析技术是一种行之有效、广为应用的分析技术。五、实际应用中的算符优先分析技术通常实际的编译程序应用算符优先分析技术实现表达式的编译时，使用的栈往往不是一个，而是两个，即运算分量栈与运算符栈，分别用来存放还不能生成目标(归约)的运算分量(标识符或常量之类终结符号)与运算符(其他终结符号)。算法框图如下：第五章语法分析----自底向上分析技术5.2算符优先分析技术第五章语法分析----自底向上分析技术第五章语法分析----自底向上分析技术5.3LR(K)分析技术5.3.1LR(K)分析技术的逻辑结构和分析过程5.3.2LR(0)分析技术5.3.3SLR(1)分析技术5.3.4LR(1)分析技术5.3.1LR(K)分析技术的逻辑结构和分析过程一、活前缀与可归前缀二、LR(K)分析技术的逻辑结构三、LR(K)分析技术的分析过程5.3.1LR(K)分析技术的逻辑结构和分析过程一、活前缀与可归前缀1、定义对于文法G[S],若S=αβ,β∈Vt*,则称α为规范前缀,又称活前缀。若α是含句柄的活前缀，并且每个句柄是α的后缀，则α为可归规范前缀，或可归前缀。例:(0)S’::=S(4)B::=C(1)S::=CbBA(5)B::=Db(2)A::=Aab(6)C::=a(3)A::=ab(7)D::=a*rr5.3.1LR(K)分析技术的逻辑结构和分析过程一、活前缀与可归前缀1、定义2、可归前缀的求法如某文法有可归前缀xAy,A∈Vn,若有规则：A::=u,则xu也是文法的可归前缀。例:设有文法G[S]:(1)S::=aAc(2)A::=Abb(3)A::=br5.3.1LR(K)分析技术的逻辑结构和分析过程二、LR(K)分析技术的逻辑结构1、逻辑结构LR(K)分析器包括：总控程序和分析表总控程序：根据不同的分析表决定下一步的处理动作。对不同的文法，总控程序都一样，只是分析表不同。分析表：是LR(K)分析技术的核心，是根据具体文法按某种规则构造出来的。图8-3LR(K)分析方法的逻辑结构5.3.1LR(K)分析技术的逻辑结构和分析过程二、LR(K)分析技术的逻辑结构1、逻辑结构2、分析表的组成(1)分析动作表：ACTION[S,y]指明当状态S与向前看符号串y相匹配时所应采取的动作。包括：移进、归约、接受、出错(2)状态转换表：GOTO[S,U]指明当状态S与非终结符号U相匹配时所转换到的下一状态。(表8-3）LR(K)分析表5.3.1LR(K)分析技术的逻辑结构和分析过程三、LR(K)分析技术的分析过程分析步骤:(1)将初始状态S0与#压进分析栈.(2)根据栈顶状态和当前输入符号查动作表进行以下工作:a.移进:当前输入符号进符号栈,新的状态进状态栈,继续扫描.b.归约:按某规则归约,若规则的右部长度n,则符号栈顶和状态栈顶n个元素同时退栈.把归约后的左部符号进符号栈,查状态转换表,新的状态进状态栈.c.接受:分析成功,结束.d.出错:报告出错信息.(3)重复(2),直到接受或出错为止.5.3.1LR(K)分析技术的逻辑结构和分析过程三、LR(K)分析技术的分析过程分析步骤:(1)将初始状态S0与#压进分析栈.(2)根据栈顶状态和当前输入符号查动作表进行以下工作:a.移进:当前输入符号进符号栈,新的状态进状态栈,继续扫描.b.归约:按某规则归约,若规则的右部长度n,则符号栈顶和状态栈顶n个元素同时退栈.把归约后的左部符号进符号栈,查状态转换表,新的状态进状态栈.c.接受:分析成功,结束.d.出错:报告出错信息.(3)重复(2),直到接受或出错为止.例:设有文法G[L]:(1)L::=E,L(2)L::=E(3)E::=a(4)E::=b分析输入串#a,b,a#5.3.2LR(0)分析技术一、基本概念二、项集规范族和特征有穷状态机三、LR(0)分析表的构造四、应用举例5.3.2LR(0)分析技术一、基本概念(1)LR(0)项定义5.14如果Ｕ∷=uv是文法G的一个规则，其中u或v可为空串，则U→u.v称为G的一个LR(0)项，简称项。完备项：圆点在整个右部之后的LR(0)项称为完备项。接受项：如果一个完备项呈Z→u.形，Z是识别符号。归约项：其余所有的完备项称归约项。不完备项：不是完备项的项。移入项：圆点之后是终结符号的不完备项。待约项：圆点之后是非终结符号的不完备项。5.3.2LR(0)分析技术一、基本概念(1)LR(0)项(2)初始项定义5.15文法G［Z］的LR(0)项Z→.u称为G的初始LR(0)项，简称初始项。5.3.2LR(0)分析技术一、基本概念(1)LR(0)项(2)初始项定义5.20文法G［Z］的LR(0)项Z→.u称为G的初始LR(0)项，简称初始项。(3)后继项定义5.16设Ｕ→u.Av是文法G的一个LR(0)项，其中A∈VN∪VT，则LR(0)项Ｕ→uA.v称为它的后继项。5.3.2LR(0)分析技术一、基本概念(4)项集定义5.17由LR(0)项组成的集合称LR(0)项集，简称项集。后继项集:如果识别程序所处状态所对应的项集中有一个项，其中圆点后面是符号X，则识别程序在该符号X下将进入所处状态的X_后继状态。相应的项集称X_后继项集。每个项集Si的后继项集S通常是基本项集的闭包集合，基本项集可直接由项集Si生成，即｛Ｕ→uA.v|Ｕ→u.Av∈Si｝5.3.2LR(0)分析技术一、基本概念(5)项集的闭包定义5.18设Si是文法G的一个项集，项集Si的闭包CLOSURE(Si)是按下列步骤构造而得的项集。步骤1Si中每个项在CLOSURE(Si)中；步骤2如果Ｕ→u.Vv∈CLOSURE(Si)，且V∷=w是一个规则，则把V→.w添入CLOSURE(Si)中；步骤3重复步骤2，直到CLOSURE(Si)不再扩大。这时所得的便是项集Si的闭包CLOSURE(Si)。5.3.2LR(0)分析技术一、基本概念二、项集规范族和特征有穷状态机一个文法G［Z］的LR(0)项集规范族的构造步骤：步骤1初始项集S0=CLO