第五章 LALR(1)方法.ppt

《第五章 LALR(1)方法.ppt》由会员分享，可在线阅读，更多相关《第五章 LALR(1)方法.ppt（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、LR(1)分析存在的问题分析存在的问题l为消除冲突，引入太多的状态为消除冲突，引入太多的状态;l有些状态含有完全相同的有些状态含有完全相同的LR(0)项目部分，只有展望项目部分，只有展望符部分是不同的符部分是不同的;lLR(1)项目的心项目的心：如果：如果(A,ss)是一个是一个LR(1)项目，则其中的项目，则其中的LR(0)项目部分称为它的心项目部分称为它的心;lLR(1)自动机自动机状态的心状态的心：一个状态所含有的所有：一个状态所含有的所有LR(1)项目的心项目的心;l同心状态同心状态：如果两个：如果两个LR(1)状态具有相同的心，则称状态具有相同的心，则称这两个状态为同心状态。这两个状

2、态为同心状态。LALR(1)分析分析l主要思想主要思想合并文法合并文法G的的LR(1)自动机中的同心状态，得到自动机中的同心状态，得到的自动机称为的自动机称为LALR(1)自动机；自动机；若这个得到的若这个得到的LALR(1)自动机没有冲突，则称文自动机没有冲突，则称文法法G是是LALR(1)文法。文法。lLALR(1)分析过程分析过程构造构造LALR(1)自动机自动机 构造构造LALR(1)分析表分析表(同同LR(1)分析表构造方法分析表构造方法)LALR(1)驱动程序驱动程序=LR(1)驱动程序驱动程序如何构造如何构造LALR(1)自动机自动机l第一种途径：第一种途径：首先构造首先构造LR

3、(1)自动机自动机然后合并其中的同心状态然后合并其中的同心状态该方法简单，但不现实该方法简单，但不现实(not practical)!Step1:构造构造LR(1)自动机自动机VT=a,b,=VN=S,L,RS=SP:(1)S L=R (2)S R (3)L aR (4)L b (5)R L0Z S,#S L=R,#S R,#R3S R,#R L,#1ZS,#Sb4L b,=,#L5S L=R,#R R L L,#L aR,=,#L b,=,#=a a6S L=R,#R L,#L aR,#L b,#12L aR,=,#R L,=,#L aR,=,#L b,=,#b b4 4L L14R L,=

4、,#a a13L aR,=,#R7S L=R,#R8R L,#L11L b,#b b9L aR,#R L,#L aR,#L b,#aL L8 8R10L aR,#b ba aStep2:合并同心状态合并同心状态l状态状态4和和11同心同心 l状态状态8和和14同心同心l状态状态10和和13同心同心l状态状态9和和12同心同心0Z S,#S L=R,#S R,#R3S R,#R L,#1ZS,#Sb4L b,=,#L5S L=R,#R R L L,#L aR,=,#L b,=,#=a a6S L=R,#R L,#L aR,#L b,#12L aR,=,#R L,=,#L aR,=,#L b,=,

5、#b b4 4L L14R L,=,#a a13L aR,=,#R7S L=R,#R8R L,#L11L b,#b b9L aR,#R L,#L aR,#L b,#aL L8 8R10L aR,#b ba a4 4141412121313 LR(1)分析表Action 表表Goto 表表ab=#SLR0S12S41531Accept 3R24R4R45S6R56S9S11877R1 LR(1)分析表(接上页.)Action 表表Goto 表表ab=#SLR8R59S9S111010R311R412S12S4141313R3R314R4R415LALR(1)分析表Action 表表Goto 表表

6、ab=#SLR0S12S41531Accept 3R24R4R45S6R56S12S41477R112S12S4141313R3R314R4R4LALR(1)自动机自动机l对于给定的上下文无关文法对于给定的上下文无关文法 GG的的LALR(1)项目跟项目跟LR(1)项目项目形式相同形式相同;LALR(1)自动机中每个状态自动机中每个状态S中各个项目的展中各个项目的展望符集是把望符集是把LR(1)自动机中所有和自动机中所有和S同心的状态同心的状态的对应项目的展望符集合合并后得到的的对应项目的展望符集合合并后得到的;如果每个如果每个LALR(1)的状态都用该状态的心的状态都用该状态的心(LR(0)

7、项目项目)替换，则替换，则LALR(1)自动机和它的自动机和它的LR(0)自动机相同自动机相同;G的的LALR(1)自动机的自动机的状态数同状态数同LR(0)自动机自动机的状态数相同；的状态数相同；能不能用能不能用LR(0)自动机构造自动机构造LALR(1)自动机呢自动机呢？如何构造如何构造LALR(1)自动机自动机l第二种途径：第二种途径：首先构造首先构造LR(0)自动机自动机然后为每个状态的每个然后为每个状态的每个LR(0)项目计算展项目计算展望符集；望符集；是实际应用中采用的方法！是实际应用中采用的方法！关键是如何计算展望符呢？关键是如何计算展望符呢？LALR(1)展望符的计算方法投影得

8、到的项目投影得到的项目:展望符集是指向该状态展望符集是指向该状态的所有状态中对应项目的所有状态中对应项目的展望符集的合集的展望符集的合集;S L=R,R L,L aR,L b,LALR(1)状态状态iS L =R,j1S L =R,jn派生得到的项目派生得到的项目:展望符集和展望符集和LR(1)中中的计算方法一样的计算方法一样;构造LALR(1)自动机VT=a,b,=VN=S,L,RS=SP:(1)S L=R (2)S R (3)L aR (4)L b (5)R LStep1:构造LR(0)自动机0 S S,S L=R,S R,R3S RR L,1SSSb4L b,L5S L=R,R R L

9、L,L aR,L b,=a a6S L=R,R L,L aR,L b,L LR7S L=R,aRLa a13L aR,14R L,12 L aR,bR R LL L aR,L L b,Step2:计算展望符0 S S,S L=R,S R,R3S RR L,1SSSb4L b,L5S L=R,R R L L,L aR,L b,=a a6S L=R,R L,L aR,L b,L LR7S L=R,aRLa a13L aR,14R L,12 L aR,b#R R LL L aR,L L b,=，#=，#=，#=，#=，#=，#=，#=，#=，#LALR(1)文法l如果文法如果文法G的的LALR(1)

10、自动机中没有冲自动机中没有冲突突,则文法则文法G称为称为LALR(1)文法文法;l注意注意:由于对由于对LR(1)自动机中的同心状态自动机中的同心状态进行了合并进行了合并,把展望符集进行合并把展望符集进行合并,因此因此有可能导致冲突有可能导致冲突,从而不是从而不是LALR(1)文法文法;l合并同心状态只能产生归约合并同心状态只能产生归约-归约冲突，归约冲突，不会产生移入不会产生移入-归约冲突，为什么？归约冲突，为什么？LR(0),SLR(1),LR(1)和LALR(1)比较l状态数状态数:LR(1)LALR(1)=SLR(1)=LR(0)l展望符的确定展望符的确定:LR(0)没有展望符；没有展

11、望符；SLR(1)取取follow集；集；LR(1)取不同位置的取不同位置的follow集；集；LALR(1)取同心项的展望符的并集；取同心项的展望符的并集；l向前看输入符向前看输入符:SLR(1),LR(1)和和LALR(1)向前看一个输入符；向前看一个输入符；LR(0)不看不看;l分析能力分析能力:LR(1)LALR(1)SLR(1)LR(0)第五章第五章 自底向上的语法分析自底向上的语法分析l5.1 自底向上的语法分析方法概述自底向上的语法分析方法概述l5.2 LR(0)分析的有限自动机分析的有限自动机l5.3 LR(0)分析分析l5.4 SLR(1)分析分析l5.5 LR(1)分析分析

12、l5.6 LALR(1)分析分析l5.7 LALR(1)语法分析器的自动生成器语法分析器的自动生成器(YACC)5.7 LALR(1)语法分析程序生成器(YACC)l是一种广泛采用的程序设计语言语法分析程是一种广泛采用的程序设计语言语法分析程序的生成工具序的生成工具;l如果文法不满足如果文法不满足 LALR(1)文法的条件，则文法的条件，则无法生成语法分析程序无法生成语法分析程序;l请同学们自己上网查找请同学们自己上网查找YACC的使用方法！的使用方法！第五章 总结l自底向上语法分析方法的思想、关键问题自底向上语法分析方法的思想、关键问题l句型语法树的构造方法，并依据语法树识别短语、句型语法树的构造方法，并依据语法树识别短语、简单短语、句柄简单短语、句柄lLR(0)LR(0)、LR(1)LR(1)、LALR(1)LALR(1)自动机、分析表自动机、分析表 的构造方法，以及的构造方法，以及LRLR分析过程分析过程