语法分析哈工大王宏志.ppt

《语法分析哈工大王宏志.ppt》由会员分享，可在线阅读，更多相关《语法分析哈工大王宏志.ppt（179页珍藏版）》请在三一办公上搜索。

1、语法分析,回顾 一个语句的翻译,P483附录：Pascal子集的词法和语法,第四章 语法分析1,语法分析方法 递归子程序法自顶向下 预测分析法(LL（1）)算符优先分析法自底向上 LR(0)、SLR(1)LR(1)、LALR,Top Down,Bottom Up,文法产生语言,自动机识别语言,从根开始，逐步为某语句构造一棵语法树,相反，将一句子归约为开始符号,问题：解决确定性问题！假定文法是压缩的：即删除了单位产生式和无用产生式。,4.1 语法分析的功能,检查由扫描器输出的单词符号序列是否符合该语言的文法句子,分析器的输入：Token序列分析器的输出分析树出错处理:定位、续编译,分析方法自顶向

2、下（递归下降、预测分析)自底向上（算符优先、LR分析器）,4.2 自上而下分析面临的问题与CFG的改造,一、自上而下的分析从文法的开始符号出发，寻求所给的输入符号串的一个最左推导。从树根S开始，构造所给输入符号串的语法树例：G为：SxAy A*|*，输入串：x*y,SxAy,x*y,S,二、存在问题回溯,S xAy x*y,x*y,S xAy x*y匹配成功,x*y,发现不匹配,需要回退,输入串x*ySxAy A*|*,存在回溯的原因,文法中每个非终结符A的产生式右部称为A的候选式，如果有多个候选式左端第一个符号相同，则语法分析程序无法根据当前输入符号选择产生式，只能试探。,二、存在问题左递归

3、问题,文法SSay|*与它的句子*ayay,*ayay,S*不对！,SSaySayaySayayaySayayayay,一个无限循环！,二、重要问题左递归问题,例 CFG:简单算术表达式的文法（语法）EE+T|E-T|TTT*F|T/F|FF(E)|idNE,T,F,P,FUN,LTid,+,-,*,/,(,)E,三、重要概念回顾,推导:(依据：)最左(Left-most)推导最左分析左句型最左推导对应最右归约最右(Right-most)推导最右分析规范推导、规范句型（右句型）最右推导对应最左归约（规范归约）二义性(先天二义性语言、二义性文法),四、消除二义性,例：简单算术表达式的文法二义性文

4、法EE+E|E-E|E*E|E/E|(E)|id非二义性文法EE+T|E-T|TTT*F|T/F|FF(E)|id改造方法：使文法含有更多的信息，引入语法变量,四、消除二义性,再例：If语句Sif E then SSif E then S else SSother设执行下列语句前b=0,If a0 then if a0 then b=1 else b=-1当a=1时,b=1;当a=-1时，b=-1If a0 then if a0 then b=1 else b=-1当a=1时,b=1;当a=-1时，b=0,一个句子有两棵不同的语法树,SSE ES SIf a0 then if a0 then

5、b=1 else b=-1SSE ES SIf a0 then if a0 then b=1 else b=-1,四、消除二义性 P174,重写文法：引入新的语法变量SU|MUif E then SUif E then M else UMif E then M else M|other,每个else与前面最近的没有配对的then配对，即：出现在then和else之间的语句必须是配对的,按照改造后的文法构造的语法树,SUSMEEMMIf a0 then if a0 then b=1 else b=-1,Mif E then M else M|other,五、消除左递归,无法根据左递归文法进行自顶

6、向下的分析A a1a2aian直接左递归A A 当前变量 输入指针(栈顶、最左变量),间接左递归A+A左递归的消除方法将AA|替换为AA 和 AA,例：表达式文法直接左递归的消除,E E+TTT T*FFF(E)id,E T EE+T E|T F TT*F TF(E)id,例：间接左递归的消除,SAc|c ABb|b BSa|a将B的定义代入A产生式得：ASab|ab|b将A的定义代入S产生式得:SSabc|abc|bc|c消除直接左递归：SabcS|bcS|cSSabcS|删除“多余的”产生式：ASab|ab|b和BSa|a 结果：SabcS|bcS|cSSabcS|,消除左递归的一般方法,

7、用产生式组A1 B|2 B|n BB1 B|2 B|n B|替换产生式组AA1|A2|An|1|2|m 其中：B为新变量，相当于A消除左递归的算法见P117的算法4.1为非终结符编号，再采用代入法将间接左递归变为直接左递归，消除直接左递归,六、解决回溯问题提取左因子,例：if语句的原始文法S if E then S|if E then S else S|other影响分析:遇到 if 时难以判断用哪一个产生式进行匹配（推导）存在左因子 if E then S,左因子提取方法,将形如 A1|2|n|1|2|m的规则改写为AA|1|2|m和 A1|2|n结果：S if E then SS|othe

8、rS|else S,七、CFG的使用限制,没有一种方法能够有效地分析所有上下文无关文法存在无法处理的型文法(CFG)每种方法能够处理一部分上下文无关文法每种方法都有适用范围,八、常用文法与分析方法,LL文法和 LR 文法都是CFG的子集(无二义性)可用不同的文法来描述同一语言对于不同的文法，可用不同的分析方法LL文法 递归下降分析法、预测分析法LR文法 LR分析法LL 文法多用于编译的手工实现LR 文法多用于编译的自动生成,4.3 自顶向下的分析方法,基本思想寻找输入符号串的最左推导试图根据当前输入单词判断使用哪个产生式基本过程从根开始，按与最左推导相对应的顺序，构造输入符号串(Token)的

9、分析树,例 符号串 id+id*id的分析,E T E E+T E T F T T*F T F(E)id 按照最左推导过程，构造分析树,id+id*id最左推导与语法树的生成对应,i d,i d,i d,1、ETE,2、TFT,3、Fid,4、T,5、E+TE,6、TFT,7、Fid,8、T*FT,9、Fid,10、T,11、E,id+id*id的最左推导再现,E TEE TE FTET FTidTEF id idET id+TEE+TE id+FTET FT id+idTEF id id+id*FTET*FT id+id*idTE F id id+id*idE T id+id*id E,候选

10、式的确定与回溯,给定文法ScAdAab|a?句子cad是该文法定义语言的句子SScAdcAd a ba产生式(候选式)的选择与回溯(Backtracking)：当要进行关于某个语法变量的推导时，希望能够根据当前符号确定候选式。如果有几个候选式（右部）左端第一个符号相同，则分析程序无法根据当前输入符号选择产生式，只能试探。,无回溯的条件,设A1|2|n是所有的A产生式如果各个i能推导出的首终结符各不相同，则可以构造无回溯的分析。,4.3.1 FIRST 和 FOLLOW 集,对于(TN)*定义:的首符号集FIRST()=a|*a，aT*如果存在A这样的产生式，则需定义FOLLOW(A）对于AN定

11、义A的后续符号集：FOLLOW(A)=a|S*Aa，aT,求FIRST(X)的算法,1)对xT，FIRST(x)=x；2)对XN，取FIRST(X)的初值：a|XaP；XPFIRST(X)=a|XaP；XP,3)对XN，重复如下过程，直到所有FIRST集不变若 XYP，且 YN，则 FIRST(X)=FIRST(X)(FIRST(Y)-)；若 XY1YnP，且Y1.Yi-1*，则 对k=1到i-1:FIRST(X)=FIRST(X)(FIRST(Yk)-)；若 Y1.Yn*，则 FIRST(X)=FIRST(X)。,例 表达式文法的语法符号的 FIRST 集,FIRST(F)=（,idFIRS

12、T(T)=FIRST(F)=（,id FIRST(E)=FIRST(T)=（,id FIRST(E)=+，FIRST(T)=*,FIRST(+)=+,FIRST(*)=*FIRST(（)=（FIRST(）)=）FIRST(id)=id,ETE E+TE|TFT T*FT|F(E)|id,求FIRST()的算法,令=X1Xn初值FIRST()=FIRST(X1)-;k=1;循环while FIRST(Xk)结束处理if k=n&FIRST(Xk)then FIRST()=FIRST(),求FOLLOW(A)的算法,对于所有非终结符,重复进行以下计算1)将#加入到 FOLLOW(S)#为句子的结束

13、符2)若 AB，则 FOLLOW(B)=FOLLOW(B)FIRST()3)如果AB或AB，且*，AB，则 FOLLOW(B)=FOLLOW(B)FOLLOW(A),例 表达式文法的语法变量的 FOLLOW 集,FOLLOW(E)=#,)FOLLOW(E)=FOLLOW(E)=#,)FOLLOW(T)=FIRST(E)FOLLOW(E)FOLLOW(E)=+,),#FOLLOW(T)=FOLLOW(T)=+,),#FOLLOW(F)=FIRST(T)FOLLOW(T)FOLLOW(T)=*,+,),#,ETE E+TE|TFT T*FT|F(E)|id,FIRST(F)=（,idFIRST(T

14、)=FIRST(F)=（,id FIRST(E)=FIRST(T)=（,id FIRST(E)=+，FIRST(T)=*,自顶向下分析希望文法满足的条件,我们希望：从左到右扫描输入串寻找它的一个最左推导对于 G 的每个非终结符 A 的任何两个不同的候选式 A|1)FIRST()FIRST()=2)如果*，则 FIRST()FOLLOW(A)=文法是 LL(1)的充要条件,4.3.2 LL(1)文法,对G中的任意变量A，A1|2|n是G的所有A产生式，它们满足下列条件，则称G是LL(1)文法，FIRST(i)FIRST(j)=ij当FIRST(j)时，FOLLOW(A)FIRST(i)=LL(1

15、)文法表示了自顶向下方法能够处理的一类文法第一个 L 表示从左向右扫描输入符号串第二个 L 表示生成最左推导1 表示读入一个符号可确定下一步推导,表达式文法是 LL(1)文法,E T E E+T E T F T T*F T F(E)id考察E:+不在 FOLLOW(E)=),#T:*不在 FOLLOW(T)=+,),#F:(和 id 不同,非 LL(1)文法的不确定性,例 对文法ScAdAab|a 输入 cad 的分析,不确定性的解决方法,1)采用回溯算法过于复杂2）改写文法将非 LL(1)文法改写为等价的 LL(1)文法无法改写时：增加其它的判别因素文法过于复杂，无法用自顶向下方法处理,4.

16、4 预测分析器（LL(1)分析器）,系统维持一个分析表和一个分析栈，根据当前扫描到的符号，选择当前语法变量（处于栈顶）的候选式进行推导希望找到相应的输入符号串的最左推导。一个通用的控制算法一个分析栈，#为栈底符号一个输入缓冲区，#为输入串结束符一个统一形式的分析表M不同语言使用内容不同的分析表,系统结构,FOLLOW(E)=),#FOLLOW(T)=+,),#FIRST(TE)=(,id FIRST(+TE)=+FIRST(FT)=(,id FIRST(*FT)=*FIRST(E)=(FIRST(id)=id,ETE E+TE|TFT T*FT|F(E)|id,考虑简单算术表达式文法的实现,表

17、达式文法的预测分析表,执行过程举例：分析 id+id*id（在黑板上同时画出语法树）,栈 输入缓冲区 输出#E id+id*id#ET id+id*id#ETE#ETF id+id*id#TFT#ETid id+id*id#Fid#ET+id*id#E+id*id#T#ET+id*id#E+TE#ET id*id#,#ETF id*id#TFT#ETid id*id#Fid#ET*id#ETF*id#T*FT#ETF id#ETid id#Fid#ET#E#T#E,输出的产生式序列形成了最左推导对应的分析树,#ET id*id#,系统的执行与特点,在系统启动时，输入指针指向输入串的第一个字符，

18、分析栈中存放着栈底符号#和文法的开始符号。根据栈顶符号A和读入的符号a，查看分析表M,以决定相应的动作。优点：1）效率高2）便于维护、自动生成关键分析表M的构造,预测分析表（LL(1)分析表）的构造算法,1)对于每一产生式 A，执行2)和3)；2)对于 FIRST()中的每一终结符a,将 A 填入 MA,a；3)如果属于 FIRST()，则对FOLLOW(A)中的每个非终结符b，将A填入MA,b；若属于 FIRST()，且#在FOLLOW(A)中，则将将A填入MA,#；4)将所有无定义的 MA,b 标上错误标志。,LL(1)通用控制算法,repeatX=当前栈顶符号;a=当前输入符号；if X

19、T#thenif X=a then if X#then 将X弹出,且前移输入指针else errorelse if MX,a=Y1Y2Yk then将X弹出;依次将YkY2Y1压入栈；输出产生式XY1Y2Yk else erroruntil X=#,预测分析法,1）构造文法2）改造文法：消除二义性、消除左递归、提取左因子3）求每个候选式的FIRST集和变量的FOLLOW集4）检查是不是 LL(1)文法若不是 LL(1),说明文法的复杂性超过自顶向下方法的分析能力，需要附加新的“信息”5）构造预测分析表6）实现预测分析器,出错处理问题,对语法变量A，如果MA,a无定义，并且a属于FOLLOW(A

20、)，则增加MA,a为“同步点”(synch)详见教材P127,关键是同步记号的选择,把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合。把高层结构的开始符号加到低层结构的同步记号集合中。把FIRST(A)的终结符加入A的同步记号集合。如果非终结符可以产生空串，若出错时栈顶是这样的非终结符，则可以使用产生空串的产生式。如果终结符在栈顶而不能匹配，弹出此终结符。,一个设想,对应每个变量设置一个处理子程序：AX1 X2 Xk Xn当遇到Xk是终极符号时直接进行匹配当遇到Xk是语法变量时就调用X对应的处理子程序要求处理子程序是可以递归调用的,ETE E+TE|TFT T*FT|F(E)|id

21、,4.5 语法图和递归子程序法,状态转换图（语法图）是非常有用的设计工具语法分析器和词法分析器的状态转换图不同每个非终结符对应一个状态转换图，边上的标记是记号和非终结符记号上的转换意味着如果该记号是下一个输入符号，就应进行转换非终结符A上的转换是对与A对应的过程的调用从文法构造语法图，对每个非终结符A执行如下操作：创建一个开始状态和一个终止状态（返回状态）。对每个产生式AX1X2 Xn，创建一条从开始状态到终止状态的路径，边上的标记分别为X1，X2，。，Xn。,基于语法图的分析器工作方式,开始，分析器进入状态图的开始状态，输入指针指向输入符号串的第一个符号。如果经过一些动作后，它进入状态s，且

22、从状态s到状态t的边上标记了终结符a，此时下一个输入符又正好是a，则分析器将输入指针向右移动一位，并进入状态t。另一方面，如果边上标记的是非终结符A，则分析器进入A的初始状态，但不移动输入指针。一旦到达A的终态，则立刻进入状态t，事实上，分析器从状态s转移到状态t时，它已经从输入符号串“读”了A（调用A对应的过程）。最后，如果从s到t有一条标记为的边，那么分析器从状态s直接进入状态t而不移动输入指针。,4.5 语法图,例 4-9：表达式文法的描述,+,T,E,E,T,E,E,ETE E+TE|TFTT*FT|F(E)|id,语法图化简规则（1/2）,Y,X,Y,Z,Y,X,Z,X,左因子提取,

23、右因子提取,AYX|YZAY(X|Z),AYX|ZXA(Y|Z)X,语法图化简规则（2/2）,Y,X,Z,X,XYX|ZAY*Z,语法图的化简,+,T,E,+,T,T,E,E+TE|,ETEET(+T)*,简化的语法图,+,T,E,i d,（,）,ET(+T)*,TF(*F)*,F(E)|id,例 简单算术表达式的分析器,的子程序(ET(+T)*)procedure E;begin T;的过程调用 while lookhead=+do begin 当前符号等于时 match(+);处理终结符 T 的过程调用 end end;lookhead：当前符号,的子程序(TF(*F)*),procedu

24、re T;begin F;的过程调用 while lookhead=*then begin 当前符号等于时 match(*);处理终结符 F 的递归调用 end end;,的子程序(F(E)|id),procedure F;begin if lookhead=(then begin 当前符号等于（match();处理终结符（E;的递归调用 match();处理终结符）end else if lookhead=id then match(id)处理终结符id else error 出错处理 end,主程序,begin lookhead:=nexttoken;调词法分析程序 E 的过程调用end,

25、procedure match(t:token);begin if lookhead=t then lookhead:=nexttoken else error 出错处理程序 end;,服务子程序,递归子程序法,1）构造文法2）改造文法：消除二义性、消除左递归、提取左因子3）求每个候选式的FIRST集和变量的FOLLOW集4）检查是不是 LL(1)文法若不是 LL(1),说明文法的复杂性超过自顶向下方法的分析能力，需要附加新的“信息”,递归子程序法,5）按照 LL(1)文法画语法图6）化简语法图7）按照语法图，编写程序按照语法图，为每个非终结符设置一个子程序。事实上，如果有一个恰当的文法，可以

26、直接根据每个语法变量的产生式设计相应的程序,优缺点分析,优点：1）直观、简单、可读性好2）便于扩充缺点：1)递归算法的实现效率低2)处理能力相对有限3)通用性差，难以自动生成从递归子程序法及FIRST与FOLLOW集看如何进一步用好当前的输入符号？,习题,1、构造如下给定文法的预测分析表 S A B A B a|B D b|D D d|2、判断下述文法可否改写为 LL(1)文法a.SA|B AaA|a BbB|bb.Si|(E)EE+S|E-S|S,练习,3、改写以下文法，消除左递归M M a H|HH b(M)|(M)|b4、求以下文法中各非终结符的FIRST集和FOLLOW集A b a B

27、|B A b b|a5、构造如下给定文法的递归子程序 S a|(T)T T,S|S,思考题,1)能否直接用语法图描述 EE+E|E-E|E*E|E/E|-E|(E)|id|const，并用递归子程序法实现语法分析？为什么？2)能否将各种单词的文法直接并入表达式语法，进行语法分析处理？试分析这样做会有哪些好的影响和不好的影响。,上机题,给定下列文法：Sid=E;Sif C then S Swhile C do S CEE CE=E用递归子程序法设计并实现语法分析程序，按照生成顺序输出产生式,5.1 自底向上分析,思想从输入串出发，反复利用产生式进行归约，如果最后能得到文法的开始符号，则输入串是句

28、子，否则输入串有语法错误。核心寻找句型中的当前归约对象“句柄”进行归约,用不同的方法寻找句柄，就可获得不同的分析方法,一个简单的归约过程,例 设文法为：SaAcBeAAb|bBd,句子分析：abbcdeaAbcdeaAcde aAcBe S,a b b c d e,语法树的形成过程,回忆几个概念,最左推导(Left-most Derivation)每次推导都施加在句型的最左边的语法变量上。与最右归约对应最右推导(Right-most Derivation)每次推导都施加在句型的最右边的语法变量上。与最左归约（规范归约）对应，得规范句型/右句型,回忆几个概念,如果*and A+，则称是句型的相对

29、于变量A的短语(Phrase)如果*and A，则称是句型的相对于变量A的直接（简单）短语最左直接短语叫做句柄(Handle),回忆几个概念,规范归约(另一表达)：设为文法 G 的句子，如果1)=nn-121=2)对每个i(1in)，i-1是将句型i中的句柄归约后得到的句型则称序列 n，.，1为的规范归约序列由规范归约组成,语法分析树的生成再演示,a b b c d e,A,A,B,S,Ab,AAb,Bd,SaAcBe,分析设想移进归约,系统框架输入缓冲区：保存输入符号串控制程序：控制分析过程，输出分析结果产生式序列栈：保存语法符号已经得到的部分结果栈+输入缓冲区剩余内容=“句型”,分析器结构

30、,id+id id#,#,移进归约控制程序,输出产生式序列,栈内容+输入缓冲区内容#“当前句型”#,栈,输入缓冲区,分析表,与LL(1)的体系结构比较,输入缓冲区(符号序列),栈,控制程序P123,预测分析表M,输出的产生式序列,分析设想移进归约,系统运行开始格局栈：#；输入缓冲区：w#存放已经分析出来的结果,并将读入的符号送入栈，一旦句柄在栈顶形成，就将其弹出进行归约，并将结果压入栈？系统如何发现句柄在栈顶形成正常结束:栈中为#S，输入缓冲区只有#,输出结果表示：用产生式序列表示语法分析树,E id,id+id*id,E,E,E,E,E,E id,E id,E E*E,E E+E,动作 栈

31、输入缓冲区,1)#id1+id2*id3#,id+id*id,2)移进#id1+id2*id3#,例5-3分析过程,3)归约 Eid#E+id2*id3#,4)移进#E+id2*id3#,5)移进#E+id2*id3#,6)归约 Eid#E+E*id3#,7)移进#E+E*id3#,8)移进#E+E*id3#,9)归约 Eid#E+E*E#,10)归约 EE*E#E+E#,11)归约 EE+E#E#,12)接受,分析器的四种动作,1)移进：将下一输入符号移入栈2)归约：用产生式左侧的非终结符替换栈顶的句柄（某产生式右部）3)接受：分析成功4)出错：出错处理？决定移进和归约的依据是什么回头看是否

32、可以找到答案,移进归约分析中的问题,1)移进归约冲突 例5-3中的 6)可以移进*或按产生式EE+E归约,动作 栈 输入缓冲区,1)#id1+id2*id3#,id+id*id,2)移进#id1+id2*id3#,例5-3分析过程,3)归约 Eid#E+id2*id3#,4)移进#E+id2*id3#,5)移进#E+id2*id3#,6)归约 Eid#E+E*id3#,7)移进#E+E*id3#,8)移进#E+E*id3#,9)归约 Eid#E+E*E#,10)归约 EE*E#E+E#,11)归约 EE+E#E#,12)接受,移进归约分析中的问题,1)移进归约冲突 例5-3中的 6)可以移进*

33、或按产生式EE+E归约 2)归约归约冲突 存在两个可用的产生式各种分析方法处理冲突的方法不同如何识别句柄？如何保证找到的直接短语是最左的?利用栈如何确定句柄的开始处与结束处？,优先法,根据归约的先后次序为句型中相邻的文法符号规定优先关系句柄内相邻符号同时归约，是同优先的句柄两端符号的优先级要高于句柄外与之相邻的符号a1ai-1aiai+1aj-1ajaj+1an,状态法,根据句柄的识别状态（句柄是逐步形成的）用状态来描述不同时刻下形成的那部分句柄因为句柄是产生式的右部，可用产生式来表示句柄的不同识别状态例如：SbBB可分解为如下识别状态S.bBB 移进bSbB.B 等待归约出BSb.BB 等待

34、归约出BSbBB.归约,5.2 算符优先分析法,算术表达式分析的启示算符优先关系的直观意义+*+的优先级低于*()(的优先级等于)+的优先级高于+方法将句型中的终结符号当作“算符”，借助于算符之间的优先关系确定句柄,算术表达式文法的再分析,EE+EEE-EEE*EEE/E E(E)EidEE+T|E-T|T TT*F|T/F|F F(E)|id,从如何去掉二义性,看对算符优先级的利用,句型的特征：(E+E)*(E-E)/E/E+E*E*E,算符文法,如果文法G=（VN，VT，P，S）中不存在形如ABC 的产生式，则称之为算符文法(OG Operator Grammar)即：如果文法 中不存在具

35、有相邻非终结符的产生式，则称为算符文法。,算符间的优先关系,设G=（VN，VT，P，S）为OG，则定义ab AabP或者 AaBbPab AaBP且(B+b或者B+Cb)ab ABbP且(B+a或者B+aC)什么是算符优先文法？,算符优先文法,设G=（V，T，P，S）为OG，如果 a,bVT,ab,ab,ab 至多有一个成立，则称之为算符优先文法(OPG Operator Precedence Grammar)在无产生式的算符文法中，如果任意两个终结符之间至多有一种优先关系，则称为算符优先文法。,算符优先关系的确定_算符优先矩阵,优先关系的确定根据优先关系的定义ab AaBP且(B+b或者B+

36、Cb)需要求出非终结符B派生出的第一个终结符集ab ABbP且(B+a或者B+aC)需要求出非终结符B派生出的最后一个终结符集设G=（VN，VT，P，S）为OG，则定义FIRSTOP(A)=b|A+b或者A+Bb,bVT,B VNLASTOP(A)=b|A+b或者A+bB,bVT,B VN,算符优先关系矩阵的构造,Aab;AaBb,则abAaB,则对bFIRSTOP(B),abABb,则对aLASTOP(B),abif ABP,then FIRSTOP(B)FIRSTOP(A)if ABP,then LASTOP(B)LASTOP(A)?编程求FIRSTOP、LASTOP,算符优先关系矩阵的构

37、造,AX1X2Xn如果XiXi+1VTVT则：XiXi+1如果XiXi+1Xi+2VTVNVT则：XiXi+2如果XiXi+1VTVN则：aFIRSTOP(Xi+1)，Xia如果XiXi+1VNVT则：aLASTOP(Xi)，aXi+1,例 4-12：表达式文法的算符优先关系,acc,+-*/()id#,+-*/（）id#,算符优先分析算法,原理识别句柄并归约，利用识别句柄尾，利用识别句柄头，分析栈存放已识别部分，比较栈顶和下一输入符号的关系，如果是句柄尾，则沿栈顶向下寻找句柄头，找到后弹出句柄，归约为非终结符。,分析例：id+id#id+id#F+id#F+id#F+id#F+F#E#,EE

38、+T|E-T|T TT*F|T/F|F F(E)|id,问题,有时未归约真正的句柄（F）不是严格最左归约归约的符号串有时与产生式右部不同仍能正确识别句子的原因OPG未定义非终结符之间的优先关系，不能识别由单非终结符组成的句柄定义算符优先分析过程识别的“句柄”为最左素短语LPP（Leftmost Prime Phase）,素短语与最左素短语,什么是短语？当前我们要找什么样的短语？至少有一个算符*and A+，至少含一个终结符，且不含更小的含终结符的短语,则称是句型的相对于变量A的素短语(Prime Phrase)句型的至少含一个终结符且不含其它素短语的短语,例,EE+T|T TT*F|F F(E

39、)|id句型 T+T*F+i 的短语有T*F i T*F+i T+T*F+i其中的素短语为T*F iT*F为最左素短语，是被归约的对象？按照文法EE+E|E*E|(E)|id，求i+E*i+i的短语和素短语,E E E T T FT+T*F+i,文法：EE+E|E*E E(E)|id句型i+E*i+i的短语,归约过程中如何发现“中间句型”的最左素短语？,i i E*i i i+E*i i+E*i+i其中的素短语为i i i,素短语与最左素短语,设句型的一般形式为#N1a1 N2a2 Nnan#(Ni VN,ai VT）它的最左素短语是满足下列条件的最左子串Niai Ni+1ai+1 Njaj

40、Nj+1其中：ai-1ai,，aiai+1aj-1aj，ajaj+1,算符优先分析的实现,系统组成移进归约分析器+优先关系表分析算法 P136/93陈参照输入串、优先关系表，完成一系列归约，生成语法分析树输出产生式,id+id*id 的分析过程,id+id*id#,算符优先分析控制器,E id,E id,E id,E E*E,E E+E,算符优先关系表,#,id#,#,+#,id+#,+#,*+#,id*+#,*+#,+#,#,算符优先函数,为了节省存储空间（n2 2n）和便于执行比较运算，用两个优先函数f和g，它们是从终结符号到整数的映射。对于终结符号a和b选择f和g，使之满足：f(a)g(

41、b)，如果a b。损失错误检测能力降低如：id id不存在，但f(id)g(id)可比较,图4-25对应的优先函数：,1)构造优先函数的算法不是唯一的。2）存在一组优先函数，那就存在无穷组优先函数。,算法4.5 从优先关系构造优先函数方法：1.aVT$,建立两个符号fa和ga;2.若a b,则把fa和gb分在一组；3.a，b VT，若a b，则从fa至gb画一条弧；若a b，则从gb至fa画一条弧;4.若图中无环，则存在优先函数，f(a)和g(b)等于从fa 和gb出发的 最长路径。,.,gid,fid,f*,g*,g+,f+,f$,g$,算符优先分析法小结,优点简单、效率高能够处理部分二义性

42、文法缺点文法书写限制大占用内存空间大不规范、存在查不到的语法错误,1、习题:给出布尔表达式的文法，构造其算符优先关系表 bexpr bexpr OR bexprbexpr bexpr AND bexprbexpr NOT bexprbexpr(bexpr)bexpr TRUEbexpr FALSE,算符优先分析法存在的问题强调算符之间的优先关系的唯一性，这使得它的适应面比较窄算法在发现最左素短语的尾时，需要回头寻找对应的头,5.3 LR(Left-Right)分析法,LR(k)分析法可分析LR(k)文法产生的语言L：从左到右扫描输入符号R：最右推导对应的最左归约k：超前读入k个符号，以便确定归

43、约用的产生式使用语言的文法描述内涵解决句柄的识别问题，从语言的形式描述入手，为语法分析器的自动生成提供了前提和基础分析器根据当前的状态，并至多向前查看k个输入符号，就可以确定是否找到了句柄，如果找到了句柄，则按相应的产生式归约，如果未找到句柄则移进输入符号，并进入相应的状态,分析器的总体结构,a1 ai an#,LR主控程序,动作表action,转移表goto,产生式序列,状态/符号栈,输入缓冲区,SmSm-1S1S0,XmXm-1X1#,LR 分析表：actions,a；gotos,X,LR(0)、SLR(1)、LR(1)、LALR将以不同的原则构造这张分析表,约定：sn:将符号a、状态n压

44、入栈rn:用第n个产生式进行归约,LR分析器的工作过程,书上的下式（格局）(s0s1sm，X1X2 Xm，aiai+1an#)在这里表示为s0s1sm#X1Xm aiai+1an#,LR分析器的工作过程,1.初始化s0#a1a2an#对应“句型”a1a2an,2.一般情况下s0s1 sm#X1Xm aiai+1an#对应“句型”X1Xmaiai+1an,If actionsm,ai=si(shift i)then 格局变为s0s1 sm i#X1Xmai ai+1an#,s0s1sm#X1Xm aiai+1an#,If actionsm,ai=acc then 分析成功If actionsm,

45、ai=err then 出现语法错,If actionsm,ai=ri(Reduce i)then 表示用第i个产生式AXm-(k-1)Xm进行归约，格局变为,s0s1 sm-k#X1Xm-kA aiai+1an#,查goto表，当gotosm-k,A=i then 格局变为s0s1 sm-k i#X1Xm-kA aiai+1an#,LR分析器主控程序(LR分析算法),置输入指针 ip 指向 w#的第一个符号；令s是栈顶状态，a 是 ip 所指向的符号;分析栈中为#和开始状态0重复执行如下过程(P144)if actions,a=si(shift i)then 把符号 a 和状态i先后压入栈；

46、使 ip 指向下一符号,elseif actions,a=ri(reduce A)then 从栈顶弹出 2*|个符号；令s是现在的栈顶状态；把 A 和 gotos,A先后压入栈中；输出产生式 A elseif actions,a=accept(acc)then return else error()；,例,文法1)SBB2)BaB3)Bb,分析表,请跟随讲解，快速抄下右侧的表格！,bab 的分析过程:1)SBB2)BaB3)Bb,栈 输入 动作说明0#bab#action(0,b)=s404#b ab#action(4,a)=r30#B ab#goto(0,B)=202#B ab#action

47、(2,a)=s3023#Ba b#action(3,b)=s40234#Bab#action(4,#)=r3023#BaB#goto(3,B)=60236#BaB#action(6,#)=r2,02#BB#goto(2,B)=5025#BB#action(5,#)=r1 0#S#goto(0,S)=1 01#S#action(1,#)=acc,规范句型活前缀,分析栈中内容+剩余输入符号=规范句型分析栈中内容为某一句型的前缀来自分析栈的活前缀(Active Prefix)不含句柄右侧任意符号的规范句型的前缀例：id+id*id 的分析中句型 E+id.*id 和 E+E*.id,活前缀,活前缀,

48、S*rmAw rm 12w,规范句型活前缀,规范归约所得到的规范句型(Canonical Sentential Form)的活前缀是出现在分析栈中的符号串，所以，不会出现句柄之后的任何字符，而且相应的后缀正是输入串中还未处理的终结符号串。活前缀与句柄的关系包含句柄 A.包含句柄的部分符号A1.2 不含句柄的任何符号A.,一、LR(0)分析表的构造,LR(0)项目从产生式寻找归约方法右部某个位置标有园点的产生式称为相应文法的LR(0)项目（Item）例 S.bBB SbB.B Sb.BB SbBB.归约（Reduce）项目:SaBB.移进（Shift）项目：S.bBB待约项目：Sb.BB SbB

49、.B,项目的意义,用项目表示分析的进程(句柄的识别状态)方法：在产生式右部加一园点以分割已获取的内容和待获取的内容：构成句柄,b a b,B,B,B,S,S B.B B.a B,拓广(Augmented)文法,需要一个对“归约成S”的表示（只有一个接受状态）文法 G=(VN,VT,P,S)的拓广文法 G：G=（VN S，VT，P SS，S）SV对应S.S（分析开始）和SS.（分析成功）例 4-13 0)SS1)SBB2)BaB3)Bb,构造识别G的所有规范句型活前缀的DFA,？如何设计能够指导分析器运行，并且能够根据当前状态（栈顶）确定句柄归约对象的头的装置,例4-13SBBBaBBb,I0:

50、S.SS.BBB.aBB.b,I1:SS.,S,B,I2:SB.BB.aBB.b,a,I4:Ba.BB.aBB.b,b,I3:Bb.,B,I5:SBB.,a,b,B,I6:BaB.,a,b,核心项目Kernel Item,识别表达式文法的所有活前缀的DFA,拓广文法 0)1)+2),3)*4)5)()6)id,I0:E.E E.E+TE.TT.T*FT.FF.(E)F.id,E,I1:EE.EE.+T,T,I2:ET.TT.*F,F,I3:TF.,(,I4:F(.E)E.E+TE.TT.T*FT.FF.(E)F.id,id,I5:Fid.,+,I6:EE+.TT.T*FT.FF.(E)F.id