资源目录
压缩包内文档预览：
编号：21836409
类型：共享资源
大小：13.06MB
格式：ZIP
上传时间：2019-09-06
上传人：QQ24****1780
认证信息
个人认证
王**（实名认证）
浙江
IP属地：浙江
25
积分
- 关 键 词：
-
大学
编译
原理
实用教程
杨德芳
课件
ppt
- 资源描述：
-
大学编译原理实用教程-杨德芳-课件PPT,大学,编译,原理,实用教程,杨德芳,课件,ppt
- 内容简介：
-
第5章 自底向上优先分析技术本章学习目标自顶向下分析法是从文法的识别符开始，试图推导出输入符号串；自底向上分析方法与自顶向下的分析方法完全相反，它从输入符号串出发，试图归约到文法的识别符。本章要点：自顶向下分析法的基本原理简单优先分析技术算符优先分析法优先函数5.1 自底向上分析方法从语法分析的角度考虑，自底向上的语法分析过程就是以输入符号串为语法树的末端结点符号串，试图向着根结点方向向上构造语法树，使识别符号正是语法树的根结点。5.1.1自底向上分析的基本思想基本思想是：对输入符号串自左向右进行扫描，并将输入符逐个移进一个后进先出的栈中，边移进边分析，一旦栈顶符号串形成某个句型的句柄或可归约串，就用该产生式的左部非终结符代替相应右部的文法符号串，称这一步为归约。重复这一过程直到归约到栈中只剩文法的开始符号则为分析成功，就确认该输入串为文法的句子。例5.1给出文法AaBbBBb|b给定某个符号串“abbb”，判定该输入串是否合法。在上例中的移进归约过程中的第7步中，栈顶中出现的符号可以认为是Bb或aBb,在归约时是用Bb还是aBb，就要作出选择，如果选择Bb，则归约的结果是aA，aA就不能再归约，必须退回重新选择，选择aBb作为可归约串。由此可见，在“移进归约”过程中，选择哪一个符号串进行归约是至关重要的。对于这个可归约串，在不同的语法分析过程中有不同的称呼，在简单优先分析中称为“句柄”，在算符优先分析中称为“素短语”。5.1.2移进归约方法一个移进归约分析器设置一个符号栈和一个输入缓冲区。当输入符号串为，分析开始时，栈和输入缓冲区的格式为：符号栈的栈底为#，输入符号串为#，其中#作为输入串的结束符。对进行分析时，将的符号从左到右逐个移进符号栈，一旦栈顶符号串与某一个产生式右部相匹配成为一个可归约串时，则将此符号串归约为一个非终结符，这个非终结符是该产生式的左部符号，当栈顶又形成一个可归约串时，则又可将此符号串归约为某个产生式左部非终结符，的符号继续逐个移进符号栈。重复这个过程，将出现如下格式：符号栈的栈底为#Z，输入符号串为#。例5.2 设文法为ZABAaAb|abBbB|c对于输入符号串aabbcc的分析过程如表5-2所示的移进归约过程，移进归约过程用算法实现的流程图见图5-2所示。：5.2简单优先分析技术自底向上优先分析分为简单优先分析法和算符优先分析法两大类。简单优先分析法的基本思想是对一个文法按一定的规则求出该文法所有的符号包括终结符和非终结符之间的优先关系，按照这种关系确定归约过程中的句柄，它的归约实际上是一种规范归约。而算符优先分析的基本思想则是只规定算符之间的优先关系，也就是只考虑终结符之间的优先关系，由于算符优先分析不考虑非终结符之间优先关系，在归约过程中只要找到可归约串就归约，并不考虑归约到哪个非终结符名，因而算符优先归约不是规范归约。说明代表优先级高于代表优先级低于=代表优先级低于简单优先分析准确、规范，但分析效率较低，实际价值不大，而算符优先分析则相反，它不是规范归约，但分析速度快，适应于表达式的分析。下面我们重点讲述简单算符优先分析技术，在下一节介绍算符优先分析法。简单优先分析法是按照文法符号的优先关系确定句柄，包括任意两个文法符号之间的优先关系、如何构造优先关系表，如何进行语法判断和编写语法分析程序。5.2.1优先关系在讲述算符优先分析之前，先介绍一种关系，称之为优先关系。设X和Y为文法G中的符号，可以是终结符或非终结符。在简单优先分析方法中，可以定义三种简单优先关系。（1）优先性等于XY表示X和Y 的优先关系相等。满足优先关系等于的定义为：当且仅当G存在产生式规则即AXY。（2）优先性低于X+Y。（3）优先性高于XY表示X的优先性比Y的优先性高。当且仅当在G中存在产生式规则即ABD，且B=+X和D=*Y。例5.3设文法S(R)|a| RT TS,T|S根据定义写出各个文法符号之间的优先关系。（1）求=关系：S(R)中(=R，R=) TS,T中，S=， ，= ，,=T（2）求关系：即非终结符在前，终结符在后。因为S(R)，RT，TS,T，TS, Ra，R从而推导出T),S),a),),）),因为TS,T中，S(R)，RT，TS,T，Ra，R所以有T,a，,，（3）求a，R得到：(T，(S,(，(a,，(，和=的定义，由文法的产生式可以求得文法符号之间的优先关系如下：1）=关系：由SbAb，A(B，BAa)可以得到：b=A,A=b，(=B, A=a， a=) 2)+(B，A=+a，可以得到：b(，b+（B；B=+a；B=+A；可得：(，(关系：由SbAb且A=+），A=+B，A=+a可以得到：）b，ab，Bb。由BAa)且A=+），且A=+a，A=+B可以得到：）a，aa，Ba上述关系可以用语法树5-3来表示。从语法树的层次关系上可以看出上面的归约关系。例如图5-3（a）中的（B是句柄，可以同时归约，所以就有（=B，而bAb在同一层，如果归约就会同时归约，则就会有b=A，和A=b。但是b和(之间的关系就是b（同样，（b），(c)，(d)图各个符号之间的关系可以通过语法树分析出来。表5-4就是例5-4的简单算符优先关系矩阵2简单优先分析法的操作步骤根据简单优先分析法的基本思想可以设计优先分析算法。构造优先关系矩阵，并把文法的产生式保存好，设置符号栈S，算法的步骤如下：（1）将输入符号串a1a2an #逐个存入符号栈S中，直到遇到栈顶符号ai的优先性下一个待输入符号 a j 时为止。（2）栈顶当前符号a i为句柄尾，由此向左在栈中找句柄的头符号a k即找到a k-1a k为止。（3）由句柄ak a2ai在文法的产生式中查找右部为ak a2ai 的产生式，若找到则用相应的左部代替句柄，若找不到则为出错，这时可断定输入串不是该文法的句子。（4）重复上述步骤直到栈中只剩文法的开始符号为止。3算法的流程图简单优先关系矩阵的判断可以用算法5-4来描述。在算法中，用到一个符号栈S，栈顶指针为i，输入符号串存放在字符数组TR中，j是下标。令#。在寻找句型的句柄时，总是先找到句柄的尾符号，然后再向前搜索其首符号。如果SiTRj，则此Si为句柄的尾部，再向前比较两个相邻符号，如果找到Sk-1*=abA若存在B=*ab，这时b和A不同时归约，则必须有S=BA，这样的句型BA中,存在相邻的非终结符B和A，所以与性质1矛盾，证明结束。注意含b的短语必含A，含A的短语不一定含b。5.3.2算符优先文法(OPG)优先关系表的构造1由直观方法构造算符优先关系这种方法就是根据运算符的优先级以及左右结合的原则，来构造算符优先关系。在通常的算符表达式求值过程中，运算次序是先算乘除后算加减。这说明了运算符是有优先级的。例如，给出一个表达式的二义性文法为：EE+E| E-E| E*E| E/E| EE|(E)|i，可以对此表达式的文法按公认的计算顺序规定优先级和结合性如下：（1）优先级最高，遵循右结合。相当于。（2）例如：232=92=512，也就是同类运算符在归约时从右向左归约。即i1i2i3为i2i3先归约。（3）*，/优先级为其次，服从左结合。相当于*、*/、/，/*。（4）对于（，）规定括号的优先性大于括号外的运算符，小于括号内的运算符，内括号的优先性对于外括号。对于句子括号#号规定与它相邻的任何运算符的优先性都比（大。此外，对于运算对象的终结符i的优先级最高。表格5-7就是算符优先关系。2由定义构造算符优先关系先定义如下两个集合：FIRSTVT(B)=b| B=+b或B=+Cb，其中表示V*中的符号串。LASTVT(B)=a| B=+a或B=+aC三种优先关系的计算为：(1)=系可以直接查看产生式的右部，对如下形式的产生式Aab 和AaBb则有a=b成立。(2)关系求出每个非终结符B的FIRSTVT(B)，观察如下产生式AaB，对于每个bFIRSTVT(B)有a关系：计算每个非终结符B的LASTVT(B)，查看如下的产生式ABb，对于每一个aLASTVT（B），则有ab成立。例5.6文法（0）E#E#（1）EE+T（2）E T（3）TT*F（4）T F（5）F PF|P（6）P （E）（7）P i计算优先关系的步骤为：1）关系：由（0）E#E#和（6）P （E）可得：#，（）下面求和，首先计算每个非终结符的FIRSTVT 集合和LASTVT集合。FIRSTVT(E)=#FIRSTVT(E)=+，*，(，iFIRSTVT(T)=*，(，iFIRSTVT(F)=，(，i表5-8定义法构造优先关系矩阵FIRSTVT(P)=(，iLASTVT(E)=#LASTVT(E)=+,*,),iLASTVT(T)=*,),iLASTVT(F)=,),iLASTVT(P)=),i逐条扫描产生式寻找终结符在前非终结符在后的相邻符号对以及非终结符在前终结符在后的相邻符号对，即：AaB和 ABb。2)关系:先列出所给出表达式的文法中终结符在前非终结符在后的所有相邻符号对，并确定相关算符的关系#E 则有：#FIRSTVT(E)+T 则有：+FIRSTVT(T)+F 则有：*FIRSTVT(F)F 则有：FIRSTVT(F)(E 则有：(#E+ 则有：LASTVT(E)+ T* 则有：LASTVT(T)*P 则有：LASTVT(P)E)则有：LASTVT(E)3由定义构造算符优先关系的算法实现对于用定义方法构造优先关系的方法可以用程序的方法来实现，这个算法是基于下面两条规则构造出来的。（1）若产生式A a或A Ba，则aFIRSTVT（A），其中A，B为非终结符，a为终结符。（2）若aFIRSTVT（B）且有产生式A B，则有aFIRSTVT（A）。算法的实现：采用的数据结构为一个布尔数组Fm,n（其中为非终结符的个数,n为终结符的个数）和一个后进先出栈STACK，用iA表示非终结符A的序号，ja表示a的序号。算法的目的是要使数组每一个元素最终取值满足：FiA，ja的值为真，当且仅当aFIRSTVT(A)。这样就求得了FIRSTVT 集合。算法的描述：pocedure INSERT(A,a) If NOT FiA,ja THEN BEGINFiA,ja:=TRUE;PUSH(A,a) ONTO STACKEND.此过程的意思是当aFIRSTVT(A)时置FiA，ja为真，并将符号对(A,a) 下推到栈中。主程序为：BEGIN(main) FOR i从1到 m,j从1到n do FiA,ja:=FALSEFOR 每个形如A a或A Ba的产生式 do INSERT(A,a)WHILE STACK非空 do BEGIN 把STACK的顶项记为(B,a) 弹出去FOR每个形如A B的产生式 doINSERT(A,a)ENDEND(main)例如：对于文法：（0）E#E#（1）EE+T（2）E T（3）TT*F（4）T F（5）F PF|P（6）P (E)（7）P i(6)(P,i）(5) (P,()(4) (F,)(3) (T,* )(2) (E,+)(1) (E,#)由产生式F P，T F，E T使栈顶（6）的内容依次变为：(F,)，(T,i)， (E,i)再无右部以E开始的产生式，所以(E,i)弹出后无进栈项，这时栈顶（5）为（P，(），同样由产生式F P，T F，E T，当前栈顶依次变化为(F,()，(T,(), (E,()。（E，(）弹出后无进栈项，此时当前栈顶（4）为（F，），由产生式T F，E T当前栈顶（4）的变化依次为：(T,)， (E,)。(E,)弹出后无进栈项。当前栈顶项（3）为（T，*），由产生式E T，栈顶项为（E，*），以下逐次弹出栈顶元素后，都再无进栈项，直到栈空。由数组布尔元素值知文法中的每个非终结符的FIRSTVT(A)集合为：FIRSTVT(E)=#FIRSTVT(E)=+,*,i,(FIRSTVT(T)=*,i,(FIRSTVT(F)=,i,(FIRSTVT(P)=i,(同样的方法可以求出每个非终结符LASTVT(A)的集合.有了文法中的每个非终结符的FIRSTVT和LASTVT后,就可以利用下列算法构造文法的优先关系表。for 每个产生式AX1X2Xn DO FOR i:=1 to n-1 do BEGIN IF Xi和Xi+1均为终结符,THEN 置XiXi+1if i n-2 且Xi和Xi+2均为终结符, 但Xi+1为非终结符THEN 置XiXi+2IF Xi为终结符,Xi+1为非终结符THEN for FIRSTVT(Xi+1)中的每个b do 置 Xib;IF Xi为非终结符，Xi+1为终结符THEN FOR LASTVT(Xi)中的每个a do 置 aXi+1;END.5.3.3算符优先分析法的算法1素短语及句型的分析因为未对非终结符定义算符优先关系，所以不能使用简单优先关系查找单个非终结符组成的句柄。因此，为了实现算符优先方法进行归约，我们不能像在规范分析中那样简单地使用“句柄”这个概念，即这种分析仍然是自底向上的，但不是严格的从左到右。因此，引进素短语的概念。素短语是算符优先分析中要涉及的一个十分重要的概念。定义 5.4素短语是至少包含一个终结符的短语，但它不能包含其他素短语。最左边的素短语称为最左素短语。例5.7 （1）EE+T（2）E T（3）TT*F（4）T F（5）F PF|P（6）P （E）（7）P i有句型#T+T*F+i#,语法树如图5-7所示。短语有：T+T*F+iT+T*FTT*Fi素短语：i和T*F最左素短语：T*F性质3 一个算符优先文法的句型的最左素短语是该句型中满足下列条件的最左子串。子串的格式为ViaiVi aiVj aj+1Vj+!，则ai-1 ai,，aiai+1,，ajaj+1。说明：在该句型中的 表示可选的。2算符优先分析算法算符优先分析算法是自下而上的语法分析方法，是对当前句型不断寻找最左素短语进行归约的过程。寻找最左素短语时，就是找到最左素短语的末尾终结符，然后向前搜索最左素短语的首终结符。图5-8是对算符优先分析算法的描述。算符优先分析算法如图5-8所示，在算符中使用了一个符号栈S，用来存放终结符和非终结符，K代表符号栈S的使用深度。k=1;Sk= #;do把下一个输入符号读进a中；if(SkVT) j=k；else j=k-1;while (Sja) do Q=Sj;if(Sj-1VT) j=j-1;else j=j-2; while Sj=Q;把Sj-1Sk归约为某个N；k=j+1;Sk=N; /*将归约后的非终结符N置于原Sj+1位置。*/if (Sjaj（2）算符优先文法在归约过程中，只考虑终结符之间的优先关系确定句柄，而与非终结符无关，只需要知道把当前句柄归约为某一个非终结符，不必知道非终结符的名字。这样就去掉了但非终结符的归约。例5.8试运用算符优先分析方法，根据下列的文法检查符号串i+i#是否是文法的合法句子。（0）E#E#（1）EE+T（2）E T（3）TT*F（4）T F（5）F PF|P（6）P （E）（7）P i例如对于输入串 (i+i)*i进行分析，其规范归约过程如表5-11所示。 例5.10已知文法为：（1）EE+T|T（2）TT*F|F（3）F（E）|i试确定F+T*i的最左素短语。根据最左素短语必须具备的条件及短语的要求（即必须包含某结点下的全部树叶）得到最左素短语为 i（该句型的最左直接短语为F）例5.11已知布尔表达式文法为：B BoT|TT TaF|FFnF|(B)|t|f该文法是算符优先文法吗？若该文法是算符优先文法，试给出输入串ntofat# 的分析过程。【解】（1）计算FIRSTVT和LASTVT集合：FIRSTVT(B)=o,a,n,(,t,fLASTVT(B)= o,a,n,t,fFIRSTVT(T)=a,n,(,t,f LASTVT(T)= a,n,t,fFIRSTVT(F)=n,(,t,f LASTVT(F)= n,t,f构造文法的算符优先关系矩阵如下表5-13所示。5.3.4实际应用中的算符优先函数及其构造在简单优先分析法中，优先关系矩阵需要占用大量的存储空间。如果某个文法有n个非终结符，则优先关系矩阵需要占据（n+1）2 个内存空间（因为有#）。 如果用优先函数来取代优先关系矩阵，则可大大的节省存储空间，只需要2(n+1)个单元存放优先函数值。1优先函数的构造设有文法G，a和b是文法的终结符如果a=b，令f(a)=g(b)如果ab，则令f(a)b，则令f(a)g(b)则称f和g为优先函数。它们的函数值可以用整数来表示。根据优先关系表构造优先函数的两种方法：一种是关系图法，另一种是由定义直接构造的方法。（1）用关系图的方法构造优先函数的步骤如下：1）对所有终结符a包括#，用有下脚标的 fa，ga为结点，画出全部n个终结符所对应的2n个结点。2）若ab或a=b，则画出一条从fa到gb的有向边；若a b，而f(a)g(b)，则令f(a)=g(b)+1。2）如果ab，而f(a)g(b)，则令g(b) = f(a) +1。3）如果a=b，而f(a)g(b)，则令f(a)=g(b)=max f(a), g(b)4）重复13直到过程收敛。如果重复过程有一个值大于2n ，则表明该算符优先文法不存在优先函数。注意：在重复13步操作时是对算符优先关系矩阵逐行扫描，并按13步修改函数f(a)和g(b)的值；这是一个迭代过程，一直进行到优先函数的值不再变化为止。或大于2n.(表明无优先函数)用关系图法定义优先函数仅适应于终结符不多的情况；而由定义直接构造优先函数可适应于任何情况，并且可以用计算机来计算。例5.13 已知文法G：EE+T|TTT*F|FF(E)|i试用关系图法和直接定义法求出本文法所对应的优先函数。【解】5.3.5 采用算符优先分析法的语法分析器的实现1设计一个自动构造优先关系表的程序设计一个自动构造优先关系表的程序，该程序的输入是算符文法G，输出是相应的优先关系表，并指出该文法是否是一个算符优先文法。（1）给定文法。G：EE+T|TTT*F|FFFP|PP(E)|i（2） 构造文法G的非终结符号的FIRSTVT集合。FIRSTVT集合是用一个布尔数组F(P,a)来表示。F是一个m行n 列的数组。m是非终结符的个数，n是终结符的个数。该算法设计一个数据结构STACK栈，用于存放相应的F（P，a）=TRUE的符号对（P，a），算法如下：BEGINFOR 任何非终结符P和终结符a对（P，a）DO FP,a:=FALSE;FOR 任何形如Pa或PQa的产生式 DO IF NOT FP,a THEN BEGIN FP,a:=TRUE；（P,a）进STACK栈 ；END；WHILE STACK 栈非空 DO BEGIN将STACK栈的栈顶元素，记为（Q，a）,并出栈；FOR 每个形如PQ的产生式DOIF NOT FP,a THEN BEGIN FP,a:=TRUE；（P,a）进STACK栈 ；END;END OF WHILE;END;(3)构造该文法的非终结符的LASTVT类似于构造FIRSTVT，LASTVT集合用一个布尔数组LP,a表示，L也是一个m行n 列的二维数组，其中m是非终结符的个数，n是非终结符的个数。构造布尔数组的算法如下：BEGINFOR 任何非终结符P和终结符a对（P，a）DO FP,a:=FALSE;FOR 任何形如P a或PaQ的产生式 DO IF NOT LP,a THEN BEGIN LP,a:=TRUE；（P,a）进STACK栈 ；END；WHILE STACK 栈非空 DO BEGIN将STACK栈的栈顶元素，记为（Q，a），并出栈；FOR 每个形如P Q的产生式DOIF NOT LP,a THEN BEGIN LP,a：=TRUE；（P,a）进STACK栈 ；END;END OF WHILE;END;（4）构造文法G的优先关系矩阵。使用文法G的任何非终结符号的LASTVT和FIRSTVT后，就可以构造文法G的优先关系表。优先关系表用一个数组Ra,b表示，R是一个n行n列的数组，n的个数就是G中非终结符的个数。其中的元素是，或空。构造算法如下：FOR 每个产生式AX1X2Xn DO FOR i:=1 to n-1 do BEGIN IF Xi和Xi+1均为终结符,THEN 置XiXi+1IF i n-2 且Xi和Xi+2均为终结符， 但Xi+1为非终结符THEN 置XiXi+2IF Xi为终结符，Xi+1为非终结符THEN FOR FIRSTVT(Xi+1)中的每个b do 置 Xib;IF Xi为非终结符，Xi+1为终结符THEN FOR LASTVT(Xi)中的每个a do 置 aXi+1;END.说明：构造优先关系表的程序设计，在程序中主要解决以下几个问题：（1）文法G的产生式的存储和输入。文法可以通过键盘输入。（2）所设计的数据结构。FIRSTVT和LASTVT；优先关系表；STACK栈。2.设计算符优先分析程序要求输入一个字符串，判断该句子是否合法，合法则输出“right”，不合法则输出“wrong”和错误信息。（1）给出文法。G：EE+T|TTT*F|FFFP|PP(E)|i（2）调用前面的分析程序构造优先关系表如表5-19所示。（3）算法优先分析算法。算符优先分析算法中使用分析栈S存放文法符号，变量p为S的栈顶指针，变量a是存放当前输入符号。ERROR为错误处理程序，分析算法如下：BEGINp:=1;Sp:=#;REPEAT将下一个输入符号读入a；IF SpVT then j:=p ELSE j:=p-1;while Sja DOBEGIN REPEAT Q：=Sj;if Sj-1 VT then j:=j-1 ELSE j:=j-2;until Sj Q;将Sj+1SP归约为一个非终结符N;p:=j+1;SP:=N;end of while;if Sj a OR Sj a then begin p:=p+1;SP:=a;endelse error;/*错误处理*/until a=#;end .5.4两种优先分析法的比较简单优先分析算法和算符优先分析技术存在很多相似之处，例如：（1）两种方法都是自下而上的语法分析法。它们对一个符号串进行分析的过程，实际上是对这个符号串进行归约的过程。在归约的每一步，它们都是要寻找句型的一个可归约串。这个可归约串，在简单优先分析技术中称为“句柄”，而在算符优先分析技术中则称为“最左素短语”。当这个可归约子串确定之后，都要去查找文法的产生式表，看是否有一个产生式的右部和这个可归约子串匹配，如果有，那么就用一个非终结符去替换可归约串。在简单优先分析方法中，它是用那个相匹配的产生式的左部符号去替换可归约串。但在算符优先分析方法中，它不管是哪一个产生式的右
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
川公网安备: 51019002004831号