第6章LR分析 nLR分析法 LR分析法概述 u LR分析器 u LR(O)分析 u SLR(1)分析 u LR(1)分析 LALR(1)分析 LR分析法小结 门自底向上语法分析小结 n本章练习 n作业 2023/2/28 课程目绿 ☒)
2023/2/28 1 第6章 LR分析 n LR分析法 u LR分析法概述 u LR分析器 u LR(0)分析 u SLR(1)分析 u LR(1)分析 u LALR(1)分析 u LR分析法小结 n 自底向上语法分析小结 n 本章练习 n 作业 课程目录
LR(k)分析法概述p123 n是一种自下而上语法分析技术 UL从左到右扫描输入符号 UR构造一个最右推导的逆过程一一最左归约 Uk超前读入k个符号，以便确定归约用的产生式 nLR分析器 U移进归约分析器+LR分析表 n特殊性 U栈=状态栈+文法符号栈 U分析表=动作表action+状态转移表goto 2023/2/28 ☒ 2
2023/2/28 2 LR(k)分析法概述 p123 n 是一种自下而上语法分析技术 uL 从左到右扫描输入符号 uR 构造一个最右推导的逆过程——最左归约 uk 超前读入k个符号，以便确定归约用的产生式 n LR分析器 u移进归约分析器 + LR分析表 n 特殊性 u栈 = 状态栈 + 文法符号栈 u分析表 = 动作表action + 状态转移表goto
各种LR分析表p123 n采用不同的构造方法 ULR(O)表构造法一— 基础 U简单LR(SLR(I))表构造法一一 理论过渡 U规范LR(I)表构造法一一理论过渡 U向前LR(LALR(I)表构造法一一实用 n不同点 U构造分析表的方法不同 U分析能力不同，实现效率不同 n共同点 U逻辑结构 U工作原理（状态转移） 2023/2/28 章节目录可□3
2023/2/28 3 各种 LR 分析表 p123 n 采用不同的构造方法 uLR(0)表构造法——基础 u简单LR(SLR(1))表构造法——理论过渡 u规范LR(1)表构造法——理论过渡 u向前LR(LALR(1))表构造法——实用 n 不同点 u构造分析表的方法不同 u分析能力不同，实现效率不同 n 共同点 u逻辑结构 u工作原理(状态转移) 章节目录
LR分析器模型p124图6.1 。 an 状态栈符号栈 输入缓冲区 X 产生式 m-I LR分析程序 序列 .S% .X# 动作表 转移表 LR action goto 分析表 2023/2/28 小节目录 5
2023/2/28 5 LR分析器模型 p124 图6.1 a1 . ai . an # ＬＲ分析程序 动作表 action 转移表 goto 产生式 序列 状态栈 输入缓冲区 LR 分析表 Sm Sm-1 . . . S1 S0 Xm Xm-1 . . . X1 # 符号栈 小节目录
LR分析表 举例p142 ACTIONZ动作 G0T0转换 态 1 + 米 井 ET F 文法6.8 表 0 s5 s4 1 2 3 (1)E→E+T 1 s6 acc (2)E→T 2 r2 s7 r2 r2 (3)T→T*F 3 r4 r4 r4 r4 (4)T→F 4s5 s4 82 3 (5)F→(E) 5 r6 r6 r6 r6 (6)F→i 6 s5 s4 9 3 约定 s5 s4 10 si将符号a,状 8 s6 sII 态i压入栈 9 rl s7 rl rl ri用第i个产 10 r3 r3 r3 r3 生式归约 rb rb rb rb 2023/2/28 ☒D6
2023/2/28 6 LR 分析表 举例 p142 表 文法6.8 (1)E→E+T (2)E→T (3)T→T*F (4)T→F (5)F→(E) (6)F→i 状 ACTION动作 GOTO转换 态 i + * ( ) # E T F 0 s5 s4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 3 r4 r4 r4 r4 4 s5 s4 8 2 3 5 r6 r6 r6 r6 6 s5 s4 9 3 7 s5 s4 10 8 s6 s11 9 r1 s7 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 约定 si将符号a,状 态i压入栈 ri用第i个产 生式归约
LR分析过程 步骤 状态栈 符号栈输入串 动作 goto表 举例p142 0 i+i*i# s5 #i +i*i# r6 文法 图6.9 34 03 F +i*i# r4 (0,F)=3 (1)E→E+T #T +i*i# r2 (0,T)=2 (2)E→T (5) 01 E +i*i# s6 (0,E)=1 ( 016 #D+ i*i# s5 (3)T→T*F 7) 0165 #把+1 *i# (4)T→F ( 0163 #E+F 米i# 4 (6,F)=3 (5)F→(E) (9) 0169 #E+T *i# (6,T)=9 (6)F→i 10) 01697 #E+T* # s5 (11) 016975 #E+T*i # r6 输入串 (12) 0169710 #E+T*F # (7,F)=10 (13) 0169 #E+T # l iti*i (6,T)=9 (14) 01 #E acc (0,E)=1 2023/2/28 K
2023/2/28 7 LR分析过程 举例 p142 文法 图6.9 (1)E→E+T (2)E→T (3)T→T*F (4)T→F (5)F→(E) (6)F→i 输入串 i+i*i 步骤 状态栈 符号栈 输入串 动作 goto表 (1) 0 # i+i*i# s5 (2) 05 #i +i*i# r6 r3 (3) 0 # 3 F +i*i# r4 (0,F)=3 (4) 02 #T +i*i# r2 (0,T)=2 (5) 01 #E +i*i# s6 (6) 016 #E+ i*i# s5 (7) 0165 #E+i *i# (6,F)=3 r6 (8) 0163 #E+F *i# (6,T)=9 r4 (9) 0169 #E+T *i# (0,E)=1 s7 (10) 01697 #E+T* i# s5 (11) 016975 #E+T*i # r6 (12) 0169710 #E+T*F # (7,F)=10 (13) 0169 #E+T # r1 (6,T)=9 (14) 01 #E # acc (0,E)=1
LR分析过程 步骤 状态栈 符号栈输入串 动作 goto表 课堂练习 1) # i*i+i# 5 (2 05 #i *i+i# r6 文法 82 *i+i# r4 (0,F)=3 (1)E→E+T *i+i拼 (0,T)=2 (5) 027 #T米 +i# ζ (2)E→T (3)T→T*F 67 0275 #T*i +i# 6 02710 #T*F +i# (7,F)=10 (4)T→F 8 81 #灯 +i# (5)F→(E) # +i# 12 (0,T)=2 (0,E)=1 (6)F→1 (10) 0 #E+ i# 5 (11) 0165 #E+i # 输入串 (12) 0163 #E+F # r4 (6,F)=3 (13) 0169 #E+T # rl i*i+i (6,T)=9 (14) 01 #E 井 acc (0,E)=1 2023/2/28 ☒D
2023/2/28 8 LR分析过程 课堂练习 文法 (1)E→E+T (2)E→T (3)T→T*F (4)T→F (5)F→(E) (6)F→i 输入串 i*i+i 步骤 状态栈 符号栈 输入串 动作 goto表 (1) 0 # i*i+i# s5 (2) 05 #i *i+i# r6 r4 (3) 03 #F *i+i# r4 (0,F)=3 (4) 02 #T *i+i# s7 (0,T)=2 (5) 027 #T* i+i# s5 (6) 0275 #T*i +i# r6 (7) 02710 #T*F +i# r3 (7,F)=10 (8) 02 #T +i# r2 (0,T)=2 (9) 01 #E +i# s6 (0,E)=1 (10) 016 #E+ i# s5 (11) 0165 #E+i # r6 (12) 0163 #E+F # (6,F)=3 (13) 0169 #E+T # r1 (6,T)=9 (14) 01 #E # acc (0,E)=1
LR分析表课堂练习 状 ACTIONZ动作 G0T0转换 态 b # B 句子bab分析 a 0 ls3 s4 1 2 BEGIN acc 状态 符号输入动作 2 s3 s4 5 1)0 井 bab# s4 3s3 s4 6 2)04 #b ab# r3 2 3)02 4 B ab# s3 r3 r3 r3 4)023 #Ba b# s4 5 rl 5)0234#Bab 井 r3 6 6 r2 r2 r2 6)0236 #BaB # r2 5 7)025 (1)S→BB #BB 井 r11 文法 8)01 S # acc (2)B→aB (3)B→b 2023/2/28 小节目录 ☒D10
2023/2/28 10 LR分析表课堂练习 文法 (1)S→BB (2)B→aB (3)B→b 状 ACTION动作 GOTO转换 态 a b # S B 0 s3 s4 1 2 1 acc 2 s3 s4 5 3 s3 s4 6 4 r3 r3 r3 5 r1 6 r2 r2 r2 句子bab分析 状态 符号 输入 动作 1)0 # bab# s4 2)04 #b ab# r3 2 3)02 #B ab# s3 4)023 #Ba b# s4 5)0234 #Bab # r3 6 6)0236 #BaB # r2 5 7)025 #BB # r1 1 8)01 #S # acc BEGIN 小节目录
LR文法的定义p123 nLR文法 U能够构造一张不含多重入口的LR分析表的文 法，即LR分析表的每个入口均是唯一确定的 nLR(k)文法 U能用一个每步顶多向前检查k个输入符号的LR 分析器进行分析的文法 U对大多数的程序设计语言来说，k=0或1就足 够了 n因此，我们只考虑k≤1的情形 n非LR文法 U栈顶内容和输入符号已知时仍无法唯一确定 应采取的动作 2023/2/28 小节目绿
2023/2/28 11 LR文法的定义 p123 n LR文法 u能够构造一张不含多重入口的LR分析表的文 法，即LR分析表的每个入口均是唯一确定的 n LR(k)文法 u能用一个每步顶多向前检查k个输入符号的LR 分析器进行分析的文法 u对大多数的程序设计语言来说，k=0或1就足 够了 n 因此，我们只考虑k≤1的情形 n 非LR文法 u栈顶内容和输入符号已知时仍无法唯一确定 应采取的动作 小节目录
6.2LR(0)分析 p124 nLR(O)分析举例 n规范句型的活前缀 nLR(0)项目 U定义、意义和构造方法 n识别活前缀的DFA U构造方法 nLR(O)项目集规范族 U定义和构造方法 nLR(O)分析表 u构造方法 nLR(O)文法及LR(O)分析存在问题 2023/2/28 章节目录 ☑D12
2023/2/28 12 6.2 LR(0)分析 p124 n LR(0)分析举例 n 规范句型的活前缀 n LR(0)项目 u定义、意义和构造方法 n 识别活前缀的DFA u构造方法 n LR(0)项目集规范族 u定义和构造方法 n LR(0)分析表 u构造方法 n LR(0)文法及LR(0)分析存在问题 章节目录