文档介绍：? LR 分析方法:一种能根据当前分析栈中的符号串(状态)和向右顺序查看输入串 k个符号就可唯一确定分析器的动作是移进还是归约以及用哪个产生式归约的自底向上语法分析算法。?是一种规范归约的过程。?四种技术 LR(0) SLR(1) LR(1) LALR(1) 第七章 LR 分析第七章 LR 分析能力强几乎所有 CFG 的语言结构都能用 LR 分析不需要对文法附加条件难点几乎不可能用手工编写 LR 分析器现实有 LR 分析器的生成器() LR 分析概述?一个 LR 分析器由 3个部分组成:总控程序; 分析表[动作(ACTION) 、状态转换(GOTO)] ; 分析栈[文法符号栈,状态栈]。 LR 分析概述? ACTION 表告诉分析器:栈顶状态为 i, 当前输入符号是 a时做什么? 1. 移进: ACTION[ i ,a]= S j2. 归约: ACTION[ i ,a]=r j ( 若第j条产生式为 A ?β) 3. 接受: ACTION[S ,a]=acc (S为文法起始符) 4. 报错: ACTION[ i ,a]=error ? GOTO 表 GOTO[ i ,A]= j 表示了当前栈顶状态为 i,遇到文法符号 A时,应转向新状态 j。分析表的具体内容及含义: LR 的分析流程开始初始状态 0和#入栈读符号根据栈顶状态和输入符号查分析动作表归约?移进?接受? 查状态转换表新状态入状态栈按产生式 i归约根据产生式 i的右部符号的个数,符号栈和状态栈相应元素出栈产生式 i的左部符号入栈输入符号入符号栈状态 i入状态栈读符号分析结束错误 YYY NNN LR 分析概述? LR(0) 文法能力最弱,理论上最重要?以例题 为例说明 LR(0) 分析过程例:文法 G[S] : (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d 对输入串 abbcde # 利用 LR 分析法进行分析。 LR(0) 文法的 LR(0) 分析表 S i : 移进,将状态 i和输入符进栈 r i : 归约,用第 i个产生式归约,同时状态栈与符号栈退出相应个符号,并把 GOTO 表相应状态和第 i个产生式的左部非终结符入栈。文法 G[S] : (1) S→ aAcBe (2) A→b (3) A→ Ab (4) B→d 分析输入串 abbcde # Step States . Syms . The rest of input Action Goto 1 0 # abbcde # s2 2 02 #a bbcde # s4 3 024 # ab bcde # r2 goto(2,A)=3 4 023 # aA bcde # s6 5 0236 # aAb cde # r3 goto(2,A)=3 6 023 # aA cde # s5 7 0235 # aAc de# s8 8 02358 # aAcd e# r4 goto(5,B)=7 9 02357 # aAcB e# s9 10 023579 # aAcBe # r1 goto(0,S)=1 11 01 #S # acc 对输入串 abbcde #的 LR 分析文法 G[S] : (1) S→ aAcBe (2) A→b (3) A→ Ab (4) B→d ?规范句型中活前缀、可归前缀?设λβ t是一个规范句型,其中β表示句柄, t∈V t*, 如果λβ= u 1u 2…u r,那么称符号串 u 1u 2…u i ( 其中 1≤i≤ r) 是句型λβ t的活前缀。?一个规范句型的活前缀可以有多个,但只有 u 1u 2…u r 含有完整句柄β,将