42自底向上的语法分析 口自底向上的语法分析是从给定的符号串出发试图将它归 约为文法的开始符号 两种自底向上分析方法 优先分析法:在文法符号之间确定优先关系,根据优先关 系确定句型的句柄,进行语法分析。 LR分析法:向前查看若千个输入符号以确定下一步应采 取的语义动作 口自底向上分析也需要一个分析栈用于存放分析过程中所 得的文法符号,开始时,先将#入栈,然后逐步地将输入符 号移进栈当在栈顶形成句柄时,则进行归约否则移进下 符号如果最后所有的符号都移进分析栈并且分析栈中 只剩下井和文法的开始符号,则表明分析成功
1 4.2 自底向上的语法分析 自底向上的语法分析是从给定的符号串出发,试图将它归 约为文法的开始符号. 两种自底向上分析方法: –优先分析法：在文法符号之间确定优先关系，根据优先关 系确定句型的句柄，进行语法分析。 –LR分析法：向前查看若干个输入符号以确定下一步应采 取的语义动作。 自底向上分析也需要一个分析栈用于存放分析过程中所 得的文法符号,开始时,先将#入栈,然后逐步地将输入符 号移进栈,当在栈顶形成句柄时,则进行归约,否则移进下 一符号.如果最后所有的符号都移进分析栈并且分析栈中 只剩下#和文法的开始符号，则表明分析成功
自底向上语法分析的例子 文法:S→ABl;A-bAa;B→> asbc,输入为 baac 步骤 分析栈内容 余留符号串 下步动作 bbaacb#移进 bacb#移进 0123456789 #bb aac b#移进 #bba aco 按A→a归约 #bbA acb#按A→bA归约 #ba acb#按A→bA归约 #A acb#移进 # Aa cb#|移进 Aac b#按S→c归约 #AaS b#移进 10 AaSb 按B→aSb归约 11 #AB 按S→AB归约 #S #分析成功
2 步 骤 分析栈内容 余留符号串 下步动作 0 # bbaacb# 移进 1 #b baacb# 移进 2 #bb aacb# 移进 3 #bba acb# 按 A→a 归约 4 #bbA acb# 按 A→bA 归约 5 #bA acb# 按 A→bA 归约 6 #A acb# 移进 7 #Aa cb# 移进 8 #Aac b# 按 S→c 归约 9 #AaS b# 移进 10 #AaSb # 按 B→aSb 归约 11 #AB # 按 S→AB 归约 12 #S # 分析成功 文法: S→AB|c；A→bA|a；B→aSb|c, 输入为bbaacb 自底向上语法分析的例子
关于自底向上分析 分析动作有移进,归约报错,接受在分析的每一步,分析 动作都是由当前栈里的内容和扫描到的符号确定的 分析过程采用最左归约(规范归约),句柄肯定出现在栈 顶位置,应注意,一旦句柄在栈顶形成,则立即归约 问题1:如何确定句型的句柄?栈顶出现的某产生式右部 不一定是句柄,如前例中第7步栈顶的a不是句柄 问题2:出现句柄时选择哪一个产生式?如前例中第8步, 对于句柄c,选择S→)c还是B→>c?
3 关于自底向上分析 分析动作有:移进,归约,报错,接受.在分析的每一步,分析 动作都是由当前栈里的内容和扫描到的符号确定的. 分析过程采用最左归约(规范归约)，句柄肯定出现在栈 顶位置，应注意，一旦句柄在栈顶形成,则立即归约。 问题1: 如何确定句型的句柄？栈顶出现的某产生式右部 不一定是句柄，如前例中第7步,栈顶的a不是句柄 问题2：出现句柄时选择哪一个产生式？ 如前例中第8步, 对于句柄c，选择S→c还是B→c？
自底向上分析潜在构造了语法树 分析过程隐含地自底向上建立了一棵语法树 (1)往分析栈移入一个终结符a时,则在语法树中添加 个以a为标记的末端结点 (2)每当将栈顶符号串XX2.Xm归约为非终结符A时, 则在语法树中添加一个结点A,并将串中的符号X, X2,.Xm按自左向右的顺序作为A的孩子结点 当分析过程结束时,如果接受了输入的符号串,则一棵 完整的语法树构造成功
4 自底向上分析潜在构造了语法树 分析过程隐含地自底向上建立了一棵语法树: （1）往分析栈移入一个终结符a时，则在语法树中添加 一个以a为标记的末端结点。 （2）每当将栈顶符号串X1X2…Xm归约为非终结符A时， 则在语法树中添加一个结点A，并将串中的符号X1, X2 ,…,Xm按自左向右的顺序作为A的孩子结点。 当分析过程结束时，如果接受了输入的符号串，则一棵 完整的语法树构造成功
42.1简单优先分析法 确定句型的句柄:在文法的各个符号(包括终结符和非 终结符)之间建立优先关系,先从左到右扫描句型中的 符号,根据优先关系确定句柄的尾部(相邻的两个符号 之间具有优先关系“>”),再反向扫描确定句柄的头部 (相邻的两个符号之间具有优先关系“<”)。 、简单优先关系的定义:若文法G中存在规范句型 =。St. s,t∈V,则s,t与a的句柄之间的关系必有下述情 况之 A s t s t s t 1.s句柄中,而t2.s与均在句3s不在句柄中, 不在句柄中 柄中 而t在句柄中
5 4.2.1 简单优先分析法 确定句型的句柄：在文法的各个符号（包括终结符和非 终结符）之间建立优先关系，先从左到右扫描句型中的 符号，根据优先关系确定句柄的尾部（相邻的两个符号 之间具有优先关系“>”），再反向扫描确定句柄的头部 （相邻的两个符号之间具有优先关系“<”） 。 A … … s t ... 1. s在句柄中,而t 不在句柄中 A … … s t … ... 2. s与t均在句 柄中 A … … s t … ... 3. s不在句柄中, 而t在句柄中 一、简单优先关系的定义: 若文法G中存在规范句型 =…st…, s,tV,则s,t与的句柄之间的关系必有下述情 况之一:
简单优先文法的定义 对于上述情况,规定 情况1:s>t;情况2:s=t;情况3:s<t 4.s和均不在句柄中,由于s和t在a中相邻出现,则一定 存在另一句型,使得s和t合上述三种情况之 注意这种优先关系是不对称的 对于在任何句型中都不相邻出现的符号对规定两个 符号之间无关系 定义4.1若一文法G的任何两个符号之间至多存在一 种优先关系,且任意两个不同的产生式无相同的右部, 则称G为简单优先文法
6 简单优先文法的定义 对于上述情况，规定 情况1: s>t; 情况2: s=t; 情况3: s<t 4. s和t均不在句柄中,由于s和t在中相邻出现，则一定 存在另一句型，使得s和t符合上述三种情况之一. • 注意,这种优先关系是不对称的! • 对于在任何句型中都不相邻出现的符号对,规定两个 符号之间无关系. 定义4.1 若一文法G的任何两个符号之间至多存在一 种优先关系,且任意两个不同的产生式无相同的右部, 则称G为简单优先文法
简卓优先文举例 例44考虑文法G[E]:E→E1,E1E1T1T1T1→>T; T→T*FF;F→>(E) 由文法的产生式可直接看出: E1=+,+=T1,T=*,*=F,(=E,E=) 考查句型E+及T(E1T)的最右推导 ●E=>E>E1T>E1+工=>ET=>E1T=>E+E ●=>E+(逆序为最左归约,划线部分为句柄) E=>E1>工=>牌多>T*>T(E)=>T*(E1T 不难看出,+,+F,+以及:气(<E1 E),T1)
7 简单优先文法举例 例4.4 考虑文法G’[E]: E→E1；E1→E1+T1 |T1；T1→T； T→T*F | F；F→(E) | i 由文法的产生式可直接看出: E1 = +, +=T1，T = *，* = F，(=E，E=) 考查句型 E1+i*i 及 T*(E1+T1 )的最右推导： E=>E1=>E1+T1=>E1+T =>E1+T*F =>E1+T*i =>E1+F*i =>E1+i*i （逆序为最左归约，划线部分为句柄） E=> E1=> T1=> T =>T*F => T*(E) =>T*(E1 ) =>T*(E1+T1 ) 不难看出, +*, +*, *), T1>)
文法GE]的简单优先矩阵 可把文法的全部优先关系用一矩阵来表示例如前面 所给文法GE相应的优先矩阵为 E「E1T1「TF EE TTF+
8 E E1 T1 T F + * ( ) i E = E1 = > T1 > > T > = > F > > > + = > > i > > > 文法G’[E]的简单优先矩阵 可把文法的全部优先关系用一矩阵来表示.例如前面 所给文法G’[E]相应的优先矩阵为:
二、简单优先分析的算法 有了优先关系矩阵,就能很容易得找到一个规范句型 的句柄:依次查看当前句型X1X2…Xm相邻两个符号的 优先关系,一旦出现X+k>x1++1,x+即为句柄的尾符号, 然后从X*开始向左反向查看已扫描过的符号,直到发 现x11#
9 二、简单优先分析的算法 有了优先关系矩阵，就能很容易得找到一个规范句型 的句柄：依次查看当前句型X1X2…Xm相邻两个符号的 优先关系,一旦出现Xi+k>Xi+k+1, Xi+k即为句柄的尾符号, 然后从Xi+k开始向左反向查看已扫描过的符号,直到发 现Xi-1#
程序4-4简单优先分彻驱动程序 int parser(void) if(LeftSide /Leftside!=0 int i=0, k=0, r; stack 0=# means the production exists * r=a k++l; j;stacki=Leftside dot int j, Leftside; Else There is no production while(!IsHigher Than(stackil, r)) which matches the right side *7 Rstack++ir; r=a[k++; if(i==2 &&r==#&& stacki STARTSYSBOL) return SUCcesS: while( Is lowerThan(stacklj 1, stackljD)j-i else return ERROR; Leftside= 3 while(1); RightsideofA Production 3/*end of parser * (stackljl, stack i, i-j+1);
10 程序4-4 简单优先分析驱动程序 int parser(void){ int i=0,k=0,r;stack[0]='#'; r=a[k++]; do{ int j,LeftSide; while(!IsHigherThan(stack[i],r)) {stack[++i]=r;r=a[k++];} j=i; while(!IsLowerThan (stack[j- 1], stack[j])) j--; LeftSide= RightSideOfAProduction (stack[j],stack[i],i-j+1); if(LeftSide){ /*LeftSide!=0 means the production exists */ i=j;stack[i]=LeftSide; }else /* There is no production which matches the right side */ if(i==2 && r=='#' && stack[i] == STARTSYSBOL) return SUCCESS; else return ERROR; } while (1); } /* end of parser */