53LR分析法 1965年, D. knuth首先提出了LRK)文法及LR(K)分析技术。 LR(K)分析是指自左向右扫描和自下而上的语法分析,且 在分析的每一步,只须根据分析栈中当前已移进和归约出的 全部文法符号,并至多再向前查看K个输入符号,就能确定 相当于某一产生式右部符号的句柄是否已在分析栈的顶部形 成。从而也就可以确定所应采取的分析动作(是移进输入符号 还是按某产生式进行归约) F: #X1X2. Xi. Xn Xn+1Xn+2.Xn+kXn+k+1.# 栈顶 当前扫描到Ⅺn+l,向前査看k个符号,来确定是把 Xn+1移进栈,还是把Xi.Xn作为句柄进行归约 )要归约时,则根据某产生式U→Xⅸ计+1.Xn进行归约: #XIX2. Xi-1UXn+1Xn+2.Xn+k.#
5.3 LR 分析法 1965年，D.knuth首先提出了LR(K)文法及LR(K)分析技术。 LR(K)分析是指自左向右扫描和自下而上的语法分析，且 在分析的每一步，只须根据分析栈中当前已移进和归约出的 全部文法符号，并至多再向前查看K个输入符号，就能确定 相当于某一产生式右部符号的句柄是否已在分析栈的顶部形 成。从而也就可以确定所应采取的分析动作（是移进输入符号 还是按某产生式进行归约）。 当前扫描到Xn+1,向前查看k个符号，来确定是把 Xn+1移进栈，还是把Xi…Xn作为句柄进行归约。 1） 要归约时，则根据某产生式U→XiXi+1…Xn进行归约： #X1X2…Xi-1UXn+1Xn+2…Xn+k…# 例：#X1X2…Xi… Xn Xn+1Xn+2…Xn+kXn+k+1…# 栈顶
2)要移进时,即把Xn+1进栈,并读下一符号: #XI2.Xi.NxN+1 Xn+2. Xn+k.# 在栈中栈顶 当前扫描符 LR(0)表示在每一步分析时都不用向前输入符号 LR(1)表示在每一步分析时都向前看一个输入符号来决定当 前的动作。 SLR(1)表示简单的LR(1),即只在动作不唯一的地方向前看 个符号,在动作唯一时则不向前看输入符号
LR(0) 表示在每一步分析时都不用向前输入符号 LR(1) 表示在每一步分析时都向前看一个输入符号来决定当 前的动作。 SLR(1) 表示简单的LR(1)，即只在动作不唯一的地方向前看一 个符号，在动作唯一时则不向前看输入符号。 2） 要移进时，即把Xn+1进栈，并读下一符号： #X1X2…Xi…XnXn+1 Xn+2…Xn+k…# 在栈中 栈顶 当前扫描符
5.3.1LR分析概论 LR分析器的逻辑结构及工作过程 从逻辑上来说,一个LR分析器如图: 栈 al.. al #输入串 总控程序 输出 ACTION GOTO 表 表 S1X1 其中S栈为状态栈 S0# Ⅹ栈为符号栈
5.3.1 LR分析概论 一 .LR分析器的逻辑结构及工作过程 从逻辑上来说，一个LR分析器如图： a1 … ai … # 输入串 Sp→ X1 # S1 S0 ┋ ┋ ┋ ┋ Sm Xm 总 控 程 序 输出 ACTION 表 GOTO 表 其中S栈为状态栈 X栈为符号栈 栈
所有LR分析器的总控程序大同小异,只有分析表各不相同。 三种不同的分析表 规范LR分析表构造法。用此法构造的分析表功能最强而且也 适合于很多文法,但实现代价比较高。 简单LR(即SLR)分析表构造法。这是一种比较容易实现的方法。 但SLR分析表的功能太弱,而且对某些文法可能根本就构造不 出相应的SLR分析表。 向前LR(即LALR)分析表构造法。这种方法构造的分析表功 能介于规范LR分析表SLR分析表之间。这种表适用于绝大多数 程序语言的文法。而且也可以设法有效的实现
所有LR分析器的总控程序大同小异,只有分析表各不相同。 三种不同的分析表 规范LR分析表构造法。用此法构造的分析表功能最强而且也 适合于很多文法，但实现代价比较高。 简单LR(即SLR)分析表构造法。这是一种比较容易实现的方法。 但SLR分析表的功能太弱，而且对某些文法可能根本就构造不 出相应的SLR分析表。 向前LR（即LALR）分析表构造法。这种方法构造的分析表功 能介于规范LR分析表SLR分析表之间。这种表适用于绝大多数 程序语言的文法。而且也可以设法有效的实现
二、LR分析器的分析过程如下: 1首先将初始状态S0及句子的左界限#分别压入状态栈和符号栈中。 2设在分析中的某一步,分析栈及余留的输入串为如下格局: #X1…X 则用栈顶状态S和当前扫描符a组成符号对(Sna)去查 分析动作表,根据 ACTIONIS,a]的指示完成相应的分析动作。 表中每一表元素所规定的动作仅能是下列四种动作之 (1) ACTIONS,al=Smn(移进) 表明句柄尚未在栈顶形成,此时正期待移进输入符号以便形成 句柄。故将当前的输入符号和表元素Sm+1分别压入栈中,有 0 mm+ H+1i+2 a.# #XX. a
二、LR 分析器的分析过程如下： 1.首先将初始状态 S0及句子的左界限#分别压入状态栈和符号栈中。 则用栈顶状态Sm和当前扫描符 ai组成符号对（ Sm , ai )去查 分析动作表，根据ACTION[Sm , ai ]的指示完成相应的分析动作。 表中每一表元素所规定的动作仅能是下列四种动作之一： S0 S1 S2 … Sm Sm+1 ai+1 ai+2 …an # # X1 X2 … Xm ai ↑ ↑ ↓ 2.设在分析中的某一步，分析栈及余留的输入串为如下格局： ↓ S0 S1… Sm ai ai+1…an #X1… Xm ↑ ↑ （1） ACTION[Sm , ai ]= Sm+1 （移进） 表明句柄尚未在栈顶形成，此时正期待移进输入符号以便形成 句柄。故将当前的输入符号和表元素Sm+1分别压入栈中，有