《编译原理重点4》由会员分享，可在线阅读，更多相关《编译原理重点4（113页珍藏版）》请在金锄头文库上搜索。
1、 An Introduction to Database System中南民族大学计算机科学学院编译原理 Compilers Principles第七章 自下而上的LR(K)分析 方法 Bottom-up parsingAn Introduction to Database System概述一. 自底向上的分析方法是一种移进-规约过程 ，关键问题是：如何确定句柄。二. LR(k)方法于1965年由Knuth提出。三. LR(k)分析器：从左到右扫描输入串，进行 规范归约。分析过程中，至多向前查看k个输 入符号，即可决定当前的动作是归约还是移进 。若为归约，能选择唯一一个产生式进行归约 。An
2、Introduction to Database SystemCompilers Principles 第7章3概述(续1)四. LR(k)分析器功能较强，主要优缺点为：1.优点:(1)对文法的限制比较少(与自顶向下的LL(K) 、自底向上的优先分析方法相比而言）。 (2)分析速度快，能准确、即时地指出出错位 置。2.缺点：对于一个实用语言文法的分析器来说， 构造工作量很大。An Introduction to Database SystemCompilers Principles 第7章4概述(续2)五. LR(k)分析器由一个总控程序和一个分 析表以及2个分析栈构成。六. 4种分析表的构造
3、方法： LR(0),SLR(1),LR(1),LALR(1)An Introduction to Database SystemCompilers Principles 第7章57.1 LR分析方法概述LR(k)分析器由一个总控程序和一个分析表以及2个分析 栈构成。 LR分析器的总控程序相同。 不同文法，分析表不同；同一文法，采用不同LR分析 法，分析表也不同。 分析表可分为动作表(ACTION)和状态转换表(GOTO)。 分析栈包括文法符号栈和相应的状态栈。LR(k)分析器的工作过程为：An Introduction to Database SystemCompilers Principle
4、s 第7章6LR分析器工作过程示意图Sn Xn . . . . . .S1 X1 S0 X0LR驱动程序动作表 转移表 action goto输出输入串XXX$An Introduction to Database SystemCompilers Principles 第7章7LR分析器工作过程示意图的说明移进 ai 和s=gotosm,ai进栈 actionsm,ai= 归约 rj : AXm-r+1Xm-r+2Xm s=gotosm-r , A 接受出错gotoSi, X = Sj X为文法符号An Introduction to Database SystemCompilers Prin
5、ciples 第7章8回顾：移进-规约分析 例1文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B d步骤符号栈输入符号串动作1） # abbcde# 移进2） #a bbcde# 移进4） #aA bcde# 移进6） #aA cde# 移进7） #aAc de# 移进9） #aAcB e# 移进11） #S # 接受对输入串abbcde#的移进-规约分析过程5） #aAb cde# 归约(AAb)3） #ab bcde# 归约(Ab)8） #aAcd e# 归约(Bd)10） #aAcBe # 归约(SaAcBe)An Introduction to Data
6、base SystemCompilers Principles 第7章9移进-归约中的问题 在步骤3中，用Ab归约 在步骤5中，用AAb归约 问题：何时移进？何时归约？用哪个产生式归约 ？ 在优先分析方法中如何解决这个问题的？An Introduction to Database SystemCompilers Principles 第7章10移进-归约中的问题分析分析：已分析过的部分在栈中的前缀不同，而且移 进和归约后栈中的状态会发生变化我们引入一个新的状态栈来表示符号栈中的符号目 前状态，用LR分析表来表示不同状态下对于各输入 符号应采取的动作3） #ab bcde# 归约(Ab)5） #
7、aAb cde# 归约(AAb)4） #aA bcde# 移进6） #aA cde# 移进An Introduction to Database SystemCompilers Principles 第7章117.2 LR(0)分析例1 文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B dSi:移进，并将状态i进 栈ri:用第i个产生式归约 ，同时状态栈与符 号栈退出相应个符 号，根据GOTO表将 相应状态入栈文法GS的LR(0)分析表(注：该表没有填写完)An Introduction to Database SystemCompilers Principle
8、s 第7章12对输入串abbcde#的LR(0)分析过程输入串abbcde#的分析过程步骤 符号栈输入符号串 动作1） # abbcde# 移进 0 S22） #a bbcde# 移进 02 S4 3） #ab bcde# 归约(Ab) 024 r2 34） #aA bcde# 移进 023 S66） #aA cde# 移进 023 S57） #aAc de# 移进 0235 S89） #aAcB e# 移进 02357 S911） #S # 接受 01 acc5） #aAb cde# 归约(AAb) 0236 r3 38） # aAcd e# 归约(Bd) 02358 r4 710） #aA
9、cBe # 归约(SaAcBe) 023579 r1 1状态栈ACTIONGOTOAn Introduction to Database SystemCompilers Principles 第7章13LR(0)分析的问题n对于一个文法，会有一些什么样 的状态呢？这些状态又是如何确 定的？nLR分析表是如何得到的？An Introduction to Database SystemCompilers Principles 第7章14可归前缀与活前缀文法GS： (1) S aAcBe1 (2) A b2 (3) A Ab3 (4) B d4每次归约句型的 前部分依次为： ab2 aAb3 aAc
10、d4 aAcBe1规范句型的这种前部分符号串称为可归前缀我们把形成可归前缀之前包括可归前缀在内 的所有规范句型的前缀都称为活前缀,a,ab ,a,aA,aAb ,a,aA,aAc,aAcd ,a,aA,aAc,aAcB,aAcBeS aAcBe1 aAcd4e1aAb3cd4e1 ab2b3cd4e1An Introduction to Database SystemCompilers Principles 第7章15活前缀（Viable Prefixes）的定义n活前缀： S =* A =是文法G中的一个规范 推导，如果符号串是的前缀，则称是G的一个 活前缀。其中，S是对原文法拓广后的开始符
11、号，即有： S - SAn Introduction to Database SystemCompilers Principles 第7章16识别活前缀的有限自动机LR方法中，并不是直接分析文法符号栈中的符号是否形 成句柄，但是，我们可以把文法的终结符和非终结符 都看成有穷自动机的输入符号，每次把一个符号进栈 看成已识别过了该符号，同时状态进行转换，当识别 到可归前缀时，相当于在栈中形成句柄，认为达到了 识别句柄的终态。即用自动机中的状态来刻画分析过程中的某一种情形 。An Introduction to Database SystemCompilers Principles 第7章17如何构
12、造识别活前缀的有限自动机n已经有了活前缀如何构造有限自动机?n活前缀及其可归前缀的一般计算方法An Introduction to Database SystemCompilers Principles 第7章18构造识别文法活前缀的DFA的三种方法一、根据形式定义求出活前缀的正规表达式， 然后由此正规表达式构造NFA再确定化为DFA( 不实用，略) 二、求出文法的所有项目，按一定规则构造识 别活前缀的NFA再确定化为DFA(了解) 三、使用闭包函数（CLOSURE）和转向函数 (GOTO(I,X)构造文法G的LR(0)的项目集规 范族，再由转换函数建立状态之间的连接关 系得到识别活前缀的DF
13、A(掌握)An Introduction to Database SystemCompilers Principles 第7章19构造识别活前缀的有限自动机 例子文法GS： S S0 S aAcBe1 A b2 A Ab3 B d4句子abbcde的可归前缀如下 ： S0 ab1 aAb3 aAcd4 aAcBe1构造识别其活前缀及可归前缀的有限自动机如下：104387131210182591461715161110SabaAbaAcdaAcBe*1*句子识别态i句柄识别态SceBAadbAbAn Introduction to Database SystemCompilers Princip
14、les 第7章20识别活前缀的有限自动机 例子104387131210182591461715161110SabaAbaAcdaAcBe*X加上开始状态X确定化 ： X13246859SabAbc Bed 7*An Introduction to Database SystemCompilers Principles 第7章21例1中abbcde#分析过程所对应的自动机步骤 符号栈 输入符号串动作1） # abbcde# 移进 0 S22） #a bbcde# 移进 02 S4 4） #aA bcde# 移进 023 S66） #aA cde# 移进 023 S57） #aAc de# 移进 0235 S89） #aAcB e# 移进 02357 S911） #S # 接受 01 acc3） #ab bcde# 归约(Ab) 024 r2
