上下文无关文法及其语法树(ppt28)-经营管理(编辑修改稿)

上下文无关文法及其语法树(ppt28)-经营管理(编辑修改稿)内容摘要：

(1) 12 软件教研室 徐慧英 吕振洪 来自 中国最大的资料库下载 文法和语言 自上而下分析法的缺陷 关键： 回溯问题 ；（ ∵ 其分析过程是一种试探过程） 回溯问题 是从各种可能的候选式中任选一个，进行推导后发现该候选式是错误的，则退回去重新选择候选式的方式。 例如上例中的 (3)。 S x A y (3) — 选用第 1个候选式 * 回溯的产生使算法代价极低，效率很低。 关于解决回溯问题将在第 5章中介绍。 * 13 软件教研室 徐慧英 吕振洪 来自 中国最大的资料库下载 自下而上的分析法 文法和语言 基本思想：从输入串开始，逐步进行“归约”，直至归约到文法的开始符号。 即从语法树的末端开始，步步向上“归约”，直到根结。 归约：若 V= γαδ， W=γβδ， α → β是文法的产生式，如有V=W，则 W直接归约到 V。 例： 文法 G[S]： (1)S→ aAcBe (2) A→ b (3)A→ Ab (4) B→ d 识别 abbcde是否为文法 S的一个句子。 解题思想：扫描 abbcde，从中找出一个子串，该子串与某一产生式的右部相匹配。 14 软件教研室 徐慧英 吕振洪 来自 中国最大的资料库下载 自下而上分析法举例 文法和语言 解： a b b c d e (1) a b b c d e A (2) a b b c d e A A (3) a b b c d e A A (4) B a b b c d e A A (5) B S 15 软件教研室 徐慧英 吕振洪 来自 中国最大的资料库下载 自下而上分析法存在的问题 文法和语言 可归约串的问题 ；（ ∵ 该分析的每一步就是从当前串中找一个子串（称“可归约串”），将它归约到某个非终结符号） 自下而上分析法的 关键 就是找哪个子串是“可归约串”，哪个不是“可归约串”。 例如上例中的 (3) a b b c d e A A (3) — 用产生式 (2)而非 (3)，则不能归约到 S 因此必须精确定义“可归约串”，事实上存在着种种不同的方法刻画“可归约串”，对这个概念的不同定义，形成了不同的自下而上的分析法。 在“规范归约”的分析中，用“句柄”来刻画“可归约串”。 来自 中国最大的资料库下载 16 软件教研室 徐慧英 吕振洪 来自 中国最大的资料库下载 短语、直接短语、句柄 文法和语言 短语： 令文法 G， 开始符号为 S， αβδ是 G的句型 （即 S αβδ），如果 S αAδ且 A β，则称 β是句型 αβδ相对于非终结符 A的短语。 直接短语 如短语中有 A=β，则称 β是句型相对于规则 A→ β的直接短语。 句柄 一个句型的最左直接短语称为该句型的句柄。