编译原理学习课件.ppt

编译原理; 第六章我们学过自底向上分析法的关键问题是在分析过程中如何确定句柄。LR分析法与第6章介绍的运算符优先函数一样，LR方法也是通过求句柄逐步归约进行语法分析。在运算符优先函数中，句柄是通过运算符的优先关系而求得，LR方法中句柄是通过求可归前缀而求得。 ;LR分析概述;LR分析的优缺点;第七章 LR分析法 ;ＬＲ分析器模型;逻辑上说，一个LR分析器由3个部分组成： (1) 总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。 (2)?分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表也不同，分析表又可分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。 (3) 分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。 分析器的动作就是由栈顶状态和当前输入符号所决定。; 总控程序根据不同的分析表来决定其下一步的处理动作，分析表是根据具体的文法按某种规则构造出来的。LR方法是根据具体文法的分析表对输入串进行分析处理。 LR分析过程的思想是在总控程序的控制下，从左到右扫描输入符号串，根据分析栈中的状态和文法及当前输入符号，按分析表完成相应的分析工作。;分析表的组成： (1) 分析动作表Action; 表中action[Si,aj]为二维数组，指出当前栈顶为状态Si，输入符号为aj是所执行的动作。其动作有四种可能，分别为移进(S)、归约(r)、接受(acc)、出错(error)。; 符号 状态;*;*;*;3、LR分析过程： LR分析步骤： (a) 将初始状态S0和句子的左界符#分别进分析栈。 (b) 根据栈顶状态和当前输入符号查动作表，进 行如下的工作。 ※ 移进：当前输入符号进符号栈，根据状态转换表新的状态进状态栈，继续扫描，从而下一输入符号变成当前输入符号。 ※ 归约： (1)按某个产生式进行归约，若产生式的右端长度为n，则符号栈顶和状态顶n个元素同时相应退栈。(2)归约后的文法符号进符号栈，(3)查;状态转换表，新的状态进状态栈。 (c) 接受：分析成功，终止分析。 (d) 出错：报告出错信息。 (2) 具体分析过程：; LR分析算法;LR分析算法; 为了介绍LR分析过程，在这里直接给出该文法的分析表，之后再介绍如何生成该表。; 根据上述分析表，即可对输入串进行分析。如输入串为#a,b,a#具体分析过程如下：;状态栈;;例：文法G[S]为： S ?aAcBe A ?b A ?Ab B ?d;对它的逆过程最左归约(规范归约)为： ab[2]b[3]cd[4]e[1] aAb[3]cd[4]e[1] aAcd[4]e[1] aAcBe[1] S;在规范句型中形成可归前缀之前包括可归前缀的所有前缀称为活前缀。活前缀为一个或若干规范句型的前缀。在规范归约过程中的任何时刻只要已分析过的部分即在符号栈中的符号串均为规范句型的活前缀，则表明输入串的已被分析过的部分是某规范句型的一个正确部分。;G=(Vn,Vt,P,S),若有S’ ? αAω ? αβω, A ? β （ β是句柄 ） γ是αβ的前缀,则称是文法G的活前缀 αβ是含句柄的活前缀，并且句柄是αβ的后端，则称αβ是可归前缀或可规范前缀。 在LR分析过程中，实际上是把αβ的前缀（即文法G的活前缀）列出放在符号栈中，一旦在栈中出现αβ（形成可归前缀），即句柄已经形成，则用产生式A ? β进行归约。;;☆ 状态栈:;☆ 分析表 ;GOTO[Si-1, xi]=Si Si-1 ---当前状态(栈顶状态) xi --- 新的栈顶符号 Si ------ 新的栈顶状态(状态转移) Si需要满足条件是: 若X1X2…. Xi-1是由S0到Si-1所识别的规范句型的活前缀,则X1X2…. Xi是由S0到Si所识别的规范句型的活前缀 ;通过对有穷自动机的了解,我们可以看出:;b. 分析动作表(ACTION表) ;分析动作：;☆ 控制程序:(Driver Routine) ;例：文法G[E] (1)E::=E+T (2)E::=T (3)T ::=T*F (4)T::=F (5)F::=(E) (6)F::=i;ACTION表 GOTO表;ACTION 表;分析过程 ： i*i+i; 11 ＃0E1+6i5 #E+i