第四部分第五七章语法分析

1、第四部分第五七章语法分析第1页，共198页，2022年，5月20日，5点28分，星期二第四部分内容4.1 自顶向下分析方法（第5章）4.2 递归下降分析(递归子程序法)（第5章）4.3 LL(1)分析方法（第5章）4.4 自底向上分析方法（第6章）4.5 算符优先分析法（第6章）4.6 LR分析方法（第7章）第2页，共198页，2022年，5月20日，5点28分，星期二 一、语法分析是编译过程的核心部分语法分析的任务：按照文法，从源程序符号串中识别出各类语法成分，同时进行语法检查，为语义分析和代码生成做准备。语法分析程序的定义：执行语法分析任务的程序称为语法分析程序，也称为语法分析器，它是编译

2、程序的主要部分之一。语法分析方法的分类：分成两大类。 自顶向下分析和自底向上分析。第3页，共198页，2022年，5月20日，5点28分，星期二二、语法分析的数学模型下推自动机（1）下推机的逻辑结构PDA的读、写、状态转移动作决定于以下三个因素：当前所处状态读头所指符号下推栈栈顶符号一个输入串能为PDA所接受，仅当输入串读完，下推栈变空；或者输入串读完，控制器到达某些终态。有限状态控制器输入带输出带下推栈下推自动机逻辑结构第4页，共198页，2022年，5月20日，5点28分，星期二（2）下推机的定义下推自动机是一个七元组M=(Q, ,H, ,q0,z0,F)，其中：Q是控制器的有限状态集；是

3、输入字母表；H是下推栈内字母表；是Q()H到QH*的有限子集映射；q0Q是控制器的初始状态；z0H是下推栈的栈初始符；F为Q的子集，是控制器的终态集。第5页，共198页，2022年，5月20日，5点28分，星期二（3）说明映射函数描述PDA动作与状态的变化 (q,a,z)=(q1,1),(q2,2),(qn,n)其中q,qi(1in) Q,a*,zH 含义：控制器当前状态为q，下推栈栈顶符号为z，输入符号为a(可为空)情况下，状态转换到序偶集(qi,i), qi为下一状态， i为代替z的栈顶符号串。映射函数不是单值映射，且下推机有两种接受状态：串读完进入终态和串读完栈空。 例子：LL(1)语法

4、分析器与PDA的对应关系设CFG G=（VN ，P，S），构造一个不确定的PDA M=（Q，H，q0 ，z0 ，F），其中Q=F=q0 ；H=VN ；z0=S; 映射关系的构造方法如下：对于形如A 产生式，有(q,A)=(q,)， (q,a,a)=(q, )其中a。第6页，共198页，2022年，5月20日，5点28分，星期二4.1 自顶向下分析方法4.1.1 带回溯的自顶向下的分析方法4.1.2 存在的问题及解决方法第7页，共198页，2022年，5月20日，5点28分，星期二4.1.1 带回溯的自顶向下的分析方法思路：对任一输入符号串，通过一切可能的办法，从树根结点(识别符号)出发，根据文

5、法自上而下地为输入串建立一棵语法树；或者说，从识别符号开始，根据文法试图为输入串建立一个推导序列。特点：是自顶向下分析的一般方法，分析过程的本质是一种试探过程。第8页，共198页，2022年，5月20日，5点28分，星期二以上文法没有左递归，且有以下两个特点： (1)每个产生式的右部都由终结符号开始。(2)如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。 举例（1）确定的自顶向下分析第9页，共198页，2022年，5月20日，5点28分，星期二以上文法没有左递归，且有以下特点： (1)产生式的右部不全是由终结符开始。(2)如果两个产生式有相同的左部，其右部是由不同的终结符或非终结

6、符开始。(3)文法中无空产生式。 第10页，共198页，2022年，5月20日，5点28分，星期二以上推导过程的特点：在第二步到第三步的推导中，即abAS = abS时，因为当前输入符号为d，而最左非终结符A的产生式右部的开始符号集合都不包含d，但A可以推出空，所以d的匹配任务就只能依赖于A后面的符号，所以 选用产生式“A 空”进行推导，句型中紧跟A后面的符号为S，S产生式右部的开始符号中包含了d，所以可匹配。 第11页，共198页，2022年，5月20日，5点28分，星期二假定有文法GS： (1) S:=cAd (2) A:=ab | a对输入串w=cad。要求自上而下地构造w的语法树。 解

7、决过程：（2）非确定的自顶向下分析第12页，共198页，2022年，5月20日，5点28分，星期二分析： 通过上述解答过程可以看出：自顶向下地为输入符号串w建立语法树的过程实际上就是设法建立w的一个最左推导序列。比如对于上例中的输入串w可以通过如下的推导过程将其推导出来： S=cAd=cad由于对输入串是自左向右扫描的，因此用最左推导，只有用最左推导，才能保证按扫描顺序去匹配输入串。第13页，共198页，2022年，5月20日，5点28分，星期二问题：缺陷：不能处理左递归文法(教材P88图5.6、图5.7)。缺点：存在回溯，算法效率低。（另：更多例子参阅教材P91）第14页，共198页，202

8、2年，5月20日，5点28分，星期二4.1.2 存在的问题及解决方法一、左递归问题直接左递归间接左递归二、回溯问题实现不带回溯的自顶向下分析的条件 文法非左递归 首符号集不相交第15页，共198页，2022年，5月20日，5点28分，星期二(一) 左递归问题（P88） 直接左递归自顶向下分析方法不能处理具有左递归性的文法的原因：例如规则U:=U是一条左递归规则，为了实现用U匹配输入串，又会遇到要用U去匹配。故又要启用上述规则的右部符号串U来完成匹配工作。如此循环下去而无法终止。第16页，共198页，2022年，5月20日，5点28分，星期二方法：用第二章中介绍的重复和选择表示法(扩充的BNF表

9、示)去改写左递归规则。例如： 规则： E:=E+T | T 改写为：E:=T+T规则：T:=T*F|T/F|F改写为：T:=F*F|/F 改写后的文法消除了直接左递归，且改写前后的文法是等价的。第17页，共198页，2022年，5月20日，5点28分，星期二将直接左递归规则转换成使用重复表示法的等价规则的处理原则：1. 规则1(提取因子)： 当出现规则U:=xy|xw|xz时，用规则U:=x(y|w|z)代替。其中，圆括号是元符号。 特例：对规则U:=x|xy，则转换为U:=x(y|)，其中是空符号。第18页，共198页，2022年，5月20日，5点28分，星期二2. 规则2 令U:=x|y|

10、z|Uv是一组规则，它具有一个直接左递归右部且位于最后。该规则表明：语法类U的成员是由x或y或或z其后随有零个或多个v组成的。因此，可以把这组规则等价变换成U:=(x|y|z)v。第19页，共198页，2022年，5月20日，5点28分，星期二算法：使用规则1，通过提取因子将规则改写成满足以下要求的形式：相对于某个非终结符号，至多只有一个直接左递归的右部；使用规则2，将规则改写为不含直接左递规的扩充的BNF形式，以消除直接左递归。第20页，共198页，2022年，5月20日，5点28分，星期二例题：1. 规则：E:=E+T|T （1）变形为：E:=T|E+T （2）由规则2，改写为：E:=T+

11、T2. 规则：T:=T*F|T/F|F （1）规则1，改写为：T:=F|T(*F|/F) （2）规则2，改写为：T:=F(*F|/F) （3）删去圆括号为：T:=F*F|/F第21页，共198页，2022年，5月20日，5点28分，星期二 间接左递归要求：（1）文法没有回路(即没有形如A=A的推导)（2）不存在形如：A:=的规则。则可以按下述算法消除文法的左递归性。第22页，共198页，2022年，5月20日，5点28分，星期二消除左递归算法(1)： 把G的非终结符整理成某种顺序A1, A2, An。 for i:=1 step 1 until n do begin for j:=1 step

12、 1 until i-1 do把每个形如Ai:= Ajr的规则替换成 Ai:= 1r2rkr，其中Aj:= 12k是当前的全部Aj 规则；消除Ai规则中的直接左递归 end 化简由所得的文法，删除所有多余规则。第23页，共198页，2022年，5月20日，5点28分，星期二例题：有文法GS：S:=Qc|c Q:=Rb|b R:=Sa|a解： 该文法有间接左递归。例如有 S= Qc = Rbc= Sabc + 即 S=Sabc（1）首先将非终结符号排列成：R，Q，S的顺序。（2）将R代入Q得：Q:=Sab|ab|b 将Q代入S得： S:=Sabc|abc|bc|c 消除S的直接左递归：S:=(a

13、bc|bc|c)abc（3）处理后的文法为： S:=(abc|bc|c)abc Q:=Sab|ab|bR:=Sa|a 化简后的文法为：S:=(abc|bc|c)abc第24页，共198页，2022年，5月20日，5点28分，星期二消除左递归算法(2)1设G是一上下文无关文法，VnX1,X2,Xn，对每个形如Xi1 | 2 | m 的产生式，根据的开始符号作如下等价变换：（1）将“|”表示成“”， “”表示成“”（2）以非终结符号Xi引导的i表示成：Xi i（3）以终结符号引导的所有i之“和”看成常数项，表示成： i变形后的产生式为： XiX11i + X22i + + Xnni +i （如产生

14、式不含有以Xi打头的候选式，则相应的系数为）产生式集可表示为： 11 12 1n 21（ X1， X2， ， Xn） （ X1， X2， ， Xn） （1，2 ，n） n1 nn 即：X=XA+B，且其通解为：X=BA*化简 X=BA* ？1j蒋立源. 编译原理M. 西北工业大学出版社. P9194第25页，共198页，2022年，5月20日，5点28分，星期二消除左递归算法(2)设： z11 z12 z1n z21 A* = Z = I = zn1 znn 则可得以下矩阵方程组： X=BZ Z=I+AZ解以上方程组并化简即可得到不含左递规的文法例题： S-Sa|Ab|a A-Sc第26页，共

15、198页，2022年，5月20日，5点28分，星期二第27页，共198页，2022年，5月20日，5点28分，星期二(二)回溯问题（P91）（1）消除回溯的理由前面介绍的带回溯的自顶向下的分析方法实际上采用了一种穷尽一切可能的选择试探法（三种回溯情形举例：教材P91） ，回溯需要记住每一步分析的现场，浪费时间和空间，因此，效率低，代价高。要构造一个行之有效的自顶向下的语法分析程序，就必须消除回溯。（2） 消除回溯的思路为了避免回溯，要求对文法的任何非终结符号，主要是对那些规则右部有多个选择(候选式)的非终结符号，当要用它去匹配输入串时，能够根据所面临的输入符号准确地选用一个候选式去执行匹配任务

16、，并且工作的结果应是确定的。即若此选择匹配输入串成功，那么这种匹配一定正确无误；若此选择无法完成匹配任务，则任何其他的选择也肯定无法完成。第28页，共198页，2022年，5月20日，5点28分，星期二（3）消除回溯的方法预测与提左因子1、预测 预测就是根据读入的符号选择满足一定条件的候选式：使其第一个符号与读头下的符号相同，或该候选式可推导出的第一个符号与读头下符号相同。所以，对文法有如下要求： 令G是一个不含左递归的文法，对每条规则中的每个候选式定义它的终结首符集 First()=a|=* a,aVT第29页，共198页，2022年，5月20日，5点28分，星期二 设AVN，且A|，如当前

17、用A去匹配输入串，且输入符号为a时，对A的候选式的选择可以分成以下四种情况(当A不能推出时)：(1)若aFirst(),而a!First()，选A;(2)若a!First(),而aFirst()，选A;(3)若a!First(),而a!First()，输入有错；(4)若aFirst(),同时aFirst()，终结符首集两两相交，则需要改写文法。第30页，共198页，2022年，5月20日，5点28分，星期二2、改造文法 方法：提取公共左因子（a）假定关于非终结符A的产生式是： A1| 2| n 那么可改写成两条规则： A AA 1| 2| |n （b）一般情况，若有关A的产生式是： A1|2|

18、 3|4| 则可写成：A A|A”A 1| 2A”3| 4| 第31页，共198页，2022年，5月20日，5点28分，星期二结论： 即当规则右部具有n个选择，从每一个选择出发，都可以推导出一个以上的终结符号串。为了避免回溯，就要保证当用非终结符号A去匹配输入串时，能够根据当前读入的符号准确地选用它的一个候选式执行任务。即对文法的要求是：对任意一个非终结符号，当对应的规则右部有多个选择时，由各个选择所推出的终结符号串的首符号集合要两两不相交。当文法不满足避免回溯的条件时，可以改写文法，对规则右部反复提取左因子。第32页，共198页，2022年，5月20日，5点28分，星期二 例题： 规则：U:

19、=xV|xW， （1）改写为：U:=x(V|W) （2）引入一个新的非终结符号Y，则规 则变换成： U:=xYY:=V|W 改写后的文法中，非终结符号U的右部只有一个选择，而引入的新非终结符号Y具有两个选择V或W，且这两个选择所推出的终结符号串所组成的头符号集合不相交。第33页，共198页，2022年，5月20日，5点28分，星期二总结：为了实现不带回溯（确定）的自顶向下分析，对文法来说，需要满足下述两个条件： 文法是非左递归的。 对文法的任一非终结符号，若对应的规则右部有多个候选式时，那么，各选择所推出的终结符号串的头符号集合要两两不相交 。第34页，共198页，2022年，5月20日，5点

20、28分，星期二4.2 递归下降分析(递归子程序法)（一）基本思路 对文法中每个非终结符号U（分别代表一种语法成分）都编出一个子程序，以完成该非终结符号所对应的语法成分的分析和识别任务。第35页，共198页，2022年，5月20日，5点28分，星期二（二）非终结符号的语法分析子程序的功能 用该非终结符号的规则的右部符号串去匹配输入串。分析过程：按文法规则自左向右地逐个处理每个文法符号，处理方法如下。(1) 对规则中的终结符号直接与输入匹配；(2)非终结符号则调用该符号的分析子程序来完成匹配，即当编译程序根据文法和当前的输入符号预测到下一个语法成分为U时，即预测到待匹配的输入符号串可以和U推导出的

21、符号串相匹配时，就确定U为子目标，并调用分析和识别U的子程序来完成该子目标的分析匹配工作。第36页，共198页，2022年，5月20日，5点28分，星期二（三）特点 在分析和识别某个语法成份的过程中，有可能还要确立其它子目标并调用相应的分析子程序。只有在被调用的分析和识别某语法成分的子程序匹配输入串成功并正确返回后，该语法成分的分析才能继续进行，并最终完成分析任务。所以该分析方法具有明显的预测性特征，并在分析过程中向下确立多级子目标。所以，该方法也被称为面向预测和目标的分析方法（Predictive parser）。第37页，共198页，2022年，5月20日，5点28分，星期二（四）例题 Z

22、:=（U）| aUbU:=dZ | Ud | eProcedure Z; if CLASS=（ then beginnextsym;U;if CLASS=） then nextsymelseerror end; else if CLASS=a then beginnextsym;U;if class=b thennextsymelseerror end; else error;第38页，共198页，2022年，5月20日，5点28分，星期二Procedure U; /首先要消除左递归：U:=(dZ | e) d if CLASS=d then beginnextsym;Z; while CLA

23、SS=d do nextsym end; else if CLASS=e then beginnexteym;while CLASS=d do nextsym end elseerror;第39页，共198页，2022年，5月20日，5点28分，星期二4.3 LL(1)分析方法基本思路： 相应的语法分析将按自左至右的顺序扫描输入符号串，并在此过程中产生一个句子的最左推导。其中第一个 L 表示从左向右扫描输入符号串，第二个 L 表示生成最左推导，括号中的“1”，则表示在分析过程中，每进行一步推导，只要向前查看一个输入符号，便能确定当前所应选用的产生式(规则)。第40页，共198页，2022年，5

24、月20日，5点28分，星期二4.3.1 LL(1)分析器的逻辑结构及工作过程（一） 逻辑结构（1）LL分析器的数学模型设CFG G=（VN，P，S），构造PDA如下： M=（Q，H，q0，z0，F），其中Q=F=q0 ；H=VN；z0=S；映射关系的构造方法如下：对于形如A 产生式，有(q,A)=(q,)， 对于a， (q,a,a)=(q, ) 。 第41页，共198页，2022年，5月20日，5点28分，星期二（2）LL分析器的逻辑结构一个LL(1)分析器由一个总控程序、一张分析表和一个分析栈组成，其中：“输入”即待分析的符号串。分析表M用一个矩阵(或二维数组)来表示，它概括了相应文法的全部

25、信息。矩阵的每一行与文法的一个非终结符号、终结符号或#相关联，而每一列则与文法的一个终结符号或#相关联。分析表元素MA,a指示分析器应采取的动作。 其中AVtVn#，aVt#第42页，共198页，2022年，5月20日，5点28分，星期二（二） 工作过程第一步：分析开始时，首先将符号#及文法的开始符号S依次置于分析栈的底部，并把各指示器调整至起始位置，即初始格局为然后，反复执行第二步的操作。第43页，共198页，2022年，5月20日，5点28分，星期二第二步：设在分析的某一步，分析栈及余留的输入符号串处于如下的格局：其中，X1，X2，Xm为分析过程中所产生的文法符号，此时，可视栈顶符号Xm的

26、不同情况，分别进行如下操作：第44页，共198页，2022年，5月20日，5点28分，星期二若XmVN，则以Xm及ai组成符号对(Xm,ai)查分析表M。设MXm,ai为一产生式，譬如说XmUVW，此时将Xm从分析栈中退出，并将UVW按反序推入栈中(即用该产生式推导)，从而得到新的格局 但若MXm,ai=“ERROR”，则调用出错处理程序进行处理；第45页，共198页，2022年，5月20日，5点28分，星期二若Xm=ai#，则表明栈顶符号已与当前正扫描的输入符号匹配，此时应将Xm(即ai)从栈中退出，并将输入符号指示器向前推进一个位置；若Xm=ai=#，则表明输入串已完全得到匹配，此时即可宣

27、告分析成功而结束分析工作。第46页，共198页，2022年，5月20日，5点28分，星期二分析流程如下：第47页，共198页，2022年，5月20日，5点28分，星期二举例：原始文法：消除左递归：第48页，共198页，2022年，5月20日，5点28分，星期二第49页，共198页，2022年，5月20日，5点28分，星期二第50页，共198页，2022年，5月20日，5点28分，星期二4.3.2 LL(1)分析表的构造方法 LL(1)分析算法对不同的LL(1)文法都相同。即总控部分相同，仅仅是分析表不同，而且总控程序十分简单，容易实现。所以，LL(1)分析方法的核心是构造LL（1）分析表。第5

28、1页，共198页，2022年，5月20日，5点28分，星期二（一）定义 符号串的首符号集假定是文法G的任一符号串，即(VTVN)*，定义：FIRST()=a|=*a，aVT特别是，若=，则规定： FIRST()，即FIRST()是从可能推导出的所有开头终结符号或可能的。第52页，共198页，2022年，5月20日，5点28分，星期二（二）定义非终结符的尾符号集假定S是文法的开始符号，对于G的任何非终结符A，定义：FOLLOW(A)=a|S=*Aa,aVT特别是，若S=*A，则规定#FOLLOW(A)。即FOLLOW(A)是所有句型中能够紧接A之后的终结符或#。（三）定义SELECT集（教材P7

29、8）对文法的产生式X，如*，则SELECT(X)FIRST()如=*， 则SELECT(X)( FIRST() ) FOLLOW(X)第53页，共198页，2022年，5月20日，5点28分，星期二（四）构造First集的算法1定义法若XVT，则 FIRST(X)=X。若XVN，对形如Xa的产生式(aVT)，或形如X的产生式，把a或加进FIRST(X)。设G中有形如XY1Y2Yk的产生式，若Y1VN，则把FIRST(Y1)中的一切非的符号加进FIRST(X)；对于一切2ik，若Y1，Y2Yi-1均为非终结符，且FIRST(Yj)，1ji-1，则将FIRST(Yi)中的一切非的符号加进FIRST

30、(X)；若对一切1jk，均有FIRST(Yj)，则将加进FIRST(X)。第54页，共198页，2022年，5月20日，5点28分，星期二关系图法（1）首先求出能推出的非终结符号第55页，共198页，2022年，5月20日，5点28分，星期二（2）然后按照下面步骤求解第56页，共198页，2022年，5月20日，5点28分，星期二对于文法G的任一符号串=X1X2Xn可按如下的步骤构造相应的FIRST()。置FIRST()=；把FIRST(X1)中的一切非符号加进FIRST()；依次进行下述操作：若FIRST(X1)，将FIRST(X2)中的一切非的符号加进FIRST()；若属于FIRST(X1

31、)及FIRST(X2)，将FIRST(X3)中一切非的符号加进FIRST()；以此类推。最后，若对于1in，FIRST(Xi)，则将加进FIRST()。第57页，共198页，2022年，5月20日，5点28分，星期二（五）构造Follow集的算法1定义法对于文法的开始符号，令#FOLLOW(S)。若G中有形如AB的产生式，且，则将FIRST()中的一切非符号加进FOLLOW(B)。(即FOLLOW不含)若G中有形如AB或AB的产生式，且FIRST()，则FOLLOW(A)中的全部元素均属于FOLLOW(B)。第58页，共198页，2022年，5月20日，5点28分，星期二2关系图法第59页，共

32、198页，2022年，5月20日，5点28分，星期二（六）构造分析表的算法 分析表M是一个二维表，每一行对应一个文法符号，每一列对应一个终结符号，元素的赋值规则如下：（1）对规则A，FRIST（）中的每一终结符a，置MA,a=“POP，PUSH（）”。其中为的倒置。 若FIRST（），则对属于FOLLOW(A)的每一终结符号b或#，置MA,b=“A”。（2）把M中所有Ma,a置为“POP，NEXTSYM”。（3）把M中所有不能按以上规则定义的元素均置为“ERROR”（出错）。简化表示：可以省略分析表中所有终结符号对应的行。第60页，共198页，2022年，5月20日，5点28分，星期二定义：一

33、个文法G，若它的分析表M不含多重定义元素，则称它是一个LL(1)文法。一个LL(1)文法是无二义的，它所定义的语言恰好就是它的分析表M所能识别的全部句子。可以证明，一个文法G是LL(1)文法，当且仅当对于G的每一个非终结符A的任何两条不同规则A:=|，下面的条件成立：（1）FIRST()FIRST()=，即由和推导不出以同一终结符a为首字符的符号串；且不应该都能推出空字符。（2）假若=*，则FIRST()FOLLOW(A)=；即若=*，则所能推出的串的首符号不应在FOLLOW(A)中。教材P78:（即SELECT(A:=)与SELECT(A:=)不相交，且两者不能同时推出 ）第61页，共198

34、页，2022年，5月20日，5点28分，星期二主要结论：任何LL(1)文法都是无二义性的。若一文法中含有左递归的非终结符号，则它必然是非LL(1)文法。存在一种算法，它能判定任一文法是否为LL(1)文法。存在一种算法，它能判定任意两个LL(1)文法是否产生相同的语言。不存在这样的算法，它能判定任意上下文无关语言能否由LL(1)文法产生。非LL(1)语言是存在的。第62页，共198页，2022年，5月20日，5点28分，星期二一、非LL（1）文法的改造（四种改造情形举例：教材P85）,第63页，共198页，2022年，5月20日，5点28分，星期二二、非LL（1）文法第64页，共198页，202

35、2年，5月20日，5点28分，星期二4.4 自底向上分析方法（一）基本思路 自底向上的分析方法，也称为“移进归约”法，这种方法的一般过程是：设置一个寄存符号的先进后出栈，称为符号栈，用来记录分析的历史和指示分析的下一步动作。第65页，共198页，2022年，5月20日，5点28分，星期二（二）分析过程 在分析进行时，把输入符号一个个地按扫描顺序移进栈里，当栈顶符号串形成一个句柄(为某条规则的右部)时，就进行一次归约，把栈顶构成句柄的那个符号串用相应规则左部的非终结符号来代替。接着再检查在栈顶是否又出现了新的句柄，若出现新的句柄，就再进行归约；若没有形成新的句柄，则再从输入符号串移进新的符号，如

36、此继续直到整个输入符号串处理完毕。最终如栈底为识别符号，则所分析的输入符号串为合法的句子，报告成功；否则，是不合法的符号串，报告错误。第66页，共198页，2022年，5月20日，5点28分，星期二例1：有文法GS： (1) S:=aAcBe(2) A:=b (3) A:=Ab(4) B:=d分析符号串abbcde第67页，共198页，2022年，5月20日，5点28分，星期二步骤栈内输入串输出带动作0#abbcde#1#abbcde#移进2#abbcde#移进3#aAbcde#2归约4#aAbcde#移进5#aAcde#2,3归约6#aAcde#移进7#aAcde#移进8#aAcBe#2,3

37、,4归约9#aAcBe#移进10#S#2,3,4,1归约11识别成功abbcde的移进归约过程：第68页，共198页，2022年，5月20日，5点28分，星期二abbcde语法树的构造过程：第69页，共198页，2022年，5月20日，5点28分，星期二（三）关键问题 在自底向上分析中，如何寻找或确定一个句型的句柄，是构造一个自左向右扫描、自底向上分析方法必须要解决的一个关键问题。下面介绍较为常用的两种方法：（1）算符优先分析方法（2）LR分析法第70页，共198页，2022年，5月20日，5点28分，星期二4.5 算符优先分析法4.5.1 方法概述4.5.2 直观算符优先分析法4.5.3 算

38、符优先分析法的进一步讨论第71页，共198页，2022年，5月20日，5点28分，星期二4.5.1 方法概述思路： 算符优先分析法是仿照算术式的四则运算过程而设计的一种语法分析方法。该方法首先要规定运算符之间的优先关系和结合性质，然后利用这种关系，通过比较相邻运算符的优先顺序来确定句型的“句柄”和进行归约。特点： 简单直观，最适用于表达式分析，宜于手工实现。第72页，共198页，2022年，5月20日，5点28分，星期二例：有文法 GE：E:=E+E | E-E | E*E | E/E | (E) | i 试分析句子 i+i-i*(i+i) 根据运算符优先顺序和结合原则的规定对句子i+i-i*

39、(i+i) 进行归约，归约过程为： #i+i-i*(i+i) # #E+i-i*(i+i) # #E+E-i*(i+i) # #E-i*(i+i) # #E-E*(i+i)# #E-E*(E+i) # #E-E*(E+E) # #E-E*(E) # #E-E*E # #E-E #(11) #E# 该归约过程是唯一的。第73页，共198页，2022年，5月20日，5点28分，星期二 在上述的整个归约过程中，起决定作用的是相邻两个终结符的优先关系，所以应用算符优先分析法自底向上地分析句子，解决了前面提到的问题，即：（1）可以只根据相邻运算符的优先关系，就能方便地并且唯一地确定归约的“句柄”；（2）

40、同时还可以发现：该方法可以用来分析二义性文法所产生的语言。 上述文法是二义性的，但用算符优先法分析其句子时，其归约过程是唯一的。我们所规定的运算符之间的优先顺序和左结合的原则，就是避免二义性的充分条件。第74页，共198页，2022年，5月20日，5点28分，星期二4.5.2 直观算符优先分析法（1）算符优先分析的关键在于定义任何两个可能相邻的终结符a和b之间的优先关系要求对于任何两个可能相继出现的终结符a和b具有形式：“ab”或“aQb”，QVN ，定义a，b之间有3种关系：(1)a ba的优先级低于b(2)aba的优先级等于b(3)aba的优先级高于b 如果a和b在任何情况下不可能相继出现

41、，则a，b之间不可比，即无关系； 要与算术中的区分，a b并不意味着b a，比如栈内的大于栈外，同时栈内也大于栈外。第75页，共198页，2022年，5月20日，5点28分，星期二优先关系矩阵示例内 外+* i()#+* i()#第76页，共198页，2022年，5月20日，5点28分，星期二（2）直观算符优先分析法的基本步骤使用两个工作栈OPTR（寄存运算符）和OPND（存放“操作数”和“运算结果”）；开始，将OPTR栈底置为#，输入串尾设置右界符#，OPND初始为空；令 代表OPTR现行栈顶符号，a存放新输入的符号；则分析算法的基本步骤如下：第77页，共198页，2022年，5月20日，5

42、点28分，星期二(1)把下一个输入符号读至a中；(2)若a为运算数i，则把它压入OPND，转(1)；(3)若a，则调用的处理程序，处理子表达式E(1)E(2)，同时，把从OPTR栈顶弹出，然后重新进入(3)；(4)若 a，则按优先关系表有两种可能： =（，a=），此时弹出OPTR顶的 （，放弃a中的），然后转(1)； =a=#，结束；(5)若a，把a移进OPTR栈，转（1）;(6) 与a不存在优先关系，则输入串有错。第78页，共198页，2022年，5月20日，5点28分，星期二4.5.3 算符优先分析法的进一步讨论(一) 算符优先文法定义1：设有一文法G，如果G中没有形如U:=VW的规则，其

43、中V和W是非终结符号，那么，就称G为算符文法（OG文法）第79页，共198页，2022年，5月20日，5点28分，星期二定义 2设G是一OG文法，并令a和b是任意两个终结符号，U、V、W是非终结符号。终结符号的优先关系定义如下：（1）a b，当且仅当文法中有形如U:=ab或U:=aVb的规则；(a、b同时归约)（2）a b，当且仅当文法中有形如U:=aW的规则，其中W=+b或 W=+Vb；（b归约在前）（3）a b，当且仅当文法中有形如U:=Wb的规则，其中W=+a或W=+aV。 （a归约在前）第80页，共198页，2022年，5月20日，5点28分，星期二三种优先关系和归约的先后顺序的图形解

44、释（参见教材P108）第81页，共198页，2022年，5月20日，5点28分，星期二定义 3设有一OG文法，如果在任意两个终结符号之间，在 、 和中至多只有一种关系成立，那么，这样的OG文法称为算符优先文法(OPG文法)。第82页，共198页，2022年，5月20日，5点28分，星期二(二) 构造优先关系矩阵定义 1 非终结符号U的FIRSTVT集合 FIRSTVT(U)= a | U=*a 或 U=*Va 定义 2 非终结符号U的LASTVT 集合 LASTVT(U)= a | U=*a 或 U=*aV第83页，共198页，2022年，5月20日，5点28分，星期二 （1）构造FIRSTV

45、T算法（LASTVT的构造算法与此类似）Procedure Insert(U,b); if not FU,b thenBegin FU,b:=TRUE; Push(U,b); / 把(U,b)下推进STACKEnd第84页，共198页，2022年，5月20日，5点28分，星期二主程序F为2维数组，如bFIRSTVT(U)，则FU,b:=TRUE BEGIN For 每个非终结符号U和终结符号b doFU,b:=FALSE；初始化为0 For 每个形如U:=b或U:=Vb的规则do Insert(U,b) While STACK 非空 doBegin Pop (V,b) 记STACK栈顶为(V,

46、b)，弹出 For 每条形如U:=V的规则 doInsert (U,b)End of While; END第85页，共198页，2022年，5月20日，5点28分，星期二例子：给定如下表达式文法GE:(0)E#E#，(1)EE+T, (2)ET, (3)TT*F,(4)TF, (5)FPF|P, (6)P(E), (7)Pi非终结符号的FIRSTVTLASTVT如右：第86页，共198页，2022年，5月20日，5点28分，星期二（2）用图形法求FIRSTVT的算法（教材P105）图形法求解结果如右图所示：第87页，共198页，2022年，5月20日，5点28分，星期二（3）构造优先关系表算法

47、 For 每条规则U:=x1x2xn DO For i:=1 TO n-1 DOBEGIN IF xi和xi+1均为终结符号 THEN置 xi xi+1； IF xi为终结符号而xi+1为非终结符 THEN置 xi xi+2； IF xi为终结符号而xi+1为非终结符 THENFor FIRSTVT(xi+1)中的每个b DO 置 xi b； IF xi为非终结符号而xi+1为终结符 THENFor LASTVT(xi)中的每个a DO 置 a xi+1；End第88页，共198页，2022年，5月20日，5点28分，星期二例：设文法GS的产生式为：SaAcBe AAb|bBdFIRSTVT(

48、S)=aFIRSTVT(A)=bFIRSTVT(B)=dLASTVT(S)=eLASTVT(A)=bLASTVT(B)=dabcdeabcde第89页，共198页，2022年，5月20日，5点28分，星期二(三) 算符优先分析算法设计定义 4文法句型的素短语是满足以下条件的一个短语，它至少包含一个终结符号，并且除它自身之外，不再包含其他素短语。第90页，共198页，2022年，5月20日，5点28分，星期二定理 1一个OPG句型的最左素短语是满足下列条件的最左子串NjajNiaiNi+1aj-1 ajaj aj+1, aj+1 aj+2, ai-2 ai-1, ai-1 ai ai ai+1出

49、现在aj 左端或ai右端的非终结符号一定属于这个素短语。举例：P116 图6.6 、图6.7第91页，共198页，2022年，5月20日，5点28分，星期二例子：P110与规范归约的比较：第92页，共198页，2022年，5月20日，5点28分，星期二继续往前扫描寻找素短语尾找到素短语尾往栈底搜索找素短语头找到素短语头S为分析栈，k为栈顶指针。第93页，共198页，2022年，5月20日，5点28分，星期二注意：(1) 在查找所应归约的最左素短语的过程中，没有用到非终结符号，因此，在符号栈中放不放相应的非终结符号，对分析过程中寻找最左素短语没有影响。(2) 与归约为某个非终结符号相对应， 语义

50、程序分配一个工作单元来存放该子表达式的运算结果。所以，对语义处理程序来说，也不需要知道真正的非终结符号的名字。第94页，共198页，2022年，5月20日，5点28分，星期二算符优先函数及其构造方法为什么要构造优先函数？ 对具有n个终结符号（包括句子界符）的算符优先文法，其优先关系矩阵需要n2的存储空间。是否可能将空间消耗控制在n的线性复杂度范围内。第95页，共198页，2022年，5月20日，5点28分，星期二算符优先函数及其构造方法把每一个终结符与一对整数f()、g()联系在一起，其中f()为终结符在栈内时的优先数，g()为终结符在栈外的优先数。（1）f()与g()的值应满足如下关系若12

51、则f(1)g(2)2个优先函数所需空间为2n第96页，共198页，2022年，5月20日，5点28分，星期二（2）优先表与优先函数的关系1)优先函数并不等价于优先表，在优先表中没有关系的终结符对存在优先函数。2)有些优先表不存在对应的优先函数f和g。3)如果存在一对优先函数，则存在无穷多对优先函数。根据不同的算法从优先表转换推演出优先函数时也可能得到不同的结果。第97页，共198页，2022年，5月20日，5点28分，星期二（3）从优先表转换为优先函数的算法算法一：逐次加1法1)对所有终结符a(包括#)，令f(a)=g(a)=c2)对所有终结符：若ab且f(a) g(b)，则f(a):=g(b

52、)+1若ab且f(a) g(b)，则g(b):=f(a)+1若ab且f(a) g(b)，则f(a)=g(b)=max(f(a)，g(b)3)重复步骤(2)直至f(a)，g(b)不再改变为止。如果f(a)或g(b)的任一值2n+c而步骤(2)还没结束，表示优先函数不存在。第98页，共198页，2022年，5月20日，5点28分，星期二例：由G(E)文法的优先表构造优先函数的过程/P118I O+* i()#+* i()#第1步：f(+)与g(+)、g(*)、g(#)比较，按算法调整对应的f、g值；第2步：f(*)与g(+)、g(*)、g(#)比较，按算法调整对应的f、g值；第n步：f(#)与g(

53、+)、g(*)、g(#)比较，按算法调整对应的f、g值；第99页，共198页，2022年，5月20日，5点28分，星期二 以上优先函数的计算迭代三次收敛。不难看出对优先函数每个元素的值都增加同一 个常数，优先关系不变，所以同一个文法的优先关系矩阵对应的优先函数可以不唯一。 但是也有一些优先关系矩阵中的优先关系是唯一的，却不存在优先函数。例如下面的优先关系矩阵： 第100页，共198页，2022年，5月20日，5点28分，星期二构造算法二：Bell有向图方法1)对每个终结符a（包括#），令其对应两个节点fa和ga，画一张以所有fa和ga为节点的有向图，如果ab或a b，就从fa画一弧指向gb，若

54、ab或a b，则从gb画一弧指向fa；2)令f(a)等于节点fa可达的节点数(包括自身)，令g(a)等于节点ga可达的节点数(包括自身)；3)检查构造出来的f(a)和g(a)，若与优先表符合则优先函数存在，否则不存在。第101页，共198页，2022年，5月20日，5点28分，星期二Bell有向图举例：i*+#fg67654322第102页，共198页，2022年，5月20日，5点28分，星期二4.6 LR分析方法4.6.1 概述4.6.2 LR(0)分析器4.6.3 SLR(1)分析器4.6.4 规范LR(1)分析器4.6.5 规范LALR(1)分析器4.6.6 语法分析程序的自动生成工具Y

55、ACC第103页，共198页，2022年，5月20日，5点28分，星期二基本思路： LR(K)分析器从左到右扫描所给定的输入串，并以相反的方向构造该输入串的最右推导(Right-most Derive即规范推导)。LR(K)分析器根据分析栈的内容以及向前查看输入串中K个符号来决定分析动作。特点：（1）分析器对源程序中错误的诊断灵敏；（2）分析器对文法适应性强，文法分析能力强；（3）分析器结构复杂，K越大，相应的分析器愈复杂。 当K0时，表示在确定分析动作时不需向前查看符号，LR（0）分析器是LR分析器中最简单的一种。LR（0）分析器分析能力弱，实用性差，一般仅作为构造更复杂的LR分析器的基础。

56、第104页，共198页，2022年，5月20日，5点28分，星期二LR分析器的逻辑结构和工作原理 LR分析器的数学模型是下推自动机。该下推机具有一个输入机构，一个分析栈和一个有穷的控制系统。一般来说，其控制系统是一个具有多状态的有穷状态机。总控程序输入带输出带下推栈下推自动机逻辑结构动作表 状态转移表4.6.1 概述第105页，共198页，2022年，5月20日，5点28分，星期二1、下推自动机的定义M =，R，q0，Z0 ，F：有穷状态集 ：堆栈字母表：输入字母表R ：转换关系 () )( *)q0 ：初态Z0 ：初始堆栈，符号Z0F： 为的子集，是控制器的终态集第106页，共198页，20

57、22年，5月20日，5点28分，星期二2、有穷自动机状态的分类有穷状态集中的状态分成3类 读状态，当读一个终结符或非终结符时，发生由一个状态到另一状态的状态转移。 归约状态，识别出当前句型的活前缀的句柄部分。处于归约状态时，检测出来的句柄将归约为一个非终结符号。识别状态，输入串被分析器成功识别。第107页，共198页，2022年，5月20日，5点28分，星期二3、LR(0)分析栈的结构 LR(0)分析器的分析栈是一个符号对偶栈。对偶的第一个元素是文法符号。对偶的第二个元素是分析器扫描一个文法符号时所进入的状态。XmXm-1X1#SmSm-1S1S0文法符号 状态 第108页，共198页，202

58、2年，5月20日，5点28分，星期二4、LR(0)分析过程 LR(0)分析器由总控程序和分析表两部分组成。分析开始时，栈内的初始状态为S0，即与分析器有关的有穷控制的开动状态。（1）当分析器处于读状态时，它将当前扫描到的符号压入堆栈，并执行由所读符号所指示的状态转移，并将该后继状态也压入栈内；（2）当分析器处于归约状态时，将对偶栈中与句柄对应的部分弹出进行归约，然后执行读操作，读入归约后的符号并压入堆栈。 如果归约到的符号为识别符号，则分析器接受所给定的符号串并停机；否则，归约生成的左部符号和当前栈顶状态将确定下一个状态转移。第109页，共198页，2022年，5月20日，5点28分，星期二一

59、、初始情况二、一般过程分析栈输入带对应“句型”S0#a1a2an# a1a2an分析栈输入带对应“句型”S0S1Sm # X1Xmaiai1an# X1Xmaiai1an第110页，共198页，2022年，5月20日，5点28分，星期二（1）If actionsm,ai= si(shift si) then 分析格局变为（2）If actionsm,ai= ri(Reduce i) then 表示用第i个产生式AXm-(k-1)Xm进行归约，分析格局变为分析栈输入带S0S1Smk # X1Xmk Aaiai1an# 分析栈输入带S0S1Sm Si# X1Xm aiai1an# 第111页，共1

60、98页，2022年，5月20日，5点28分，星期二然后查goto表，If gotosm-k,A= si then 格局变为（3）If actionsm,ai=acc then 分析成功分析栈输入带S0S1Smk Si# X1Xmk Aaiai1an# 第112页，共198页，2022年，5月20日，5点28分，星期二5、举例（P124）文法GS：SaAcBeAbAAbBd第113页，共198页，2022年，5月20日，5点28分，星期二注意：分析中只需要状态栈信息1）因为分析器的有穷控制是确定的，所以文法符号可不必压入栈内。2）当到达一归约状态时，与该状态对应的句柄是确定的。第114页，共19