资源目录
压缩包内文档预览：(预览前20页/共101页)
编号：21836409
类型：共享资源
大小：13.06MB
格式：ZIP
上传时间：2019-09-06
上传人：QQ24****1780
认证信息
个人认证
王**（实名认证）
浙江
IP属地：浙江
25
积分
- 关 键 词：
-
大学
编译
原理
实用教程
杨德芳
课件
ppt
- 资源描述：
-
大学编译原理实用教程-杨德芳-课件PPT,大学,编译,原理,实用教程,杨德芳,课件,ppt
- 内容简介：
-
第5章 自底向上优先分析技术,本章学习目标,自顶向下分析法是从文法的识别符开始，试图推导出输入符号串；自底向上分析方法与自顶向下的分析方法完全相反，它从输入符号串出发，试图归约到文法的识别符。本章要点： 自顶向下分析法的基本原理 简单优先分析技术 算符优先分析法 优先函数,从语法分析的角度考虑，自底向上的语法分析过程就是以输入符号串为语法树的末端结点符号串，试图向着根结点方向向上构造语法树，使识别符号正是语法树的根结点。,5.1.1自底向上分析的基本思想,基本思想是：对输入符号串自左向右进行扫描，并将输入符逐个移进一个后进先出的栈中，边移进边分析，一旦栈顶符号串形成某个句型的句柄或可归约串，就用该产生式的左部非终结符代替相应右部的文法符号串，称这一步为归约。重复这一过程直到归约到栈中只剩文法的开始符号则为分析成功，就确认该输入串为文法的句子。,例5.1给出文法AaBb BBb|b 给定某个符号串“abbb”，判定该输入串是否合法。,在上例中的移进归约过程中的第7步中，栈顶中出现的符号可以认为是Bb或aBb,在归约时是用Bb还是aBb，就要作出选择，如果选择Bb，则归约的结果是aA，aA就不能再归约，必须退回重新选择，选择aBb作为可归约串。 由此可见，在“移进归约”过程中，选择哪一个符号串进行归约是至关重要的。对于这个可归约串，在不同的语法分析过程中有不同的称呼，在简单优先分析中称为“句柄”，在算符优先分析中称为“素短语”。,5.1.2移进归约方法,一个移进归约分析器设置一个符号栈和一个输入缓冲区。当输入符号串为，分析开始时，栈和输入缓冲区的格式为：符号栈的栈底为#，输入符号串为#，其中#作为输入串的结束符。 对进行分析时，将的符号从左到右逐个移进符号栈，一旦栈顶符号串与某一个产生式右部相匹配成为一个可归约串时，则将此符号串归约为一个非终结符，这个非终结符是该产生式的左部符号，当栈顶又形成一个可归约串时，则又可将此符号串归约为某个产生式左部非终结符，的符号继续逐个移进符号栈。重复这个过程，将出现如下格式：符号栈的栈底为#Z，输入符号串为#。,例5.2 设文法为ZAB AaAb|ab BbB|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,，(,例5.4若有文法 SbAb A(B|a BAa) 设计出该文法的简单优先关系矩阵。 【解答】根据上面提到的，+(B，A=+a，可以得到：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-1Sk，则Sk为句柄的首符号，所有的比较都是以简单优先关系矩阵为依据。找到句柄后，就查找文法的产生式表，如果有一个文法的规则和句柄匹配，则用该产生式的左部符号替换符号栈中的句柄。最后，如果Si为文法的识别符号，而TRj为“#”，则表示输入符号串是文法的一个句子，算法终止。否则，输入符号串不是文法的一个句子。,例5.5设文法S(R)|a| RT TS,T|S 运用简单优先分析算法对终结符号串=(a),a)进行检查。下表5-5的分析过程，就是对输入串=(a),a)的一个判断。由此表可以判断该符号串是一个句子。,5.2.3简单优先分析法的局限性,简单优先分析法是有局限性的，它只适应于简单优先文法，但是一般程序设计语言的文法一般都不是简单优先文法，即使是关于表达式的文法也不是简单优先文法。如果要使用简单优先文法，就必须修改相应语言的文法，使之成为简单优先文法。 例5.4设文法EE+T|T TT*F|F E（E）|i,【解】因为有EE+T，所以有+=T，但由于T T*F，所以有+T，从上面的分析我们可以看出在+和T之间存在两种简单优先关系，所以关于简单算术表达式的文法不是一个简单优先文法，因而不能使用简单优先分析法，当然,此文法也可能修改成简单优先文法，上述文法就可以改为： EE EE+T|T TT TT*F|F E（E）|i,5.3算符优先分析方法,算符优先分析方法是根据算符之间的优先关系而设计一种自底向上的语法分析方法。算符优先分析的基本思想是只规定算符之间的优先关系，也就是只考虑终结符之间的优先关系。由于算符优先分析不考虑非终结符之间的优先关系，在归约过程中只要找到可归约串就归约，并不考虑归约到那个非终结符，因而算符优先归约不是规范归约。 设计算符优先分析法的必要性可以通过如下文法看出： （1）EE+E （2）EE*E （3）Ei,5.3.1算符优先文法,1算符文法和算符优先文法的定义及性质 定义5.1一个文法G，如果G中没有形如ABC的产生式，其中B和C为非终结符，则称G为算符文法，又称之为OG文法。 例如：表达式文法EE+E| E-E| E*E| E/E| EE|(E)|i 定义5.2设G是一个不含产生式的算符文法，a和b是任意两个终结符，A和B 、C是非终结符，算符优先关系，定义如下： （1）ab 当且仅当G中含有形如Aab 或AaBb的产生式。 （2）ab当且仅当G中含有形如AaB的产生式，且Bb或BCb （3）ab当且仅当G中含有形如ABb的产生式，且B a或BaC,上面的三种关系可以用下列的语法树来表示。 (1)ab则相对应的语法树为5-5的（a），其中为或B，由于a和b在同一个句柄中所以优先级相同。 (2) ab则相对应的语法树为5-5的（b）其中为或C，因为a和b不在同一个句柄中，所以a的优先级低于b. (3) ab则相对应的语法树为5-5的（c），其中为或C，a和b不在同一个句柄中，a 先归约，所以a的优先性大于b。,定义5.3 设有一个不含产生式的算符文法G，如果对任意两个终结符对a和b之间 至多只有，三种关系的一种成立，则称G是一个算符优先文法，即OPG文法。 例如前面介绍的表达式文法EE+E| E-E| E*E| E/E| EE|（E）|i，是一个二义性文法，它不是一个算符优先文法，但它是一个算符文法。 给出句型E+E*E，可以画出两棵语法树，见图5-6所示。,性质1在算符文法中任何一个句型都不包含两个相邻的非终结符。 证明：用归纳法 设是句型，S是文法的开始符号，且有S S=012n-1n= 推导长度为n，用数学归纳法来证明。 当n=1时，n-1满足性质1。 假设有n-1=A，A为终结符。由假设知的尾符号和的首符号都不可能是非终结符， 否则与假设相矛盾。 若A是文法的产生式，则有n-1n= 由A是文法的原产生式不含两个相邻的非终结符，所以不含两个相邻的非终结符，证明结束。,性质2 如果Ab出现在算符文法的句型中，其中AVN，bVT，则中任何含此b的短语必含A。 证明：用反证法 因为有算符文法的性质1则有: S=*=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的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)=+，*，(，i FIRSTVT(T)=*，(，i FIRSTVT(F)=，(，i 表5-8定义法构造优先关系矩阵 FIRSTVT(P)=(，i,LASTVT(E)=# LASTVT(E)=+,*,),i LASTVT(T)=*,),i LASTVT(F)=,),i LASTVT(P)=),i 逐条扫描产生式寻找终结符在前非终结符在后的相邻符号对以及非终结符在前终结符在后的相邻符号对，即：AaB和 ABb。,2)关系:先列出所给出表达式的文法中终结符在前非终结符在后的所有相邻符号对，并确定相关算符的关系 #E 则有：#FIRSTVT(E) +T 则有：+FIRSTVT(T) +F 则有：*FIRSTVT(F) F 则有：FIRSTVT(F) (E 则有：(FIRSTVT(E),3)关系：列出所给表达式文法中非终结符在后的所有相邻符号对，并确定相关算符的关系。 E# 则有：LASTVT(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 BEGIN FiA,ja:=TRUE; PUSH(A,a) ONTO STACK END.,此过程的意思是当aFIRSTVT(A)时置FiA，ja为真，并将符号对(A,a) 下推到栈中。主程序为： BEGIN(main) FOR i从1到 m,j从1到n do FiA,ja:=FALSE FOR 每个形如A a或A Ba的产生式 do INSERT(A,a) WHILE STACK非空 do BEGIN 把STACK的顶项记为(B,a) 弹出去 FOR每个形如A B的产生式 do INSERT(A,a) END END(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+1 if i n-2 且Xi和Xi+2均为终结符, 但Xi+1为非终结符 THEN 置XiXi+2 IF 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+i T+T*F T T*F i 素短语：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 (Sja)|(Sj=a) k=k+1; Sk=a; else error(); while(a!=#); 该算法工作过程中若出现j减1后其值小于或等于0，则意味着输入串有错。在正确的情况下，算法工作完毕时符号栈将出现#S#的状态。,3算符优先归约和规范归约的区别 （1）根据算符优先归约的性质，可知道算符优先文法的任何一个句型为如下的形式： #N1a1 N2a2 Nnan Nn+1# 其中，Ni为非终结符或空，ai(1in)为终结符。 若有句型Niai NjajNj+1，当ai Njaj属于句柄，则Ni和Nj+1也在句柄中，这是因为由于算符文法的任何句型中均无两个相邻的非终结符，且终结符和非终结符相邻时，含终结符的句柄必含相邻的非终结符。 该句柄的终结符的关系为： ai-1= ai ai= ai+1aj-1 =aj aj-1aj,（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|T T TaF|F FnF|(B)|t|f 该文法是算符优先文法吗？若该文法是算符优先文法，试给出输入串ntofat# 的分析过程。,【解】 （1）计算FIRSTVT和LASTVT集合： FIRSTVT(B)=o,a,n,(,t,f LASTVT(B)= o,a,n,t,f FIRSTVT(T)=a,n,(,t,f LASTVT(T)= a,n,t,f FIRSTVT(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)g(b) 则称f和g为优先函数。它们的函数值可以用整数来表示。,根据优先关系表构造优先函数的两种方法：一种是关系图法，另一种是由定义直接构造的方法。 （1）用关系图的方法构造优先函数的步骤如下： 1）对所有终结符a包括#，用有下脚标的 fa，ga为结点，画出全部n个终结符所对应的2n个结点。 2）若ab或a=b，则画出一条从fa到gb的有向边；若a b或a=b，则画出一条从gb到fa的有向边。 3）对每个结点都赋予一个数，此数等于从该结点出发所能到达的结点（包括出发结点自身在内）的个数，赋给fa的数作为f(a)，赋给gb的数作为g(b)。 4）检查所构造出来的函数f 和 g，看它们同原来的关系表是否有矛盾。如果没有矛盾，则f和g就是所要的优先函数；如果有矛盾，那么就不存在优先函数。,（2）由定义直接构造优先函数时，对每个终结符a包括#，令f(a)=g(a)=1 则： 1）如果ab，而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|T TT*F|F F(E)|i 试用关系图法和直接定义法求出本文法所对应的优先函数。 【解】,5.3.5 采用算符优先分析法的语法分析器的实现 1设计一个自动构造优先关系表的程序 设计一个自动构造优先关系表的程序，该程序的输入是算符文法G，输出是相应的优先关系表，并指出该文法是否是一个算符优先文法。 （1）给定文法。 G： EE+T|T TT*F|F FFP|P P(E)|i （2） 构造文法G的非终结符号的FIRSTVT集合。 FIRSTVT集合是用一个布尔数组F(P,a)来表示。F是一个m行n 列的数组。m是非终结符的个数，n是终结符的个数。,该算法设计一个数据结构STACK栈，用于存放相应的F（P，a）=TRUE的符号对（P，a），算法如下： BEGIN FOR 任何非终结符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的产生式DO IF 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是非终结符的个数。构造布尔数组的算法如下： BEGIN FOR 任何非终结符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的产生式DO IF 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+1,IF i n-2 且Xi和Xi+2均为终结符， 但Xi+1为非终结符 THEN 置XiXi+2 IF 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|T TT*F|F FFP|P P(E)|i （2）调用前面的分析程序构造优先关系表如表5-19所示。,（3）算法优先分析算法。 算符优先分析算法中使用分析栈S存放文法符号，变量p为S的栈顶指针，变量a是存放当前输入符号。ERROR为错误处理程序，分析算法如下： BEGIN p:=1; Sp:=#; REPEAT 将下一个输入符号读入a； IF SpVT then j:=p ELSE j:=p-1; while Sja DO BEGIN 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; end else error;/*错误处理*/ until a=#; end .,5.4两种优先分析法的比较 简单优先分析算法和算符优先分析技术存在很多相似之处，例如： （1）两种方法都是自下而上的语法分析法。它们对一个符号串
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
川公网安备: 51019002004831号