资源描述：
《编译原理 第06章_LR分析法(1).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、6.1LR分析法LR分析法是一种自下而上进行规范归约的语法分析方法。这里L是指从左到右扫描输入符号串。R是指构造最右推导的逆过程。LR分析法主要缺点：对于一个语言的文法，构造LR分析器的工作量相当大，具体实现较困难。因此，目前对于真正实用的编译程序，采用构造LR分析器的专用工具“YACC”自动地构造出LALR(1)语法分析器。本章主要介绍LR分析法的基本思想和LR(0)、SLR(1)、LR(1)、LALR(1)分析器的工作原理和构造方法。6.1LR分析法LR分析法的基本思想:LR分析法是一种规范归约分析法。规范归约分析法的
2、关键是在分析过程中如何确定分析栈栈顶的符号串是否形成句柄。6.1.1LR分析器的逻辑结构和工作过程LR分析法确定句柄的基本思想:在规范归约分析过程中，根据分析栈中记录的已移进和归约出的整个符号串（即历史）和根据使用的规则推测未来可能遇到的输入符号（即展望）以及现实读到的输入符号这三个方面的信息来确定分析栈栈顶的符号串是否构成句柄。6.1.1LR分析器的逻辑结构和工作过程LR分析器的逻辑结构一个LR分析器的逻辑结构示意图如下图所示。它由分析栈、分析表和总控程序3个部分组成。总控程序LR分析表a1···ai···am#SmXm
3、······#S0X1S1分析栈输出6.1.1LR分析器的逻辑结构和工作过程分析栈用来存放分析过程中的历史和展望信息。LR分析法将历史和展望信息抽象成状态，并放在分析栈中，这就是说分析栈中的每个状态概括了从分析开始到某一归约阶段的整个分析历史和对未来进行的展望。1.分析栈6.1.1LR分析器的逻辑结构和工作过程例如，对文法G[E]:E→E+T
4、TT→T*F
5、FF→(E)
6、id状态Sm不仅表征了从分析开始到现在已扫描过的输入符号被归约成#E＋T，而且由Sm可以预测，如果输入串没有语法错误，根据归约时所用规则（非终结符T的规则
7、）推测出未来可能遇到的输入符号仅是中的任意一个符号。FOLLOW(T)={+,*,),#}SmTE#···+S0S1分析栈示意图6.1.1LR分析器的逻辑结构和工作过程只有FOLLOW(T)中的符号才会跟在T后面若当前读到的输入符号是‘*’，根据文法可知‘*’的优先级高于‘＋’，栈顶尚未形成句柄，则应将‘*’移入栈中；若当前读到的输入符号是‘＋’或’)’或‘#’时，根据文法可知栈顶已形成句柄，则应将符号串E＋T归约为E；若当前读到的输入符号不是上述四种符号之一，则表示输入串有语法错误。由此可知，LR分析器的每一步分析工作，
8、都是由栈顶状态和现行输入符号所唯一确定的。6.1.1LR分析器的逻辑结构和工作过程LR分析表是LR分析器的核心部分。一张LR分析表由分析动作(ACTION)表和状态转换(GOTO)表两部分组成，它们都是二维数组。状态转换表元素GOTO[Si,X]规定了当状态Si面临文法符号X时，应转移到的下一个状态。2.LR分析表6.1.1LR分析器的逻辑结构和工作过程见表分析动作表元素ACTION[Si,a]规定了当状态Si面临输入符号a时应执行的动作。分析动作表对应四种可能动作：移进：把状态Sj=GOTO[Si,a]和输入符号a移入分
9、析栈。归约：当栈顶符号串α形成句柄，且文法中有A→α的规则，其中
10、α
11、=β，则归约动作是从分析栈栈顶去掉β个文法符号和β个状态，并把归约符A和GOTO[Si-β，A]=Sj移入分析栈中。6.1.1LR分析器的逻辑结构和工作过程见表6.1.1LR分析器的逻辑结构和工作过程接受（acc):表示分析成功。此时，分析栈中只剩文法开始符号S'和当前读到的输入符号‘#’。即输入符号串已经分析结束。报错：表示输入串含有错误，此时出现栈顶的某一状态遇到了不该遇到的输入符号。见表总控程序也称为驱动程序。总控程序从左至右扫描输入符号串，并根据
12、当前分析栈中栈顶状态以及当前读到的输入符号按照LR分析表元素所指示的动作完成每一步的分析工作。3.总控程序对所有的LR分析器其总控程序是相同的。6.1.1LR分析器的逻辑结构和工作过程总控程序算法：输入：输入串w和LR分析表。输出：若w是句子，得到w的自下而上分析成功，否则输出错误信息。(LR分析器的工作过程的形式化描述)算法：初始化时，初始状态S0在分析栈栈顶，输入串w#的第1个符号读入a中。6.1.1LR分析器的逻辑结构和工作过程{};)(error)]a,[(ERRORSACTIONifelse==)]a,[(rSA
13、CTIONifelsej==)]a,[(SSACTIONifi==)]!a,[(accSACTIONwhile=}aa{i中；将下一个输入符号读入进栈；和输入符号将状态}SA],SGOTO[AS′
14、
15、
16、
17、{Aj〞=′→进栈；和，将当前栈顶状态为个输入符号退栈；个状态和将归约：条规则用第aaa6.1.1
