第6章LR分析 ■LR分析法 ◆LR分析法概述 ◆LR分析器 ◆LR(O)分析 ◆SLR(1)分析 ◆LR(1)分析 ◆LALR(1)分析 ◆LR分析法小结 ■自底向上语法分析小结 ■本章练习 ■作业 2025/4/3 课程目录 ☑1
2025/4/3 1 第6章 LR分析 ◼LR分析法 ◆LR分析法概述 ◆LR分析器 ◆LR(0)分析 ◆SLR(1)分析 ◆LR(1)分析 ◆LALR(1)分析 ◆LR分析法小结 ◼自底向上语法分析小结 ◼本章练习 ◼作业 课程目录
LR(k)分析法概述p123 ■是一种自下而上语法分析技术 ◆L从左到右扫描输入符号 ◆R构造一个最右推导的逆过程—一最左归约 ◆k超前读入k个符号，以便确定归约用的产生式 ■LR分析器 ◆移进归约分析器+LR分析表 ■特殊性 ◆栈=状态栈+文法符号栈 ◆分析表=动作表action+状态转移表goto 2025/4/3 ☒D 2
2025/4/3 2 LR(k)分析法概述 p123 ◼是一种自下而上语法分析技术 ◆L 从左到右扫描输入符号 ◆R 构造一个最右推导的逆过程——最左归约 ◆k 超前读入k个符号，以便确定归约用的产生式 ◼LR分析器 ◆移进归约分析器 + LR分析表 ◼特殊性 ◆栈 = 状态栈 + 文法符号栈 ◆分析表 = 动作表action + 状态转移表goto
各种LR分析表p123 ■采用不同的构造方法 ◆LR(O)表构造法一—基础 ◆简单LR(SLR(1))表构造法 一理论过渡 ◆规范LR(1)表构造法一理论过渡 ◆向前LR(LALR(1)表构造法一实用 ■不同点 ◆构造分析表的方法不同 ◆分析能力不同，实现效率不同 ■共同点 ◆逻辑结构 ◆工作原理（状态转移） 2025/4/3 章节目录 ☑3
2025/4/3 3 各种 LR 分析表 p123 ◼ 采用不同的构造方法 ◆LR(0)表构造法——基础 ◆简单LR(SLR(1))表构造法——理论过渡 ◆规范LR(1)表构造法——理论过渡 ◆向前LR(LALR(1))表构造法——实用 ◼ 不同点 ◆构造分析表的方法不同 ◆分析能力不同，实现效率不同 ◼ 共同点 ◆逻辑结构 ◆工作原理(状态转移) 章节目录
LR分析器模型p124图7.1 1 .an 状态栈符号栈 输入缓冲区 Sm Xm 工R分析程序 心产生式 Sm-1 m-1 序列 .S% 动作表 转移表 LR # action goto 分析表 SHAHMADEHHMAAMAMMMEMAAMEMMHHAMMDHHEMAHHMMDDAMHHMAMHHMADAHMMMH 2025/4/3 小节目录
2025/4/3 4 LR分析器模型 p124 图7.1 a1 . ai . an # ＬＲ分析程序 动作表 action 转移表 goto 产生式 序列 状态栈 输入缓冲区 LR 分析表 Sm Sm-1 . . . S1 S0 Xm Xm-1 . . . X1 # 符号栈 小节目录
LR文法的定义p123 ■LR文法 ◆能够构造一张不含多重入口的LR分析表的文 法，即LR分析表的每个入口均是唯一确定的 ■LR(k)文法 ◆能用一个每步顶多向前检查k个输入符号的 LR分析器进行分析的文法 ◆对大多数的程序设计语言来说，k=0或1就足 够了 ■因此，我们只考虑k≤1的情形 非LR文法 ◆栈顶内容和输入符号已知时仍无法唯一确定 应采取的动作 2025/4/3 小节目录 ☒5
2025/4/3 5 LR文法的定义 p123 ◼LR文法 ◆能够构造一张不含多重入口的LR分析表的文 法，即LR分析表的每个入口均是唯一确定的 ◼LR(k)文法 ◆能用一个每步顶多向前检查k个输入符号的 LR分析器进行分析的文法 ◆对大多数的程序设计语言来说，k=0或1就足 够了 ◼因此，我们只考虑k≤1的情形 ◼非LR文法 ◆栈顶内容和输入符号已知时仍无法唯一确定 应采取的动作 小节目录
7.2LR(0)分析p124 ■LR(O)分析举例 ■规范句型的活前缀 ■LR(0)项目 ◆定义、意义和构造方法 ■识别活前缀的DFA ◆构造方法 ■LR(O)项目集规范族 ◆定义和构造方法 ■LR(O)分析表 ◆构造方法 ■LR(O)文法及LR(O)分析存在问题 2025/4/3 章节目录 可6
2025/4/3 6 7.2 LR(0)分析 p124 ◼LR(0)分析举例 ◼规范句型的活前缀 ◼LR(0)项目 ◆定义、意义和构造方法 ◼识别活前缀的DFA ◆构造方法 ◼LR(0)项目集规范族 ◆定义和构造方法 ◼LR(0)分析表 ◆构造方法 ◼LR(0)文法及LR(0)分析存在问题 章节目录
状 ACTION GOTO LR (0)分 a b d # A E B 0 s2 s3 1 1 acc 2 s4 s10 6 3 s5 s11 7 4 s4 s10 8 5 s5 s11 9 6 rl rl rl rl rl ■ 文法G[S]: 试分 7 r2 r2 r2 r2 r2 (0)S'→E 析输 (1)E→aA 8 r3 r3 r3 r3 r3 入串 (2)E-→bB 9 r5 r5 r5 r5 r5 (3)A→cA bed 10 r4 r4 r4 r4 r4 (4)A→d (5)B→cB 11 r6 r6 r6 r6 r6 (6)B→d 2025743 小带目豪
2025/4/3 7 LR (0)分 析 举 例 p135 p136 表7.3 状 态 ACTION a b c d # GOTO E A B 0 1 2 3 4 5 6 7 8 9 10 11 s2 s3 1 acc s4 s10 6 s5 s11 7 s4 s10 8 s5 s11 9 r1 r1 r1 r1 r1 r2 r2 r2 r2 r2 r3 r3 r3 r3 r3 r5 r5 r5 r5 r5 r4 r4 r4 r4 r4 r6 r6 r6 r6 r6 试分 析输 入串 bcd ◼ 文法G[S’]: (0)S’→E (1)E→aA (2)E→bB (3)A→cA (4)A→d (5)B→cB (6)B→d 小节目录
LR分析表p124 ■action[k,a]状态k面临输入符号a时的动作 ◆移进sj action[k,a]=sj,将状态j移进状态栈，a移进符 号栈，输入指针移向下一位置 ◆归约rj action[k,a]=rj,用第j个产生式A→B进行归约， |B=m,移去状态栈的m个状态和符号栈的m个符号，用当 前状态栈顶状态k'和A查goto(k',A)=t,将状态t移进 状态栈，A移进符号栈。输入指针不动 ◆接受acc宣布输入符号串为一个句子 ◆报错error状态与文法符号不匹配，宣布输入符号 串不是句子 ■goto[k,X] 状态k遇到文法符号X时转移到的下 状态 2025/4/3 ☒ 8
2025/4/3 8 LR 分析表 p124 ◼ action[k,a] 状态k面临输入符号a时的动作 ◆移进sj action[k,a]=sj,将状态j移进状态栈，a移进符 号栈，输入指针移向下一位置 ◆归约rj action[k,a]= rj,用第j个产生式A→β进行归约, |β|=m,移去状态栈的m个状态和符号栈的m个符号，用当 前状态栈顶状态k’和A查goto(k’,A)=t，将状态t移进 状态栈，A移进符号栈。输入指针不动 ◆接受acc 宣布输入符号串为一个句子 ◆报错error 状态与文法符号不匹配，宣布输入符号 串不是句子 ◼ goto[k,X] 状态k遇到文法符号X时转移到的下一 状态
可归前缀和活前缀的定义p125 ■前缀一个句型的任意首部 ■ 可归前缀LR分析过程中每次采取归约动作前符号 栈中的内容，即规范句型的可归前缀 ■活前缀形成可归前缀之前包括可归前缀在内的所有 规范句型的前缀 ·分析决策依据栈顶状态和当前输入符号是什么？ ◆利用LR(O)项目构造识别活前缀和句柄的DFA 2025/4/3 ☑9
2025/4/3 9 可归前缀和活前缀的定义 p125 ◼ 前缀 一个句型的任意首部 ◼ 可归前缀 LR分析过程中每次采取归约动作前符号 栈中的内容，即规范句型的可归前缀 ◼ 活前缀 形成可归前缀之前包括可归前缀在内的所有 规范句型的前缀 ◼ 分析决策依据栈顶状态和当前输入符号是什么？ ◆利用LR(0)项目构造识别活前缀和句柄的DFA
LR(0)项目定义和意义p130 ■在文法G的产生式右部某个位置标有‘.的产生式， 称为文法的一个LR(O)项目(Item) ■例产生式A→XYZ对应有四个LR(O)项目： A→.XYZ A→X.YZ A→XY.Z A→XYZ. 约定：A→e对应的LR(O)项目为A→. ■每个项目的含义与“.”的位置有关 {已识别过的部分}.{待识别的部分】 2025/4/3 10
2025/4/3 10 LR(0)项目定义和意义 p130 ◼ 在文法G的产生式右部某个位置标有‘.’的产生式， 称为文法的一个LR(0)项目(Item) ◼ 例产生式A→XYZ对应有四个LR(0)项目： A→.XYZ A→X.YZ A→XY.Z A→XYZ. 约定：A→ε对应的LR(0)项目为 A→. ◼ 每个项目的含义与“.”的位置有关 {已识别过的部分}.{待识别的部分}