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→. ◼ 每个项目的含义与“.”的位置有关 {已识别过的部分}.{待识别的部分}