编译原理 语法分析―自底向上分析技术

编译原理CompilerPrinciples2013年9月闫雷鸣第五章语法分析——自底向上分析技术5.1引言5.1.1自底向上分析技术及识别算法1.基本思想句型分析，识别一个符号串是否是某文法的句型，是某个推导或语法分析树的构造过程。从语法分析树的角度，自底向上分析过程将以输入符号串为语法分析树的末端结点符号串，试图向着根结点方向往上构造语法分析树，使识别符号正是根结点。按自底向上分析技术，句型分析的过程是一个不断从语法分析树中剪去分支的过程。2.识别算法基于自底向上分析技术对输入符号串进行句型分析的算法称为自底向上识别算法。实现识别算法的程序称为识别程序。识别程序功能：进行句型分析(识别)。3.要解决的基本问题自底向上分析技术要解决的基本问题：在每一分析步的当前句型中，·找出要被(直接)归约的（简单）短语u·把所找出的（简单）短语u（直接）归约到哪一个非终结符号U?为什么自底向上分析技术可行？凡是句子都存在规范分析。5.1.2讨论的前提•语法分析程序的输入是中间表示形式的符号串•讨论是以压缩了的上下文无关文法为基础•分析过程是从左到右逐个符号地进行规范分析语法分析的基础文法是上下文无关文法输入和输出输入：词法分析程序的输出(属性字序列)输出：识别出是句子时，输出语法分析树或其他内部中间表示；出错时报错。5.1.3基本实现方法:移入-归约法1.基本思想分析栈顶形成要归约的短语时进行归约，当还未形成时便移入(输入符号)。分析动作：移入归约成功报错2.基本实现工具：栈3.例G[E]：E∷=E+E|E*E|(E)|i输入符号串：i*i+iE=E+E=E+i=E*E+i=E*i+i=i*i+i应用移入-归约法的分析过程如下。移入-归约法分析过程：步骤栈输入其余部分动作规则（1）#i*i+i#移入（2）#i*i+i#归约E::=i（3）#E*i+i#移入（4）#E*i+i#移入（5）#E*i+i#归约E::=i（6）#E*E+i#归约E::=E*E（7）#E+i#移入（8）#E+i#移入（9）#E+i#归约E::=i（10）#E+E#归约E::=E+E（11）#E#成功所以，输入符号串i*i+i是该文法的句子。4.是规范分析吗？为什么？移入-归约法解决了自底向上分析技术的2个基本问题？·找出要被归约的短语u·确定归约到哪个非终结符号U答案：？下例的语法分析如何？例G[E]：E∷=E+E|E*E|(E)|i输入符号串：i+i*i先规约i+i为E+E，然后才规约乘法5.2算符优先分析技术自底向上分析技术的两个基本问题：·找出被归约的短语·把被归约的短语归约为哪个非终结符号5.2.1算符优先分析技术的引进寻找被归约短语的基本思想·仅由终结符号决定归约顺序·每次只查看两个相邻的终结符号：先找出被归约短语的尾终结符号然后再找出被归约短语的头终结符号再确定归约的规则(左部非终结符号)5.2.2算符文法（OG）1.算符文法:没有形如U∷=…VW…的规则的文法，其中U、V、W∈VN。即，任意两个非终结符号之间必有终结符号（算符），不存在含两个相邻非终结符号的句型。在算符文法的基础上才能应用算符优先分析技术。例G[E]：E::=E+TE::=TT::=T*FT::=FF::=(E)F::=i2.OG重要性质：（设TVT，UVN）如果某个终结符号被包含在某个短语中，则与其相邻的非终结符号也必定被包含在同一个短语中:如果句型w中包含TU，则w中任何包含其中之T的短语也必包含其中之U;类似地，如果句型w中包含UT，则w中任何包含其中之T的短语也必包含其中之U。概括之，在任何算符文法句型中，不存在其紧前与紧后是一个非终结符号的短语。算符文法的句型必呈下形（不包含两个相邻非终结符号）:[N1]T1[N2]T2[N3]…[Nm-1]Tm-1[Nm]Tm[Nm+1]3.对C语言的简单讨论例如下定义C语言的文法不是算符文法：函数定义::=函数首部函数体条件语句::=if(表达式）语句否则部分否则部分::=else语句|ε必须对描述C语言的文法进行文法等价变换，变换成OG文法，才能应用算符分析技术。5.2.3算符优先关系与算符优先文法1.算符优先关系算符优先关系:=UUU…Tk[N]Tl……Tk[N]Tl……Tk[N]Tl…Tk=TlTkTlTkTl·定义（U、V、WVN，TVT）Tj=TiiffU::=…TjTi…或U::=…TjWTi…TjTiiffU::=…TjV…V=+Ti…或V=+WTi…TjTiiffU::=…VTi…V=+…Tj或V=+…TjW2.构造算符优先关系·画语法分析树，从语法分析树找算符优先关系。G[E]：E::=E+T|TT::=T*F|FF::=(E)|iEEE+TE+TTT*FE+TFFT*Fi(E)i(=)+(++*ii+**+*画足够多的有代表性的语法分析树可找出一切算符优先关系。不足：易遗漏或重复。·按定义，对照定义找出一切算符优先关系。Tj=TiiffU::=…TjTi…或U::=…TjWTi…TjTiiffU::=…TjV…V=+Ti…或V=+WTi…TjTiiffU::=…VTi…V=+…Tj或V=+…TjWV=U1t=U2t=…=UTtVFirstTerm+TU::=…VTi…U::=…TjV…TTi?TjT?G[E]：E::=E+T|TT::=T*F|FF::=(E)|iE=*iE=*(…T=*iT=*(…T=T*Fi++i+(+*i***(i(=)算符优先矩阵:合并了一切三类算符优先关系的矩阵。例G[E]：E::=E+T|TT::=T*F|FF::=(E)|i+＜i、+＜*、*＜(、(＜+、+＞+、+＜(算符优先矩阵：+*()i+＞＜＜＞＜*＞＞＜＞＜(＜＜＜═＜)＞＞＞i＞＞＞3.算符优先文法定义：若一个算符文法，其任何两个终结符号之间至多只有一种算符优先关系成立，则该算符文法称为算符优先文法。例G[E]：E::=E+T|TT::=T*F|FF::=(E)|i是算符优先文法。+*()i+＞＜＜＞＜*＞＞＜＞＜(＜＜＜═＜)＞＞＞i＞＞＞5.2.4算符优先文法句型的识别1.质短语质短语：句型中至少包含一个终结符号，且除它自身外不再包含其他质短语的短语。如文法G[E]：E::=E+T|TT::=T*F|FF::=(E)|i的句型E+T*F*i+i中的T*F和i是质短语。如何人工寻找句型中的质短语？先找出一切短语，再从最短的找起。E+T*F*i+i中的短语和质短语?句型分析中自动寻找质短语的思路：先从左向右寻找质短语的尾终结符号，再从右向左寻找质短语的头终结符号，即，先找优先关系(？)再找优先关系(？)2.句型的识别关于文法G[E]，对输入符号串i+(i+i)*i句型分析步骤句型关系最左质短语归约到符号1i+(i+i)*i#＜i＞+iF2F+(i+i)*i#＜+＜(＜i＞+iF3F+(F+i)*i#＜+＜(＜+＜i＞)iF4F+(F+F)*i#＜+＜(＜+＞)F+FE5F+(E)*i#＜+＜(=)＞*(E)F6F+F*i#＜+＜*＜i＞#iF7F+F*F#＜+＜*＞#F*FT8F+T#＜+＞#F+TE所以,i+(i+i)*i是文法G[E]的句子。步骤栈关系下一符号其余输入部分最左质短语0#i+i*i#1#i+i*i#i2#N+i*i#3#N+i*i#4#N+i*i#i5#N+N*i#6#N+N*i#7#N+N*i#i8#N+N*N#N*N9#N+N#N+N10#N#所以输入符号串i+(i+i)*i是文法G[E]的句子。开始置初值/*top=1,S[top]=#*/当前输入符号Rtop-1jYS[top]VNNtopjS[j]与R间无优先关系Y输出“非句子”出口NS[j]RNtop+1topRS[top]Y/*寻找质短语尾*/S[j]Qj-1jNj-1jS[j]VTYS[j]QN/*寻找质短语头*/Y调用语义子程序处理最左质短语Sj+1…Stopj+1topNS[top]/*进行归约*/Ntop=2且R=#Y出口算符优先识别程序的控制流程示意图3.*算符优先识别算法4.实现之考虑算符优先识别算法的实现,两个要点，一个是分析栈的实现，另一个是优先关系的确定。·分析栈的实现分析栈存放还不能归约的符号，可定义为：char分析栈[MaxStackDepth];但为处理方便，符号用序号代替，定义为：int分析栈[MaxStackDepth];·算符优先关系的确定关键是算符优先矩阵的存放，用数值表示优先关系：int算符优先矩阵[MaxVtNum][MaxVtNum]:1=:2:3出错：05.2.5优先函数1.优先函数的引进为减少算符优先矩阵的存储量，引进优先函数，以数值的比较代替算符优先关系的比较。优先函数是关于算符优先文法的算符优先矩阵的优先函数。并非一切算符优先矩阵都存在优先函数，但只要存在一个，就存在无数个。定义对于某个算符优先文法G的算符优先矩阵M，如果存在两个函数f与g，它们满足下列条件：假定Tj和Ti是文法G的VT中任意一对存在唯一算符优先关系的终结符号，如果Tj=Ti，则f(Tj)=g(Ti)如果TjTi，则f(Tj)＜g(Ti)如果TjTi，则f(Tj)＞g(Ti)则称f与g为文法G的对于算符优先矩阵M的(双)线性优先函数，简称优先函数。2.优先函数构造法逐次加一法Bell有向图法Martin算法例G[S]：S::=a|b|(T)T::=T,S|SG[S]:S::=a|b|(T)T::=T,S|S算符优先矩阵：ab(),ab(),=2.构造优先函数1)逐次加一法，也称Floyd法。基本思想：如果应f(Tj)=g(Ti)，但非，则让f(Tj)=g(Ti)=max(f(Tj),g(Ti))如果应f(Tj)＜g(Ti)，但非，则让g(Ti)=f(Tj)+1如果应f(Tj)＞g(Ti)，但非，则让f(Tj)=g(Ti)+1反复检查，按照优先函数的定义对函数值逐次加一，最终可以得到优先函数。步骤1置初值：全为1；步骤2判算符优先关系，修改f与g的值；步骤3判算符优先关系，修改f与g的值；步骤4判算符优先关系=，修改f与g的值；步骤5重复步骤2-4，直到过程收敛为止，这时所得的f和g为所求的一对优先函数。如果f和g的任何值都已大于2n（n为终结符号个数），则该过程不会收敛，表明不存在对于相应优先矩阵的优先函数。例对于上述文法G[S]:S::=a|b|(T)T::=T,S|S应用逐次加一法生成的算符优先函数f与g如下所示。ab(),f33132g444122)Bell基本思想：利用对有向图中一个结点所能达到的结点个数计数的办法来确定优先函数的值。例如，若TjTi，则Tj相应的结点能达到的结点将比Ti相应的结点能达到的结点更多。对于与=的情况类似，从而体现优先关系。假定某算符优先文法的VT={T1，T2，…，Tn},按此排序。Bell有向图法构造优先函数的步骤如下。步骤1作一个有向图，它具有2n个结点，上下两排各n个结点。上排结点标记为f1、f2、…、fn，下排结点标记为g1、g2、…、gn。如果TjTi，则从fj到gi画一条弧（fjgi）；如果TjTi，则从gi到fj画一条弧（gifj）；如果Tj=Ti，则既从fj到gi画一条弧（fjgi），也从gi到fj画一条弧（gifj）。步骤2关于每个结点，对从它出发可达到的结点计数，包括该结点本身在内，把此个数的数值赋给相应的结点。赋给fj的数值是f(Tj)，赋给gi的数值是g(Ti)。步骤3检查这样构造出来的函数f和g是否符合优先函数的定义，也就是说f和g的数值大小比较是否和原来的优先关系一致。如果相一致，则f和g为所求的优先函数；否则不相一致，不存在这样的优先函数。例对于文法G[S]:S::=a|b|(T)T::=T,S|Sf1f2f3f4