第四章语法分析,哈工大王宏志

《第四章语法分析,哈工大王宏志》由会员分享，可在线阅读，更多相关《第四章语法分析,哈工大王宏志（179页珍藏版）》请在装配图网上搜索。

1、语法分析语法分析回顾回顾 一个语句的翻译一个语句的翻译P483P483附录：附录：PascalPascal子子集的词法和语法集的词法和语法第四章第四章 语法分析语法分析1 1n语法分析方法语法分析方法 递归子程序法递归子程序法n自顶向下自顶向下 预测分析法预测分析法(LLLL（1 1）)算符优先分析法算符优先分析法n自底向上自底向上 LR(0)LR(0)、SLR(1)LR(1)SLR(1)LR(1)、LALRLALRTop DownTop DownTop DownTop DownBottom UpBottom UpBottom UpBottom Up文法产生语言自动机识别语言从根开始，逐步从根

2、开始，逐步为某语句构造一为某语句构造一棵语法树棵语法树相反，将一句子相反，将一句子归约为开始符号归约为开始符号问题：解决确定性问题！问题：解决确定性问题！假定文法是压缩的：即删除了单位产生式和无用产生式。假定文法是压缩的：即删除了单位产生式和无用产生式。4.1 4.1 语法分析的功能语法分析的功能n检查由扫描器输出的单词符号序列检查由扫描器输出的单词符号序列是否符合该语言的文法是否符合该语言的文法句子句子n分析器的输入：分析器的输入：TokenToken序列序列n分析器的输出分析器的输出uu分析树分析树分析树分析树uu出错处理出错处理出错处理出错处理:定位、续编译定位、续编译定位、续编译定位、

3、续编译分析方法分析方法自顶向下（递归下降、预测分析自顶向下（递归下降、预测分析)自底向上（算符优先、自底向上（算符优先、LRLR分析器）分析器）4.2 4.2 自上而下分析面临的问题与自上而下分析面临的问题与CFGCFG的改造的改造n一、自上而下的分析一、自上而下的分析n从文法的开始符号出发，寻求所给的输入符从文法的开始符号出发，寻求所给的输入符号串的一个最左推导。号串的一个最左推导。n从树根从树根S S开始，构造所给输入符号串的语法树开始，构造所给输入符号串的语法树n例：例：G G为：为：SxAySxAy A*|*A*|*，输入串：输入串：x*yx*yS S S SxAy x*yS S S

4、Sx x x xA A A Ay y y y*二、存在问题二、存在问题回溯回溯S S xAyxAy x*yx*yS S S Sx x x xA A A Ay y y y*S S S Sx x x xA A A Ay y y y*x*yx*yx*yx*yS S S S xAyxAyxAyxAy x*yx*yx*yx*y匹配成功匹配成功匹配成功匹配成功x*yx*yx*yx*y发现不匹配发现不匹配发现不匹配发现不匹配,需要回退需要回退需要回退需要回退输入串输入串输入串输入串x*yx*yx*yx*ySxAySxAy A*|*A*|*存在回溯的原因存在回溯的原因n文法中每个非终结符文法中每个非终结符A

5、A的产生式右部称为的产生式右部称为A A的候选式，如果有多个候选式左端第一的候选式，如果有多个候选式左端第一个符号相同，则语法分析程序无法根据个符号相同，则语法分析程序无法根据当前输入符号选择产生式，只能试探。当前输入符号选择产生式，只能试探。二、存在问题二、存在问题左递归问题左递归问题n文法文法SSay|*SSay|*与它的句子与它的句子*ayayayay*ayayayayS S*不对不对！S SSaySayaySayayaySayayayay一个无限一个无限循环！循环！二、重要问题二、重要问题左递归问题左递归问题n例例 CFG:CFG:简单算术表达式的文法（语法）简单算术表达式的文法（语法

6、）nEE+T|E-T|TEE+T|E-T|TnTT*F|T/F|FTT*F|T/F|FnF(E)|idF(E)|idnN NE,T,F,P,FUN,LE,T,F,P,FUN,LnT Tidid,+,-,*,/,(,),+,-,*,/,(,)nE E三、重要概念回顾三、重要概念回顾n推导推导:(依据：依据：)n最左最左(Left-most)Left-most)推导推导最左分析最左分析n左句型左句型n最左推导对应最右归约最左推导对应最右归约n最右最右(Right-most)Right-most)推导推导最右分析最右分析n规范推导、规范句型（右句型）规范推导、规范句型（右句型）n最右推导对应最左归约

7、（规范归约最右推导对应最左归约（规范归约）n二义性二义性(先天二义性语言、二义性文法先天二义性语言、二义性文法)四、消除二义性四、消除二义性例：简单算术表达式的文法例：简单算术表达式的文法二义性文法二义性文法nEE+E|E-E|E*E|E/E|(E)|idEE+E|E-E|E*E|E/E|(E)|id非二义性文法非二义性文法nEE+T|E-T|TEE+T|E-T|TnTT*F|T/F|FTT*F|T/F|FnF(E)|idF(E)|id改造方法：使文法含有更多的信息，引入语法变量改造方法：使文法含有更多的信息，引入语法变量四、消除二义性四、消除二义性再例：再例：IfIf语句语句Sif E th

8、en SSif E then SSif E then S else SSif E then S else SSotherSother设执行下列语句前设执行下列语句前b=0,b=0,If a0 then If a0 then if a0 then b=1 else b=-1if a0 then b=1 else b=-1当当a=1a=1时时,b=1;b=1;当当a=-1a=-1时，时，b=-1b=-1If a0 then If a0 then if a0 then b=1if a0 then b=1 else b=-1 else b=-1当当a=1a=1时时,b=1;b=1;当当a=-1a=-1

9、时，时，b=0b=0一个句子有两棵不同的语法树一个句子有两棵不同的语法树S SS SE E E ES S S SIf a0 then If a0 then ifif a0 a0 thenthen b=1 b=1 elseelse b=-1 b=-1S SS SE E E ES S S SIfIf a0 a0 thenthen if a0 then b=1 if a0 then b=1 elseelse b=-1 b=-1四、消除二义性四、消除二义性 P174P174n重写文法：引入新的语法变量重写文法：引入新的语法变量SU|MU|MUif E then SUif E then SUif E t

10、hen M else UUif E then M else UMif E then M else M|otherMif E then M else M|other每个每个elseelse与前面最近的没有配对的与前面最近的没有配对的thenthen配对，即：出现在配对，即：出现在thenthen和和elseelse之间的语句必须是配对的之间的语句必须是配对的按照改造后的文法构造的语法树按照改造后的文法构造的语法树SUSMEEMMIf a0 then if a0 then b=1 else b=-1If a0 then if a0 then b=1 else b=-1Mif E then M el

11、se M|otherMif E then M else M|other五、消除左递归五、消除左递归n无法根据左递归文法进行自顶向下的分析无法根据左递归文法进行自顶向下的分析A a1a2aiann直接左递归直接左递归nA A 当前变量当前变量 输入指针输入指针(栈顶、最左变量栈顶、最左变量)n n间接左递归间接左递归间接左递归间接左递归uuA A+AAn n左递归的消除方法左递归的消除方法左递归的消除方法左递归的消除方法uu将将将将AA|AA|AA|AA|替换为替换为替换为替换为AAAAAAAA 和和和和 A A A A AAAA 例：例：表达式文法直接左递归的消除表达式文法直接左递归的消除E

12、E+TE E+TT TT T*FT T*FF FF (E)F (E)ididE T EE T EE E+T E+T E|T F TT F TT T*F T*F TF(E)F(E)idid例：例：间接左递归的消除间接左递归的消除SAc|cSAc|c ABb|b ABb|b BSa|aBSa|a将将B B的定义的定义代入代入A A产生式得：产生式得：ASab|ab|bASab|ab|b将将A A的定义的定义代入代入S S产生式得产生式得:SSabc|abc|bc|cSSabc|abc|bc|c消除直接左递归：消除直接左递归：SabcS|bcS|cSSabcS|bcS|cSSabcS|SabcS|删

13、除删除“多余的多余的”产生式：产生式：ASab|ab|bASab|ab|b和和BSa|a BSa|a 结果：结果：SabcS|bcS|cSSabcS|bcS|cSSabcS|SabcS|消除左递归的一般方法消除左递归的一般方法n用产生式组用产生式组nA A1 1 B|B|2 2 B B|n n B BnB B1 1 B|B|2 2 B B|n n B|B|n替换产生式组替换产生式组nAAAA1 1|A|A2 2|A|An n|1 1|2 2|m m n其中：其中：B B为新变量，相当于为新变量，相当于AAn消除左递归的算法见消除左递归的算法见P117P117的算法的算法4.14.1n为非终结符

14、编号，再采用代入法将间接左递归变为非终结符编号，再采用代入法将间接左递归变为直接左递归，消除直接左递归为直接左递归，消除直接左递归六、六、解决回溯问题解决回溯问题提取左因子提取左因子n例：例：ifif语句的原始文法语句的原始文法nS if E then S S if E then S n|if E then S else S|if E then S else S n|other|othern影响分析影响分析:遇到遇到 if if 时难以时难以判断用哪一个产生式进行判断用哪一个产生式进行匹配（推导）匹配（推导）n存在左因子存在左因子 if E then Sif E then S左因子提取方法左因

15、子提取方法将形如将形如 AA1 1|2 2|n n|1 1|2 2|m m的规则改写为的规则改写为AA|AA|1 1|2 2|m m和和 AA1 1|2 2|n nn结果：结果：nS if E then SS|otherS if E then SS|othernS|else SS|else S七、七、CFGCFG的使用限制的使用限制n没有一种方法能够有效地分析所有上下文没有一种方法能够有效地分析所有上下文无关文法无关文法n存在无法处理的型文法存在无法处理的型文法(CFG)CFG)n每种方法能够处理一部分上下文无关文法每种方法能够处理一部分上下文无关文法n每种方法都有适用范围每种方法都有适用范围

16、八、常用文法与分析方法八、常用文法与分析方法nLLLL文法和文法和 LR LR 文法都是文法都是CFGCFG的子集的子集(无二义性无二义性)n可用不同的文法来描述同一语言可用不同的文法来描述同一语言n对于不同的文法，可用不同的分析方法对于不同的文法，可用不同的分析方法nLLLL文法文法 递归下降分析法、预测分析法递归下降分析法、预测分析法nLRLR文法文法 LRLR分析法分析法nLL LL 文法多用于编译的手工实现文法多用于编译的手工实现nLR LR 文法多用于编译的自动生成文法多用于编译的自动生成4.3 4.3 自顶向下的分析方法自顶向下的分析方法n基本思想基本思想n寻找输入符号串的最左推导

17、寻找输入符号串的最左推导n试图根据当前输入单词判断使用哪个产生式试图根据当前输入单词判断使用哪个产生式n基本过程基本过程n从根开始，按与最左推导相对应的顺序，构从根开始，按与最左推导相对应的顺序，构造输入符号串造输入符号串(Token)Token)的分析树的分析树例例 符号串符号串 id+id*idid+id*id的分析的分析nE T E E T E nE+T EE+T E nT F T T F T nT*F TT*F T nF (E)F (E)id id 按照最左推导过程，构造分析树按照最左推导过程，构造分析树id+id*idid+id*id最左推导与语法树的生成对应最左推导与语法树的生成对

18、应i di di d1、ETEETE2 2、TFTTFT3 3、FidFid4 4、TT5 5、E+TEE+TE6 6、TFTTFT7 7、FidFid8 8、T*FTT*FT9 9、FidFid1010、TT1111、EEid+id*idid+id*id的最左推导再现的最左推导再现E TETEE E TETE FTEFTET T FTFTidTEidTEF F idid idEidETT id+TEid+TEEE+TE+TE id+FTEid+FTET T FTFT id+idTEid+idTEF F idid id+id*FTEid+id*FTETT*FT*FT id+id*id+id*i

19、dTEidTE F F idid id+id*id+id*idEidE T T id+id*id id+id*id E E候选式的确定与回溯候选式的确定与回溯n给定文法给定文法ScAdAab|a?句子句子cad是该文法定义语言的句子是该文法定义语言的句子SScAdcAd a ban产生式产生式(候选式候选式)的选择与回溯的选择与回溯(Backtracking)：当要进行关于某个语法当要进行关于某个语法变量的推导时，希望能够根据当前符号确定候选式。如果有几个候选式变量的推导时，希望能够根据当前符号确定候选式。如果有几个候选式（右部）左端第一个符号相同，则分析程序无法根据当前输入符号选择（右部）左

20、端第一个符号相同，则分析程序无法根据当前输入符号选择产生式，只能试探。产生式，只能试探。无回溯的条件无回溯的条件n设设AA1 1|2 2|n n是所有的是所有的A A产生式产生式n如果各个如果各个i i能推导出的首终结符各不相能推导出的首终结符各不相同，则可以构造无回溯的分析。同，则可以构造无回溯的分析。4.3.1 4.3.1 FIRST FIRST 和和 FOLLOW FOLLOW 集集n对于对于(T TN N)*定义定义:的首符号集的首符号集nFIRST()=a|FIRST()=a|*aa，aaT T*n如果存在如果存在AA这样的产生式，则需定义这样的产生式，则需定义FOLLOW(AFOL

21、LOW(A）n对于对于 AAN N定义定义A A的后续符号集：的后续符号集：nFOLLOW(A)=a|FOLLOW(A)=a|S S*AaAa，aaT T 求求FIRST(X)FIRST(X)的算法的算法1)1)对对 x xT T，FIRST(x)=x FIRST(x)=x；2)2)对对 XXN N，取取FIRST(X)FIRST(X)的初值：的初值：a|XaPa|XaP；XX P PFIRST(X)=FIRST(X)=a|XaP a|XaP；XPXP3)3)对对 XXN N，重复如下过程，直到所有重复如下过程，直到所有FIRSTFIRST集不变集不变若若 XYXYPP ，且且 YYN N，则

22、则 FIRST(X)=FIRST(X)(FIRST(Y)-)FIRST(X)=FIRST(X)(FIRST(Y)-)；若若 XYXY1 1Y Yn nPP，且且Y Y1 1.Y.Yi-1i-1*，则则 对对k=1k=1到到i-1:i-1:FIRST(X)=FIRST(X)=FIRST(X)(FIRST(YFIRST(X)(FIRST(Yk k)-)-)；若若 Y Y1 1.Y Yn n*，则则 FIRST(X)=FIRST(X)FIRST(X)=FIRST(X)。例例 表达式文法的语法符号的表达式文法的语法符号的 FIRST FIRST 集集FIRST(F)=FIRST(F)=（,id,idF

23、IRST(T)=FIRST(F)=FIRST(T)=FIRST(F)=（,id ,id FIRST(E)=FIRST(T)=FIRST(E)=FIRST(T)=（,id ,id FIRST(E)=+FIRST(E)=+，FIRST(T)=*,FIRST(T)=*,FIRST(+)=+,FIRST(*)=*FIRST(+)=+,FIRST(*)=*FIRST(FIRST(（)=)=（FIRST(FIRST(）)=)=）FIRST(id)=idFIRST(id)=idETE ETE ETE ETE E+TEE+TEE+TEE+TE|TFT TFT TFT TFT T*FTT*FTT*FTT*FT|

24、F(E)|idF(E)|idF(E)|idF(E)|id求求FIRST()FIRST()的算法的算法n令令=X X1 1X Xn nn初值初值nFIRST()=FIRST(XFIRST()=FIRST(X1 1)-;nk=1;k=1;n循环循环nwhile while FIRST(XFIRST(Xk k)&k)&kn doEEEn C CE=EE=E用递归子程序法设计并实现语法分析程序，用递归子程序法设计并实现语法分析程序，按照生成顺序输出产生式按照生成顺序输出产生式5.1 5.1 自底向上分析自底向上分析n思想思想n从输入串出发，反复利用产生式进行归约，如从输入串出发，反复利用产生式进行归约

25、，如果最后能得到文法的开始符号，则输入串是句子，果最后能得到文法的开始符号，则输入串是句子，否则输入串有语法错误。否则输入串有语法错误。n核心核心n寻找句型中的当前归约对象寻找句型中的当前归约对象“句柄句柄”进行进行归约归约,用不同的方法寻找句柄，就可获得不同的用不同的方法寻找句柄，就可获得不同的分析方法分析方法一个简单的归约过程一个简单的归约过程n例例 设文法为：设文法为：SaAcBeSaAcBeAAb|bAAb|bBdBd句子分析：句子分析：句子分析：句子分析：a a a ab b b bbcdebcdebcdebcdea a a aA A A Ab b b bcdecdecdecdea

26、a a aA A A Ac c c cd d d de e e e aAcaAcaAcaAcB B B Be e e e S S S SA Aa b b c d ea b b c d eB BA AS S语法树的语法树的语法树的语法树的形成过程形成过程形成过程形成过程回忆几个概念回忆几个概念n最左推导最左推导(Left-most Derivation)Left-most Derivation)n每次推导都施加在句型的最左边的语每次推导都施加在句型的最左边的语法变量上。法变量上。与最右归约对应与最右归约对应n最右推导最右推导(Right-most Derivation)Right-most De

27、rivation)n每次推导都施加在句型的最右边的语每次推导都施加在句型的最右边的语法变量上。法变量上。与最左归约（规范归与最左归约（规范归约）对应，得规范句型约）对应，得规范句型/右句型右句型回忆几个概念回忆几个概念如果如果*and A and A+，则称则称是句型是句型的相对于变量的相对于变量A A的短语的短语(Phrase)Phrase)如果如果*and A and A，则称则称是句型是句型的相对于变量的相对于变量A A的直接（简单）短语的直接（简单）短语最左直接短语叫做句柄最左直接短语叫做句柄(Handle)Handle)回忆几个概念回忆几个概念n规范归约规范归约(另一表达另一表达)：

28、设：设为文法为文法 G G 的句子，如果的句子，如果n1)1)=n nn-1n-12 21 1=n2)2)对每个对每个i(1in)i(1in)，i-1i-1是将句型是将句型i i中的句柄归约后得到的句型中的句柄归约后得到的句型n则称序列则称序列 n n，.，1 1为为的规范的规范归约序列归约序列由规范归约组成由规范归约组成语法分析树的生成再演示语法分析树的生成再演示a b b c d ea b b c d eAABSAbAbAAbAAbBdBdSaAcBeSaAcBe分析设想分析设想移进归约移进归约n系统框架系统框架n输入缓冲区：保存输入符号串输入缓冲区：保存输入符号串n控制程序：控制分析过程

29、，输出分析控制程序：控制分析过程，输出分析结果结果产生式序列产生式序列n栈：保存语法符号栈：保存语法符号已经得到的部分已经得到的部分结果结果n栈栈+输入缓冲区剩余内容输入缓冲区剩余内容=“=“句型句型”分析器结构分析器结构 id+id+id id id#id#移进归约移进归约控制程序控制程序输出产生输出产生输出产生输出产生式序列式序列式序列式序列栈内容栈内容+输入缓冲区内容输入缓冲区内容#“当前句型当前句型 ”#栈栈输入缓冲区输入缓冲区 分析表分析表分析表分析表与与LL(1)LL(1)的体系结构比较的体系结构比较 输入缓冲区输入缓冲区(符号序列符号序列)栈栈控制程序控制程序P123P123预测

30、分析表预测分析表M M输出的输出的输出的输出的产生式序列产生式序列产生式序列产生式序列分析设想分析设想移进归约移进归约n系统运行系统运行n开始格局开始格局n栈：栈：#；输入缓冲区：；输入缓冲区：w#w#n存放已经分析出来的结果存放已经分析出来的结果,并将读入的符号并将读入的符号送入栈，一旦句柄在栈顶形成，就将其弹送入栈，一旦句柄在栈顶形成，就将其弹出进行归约，并将结果压入栈出进行归约，并将结果压入栈n？系统如何发现句柄在栈顶形成系统如何发现句柄在栈顶形成n正常结束正常结束:栈中为栈中为#S S，输入缓冲区只有输入缓冲区只有#输出结果表示：输出结果表示：用产生式序列表示语法分析树用产生式序列表示

31、语法分析树E idE idid +id *id EEEEEE idE idE idE idE idE idE idE idE E*EE E*EE E*EE E*EE E+EE E+EE E+EE E+E动作动作动作动作 栈栈栈栈 输入缓冲区输入缓冲区输入缓冲区输入缓冲区1)#1)#1)#1)#idididid1 1 1 1+id+id+id+id2 2 2 2*id*id*id*id3 3 3 3#id+id *idid+id *id2)2)2)2)移进移进移进移进#idididid1 1 1 1 +id +id +id +id2 2 2 2*id*id*id*id3 3 3 3#例例5-35

32、-3分析过程分析过程3)3)3)3)归约归约归约归约 Eid#E +idEid#E +idEid#E +idEid#E +id2 2 2 2*id*id*id*id3 3 3 3#E E4)4)4)4)移进移进移进移进#E+idE+idE+idE+id2 2 2 2*id*id*id*id3 3 3 3#5)5)5)5)移进移进移进移进#E+idE+idE+idE+id2 2 2 2 *id *id *id *id3 3 3 3#6)6)6)6)归约归约归约归约 Eid#E+E *idEid#E+E *idEid#E+E *idEid#E+E *id3 3 3 3#E EE E7)7)7)7)

33、移进移进移进移进#E+E*idE+E*idE+E*idE+E*id3 3 3 3#8)8)8)8)移进移进移进移进#E+E*idE+E*idE+E*idE+E*id3 3 3 3#9)9)9)9)归约归约归约归约 Eid#E+E*E#Eid#E+E*E#Eid#E+E*E#Eid#E+E*E#10)10)10)10)归约归约归约归约 EE*E#E+E#EE*E#E+E#EE*E#E+E#EE*E#E+E#E E11)11)11)11)归约归约归约归约 EE+E#E#EE+E#E#EE+E#E#EE+E#E#12)12)12)12)接受接受接受接受E E分析器的四种动作分析器的四种动作n1)1)

34、移进：将下一输入符号移入栈移进：将下一输入符号移入栈n2)2)归约：用产生式左侧的非终结符替换栈顶归约：用产生式左侧的非终结符替换栈顶的句柄（某产生式右部）的句柄（某产生式右部）n3)3)接受：分析成功接受：分析成功n4)4)出错：出错处理出错：出错处理n？决定移进和归约的依据是什么？决定移进和归约的依据是什么回头看回头看是否可以找到答案是否可以找到答案移进归约分析中的问题移进归约分析中的问题n1)1)移进归约冲突移进归约冲突 n例例5-35-3中的中的 6)6)可以移进可以移进*或按产生式或按产生式EE+EEE+E归约归约 动作动作动作动作 栈栈栈栈 输入缓冲区输入缓冲区输入缓冲区输入缓冲区

35、1)#1)#1)#1)#idididid1 1 1 1+id+id+id+id2 2 2 2*id*id*id*id3 3 3 3#id+id *idid+id *id2)2)2)2)移进移进移进移进#idididid1 1 1 1 +id +id +id +id2 2 2 2*id*id*id*id3 3 3 3#例例5-35-3分析过程分析过程3)3)3)3)归约归约归约归约 Eid#E +idEid#E +idEid#E +idEid#E +id2 2 2 2*id*id*id*id3 3 3 3#E E4)4)4)4)移进移进移进移进#E+idE+idE+idE+id2 2 2 2*i

36、d*id*id*id3 3 3 3#5)5)5)5)移进移进移进移进#E+idE+idE+idE+id2 2 2 2 *id *id *id *id3 3 3 3#6)6)6)6)归约归约归约归约 Eid#E+E *idEid#E+E *idEid#E+E *idEid#E+E *id3 3 3 3#E EE E7)7)7)7)移进移进移进移进#E+E*idE+E*idE+E*idE+E*id3 3 3 3#8)8)8)8)移进移进移进移进#E+E*idE+E*idE+E*idE+E*id3 3 3 3#9)9)9)9)归约归约归约归约 Eid#E+E*E#Eid#E+E*E#Eid#E+E*

37、E#Eid#E+E*E#10)10)10)10)归约归约归约归约 EE*E#E+E#EE*E#E+E#EE*E#E+E#EE*E#E+E#E E11)11)11)11)归约归约归约归约 EE+E#E#EE+E#E#EE+E#E#EE+E#E#12)12)12)12)接受接受接受接受E E移进归约分析中的问题移进归约分析中的问题n1)1)移进归约冲突移进归约冲突 n例例5-35-3中的中的 6)6)可以移进可以移进*或按产生式或按产生式EE+EEE+E归约归约 n2)2)归约归约冲突归约归约冲突 n存在两个可用的产生式存在两个可用的产生式n各种分析方法处理冲突的方法不同各种分析方法处理冲突的方法

38、不同n如何识别句柄？如何识别句柄？n如何保证找到的直接短语是最左的如何保证找到的直接短语是最左的?利用栈利用栈n如何确定句柄的开始处与结束处？如何确定句柄的开始处与结束处？优先法优先法n根据归约的先后次序为句型中相邻的文法符根据归约的先后次序为句型中相邻的文法符号规定优先关系号规定优先关系n句柄内相邻符号同时归约，是同优先的句柄内相邻符号同时归约，是同优先的n句柄两端符号的优先级要高于句柄外与之相邻句柄两端符号的优先级要高于句柄外与之相邻的符号的符号na a1 1aai-1i-1a ai iaai+1i+1aaj-1j-1aaj jaaj+1j+1aan n状态法状态法n根据句柄的识别状态（根

39、据句柄的识别状态（句柄是逐步形成的句柄是逐步形成的）n用状态来描述不同时刻下形成的那部分句柄用状态来描述不同时刻下形成的那部分句柄n因为句柄是产生式的右部，可用产生式来表示因为句柄是产生式的右部，可用产生式来表示句柄的不同识别状态句柄的不同识别状态n例如：例如：SbBBSbBB可分解为如下识别状态可分解为如下识别状态nS.bBBS.bBB 移进移进b bnSbB.BSbB.B 等待归约出等待归约出B BnSb.BB Sb.BB 等待归约出等待归约出B BnSbBBSbBB.归约归约5.2 5.2 算符优先分析法算符优先分析法n算术表达式分析的启示算术表达式分析的启示n算符优先关系的直观意义算符

40、优先关系的直观意义n+*+*+的优先级低于的优先级低于*n()()(的优先级等于的优先级等于)n+的优先级高于的优先级高于+n方法方法n将句型中的终结符号当作将句型中的终结符号当作“算符算符”，借助，借助于算符之间的优先关系确定句柄于算符之间的优先关系确定句柄算术表达式文法的再分析算术表达式文法的再分析nEE+EEE+EnEE-EEE-EnEE*EEE*EnEE/E EE/E nE(E)E(E)nEidEidnEE+T|E-T|T EE+T|E-T|T TT*F|T/F|F TT*F|T/F|F F(E)|idF(E)|id从如何去掉二义性从如何去掉二义性从如何去掉二义性从如何去掉二义性,看看

41、看看对算符优先级的利用对算符优先级的利用对算符优先级的利用对算符优先级的利用句型的特征：句型的特征：句型的特征：句型的特征：(E E E E+E E E E)*()*()*()*(E E E E-E E E E)/)/)/)/E E E E/E E E E+E E E E*E E E E*E E E E算符文法算符文法n如果文法如果文法G=G=（V VN N，V VT T，P P，S S）中不存在形如中不存在形如ABC ABC 的产生式，则称之为算符文法的产生式，则称之为算符文法(OG Operator OG Operator Grammar)Grammar)即：如果文法即：如果文法 中不存在

42、具有相邻非终结符的中不存在具有相邻非终结符的产生式，则称为算符文法。产生式，则称为算符文法。算符间的优先关系算符间的优先关系n设设G=G=（V VN N，V VT T，P P，S S）为为OGOG，则定义则定义nab ab A AababPP或者或者 A AaBbaBbPPnab ab A AaBaBPP且且(B B+bb或者或者B B+C Cb b)nab ab A AB BbPbP且且(B B+aa或者或者B B+a aC C)n什么是算符优先文法？什么是算符优先文法？算符优先文法算符优先文法n设设G=G=（V V，T T，P P，S S）为为OGOG，如果如果 a,ba,bVVT T,a

43、b,ab,ab ab,ab,ab 至多有一个成立，则称之为至多有一个成立，则称之为算符优先文法算符优先文法(OPG Operator Precedence OPG Operator Precedence GrammarGrammar)在无在无产生式的算符文法中，如果任意产生式的算符文法中，如果任意两个终结符之间至多有一种优先关系，则称两个终结符之间至多有一种优先关系，则称为算符优先文法。为算符优先文法。算符优先关系的确定算符优先关系的确定_算符优先矩阵算符优先矩阵n优先关系的确定优先关系的确定n根据优先关系的定义根据优先关系的定义nab ab A AaBaBPP且且(B B+bb或者或者B B

44、+C Cb b)n需要求出非终结符需要求出非终结符B B派生出的第一个终结符集派生出的第一个终结符集nab ab A AB BbPbP且且(B B+aa或者或者B B+a aC C)n需要求出非终结符需要求出非终结符B B派生出的最后一个终结符集派生出的最后一个终结符集n设设G=G=（V VN N，V VT T，P P，S S）为为OGOG，则定义则定义nFIRSTOP(A)=b|AFIRSTOP(A)=b|A+bb或者或者A A+Bb,Bb,bVbVT T,B,B VVN N nLASTOP(A)=b|ALASTOP(A)=b|A+bb或者或者A A+bB,bB,bVbVT T,B,B VV

45、N N 算符优先关系矩阵的构造算符优先关系矩阵的构造nA Aabab;A AaBbaBb,则则a ab bnA AaBaB,则对则对 b bFIRSTOP(B),abFIRSTOP(B),abnA ABb,Bb,则对则对 a aLASTOP(B),abLASTOP(B),abnif if ABABP,then FIRSTOP(B)P,then FIRSTOP(B)FIRSTOP(A)FIRSTOP(A)nif if ABABP,then LASTOP(B)P,then LASTOP(B)LASTOP(A)LASTOP(A)n?编程求编程求FIRSTOPFIRSTOP、LASTOPLASTOP算

46、符优先关系矩阵的构造算符优先关系矩阵的构造nAXX1 1X X2 2X Xn nn如果如果X Xi iX Xi+1i+1VVT TV VT T则：则：X Xi iX Xi+1i+1n如果如果X Xi iX Xi+1i+1X Xi+2i+2VVT TV VN NV VT T则：则：X Xi iX Xi+2i+2n如果如果X Xi iX Xi+1i+1VVT TV VN N则：则：a aFIRSTOP(XFIRSTOP(Xi+1i+1)，X Xi iaan如果如果X Xi iX Xi+1i+1VVN NV VT T则：则：a aLASTOP(XLASTOP(Xi i)，a aX Xi+1i+1例例

47、 4-12 4-12：表达式文法的算符优先关系表达式文法的算符优先关系 accacc+-*/()idid#+-*/（）idid#算符优先分析算法算符优先分析算法n原理原理n识别句柄并归约，利用识别句柄并归约，利用识别句柄尾，利用识别句柄尾，利用识别句柄头，分析栈存放已识别部分，比较栈识别句柄头，分析栈存放已识别部分，比较栈顶和下一输入符号的关系，如果是句柄尾，则顶和下一输入符号的关系，如果是句柄尾，则沿栈顶向下寻找句柄头，找到后弹出句柄，归沿栈顶向下寻找句柄头，找到后弹出句柄，归约为非终结符。约为非终结符。n分析例：分析例：id+idid+idn#idid +idid#n#F F+idid#n

48、#F+F+idid#n#F+F+idid#n#F#F+F F#n#E#E#EE+T|E-T|T TT*F|T/F|F F(E)|idEE+T|E-T|T TT*F|T/F|F F(E)|id问题问题n有时未归约真正的句柄（有时未归约真正的句柄（F F）n不是严格最左归约不是严格最左归约n归约的符号串有时与产生式右部不同归约的符号串有时与产生式右部不同n仍能正确识别句子的原因仍能正确识别句子的原因nOPGOPG未定义非终结符之间的优先关系，不能识别未定义非终结符之间的优先关系，不能识别由单非终结符组成的句柄由单非终结符组成的句柄n定义算符优先分析过程识别的定义算符优先分析过程识别的“句柄句柄”为

49、最左为最左素短语素短语LPPLPP（Leftmost Prime PhaseLeftmost Prime Phase）素短语与最左素短语素短语与最左素短语n什么是短语？当前我们要找什么样的什么是短语？当前我们要找什么样的短语？短语？至少有一个算符至少有一个算符n*and A and A+，至少含一个至少含一个终结符，且不含更小的含终结符的短语终结符，且不含更小的含终结符的短语,则称则称是句型是句型的相对于变量的相对于变量A A的素的素短语短语(Prime Phrase)Prime Phrase)n句型的至少含一个终结符且不含其它句型的至少含一个终结符且不含其它素短语的短语素短语的短语例例nEE

50、+T|T TT*F|F F(E)|idEE+T|T TT*F|F F(E)|id句型句型 T+T*F+i T+T*F+i 的短语有的短语有T*F i T*F+i T+T*F+iT*F i T*F+i T+T*F+i其中的素短语为其中的素短语为T*F iT*F iT*FT*F为最左素短语，是被归约的对象为最左素短语，是被归约的对象？按照文法按照文法EE+E|E*E|(E)|id EE+E|E*E|(E)|id，求求i+E*i+ii+E*i+i的短语和素短语的短语和素短语 E E E E E E T T T F T FT +T *F +iT +T *F +i文法：文法：EE+E|E*EEE+E|E

51、*E E(E)|id E(E)|id句型句型i+E*i+ii+E*i+i的短语的短语 E E E E E EE E E E E Ei +E *i +ii +E *i +i 归约过程中如何发现归约过程中如何发现归约过程中如何发现归约过程中如何发现“中中中中间句型间句型间句型间句型”的最左素短语？的最左素短语？的最左素短语？的最左素短语？i i E*i i i i E*i i i+E*i i+E*i+ii+E*i i+E*i+i其中的素短语为其中的素短语为i i ii i i素短语与最左素短语素短语与最左素短语设句型的一般形式为设句型的一般形式为#N#N1 1a a1 1 N N2 2a a2 2

52、 N Nn na an n#(N Ni i V VN N,a,ai i VVT T）它的最左素短语是满足下列条件的最左子串它的最左素短语是满足下列条件的最左子串N Ni ia ai i N Ni+1i+1a ai+1i+1 N Nj ja aj j N Nj+1j+1其中：其中：a ai-1i-1aai,i,，a ai ia ai+1i+1a aj-1j-1a aj j ，a aj ja aj+1j+1算符优先分析的实现算符优先分析的实现n系统组成系统组成n移进归约分析器移进归约分析器+优先关系表优先关系表n分析算法分析算法 P136/93P136/93陈陈n参照输入串、优先关系表，完成一系列

53、参照输入串、优先关系表，完成一系列归约，生成语法分析树归约，生成语法分析树输出产生式输出产生式id+id*id id+id*id 的分析过程的分析过程id+id*id#算符优先分析算符优先分析控制器控制器E idE idE idE idE idE idE E*EE E*EE E+EE E+E算符优先关系表算符优先关系表#id#+#id+#+#*+#id*+#*+#+#算符优先函数算符优先函数n为了节省存储空间（为了节省存储空间（n n2 2 2n 2n）和便于执行比较运算，和便于执行比较运算，用两个优先函数用两个优先函数f f和和g g，它们是从终结符号到整数的映它们是从终结符号到整数的映射。

54、对于终结符号射。对于终结符号a a和和b b选择选择f f和和g g，使之满足：使之满足：n f(a)g(b)，如果如果a b。n损失损失n错误检测能力降低错误检测能力降低n如：如：id idid id不存在，但不存在，但f(id)g(id)f(id)g(id)可比较可比较图图4-254-25对应的优先函数：对应的优先函数：1)1)构造优先函数的算法不是唯一的。构造优先函数的算法不是唯一的。2 2）存在一组优先函数，那就存在无穷组存在一组优先函数，那就存在无穷组优先函数。优先函数。算法算法4.5 从优先关系构造优先函数从优先关系构造优先函数方法：方法：1.a VT$,建立两个符号建立两个符号f

55、a和和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出发的出发的 最长路径。最长路径。.gidfidf*g*g+f+f$g$算符优先分析法小结算符优先分析法小结n优点优点n简单、效率高简单、效率高n能够处理部分二义性文法能够处理部分二义性文法n缺点缺点n文法书写限制大文法书写限制大n占用内存空间大占用内存空间大n不规范、存在查不到的语法错误不规范、存在查不

56、到的语法错误n1 1、习题习题:给出布尔表达式的文法，构造其算给出布尔表达式的文法，构造其算符优先关系表符优先关系表 nbexprbexpr bexprbexpr OROR bexprbexprnbexprbexpr bexprbexpr ANDAND bexprbexprnbexprbexpr NOTNOT bexprbexprnbexprbexpr (bexprbexpr )nbexprbexpr TRUETRUEnbexprbexpr FALSEFALSEn算符优先分析法存在的问题算符优先分析法存在的问题n强调算符之间的优先关系的唯一性，这强调算符之间的优先关系的唯一性，这使得它的适应面

57、比较窄使得它的适应面比较窄n算法在发现最左素短语的尾时，需要回算法在发现最左素短语的尾时，需要回头寻找对应的头头寻找对应的头5.3 5.3 LR(Left-Right)LR(Left-Right)分析法分析法nLR(k)LR(k)分析法可分析分析法可分析LR(k)LR(k)文法产生的语言文法产生的语言nL L：从左到右扫描输入符号从左到右扫描输入符号nR R：最右推导对应的最左归约最右推导对应的最左归约nk k：超前读入超前读入k k个符号，以便确定归约用的产生式个符号，以便确定归约用的产生式n使用语言的文法描述内涵解决句柄的识别问题，从语言的使用语言的文法描述内涵解决句柄的识别问题，从语言的

58、形式形式描述描述入手，为语法分析器的入手，为语法分析器的自动生成自动生成提供了前提和基础提供了前提和基础n分析器根据当前的状态，并至多向前查看分析器根据当前的状态，并至多向前查看k k个输入符号，个输入符号，就可以确定是否找到了句柄，如果找到了句柄，则按相就可以确定是否找到了句柄，如果找到了句柄，则按相应的产生式归约，如果未找到句柄则移进输入符号，并应的产生式归约，如果未找到句柄则移进输入符号，并进入相应的状态进入相应的状态分析器的总体结构分析器的总体结构a1 ai an#LR主控程序主控程序动作表动作表action转移表转移表gotogoto产生式产生式产生式产生式序列序列序列序列状态状态/

59、符号符号栈栈输入缓冲区输入缓冲区分析表分析表SmSm-1S1S0XmXm-1X1#LR LR 分析表：分析表：actions,aactions,a；gotos,Xgotos,X 动作表动作表动作表动作表 转移表转移表转移表转移表状态状态状态状态 action action action action gotogotogotogoto a b#S B a b#S B a b#S B a b#S B 0 s3 s4 1 2 0 s3 s4 1 2 0 s3 s4 1 2 0 s3 s4 1 2 1 acc 1 acc 1 acc 1 acc 2 s3 s4 5 2 s3 s4 5 2 s3 s4

60、5 2 s3 s4 5 3 s3 s4 6 3 s3 s4 6 3 s3 s4 6 3 s3 s4 6 4 r3 r3 r3 4 r3 r3 r3 4 r3 r3 r3 4 r3 r3 r3 5 5 5 5 r1 r1 r1 r1 r1 r1 r1 r1 r1 r1 r1 r1 6 r2 r2 r2 6 r2 r2 r2 6 r2 r2 r2 6 r2 r2 r2 LR(0)LR(0)、SLR(1)SLR(1)、LR(1)LR(1)、LALRLALR将以将以不同的原则构造不同的原则构造这张分析表这张分析表约定：约定：snsn:将符号将符号a a、状状态态n n压入栈压入栈rnrn:用第用第n

61、n个产生个产生式进行归约式进行归约LRLR分析器的工作过程分析器的工作过程n书上的下式（格局）书上的下式（格局）(s s0 0s s1 1ssm m，X X1 1X X2 2 X Xm m ，a ai ia ai+1i+1aan n#)#)n在这里表示为在这里表示为s s0 0s s1 1s sm m#X X1 1X Xm m a ai ia ai+1i+1aan n#LRLR分析器的工作过程分析器的工作过程n n1.初始化初始化s0#a1a2an#对应对应对应对应“句型句型句型句型”a a a a1 1 1 1a a a a2 2 2 2a a a an n n nn n2.一般情况下一般情

62、况下s0s1 sm#X1Xm aiai+1an#对应对应对应对应“句型句型句型句型”X X X X1 1 1 1X X X Xm m m ma a a ai i i ia a a ai+1i+1i+1i+1a a a an n n nnIfIf actionsm,ai=si(shift(shift i)i)thenthen 格局变为格局变为s0s1 sm i#X1Xmai ai+1an#s s0 0s s1 1s sm m#X X1 1X Xm m a ai ia ai+1i+1aan n#IfIf actionsactionsm m,a,ai i=acc=acc thenthen 分析成功分

63、析成功IfIf actionsactionsm m,a,ai i=err=err thenthen 出现语法错出现语法错IfIf actionsm,ai=ri(Reduce(Reduce i)i)thenthen 表示用第表示用第i i个产生式个产生式AXAXm-(k-1)m-(k-1)X Xm m进行进行归约，格局归约，格局变为变为s0s1 sm-k#X1Xm-kA aiai+1an#查查goto表表，当，当gotosm-k,A=i thenthen 格局格局变为变为s0s1 sm-k i#X1Xm-kA aiai+1an#LRLR分析器主控程序分析器主控程序(LRLR分析算法分析算法)n置

64、输入指针置输入指针 ipip 指向指向 w#w#的第一个符号；令的第一个符号；令s s是是栈顶状态，栈顶状态，a a 是是 ipip 所指向的符号所指向的符号;分析栈中分析栈中为为#和开始状态和开始状态0 0n重复执行如下过程重复执行如下过程(P144)P144)n if actions,a=if actions,a=si(shiftsi(shift i)then i)thenn 把符号把符号 a a 和状态和状态i i先后压入栈；先后压入栈；n 使使 ipip 指向下一符号指向下一符号 n elseifelseif actions,a=actions,a=ri(reduceri(reduce

65、 A)A)thenthenn 从栈顶弹出从栈顶弹出 2*|2*|个符号；个符号；n 令令ss是现在的栈顶状态；是现在的栈顶状态；n 把把 A A 和和 gotos,Agotos,A 先后压入栈中；先后压入栈中；n 输出产生式输出产生式 AAn elseifelseif actions,a=accept(acc)then actions,a=accept(acc)thenn return returnn else else n error()error()；例例文法文法1)1)SBBSBB2)2)BaBBaB3)Bb3)Bb分析表分析表 动作表动作表动作表动作表 转移表转移表转移表转移表状态状态

66、状态状态 action action action action gotogotogotogoto a b#S B a b#S B a b#S B a b#S B 0 s3 s4 1 2 0 s3 s4 1 2 0 s3 s4 1 2 0 s3 s4 1 2 1 acc 1 acc 1 acc 1 acc 2 s3 s4 5 2 s3 s4 5 2 s3 s4 5 2 s3 s4 5 3 s3 s4 6 3 s3 s4 6 3 s3 s4 6 3 s3 s4 6 4 r3 r3 r3 4 r3 r3 r3 4 r3 r3 r3 4 r3 r3 r3 5 r1 r1 r1 5 r1 r1 r1 5 r1 r1 r1 5 r1 r1 r1 6 r2 r2 r2 6 r2 r2 r2 6 r2 r2 r2 6 r2 r2 r2 请跟随讲请跟随讲解，快速解，快速抄下右侧抄下右侧的表格！的表格！babbab 的分析过程的分析过程:1)1)1)1)SBBSBBSBBSBB2)2)2)2)BaBBaBBaBBaB3)Bb3)Bb3)Bb3)Bb栈栈 输入输入 动作说明动作说明0 0#babbab#a