第六章-自底向上优先分析课件

1、指导教师:杨建国二零零七年十一月编 译 原 理第6章自底向上优先分析语法分析推导自上而下的语法分析过程预测分析程序，递归下降分析法（最左推导）注：要求文法是LL(1)文法归约自下而上的语法分析过程简单优先分析法，算符优先分析法，LR分析法1.自底向上优先分析概述2.简单优先分析（优先关系的理解）3.算符优先分析确定句型的短语、直接短语、句柄、素短语、最左素短语算符优先关系矩阵的构造及输入串的过程分析学习目标第一节 自底向上优先分析概述第二节 简单优先分析法第三节 算符优先分析法第四节 典型例题及解答教学内容知识结构从输入串开始，逐步进行“归约”，直至归约到文法开始符号；或者说，从语法树的末端开

2、始，步步向上“归约”，直到根结点。引言 1.基本思想自下而上的语法分析过程是一个最左归约的过程，从输入串开始，朝着文法的开始符号进行归约，直到到达文法的开始符号为止的过程。从语法树角度看，是以输入符号串作为语法树的末端结点符号串，自底向上地构造语法树，使文法开始符号正好是该语法树的根。如果最终根结点是开始符号，则输入符号串是语言的一个句子，否则不是。自底向上分析过程实际上是一个不断进行直接归约的过程。注意：输入串在这里是指从词法分析器送来的单词符号组成的二元式的有限序列。 分析过程是重复以下步骤：1、找出当前句型的句柄 x （或句柄的变形）2、找出以x为右部的规则Xx 3、把x规约为X，产生语

3、法树的一枝关键：找出当前句型的句柄x(或其变形），这不是很容易。2.实现方式-“移进归约”方式 语法分析程序 语法表 a+b#输出带# 自左至右把输入串的符号逐个移进栈【注】初态时栈内仅有栈底符“”，读头指在最左边的单词符号上。 若栈顶形成某个句型的句柄，就将此句柄用相应的产生式左部替换（归约），若再形成句柄，就继续替换，直到栈顶不再形成句柄为止。重复上面的过程直到栈顶只剩下#和文法的开始符号，同时输入串读完为止，这样就认为识别了一个句子。3.语法分析程序执行的动作移进 读入下一个输入符号并压入栈内，读头后移；归约 检查栈顶若干个符号能否进行归约，若能，就以产生式左部替代该符号串，同时输出产生

4、式；接受 移进归约的结局是栈内只剩下栈底符号和文法开始符号，读头也指向语句的结束符； 报错 当识别程序察觉一个错误，因此输入符号串不是句子而无法继续识别工作时，调用一个出错处理子程序进行处理或停止。例1：文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B dabbcde步骤符号栈输入符号串动作 1） # abbcde# 移进 2） #a bbcde# 移进A 3） #ab bcde# 归约(Ab) 4） #aA bcde# 移进A 5） #aAb cde# 归约(AAb) 6） #aA cde# 移进 7） #aAc de# 移进B 8） #aAcd e# 归约(Bd)

5、9） #aAcB e# 移进11） #S # 接受S10） #aAcBe # 归约(S aAcBe)符号串abbcde是否是GS的句子对输入串abbcde#的移进-归约分析过程SaAcBeaAcdeaAbcdeabbcde顺序扫描输入符号并依次移进栈栈顶部的符号串是否构成一句柄？YN进行一次归约输入串扫描完否？noY栈中仅有开始符号？noerror输入串合法，报告分析报告出口移进-归约过程Y（1）例子的分析过程是一步步地归约当前句型的句柄该句子的唯一语法树为:aAcBeAbbdS注意两点：（a）栈内符号串+ 未处理输入符号串 = 当前句型（b）句柄都在栈顶实际上，以上分析过程并未真正解决句柄的

6、识别问题说明:（2）未真正解决句柄的识别 *上述分析过程是怎样识别句柄的，主要看栈顶符号串 是否形成规则的右部。这种做法形式上是正确的，但在实际上不一定正确。 举例的分析过程可以说是一种巧合。 因为不能认为:对句型 xuy 而言，若有Uu，即Uu 就断定u是简单短语，u就是句柄，而是要同时满足 Z xUy一.优先分析法的类别6.1自底向上优先分析概述1.优先分析器（Precedence Parser）简单优先分析法算符优先分析法2.LR分析器二.简单优先分析法基本思想：按一定原则定义文法中所有符号（终结符和非终结符）之间的优先关系，按照这种关系确定归约过程中的句柄并实行归约。是一种规范归约。简

7、单优先分析法准确、规范，但效率低，不实用，不流行。三.算符优先分析法基本思想：只定义文法中终结符之间的优先关系（不考虑非终结符），并由这种关系指导分析过程不是规范归约算符优先分析法分析速度快，特别适用于表达式的分析。缺点是不规范，常常要采用适当措施克服其缺点。 6.2简单优先分析法一.优先关系的符号表示6.2.1 优先关系.+*.+（1） XY当且仅当G中存在产生式规则 AXY（2） XY当且仅当G中存在产生式规则 A XB，且BY（3） XY当且仅当G中存在产生式规则 ABD,且B X和D Y三.从语法树判别优先性设G是已化简的文法,s,tV,若G中存在规范句型 =st, 则s,t与的句柄之

8、间的关系必有下述情况之一:1.s在句柄中,而t不在句柄中2.s与t均在句柄中3.s不在句柄中,而t在句柄中对于上述情况,我们规定：情况1:st;情况2:s=t;情况3:stA s t .A s t .A s t . 另外,还有一种情况,就是s和t均不在句柄中,那么一定存在某句型使得它们进入上述三种情况之一。 若s和t在任何句型中都不可能相邻出现,则我们规定二者无关系。 注意,这种优先关系是不对称的!在句型中，句柄内各相邻符号之间具有相同的优先级。结论由于句柄要先归约，所以规定句柄两端符号的优先级 要比位于句柄之外的相邻符号的优先级高。 句型中NiNj是句柄，则 N1Ni-1 Ni Nj Nj+

9、1Nn .【注】优先分析法基本思想也可以表述为： 若句型中NiNj是句柄，语法分析程序可以 通过寻找Ni-1 Ni和Nj Nj+1 这两个关系来确定句 柄的头尾，从而确定句柄进行归约。 .我们可以通过两个相邻符号SiSi+1之间的关系来找到句柄：SiSi+1在句柄内：必然有规则USiSi+1Si在句柄内部，但是Si+1在句柄之后，必然有规则USi，且存在规范句型USi+1。如果Si+1在句柄内，而Si在句柄外，那么必然存在规范句型SiU，且有USi+1。如何确定优先关系？例2文法GS：(1) S bAb(2) A (B|a(3) B Aa)1.求=关系：由(1)：b=A A=b由(2)：(=B

10、由(3)：A=a a=)注意：行列与左右，空4.#3.求关系：由(1)：Bb ab )b由(3)：Ba aa )a2.求关系：由(1)(2)：b ba由(2)(3)：(A ( (.第二步：找句柄头trjkiSk-1 Skkk-1=SkSk+1Si是句柄，用它查产生式表与一产生式右部相同Si=#且trj=#结束ik，Si UU是该产生式左部符号errorii+1Si trjjj+1YNNYYNYYNerrorN文法GS：(1) S bAb(2) A (B|a(3) B Aa)步骤符号栈输入符号串动作 1） # b(aa)b# 2） #b (aa)b# 3） #b( aa)b# 4） #b(a a

11、)b# 5） #b(A a)b# 6） #b(Aa )b# 7） #b(Aa) b# 8） #b(B b# 9） #bA b#10） #bAb #11） #S #对输入串b(aa)b#的简单优先分析过程简单优先关系矩阵注意：何时移进，何时归约？归约中如何确定句柄？#b(a#b,移进b(,移进(a,用Aa归约A=a,移进a=),移进#b(Aa)b,用BAa)归约#b(BBb,用A(B归约A=b,移进#bAbb#,用SbAb归约接受6.2.4 简单优先分析法的优缺点优点：技术简单 缺点：适用范围小，分析表尺寸太大。 6.2.5 简单优先分析法的局限性简单优先分析法是有局限性的，它只适应于简单优先文

12、法，但是程序设计语言的文法一般都不是简单优先文法，即使是关于表达式的文法也不是简单优先文法。如果要使用简单优先文法，就必须修改相应语言的文法，使之成为简单优先文法。例3 设文法G：EE+T|T TT*F|F E（E）|i【解】因为有EE+T，所以有+=T，但由于T T*F，所以有+.+( = )注意：是三种有序关系，与数学中的不同，所以a=b不意味b=a，ab不意味b +，在(E+T)中得 + )a1 a2 a3 ai an# 优先关系表总控程序X1Xn-1Xn#分析器的逻辑结构：优先关系表、分析栈、总控程序文法符号二.分析器结构例7 GE：EE+E|E-E|E*E|E/E|EE|(E)|i

13、这是一个二义文法，要用算符优先法分析由该文法所确定的语言句子。如：i+i*i 二义性文法的句子往往有不同的规范推导，句子i+i*i的两种不同的规范归约过程如下：第一个规范归约过程(1) i+i*i(2) E+i*i(3) E+E*i(4) E+E*E(5) E+E(6) E第二个规范归约过程(1) i+i*i(2) E+i*i(3) E+E*i(4) E*i(5) E*E(6) Ei是句柄E+E是句柄按传统的习惯规定优先级从高到低为:（0）i的优先级最高（1）优先级次于i，右结合（2）*和/优先级次之，左结合（3）+和-优先级最低，左结合（4）括号(,)的优先级大于括号外的运算符，小于括号内的

14、运算符，内括号的优先性大于外括号（5）#优先性低于与其相邻的算符算符优先关系表 但是采用关于算符优先顺序和结合规则的规定，并按这种规定归约，那么归约过程就是唯一的。 矩阵元素空白处表示这两个终结符不能相邻,故没有优先关系分析过程 i+i*i步骤符号栈输入串优先关系 动作1234567891011#i#E#E+#E+i#E+E#E+E*#E+E*i#E+E*E#E+E#E#i#*i#*i#i*i#+i*i#+i*i#i+i*i#+#+*+*#*#+#移进移进移进移进移进规约规约规约规约规约接受算法: 当栈顶项(或次栈顶项)终结符的优先级大于栈外的终结符的优先级则进行规约，否则移进。分析过程是从符

15、号串开始,根据相邻终结符之间的优先 关系确定句型的“句柄”,并进行规约,直到识别符号E,最 后分析成功: i+i*iL（GE）出错情况: 1.相邻终结符之间无优先关系 2.对双目运行符进行规约时,符号栈中无足够项 3.非正常结束状态 6.3.2 算符优先文法定义一.算符文法的定义定义6.1 对上下文无关文法G，若它所有的产生式的右部均不含相连的非终结符，则该文法为算符文法。显然算符文法中没有下列形式的产生式 P-QR 例GE: EEE|E*E |(E) |i GE: EEAE|(E)|i A|*注：算符文法保证了两个运算符之间只有一个操作数。 证明：用归纳法设是句子，S，即S01.n-1n推导

16、长度是n，归纳起点n1时，S=0 1，即S，必存在一个规则S，而由算符文法的定义，文法的规则中无相邻的非终结符，满足性质1。 假设n1，n-1满足性质1。若n-1A，A为非终结符。由假设的的尾符号和的首符号都不是非终结符，否则与假设矛盾。又若A是文法的规则，则有n-1n=而A是文法的规则，它不含两个相邻非终结符，所以 也不含两个相邻的非终结符，满足性质1。*性质1：在算符文法中，任意句型都不含两个相邻的非终结符。性质2：若Ab或bA出现在算符文法的句型中，其中AVN ,bVT,则中任何含b的短语必包含A。 证明：用反证法。由算符文法的性质1可知。SbA若存在Bb，（b是仅含b但不含A的短语）这

17、时b和A不同时归约，分属于不同的短语，则必有SBA，这样在句型BA中，存在相邻的非终结符，所以与性质1矛盾。故：中任何含b的短语必包含A，证毕。*注意：含b的短语必含A，含A的短语不一定含b。二.算符优先文法的定义优先关系的定义定义6.2 设G是一个不含产生式的算符文法，A、B、C是非终结符，a、b是终结符，则算符优先关系定义为：1)a=b iff文法中有形如 Aab或A aBb2)ab iff文法中有形如 A Bb, 其中B a或B aV +1)当栈顶为a，预扫描的下一字符为b，应该执行移进操作，因为a和b在同一个产生式A中。2)当栈顶为a，预扫描的下一字符为b，应该执行移进操作，期望先规约

18、出B，然后再试图规约出A。3)当栈顶为a，预扫描的下一字符为b，应该先执行规约操作，规约出B，然后再移入b。以上三种关系存在语法子树如下图：算符优先文法的定义定义6.3 设有一OG文法,如果在任意两个终结符之间,至多只有上述关系中的一种成立,则称该文法为算符优先文法，也叫OPG（operator precedence grammar）文法。结论:算符优先文法是无二义的。例GE: EEE|E*E |(E) |i EE+T| E-T|T TT*F| T/F|F F(E)|i例8 文法GE：EE+E|E*E|(E)|i所有规则中都没有相邻的非终结符，所以它是算符文法OG。由于EE+E 和EE*E，所

19、以有+*运算符+和*之间存在两种不同的优先关系，所以该文法不是算符优先文法OPG。+三.算符文法和算符优先文法定义的意义 这两个定义相当于对文法的句型和可归约的短语做了如下规定：设A1A2Ai-1AiAi+1An是文法G的一个句型， 1、若AiVN，则Ai-1、Ai+1 VT，即不许出现相继两个非终结符； 2、若B1B2Bm是当前可归约短语，并可归约为Ai，则：a)B1B2Bm中不能有相继两个非终结符且相邻的终结符优先级别全相等；b)对于B1B2Bm中首终结符b有Ai-1 b；c)对于B1B2Bm中尾终结符b有b Ai+1。 注：实际上，可归约短语是某产生式右部符号串，所以通过检查G的每个产生

20、式的每个候选式，可以查找出任意优先级相同的终结符序偶。要找出所有满足关系 和 的终结符序偶，就要找出各非终结符B的首终结符集和尾终结符集。6.3.3 算符优先关系表的构造由定义直接构造由算法构造由关系图形构造一.由定义直接构造算符优先关系表1.求各个非终结符的首终结符集和尾终结符集 定义 （1）首终结符集FIRSTVT(B)=b|B b或B Cb.直观含义：对于非终结符B，其往下推导所可能出现的最左边的终结符集合（允许其左边有一非终结符集）思考：ABaBeFIRST（A）？FIRSTVT（A）？FIRST（B）？FIRSTVT（B）？（2）尾终结符集LASTVT(B)=a|B a或B . aC

21、直观含义：对于非终结符B，其往下推导所可能出现的最右边的终结符集合（允许其右边有一非终结符集）思考：ABaBeFollow（A）？LASTVT（A）？Follow（B）？LASTVT（B）？（1）=关系直接看产生式的右部，若出现了Aab或AaBb,则a=b（2）关系求出每个非终结符B的FIRSTVT(B)若AaB,则bFIRSTVT(B),a关系求出每个非终结符B的LASTVT(B)若ABb,则aLASTVT(B),ab2.三种优先关系的计算例9文法GE：(0) E#E#(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) PiFIRSTVT(E)=

22、#FIRSTVT(E)=+,*,(,iFIRSTVT(T)=*,(,iFIRSTVT(F)=,(,iFIRSTVT(P)=(,iLASTVT(E)=#LASTVT(E)=+,*,),iLASTVT(T)=*,),iLASTVT(F)= ,),iLASTVT(P)= ),i2)=关系 逐条扫描产生式,由产生式(0)和(6),得#=#，（=）4)关系找：ABb的产生式E# ,则 LASTVT(E)#E+ ,则 LASTVT(E)+ T* ,则 LASTVT(T)* P ,则 LASTVT(P) E) ,则 LASTVT(E)3）关系找：AaB产生式#E：则#FIRSTVT(E)+T: 则+FIRS

23、TVT(T) *F: 则*FIRSTVT(F)F: 则FIRSTVT(F)(E: 则(FIRSTVT(E)注意技巧！1)求每个非终结符的FIRSTVT和LASTVT表达式文法算符优先关系表：+*i()#+*i()#.二.由算法构造算符优先关系表1.构造FIRSTVT集的两条规则若有产生式Aa或ABa,则aFIRSTVT(A)若aFIRSTVT(B)，且有产生式AB,则aFIRSTVT(A)2.构造FIRSTVT集的算法（1）前期工作建立一个布尔数组Fm，n(m为非终结符个数，n为终结符个数)和一个后进先出栈STACK将所有的非终结符排序，用iA表示非终结符A的序号，再将所有的终结符排序，用ja

24、表示终结符a的序号（2）算法目的要使数组每一个元素最终取值满足：当且仅当aFIRSTVT(A)， FiA，ja的值为真（3）步骤【1】首先按第一条规则对数组元素赋初值为假，再经分析让所有初值为真的符号对(A, a)进栈STACK。【2】若栈不空，则逐项出栈记为(B, a)，对每个形如AB的产生式，若FiA，ja为假，则变为真且(A, a)入栈；反复操作，直至栈空。（4）程序描述PROCEDURE INSERT(A,a); IFNOT FiA，ja THEN BEGIN FiA，ja:=TRUE PUSH(A，a） ONTOSTACK END INSERT过程说明：当aFIRSTVT(A)时置F

25、iA，ja为真，并将符号对（A,a）下推到栈中主程序BEGIN（MAIN）FORi从1到m，j从1到n DO FiA，ja :=FALSE; */赋值符*/ FOR 每个形如Aa或ABa的产生式 DOINSERT（A,a) WHILE STACK 非空DO BEGIN 把STACK的顶项记为（B,a）弹出去 FOR每个形如AB的产生式DOINSERT（A,a) ENDEND（MAIN）例10文法GE：(0) E#E#(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) Pi 第一次扫描产生式后，栈STACK的初值为：（6） （P，i )（5） （P，

26、( )（4） （F，)（3） （T，* )（2） （E，+ )（1） （E，#)由产生式FP，TF，ET栈顶（6）的内容逐次改变为：（F,i)，（T,i)，（E,i)再无右部以E开始的产生式所以（E,i)弹出后无进栈项， 这时栈顶（5）为（P，()，同样由产生式： FP，TF，ET当前栈顶（5）的变化依次为： （F,( )， （T,( ) ，（E,( ) （E,( )弹出后无进栈项,此时当前栈顶（4）为（F，），由产生式TF，ET当前栈顶（4）的变化依次为： （T, )， （E,) （E, )弹出后无进栈项当前栈顶（3）为（T,*），由产生式ET，栈顶（3）变为（E，*），以下逐次弹出栈顶元素

27、后，都再无进栈项，直至栈空由算法可知，凡在栈中出现过的非终结符和终结符对，在相应数组元素的布尔值为真，在下表的数组中用“1”表示+*i()#EETFP布尔数组的值111111111111111由上表，我们得出FIRSTVT（A）集合为：FIRSTVT（E）FIRSTVT（E） +，*，(，iFIRSTVT（T） *，(，iFIRSTVT（F） ，(，i FIRSTVT（P） (，i与直接由定义计算结果相同。3.构造LASTVT集的两条规则若产生式Aa，或AaB，则aLASTVT(A)若有产生式AB，且aLASTVT(B)，则aLASTVT(A)4.构造LASTVT集的算法设一个栈ST,和一个布

28、尔数组H PROCEDURE INSERT(A,a) IF NOT HA,a THEN BEGIN HA,a:=TRUE;把(A,a)推进ST栈; END;BEGIN FOR 每个非终结符号A和终结符号a DO HA,a:=FALSE; FOR 每个形如Aa或AaB的产生式 DO INSERT (A,a); WHILE ST栈非空 DO BEGIN 把ST栈的栈顶弹出,记为(B,a); FOR 每条形如AB的规则 DO INSERT(A,a); END OF WHILE; END;三.由关系图形构造算符优先关系表图中的结点为某个非终结符的FIRSTVT集或终结符对每一个形如Aa和ABa的产生式

29、，则构造由FIRSTVT（A）结点到终点符结点用箭弧连接的图形对每一形如AB的产生式，则对应图中由FIRSTVT（A）结点到FIRSTVT（B）结点用箭弧连接若某一非终结符A的FIRSTVT（A）经箭弧有路径能到达某终结符结点a，则有aFIRSTVT（A）FIRSTVT(E)FIRSTVT(E)FIRSTVT(T)FIRSTVT(F)FIRSTVT(P)#+* ( i练习：用关系图求每个非终结符的LASTVT(A)的集合四.优先关系表的构造算法for 每条产生式BX1X2Xn for(i=1;in;i+) if ( Xi和Xi+1都是终结符) XiXi+1; if (i= n-2 且 Xi和X

30、i+2为终结符， Xi+1为非终结符) Xi =Xi+2; if (Xi为终结符而Xi+1为非终结符) for FIRSTVT(Xi+1)中的每个元素b XiXi+1; 例11 试构造例10中文法GE的优先关系表。 可根据优先关系表判断该文法是否为算符优先文法如果表中元素不存在冲突，即文法的任何终结符至多只存在一种优先关系，则该文法是一个算符优先文法一.算符优先分析句型的性质算符文法的任一句型有如下形式（不允许Ni相连）：#N1a1N2a2.NnanNn+1#,若Niai.NjajNj+1为句 柄，则有ai-1 ai+1根据算符优先文法的定义可知算符优先分析句型有如下性质： 如果aNb（或ab

31、）出现在句型r中，则a和b之间有且只有一种优先关系即若ab则在r中必含有b而不含a的短语存在若ab则在r中必含有a而不含b的短语存在若ab则在r中必含有a必含b的短语存在，反之亦然.6.3.4 算符优先分析算法说明： 算符优先分析法的归约过程与规范归约不同规范归约 严格按照句柄进行归约，终结符和非终结符一起考虑，只要栈顶形成句柄，不管句柄内是否包含终结符都要进行归约。 算符优先分析法的归约过程 在算符优先分析中，仅研究终结符之间的优先关系，而不考虑非终结符之间的优先关系，但句柄是由终结符和非终结符一起构成的，所以算符优先分析相对来说是非规范的分析。 例12 考虑非二义的表达式文法G(E)： E

32、E+T|T TT*F|F F(E)| i 识别语句 i+i*i的过程（1）规范归约i+i*i#1.F+i*i# 6. E+T*F# 2.T+i*i# 7. E+T#3.E+i*i# 8. E# 4.E+F*i# 5.E+T*i#（2）算符优先分析法的归约过程-i+i*i#1.E+i*i# 4. E+T#2.E+T*i# 5. E# 3.E+T*F#两种分析的语法树对比EE TT T * FF F i i iEE T i T * F i i【注】当单个非终结符是句柄时，算符优先法无法确定该非终结符为句柄因为未对非终结符定义算符优先关系，所以不能使用简单优先关系查找单个非终结符组成的句柄。因此，为

33、了实现算符优先方法进行归约，我们不能像在规范分析中那样简单地使用“句柄”这个概念，即这种分析仍然是自底向上的，但不是严格的从左到右。因此，引进素短语的概念。素短语是算符优先分析中要涉及的一个十分重要的概念。二.素短语 所谓素短语是指这样的一个短语，它至少含有一个终结符，并且除它自身之外不再含有任何更小的素短语。 最左素短语是指处于句型最左边的那个素短语。最左素短语是算符优先分析算法的可归约串。素短语是满足下面条件的短语：（1）至少包含一个终结符号。（2）该短语不再包含满足第一个条件的更小的短语。1.素短语和最左素短语定义例13文法GE：(1) EE+T(2) ET(3) TT*F(4) TF(

34、5) FPF|P(6) P(E)(7) Pi句型#T+T*F+i#其短语有：最左素短语：T*F素短语：T*F， i*EET+ETFFTTi句型T+T*F+i的语法树T+T*F+iT+T*FTT*Fi规范归约每次归约当前句型中的句柄，上面句型的句柄是T算符优先分析每次归约当前句型的最左素短语，T*F，去掉了单非终结符的归约，因为若只有一个非终结符时，无法与句型中该非终结符的左部和右部的串比较优先关系，也就无法确定该非终结符为句柄。2. 最左素短语的判断定理:一个OPG句型的最左素短语是描述下列条件的最左子串:NiaiNjajNj+1 ai-1aj+1寻找最左素短语的方法: 从左到右扫描符号串w

35、,找到第一个ajaj+1时,记下aj,再回扫, 找到第一个ai-1ai,此时, NiaiNi+1ai+1NjajNj+1就是应被子归约的最左素短语。 注意:出现在aj左端和ai右端的非终结符号一定属于 这个素短语,因为我们的运算是中缀形式给出 的(OPG文法的特点)NaNaNaN NaWaN例: 文法GE E:=E+T|T T:=T*F|F F:=(E)|i分析文法的句型T+T*F+i步骤句型关系最左子串规约符号1234#T+T*F+i#T+T+i#E+i#E+F#+#+#+#T*FT+TiE+FTEEF例14文法GE EE+T|T TT*F|F F(E)|i三.算符优先分析规约过程算法基本思

36、想：先利用关系找到最左素短语的尾，再利用关系aj+1为止；2）最左素短语尾已在符号栈S的栈顶，由栈顶向下找最左素短语的头符号，即找到第一个关系：ai-1ai；向栈中移进符号，以形成最左素短语寻找满足的sj a 的sj+1 ，即最左素短语的头S：符号栈K：栈顶a:输入符号j:指向素短语的前一个位置Q：Sj1k=1,sk=# ;/s为符号栈，#压入栈，sk为栈顶项do a=getsym( );/读入下一个符号给a if(skVT ) j=k; else j=k-1; while(sj a) do/在栈中寻找满足的sj a 的sj+1 ， 即最左素短语的头 Q= sj ; if(sj-1 VT )

37、j=j-1; else j=j-2; while(sj =Q) sj+1 sk N; /归约最左素短语 k=j+1; sk=N;/end of while if(sj a| sj = a)k=k+1;sk=a; /移进 else error while(a!=# | 符号栈中不是#S) 若出现j减1后的值小于等于0时，说明输入串有错，算法成功时，S中应为#N#。算法并没有指出应把所找到的最左素短语归约到哪一个非终结符号“N”。N是指这样一个产生式的左部符号，此产生式的右部和Sj+1Sk构成如下一一对应关系：自左至右，终结符对终结符，非终结符对非终结符，而且对应的终结符相同。由于非终结符对归约没

38、有影响，因此，非终结符根本可以不进栈。算法说明：1.算法中每次都取终结符进行比较，当栈顶符号不是终结符时，便取其下面符号（这时一定是终结符）2.归约时检查是否有与最左素短语对应的产生式，查看产生式的右部：符号个数与该素短语的符号个数相等非终结符位置对应，不管其符号名是什么终结符名字和位置都对应相等；若有满足以上条件的产生式才归约，否则出错构造方法非常简单分析速度也比较快诊查错误的能力较弱适用的范围小算符优先分析法的优缺点优点缺点关于算符优先分析的若干结论按算符优先分析所确定的归约子串恰好是当前句型的最左素短语(证明略);算符优先分析是自底向上的,但并不是规范归约,因此,每步所得句型不是规范句型

39、;由于分析过程中只考虑两个相邻VT之间的关系,VN无关紧要,所以归约所得的VN可任意命名;分析所得的语法树不是真正意义上的语法树,而是其分枝构架,它省略了单产生式的归约过程;分析算法可容易地形式化:引入一分析栈,先将#压入栈,分析时总是用栈顶符与当前扫描符进行比较,遇时回头查找最左素短语,归约之;若两个符号无关系,则报错.若栈顶为开始符S,扫描符为#,成功。6.3.5 优先函数在算符优先分析法中，文法终结符之间的优先关系是用矩阵表示的，这样需要大量的内存空间。当文法有n个终结符时，就需要(n+1)2个内存单元(包括#)。实际实现中使用优先函数来代替优先矩阵表示优先关系，对具有n个终结符的文法，它只需2(n+1)个内存单元存放优先函数，可以节省大量存储空间。优先关系表 (n+1)2 个单元优先函数表 2(n+1) 个单元i+#i+#=i