编译原理_06_07LR语法分析方法与中间代码.pptx

第7章 LR分析法 主要内容7.1 LR分析法概述7.2 LR(0)分析法第 十四 讲课题：LR分析法基本思想和LR(0)分析法目的要求： 1.理解LR分析法的基本思想； 2.了解LR(0)分析法；?教学重点： 1.LR分析法的基本思想； 2.前缀、活前缀与可归前缀等概念教学难点 ： LR(0)分析法教学课时：2教学方法：多媒体教学教学内容和步骤 ：（如下）7.1 LR分析方法概述 我们已经学过自顶向下和自底向上两种分析方法。 自底向上分析法是一种移进-归约过程，其关键问题是在分析过程中如何确定句柄。 LR分析方法也是通过求句柄并逐步归约来进行语法分析的。是规范归约。 在算符优先分析法中，句柄是通过运算符的优先关系而求得，LR方法中句柄是通过求可归前缀而求得。 所谓LR(K)分析就是根据当前分析栈中的符号串和向右顺序查看输入串的K(K≥0)个符号就可以唯一确定分析器的动作的一种方法。 LR分析法的特点：对文法限制较低、速度快、准确，并能及时指出出错的位置。 LR(0)分析法对文法的限制较多，因此实用性很差，但是它是构造其他LR分析器的基础。LR分析器1. 一个LR分析器由3个部分组成： (1) 总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。 (2)?分析表或分析函数，分析表又可分为动作表（ACTION）和状态转换表（GOTO）两个部分。 (3) 分析栈，包括文法符号栈和相应的状态栈。 分析器的动作就是由栈顶状态和当前输入符号所决定。2. 分析器的动作决定于栈顶状态和当前输入符号，有四种可能： (1) 移进：栈顶未出现句柄，当前输入符号进符号栈，状态转换，新的状态进状态栈； (2) 归约：栈顶出现句柄，按某个产生式进行归约。归约后的文法符号进符号栈，同时根据状态转换表，新状态进状态栈。 (3) 接受(acc) ：符号栈只剩开始符且当前输入符号为‘#’，则分析成功。 (4) 出错(error) ：栈顶状态与当前输入符不匹配。7.2 LR(0)分析法 几个基本概念：前缀、活前缀与可归前缀 设有符号串 γ ，文法G的某句型? ： 前缀： γ是句型?的头， 则称γ为句型?前缀； 活前缀： γ是句型?前缀，且?是规范句型。 可归前缀： γ是文法G的一个活前缀，且γ的末端恰好是规范句型?的句柄的末端。 也可以说，活前缀就是指形成可归前缀之前包括可归前缀在内的所有规范句型的前缀。r形式定义如下：对于文法G[S]，若 (最右推导) S??Aω? ?βω， ω?Vt*如果符号串γ是串??的头，则γ是??的前缀，(或者称γ是规范句型??ω的前缀，注意:| γ |=|??|)，又称γ是文法G的一个活前缀；若| γ |=|??|(即含句柄)，则称γ是文法G的一个可归前缀。下面我们来分析一个具体的例子：*为产生式加序号变为： S ?aAcBe[1] A ?b[2] A ?Ab[3] B ?d[4]例1：文法G[S] ： S ?aAcBe A ?b A ?Ab B ?d对于输入串abbcde句子的最右推导如下：S?aAcBe[1] ?aAcd[4]e[1] ?aAb[3]cd[4]e[1] ?ab[2]b[3]cd[4]e[1]对它的逆过程最左归约(规范归约)为： ab[2]b[3]cd[4]e[1] aAb[3]cd[4]e[1] aAcd[4]e[1] aAcBe[1] S 我们把每次采取归约动作前的符号串部分称为可归前缀。 活前缀为一个或若干规范句型的前缀。在规范归约过程中的任何时刻只要已分析过的部分(即在符号栈中的符号串)均为规范句型的活前缀，则表明已分析过的部分是正确的。例如：有下面规范句型的前缀：?，a，ab?，a，aA，aAb?，a，aA，aAc，aAcd?，a，aA，aAc，aAcB，aAcBe不难发现a，aA，aAc是多个规范句型前缀和活前缀。LR(0)项目集规范族的构造1. 基本概念 (1) 项目：在文法G中每个产生式的右部适当位置添加一个圆点构成项目。 例如：产生式S?aAcBe对应有6个项目。 [0] S?·aAcBe [1] S?a·AcBe [2] S?aA·cBe [3] S?aAc·Be [4] S?aAcB·e [5] S?aAcBe ·注意： 产生式 A ? ? 仅有一个项目A ? · 项目的含义与圆点位置有关：左部表示用该产生式归约时已识别部分，右部为待识别部分。当右部为 ? 时，表示句柄形成，进行归约。 每个项目相当于NFA中的一个状态（由此亦可以构造出文法相应的NFA，进而求出DFA，只是仍然十分复杂。见教材P131页例题）(2)项目集：是指构成识别一个文法活前缀的DFA的每个状态中所含项目的集合。(3) 项目集规范族：是指上述DF