第4章语法分析3_LR分析法概述ppt课件.ppt

《第4章语法分析3_LR分析法概述ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、两种自下而上分析方法比较4-4-1自下而上的分析法——LR分析法概述算符优先分析法：不是规范规约最左素短语LR分析法：是规范规约句柄二、规范推导和规范规约1、规范推导是最右推导S对中的每个最右VN用A去替换+适合于自上而下预测分析法递归下降分析法必须是LL(1)文法，且用的是最左推导。2021/9/31计算机教研室二、规范推导和规范规约2、规范规约(是规范推导的逆过程)关键是找“当前可规约串”(最左素短语或句柄)适合于自下而上LR分析法算符优先分析法每次去找句柄(最左简单短语)局限性对单非产生式跳过

2、，且对NN(VN)无比较，必须是OPG文法，总是找最左素短语。LR分析法优点：1)无二义性的上下文无关文法；2)分析效率较高；3)程序中可以准确指出出错位置。4-4-1自下而上的分析法——LR分析法概述2021/9/32计算机教研室二、规范推导和规范规约SOS1............Sn#x1xnSPa1#ana2……输入串总控程序输出分析表actionGoTo分析栈状态规约符号3、LR基本思想：1)记住历史(分析栈记录)；2)依据现实(据分析栈，确定是要移进还是规约)；3)展望未来(确定了是要移进还是规约，

3、若规约用哪条规则式)；4-4-1自下而上的分析法——LR分析法概述2021/9/33计算机教研室三、LR分析器(一)逻辑结构(见下图)SOS1............Sn#x1xnSPa1#ana2……输入串总控程序输出分析表actionGoTo分析栈状态规约符号1、从逻辑上来看，关键是一个总控程序+分析表；2、从实质上来看，是带分析栈的确定有穷自动机；3、分析栈：如左图所示，包括状态和规约符号两部分；4、分析表action(动作：移进还是规约)GoTo(转向)4-4-1自下而上的分析法——LR分析法概述2021

4、/9/34计算机教研室三、LR分析器(一)逻辑结构(见下图)分析表的元素action[S,a]规定，当状态S面临一个输入符号a应采取的动作为：Si表示可以移进，并且移进后要转到第i状态；ri表示可以规约，并且按第i规则式进行规约；acc表示接受(accept)；空白表示出错；GoTo[S,x]规定：状态S面临一个文法输入符号x时应转到下一个状态；4-4-1自下而上的分析法——LR分析法概述2021/9/35计算机教研室三、LR分析器(一)逻辑结构(见下图)10abcd#SABactionGoToSiS401234

5、56789S5S6123accr1r1r1r1r1r2r2r2r2r2S4S5S6r4r4r4r4r4r6r6r6r6r6r3r3r3r3r3r5r5r5r5r5S8S1079LR分析表5、工作过程1)分析栈的初始格局S0#a1a2…an#2)设在分析的某一步ai…an##S0S1…S2Smx1x2…xm以符号对去查表：4-4-1自下而上的分析法——LR分析法概述2021/9/36计算机教研室三、LR分析器(一)逻辑结构(见下图)5、工作过程①移进action[Sm,ai]=Sm+1或GoTo[Sm,A]=Sm+

6、1，结果为：ai+1…an##S0S1…S2Smx1x2…xmaiSm+1②规约若action[Sm,ai]=rj且rj是按第j条规则式：A规约；ai…an#Sl#S0S1…S2Sm-x1x2…xm-A此时=且GoTo[Sm-,A]=Si,则状态Si是通过Sm-与A查表得出的。③若action[Sm,ai]=acc表示分析成功；④若action[Sm,ai]=空白表示输入串有错，处理错误；3)重复2)直至栈中为如右所示或报错结束。#S0#SaZZ为G开始符号4-4-1自下而上的分析法——LR分

7、析法概述2021/9/37计算机教研室三、LR分析器解：依题意，首先将文法G扩展为G：Ex：已知文法G[S]：S→A

8、BA→aAb

9、cB→aBb

10、d对输入串#aacbb的分析过程。0S→S1S→AS→BA→aAbA→cB→aBb6B→dG[S]并假设我们现在已经有了LR分析表，则输入串#aacbb的分析过程为：0#caab#b04#acab#b由查表得action[0,a]=S4再由查表得action[4,a]=S44-4-1自下而上的分析法——LR分析法概述2021/9/38计算机教研室三、LR分析器10

11、abcd#SABactionGoToSiS40123456789S5S6123accr1r1r1r1r1r2r2r2r2r2S4S5S6r4r4r4r4r4r6r6r6r6r6r3r3r3r3r3r5r5r5r5r5S8S1079044#aacb#b0445#aacb#b044#aaAb#b7#b044#aaAb78#b#a04A74-4-1自下而上的分析法——LR分析法