《编译 第六章》由会员分享，可在线阅读，更多相关《编译 第六章（142页珍藏版）》请在金锄头文库上搜索。
1、第六章 LR分析法及 分析程序自动构造第六章 LR分析法及分析程序自动构造（1）第一节 概述v本章介绍上下文无关文法的LR分析方法及分 析程序的自动构造vLR：自左至右扫描,最右推导的逆过程 一、LR方法 1.基本思想在规范归约过程中，一方面记住已移 进和归约的整个符号串，另一方面根据当前 所用的产生式推测未来可能碰到的输入符号 . 第六章 LR分析法及分析程序自动构造（2）第一节 概述 一、LR方法 2.优缺点v优点：与其它技术相比，适应文法范围更广。能 力更强，识别效率相当，尤其在自左向右扫描输 入串时就能发现其中错误，并能准确指出出错位 置。v缺点：若用手工构造分析程序，工作量太大，且
2、容易出错，所以必须使用自动产生这种分析程序 的产生器。 3.产生器的作用v应用产生器产生一大类上下文无关文法的LR分析 程序v对二义性文法或难分析的特殊文法，施加一些限 制，使之能用LR分析。第六章 LR分析法及分析程序自动构造（3）vLR分析法通过LR分析器来实现总控程序分析表输出带第一节 概述 二、LR分析器输入带下推栈第六章 LR分析法及分析程序自动构造（4）1、从逻辑上说，LR分析器包括两部分： 总控程序，或称为语法分析程序； 分析表v注：后面要学习的所有LR分析器的总控程序都相 同。仅仅是它们的分析表不同 2、总控程序作用： 查分析表，根据分析表的内容做若干简单动作， 如读头后移，入
3、栈出栈等。v注：由于总控程序很简单，所以产生器的任务就 是产生分析表第一节 概述 二、LR分析器第六章 LR分析法及分析程序自动构造（5）v一个文法的LR分析器常常对应着若干不同分析表 ，所有分析表都恰好识别文法所产生的所有语句v本章将讨论四种不同分析表构造方法 1.LR(0)分析表：v分析能力有限，但这是建立其它LR分析法的基础 。 2.SLR分析表：v简单LR分析表构造法，是一种容易实现又有实用 价值的方法，但存在一些文法构造不出SLR分析表第一节 概述 三、分析表第六章 LR分析法及分析程序自动构造（6）v3、规范LR分析表 它能力最强，但实现代价过高，分析表尺寸太大v4、LALR分析表
4、 向前看LR分析表构造文法，也是一种常用方法v注：实际上，SLR和LALR分别是对LR(0)和规范LR 的改进v最后，将讨论如何使用二义文法构造LR分析器并 产生高效的分析技术第一节 概述 三、分析表第六章 LR分析法及分析程序自动构造（7）6.1 LR分析器 一、LR分析法的基本思想v在规范归约时，当一串貌似句柄的符号串呈现于 栈顶时，LR分析法根据三方面的信息找句柄： 历史：记录在栈内的符号串移进，归约的历史情 况 展望：预测句柄之后可能出现的信息； 现实：读头下的符号v注：LR分析法的基本思想是符号人的思维习惯的 ，但实现有困难，因为基于“历史”对未来的“ 展望”可能存在多种可能。当把“
5、历史” 和“展 望”材料综合在一起时复杂性就大大增加。如果 简化对“展望”的要求，就可获得实际可行的分 析算法。第六章 LR分析法及分析程序自动构造（8）6.1 LR分析器总控程序分析表输出带输入带下推栈二、LR分析器一个LR分析器实际上是带有下推栈的确定的有限状 态自动机。可将一个“历史”与这个“历史”下的展 望信息综合为抽象的一个状态 第六章 LR分析法及分析程序自动构造（9）v1、下推栈： 下推栈用于存放分析输入串过程中的所有 和“历史”及相应“展望”信息形成的抽象 状态 由于每个状态都概括了从分析开始到归约 阶段的全部“历史”和“展望”信息，所以 LR分析器的每步动作可由栈顶状态和读头
6、下 符号唯一确定6.1 LR分析器 二、 LR分析器第六章 LR分析法及分析程序自动构造（10）1、下推栈：6.1 LR分析器 二、LR分析器sms0xm#状态栈符号栈下推栈栈顶指针把一个“历史”和这个“历史”下的“展望”信 息综合为抽象的一个状态，下推栈用于存放在对输 入串进行分析的过程中这些状态，由于每个状态都 概括了从分析开始到归约阶段的全部“历史”和 “展望”信息，所以栈顶的状态就可用于决定当前 的动作第六章 LR分析法及分析程序自动构造（11）v1、下推栈：6.1 LR分析器 二、 LR分析器sms0xm#状态栈符号栈下推栈栈顶指针为了便于了解栈顶状态对正规分析过程的作用，我们 把栈
7、分为两栏：状态栏和符号栏。符号栈仅用于记录迄 今移进-归约所得到的文法符号，由于它们已经被概 括在“状态”里了，所以对语法分析不起作用。初始时，状态栈放S0（初态），符号栈放“#”（栈 底符）；栈顶Sm代表符号栈内的符号串XmXm-1X1及其展 望信息第六章 LR分析法及分析程序自动构造（12）6.1 LR分析器 二、LR分析器 2 .分析表vLR分析器的核心是分析表a1 a2 ana1 a2 an A1 A2 AnS0 . . Sk这张分析表包含两部分：动作表（Action)和转向表(GoTo)， 它们都是二维数组Si表示状态，ai表示终结符，Ai表示非终结符Actiongoto第六章 LR
8、分析法及分析程序自动构造（13）状态ACTIONGOTO i+*()#ETF 0S5S4123 1S6acc 2r2S7r2r2 3r4r4r4r4 4S5S4823 5r6r6r6r6 6S5S493 7S5S410 8S6S11 9r1r1r1 10r3r3r3r3 11r5r5r5r5第六章 LR分析法及分析程序自动构造（15）2 .分析表v 2）动作表ACTION ACTIONS,a表示在当前状态S下，面临读头下的符号a所应 采取的动作， 注：该动作有四种可能：移进，归约，出错，接受v 3）转向表(GOTO) GOTOS,X表示：若XVT，表示在当前状态下，读入X应转 向什么状态；若X
9、VN，表示当前栈顶句柄归约成X后，应 转向什么状态 注：对终结符的移进动作和转向动作可以合并在一起填在 动作表中，这样，转向表可以只保留非终结符转向部分6.1 LR分析器 二、LR分析器第六章 LR分析法及分析程序自动构造（14）状态ACTIONGOTO i+*()#ETF 0S5S4123 1S6acc 2r2S7r2r2 3r4r4r4r4 4S5S4823 5r6r6r6r6 6S5S493 7S5S410 8S6S11 9r1r1r1 10r3r3r3r3 11r5r5r5r5第六章 LR分析法及分析程序自动构造（15）3.总控程序的动作 v1）移进 把(Sm,ai)的下一个状态S=G
10、OTO(Sm,ai)连同读头 下符号推进栈内,栈顶成为(S,ai),读头前进一格v2）归约 指用某产生式A b进行归约。若b的长度为 g，则弹出栈顶的g个元素，使得栈顶的状态变成Sm-g,然 后把 （Sm-g,A)的下一个状态S=GOTO(Sm-g,A)连同非终结符A一 起推进栈，栈顶变成（S,A)，读头不动。v3）接受 分析成功，退出总控程序v4）报错 输入串出错，调出相应出错程序v注：不管哪一类分析程序，总控程序的动作都一样。程序 本身很简单，按动作表中填的内容具体实施而已。6.1 LR分析器 二、LR分析器第六章 LR分析法及分析程序自动构造（17）6.1 LR分析器v例：根据表达式文法
11、的LR分析表分析输入串 i*i+i的LR动作过程vE E+TvE TvT T*FvT FvF (E)vF i第六章 LR分析法及分析程序自动构造（18）状态ACTIONGOTOi+*()#ETF 0S5S4123 1S6acc 2r2S7r2r2 3r4r4r4r4 4S5S4823 5r6r6r6r6 6S5S493 7S5S410 8S6S11 9r1r1r1 10r3r3r3r3 11r5r5r5r5第六章 LR分析法及分析程序自动构造（19）v注：表中符号的含义：vSj shift j,指将读入符号a移进栈内并转到j 状态，栈顶变成（j,a);vrj reduce j ,按第j号产生式
12、进行归约；vacc accept,分析成功；v空白格 出错标志，若填入相应出错处理程序的 编号，便转相应程序处理。v分析过程vLR分析器的动作情况也可以描述成机器内部的 格局间转换，其格局用三元式表示为（状态栈， 已归约的符号栈，待继续分析的输入串）6.1 LR分析器第六章 LR分析法及分析程序自动构造（16）状态ACTIONGOTOi+*()#ETF 0S5S4123 1S6acc 2r2S7r2r2 3r4r4r4r4 4S5S4823 5r6r6r6r6 6S5S493 7S5S410 8S6S11 9r1r1r1 10r3r3r3r3 11r5r5r5r5第六章 LR分析法及分析程序自
13、动构造（19）0#状态、符号栈i*i+i #E E+TE TT T*FT FF (E)F i第六章 LR分析法及分析程序自动构造（20）状态ACTIONGOTOi+*()#ETF 0S5S4123 1S6acc 2r2S7r2r2 3r4r4r4r4 4S5S4823 5r6r6r6r6 6S5S493 7S5S410 8S6S11 9r1r1r1 10r3r3r3r3 11r5r5r5r5第六章 LR分析法及分析程序自动构造（19）0#状态、符号栈*i+i #E E+TE TT T*FT FF (E)F i5i5 i第六章 LR分析法及分析程序自动构造（21）状态ACTIONGOTOi+*(
14、)#ETF 0S5S4123 1S6acc 2r2S7r2r2 3r4r4r4r4 4S5S4823 5r6r6r6r6 6S5S493 7S5S410 8S6S11 9r1r1r1 10r3r3r3r3 11r5r5r5r5第六章 LR分析法及分析程序自动构造（19）0#状态、符号栈*i+i #E E+TE TT T*FT FF (E)F i3F第六章 LR分析法及分析程序自动构造（22）状态ACTIONGOTOi+*()#ETF 0S5S4123 1S6acc 2r2S7r2r2 3r4r4r4r4 4S5S4823 5r6r6r6r6 6S5S493 7S5S410 8S6S11 9r1
15、r1r1 10r3r3r3r3 11r5r5r5r5第六章 LR分析法及分析程序自动构造（19）0#状态、符号栈*i+i #E E+TE TT T*FT FF (E)F i3 F第六章 LR分析法及分析程序自动构造（23）状态ACTIONGOTOi+*()#ETF 0S5S4123 1S6acc 2r2S7r2r2 3r4r4r4r4 4S5S4823 5r6r6r6r6 6S5S493 7S5S410 8S6S11 9r1r1r1 10r3r3r3r3 11r5r5r5r5第六章 LR分析法及分析程序自动构造（19）0#状态、符号栈*i+i #E E+TE TT T*FT FF (E)F i2T第六章 LR分析法及分析程序自动构造（24）状态ACTIONGOTOi+*()#ETF 0S5S4123 1S6acc 2r2S7r2r2 3r4r4r4r4 4S5S4823 5r6r6r6r6 6S5S493 7S5S410 8S6S11 9r1r1r1 10r3r3r
