第六章LR分析 自下而上的语法分析 特定的一种h+ reduce实现技术 能力强 几乎所有CFG的语言结构都能用LR分析 不需要对文法附加条件 难点 几乎不可能用手工编写LR分析器 现实 有LR分析器的生成器
第六章ＬＲ分析 自下而上的语法分析 特定的一种shift-reduce实现技术 能力强 几乎所有CFG的语言结构都能用LR分析 不需要对文法附加条件 难点 几乎不可能用手工编写LR分析器 现实 有LR分析器的生成器
第六章LR分析 61概述 自下而上的语法分析 LR分析器 62LR(0)分析 63SLR(1)分析技术,二义文法的应用 64LR(1)和LALR(1)分析
第六章ＬＲ分析 6.1 概述 自下而上的语法分析 LR分析器 6.2 LR(0)分析 6.3 SLR(1)分析技术，二义文法的应用 6.4 LR(1)和LALR(1)分析
61概既述 自下而上的语法分析 例:文法G:S→cAd A→ab A 识别输入串w=cabd是否该文法的句子 归约过程构造的推导:cAd→ cabd S→cAd
6.1 概述 自下而上的语法分析 例：文法G： S → cAd A → ab A → a 识别输入串w=cabd是否该文法的句子 S A A c a b d c a b d c d 归约过程构造的推导： cAd cabd S cAd
(1)S→cAd(2)A→ab(3)A→a 识别输入串w=cabd是否为该文法的句子 自下而上的语法分析 对串cabd的分析中,如果不是 选择ab用产生式(2)而是选 择a用产生式(3)将a归约到 c abd 了A,那么在cAb 中无法找到一个可归约串 最终就达不到归约到S的结 果,因而也无从知道cabd是cAbd 在自下而上的分析方法中如何 识别可归约的串? 在分析程序工作的每一步, 都是从当前串中选择一个 子串,将它归约到某个非 终结符号,该子串称为 可岿约串
(1)S → cAd (2) A → ab (3)A → a 识别输入串w=cabd是否为该文法的句子 自下而上的语法分析 对串cabd的分析中，如果不是 选择ab用产生式(2),而是选 择a用产生式(3)将a归约到 了A，那么在c A b d 中无法找到一个可归约串了， 最终就达不到归约到S的结 果，因而也无从知道cabd是 一个句子 在自下而上的分析方法中如何 识别可归约的串？ 在分析程序工作的每一步， 都是从当前串中选择一个 子串，将它归约到某个非 终结符号，该子串称为 “可归约串” c a b d c A b d a
刻画“可归约串” 文法G|S 句型的短语 S=*aA6且A=+β,则称β是句型aB8 相对于非终结符A的短语 句型的直接短语 若有A→β,则称β是句型aβ8相对于非终结 符A的直接短语 句型的句柄 个句型的最左直接短语称为该句型的句柄
刻画“可归约串” 文法G[S] 句型的短语 S =>* αAδ且 A =>+ β，则称β是句型αβδ 相对于非终结符A的短语 句型的直接短语 若有A β，则称β是句型αβδ相对于非终结 符A 的直接短语 句型的句柄 一个句型的最左直接短语称为该句型的句柄