第5章 自下而上的语法分析(Tsu版电子教案)VIP专享VIP免费

第 5 章 自下而上的语法分析从叶结点出发，步步向上归约。若能归约到根结点，说明输入串是文法的一个句子，否则输入串存在语法错误。5.1 自下而上的语法分析概述㈠概述实质上是一种移进归约法，设置一个栈，将输入串符号逐个移进栈内，一旦发现栈顶形成某个产生式的候选式时，立即将栈顶这一部分符号替换（归约）成该产生式的左部符号。例给定文法Ｇ：S→aAcBeA→b | AbB→d 和输入串 abbcde，其移进归约过程如下所示：edBBbccccbAAAAAAAaaaaaaaaaS 移 移 归 移 归 移 移 归 移 归 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩因最终归约到根结点，输入串 abbcde 是文法的一个句子。㈡问题从第④步到第⑤步有二种选择，可将 b 归约成 A，栈顶成 aAA；也可将 Ab 归成 A，栈顶成 aA，显然后者是正确的，故需精确定义可归约串。㈢句柄和规范归约① 短语② 直接短语（简单短语）③ 句柄继续问题的讨论。句型 aAbcde 中存在三个短语，它们是 Ab、d 和 aAbcde，其中 Ab 和d 是直接短语，句柄是 Ab。不能因为存在规则 A→b，就断定 b 是这个句型的一个短语，b不是句柄，甚至连短语都不是。④ 规范归约（最左归约）⑤ 规范句型⑥ 规范推导⑦ 图解法5.2 LR 分析法的基本原理㈠前缀㈡活前缀㈢ LR 分析法的基本思想㈣ LR(0)项目（简称项目）在产生式右部的某个位置添加一个园点“.”。特例，A→ε 的项目为 A→.。例文法0.S'→E1.E→aA2.A→cA3.A→d4.E→d这个文法的项目有S'→.ES'→E.E→.aAE→a.AE→aA.A→.cAA→c.AA→cA.A→.dA→d.E→.dE→d.㈤构造识别活前缀的 NFA① 将每个项目视为识别活前缀 NFA 的一个状态。② 规定状态 S'→.S 为 NFA 的唯一初态，状态 S'→S.为 NFA 的唯一接受态（S 为原文法开始符号，S'为拓广文法开始符号）。③ 因在每个状态都可识别出一个活前缀（初态可识别出活前缀 ε），故 NFA 的每个状态都是终态，终态又称为活前缀识别态。④ 如果状态 i 和状态 j 源自于同一产生式，而且状态 i 和状态 j 的园点位置相差一个文法符号，例状态 i 为i:X→X1……Xi-1 .XiXi+1……Xn状态 j 为j:X→X1……Xi-1Xi .Xi+1……Xn那么状态 i 和 j 之间存在一条弧，标记为 Xi，表示在状态 i 读入 Xi进入状态 j。⑤ 若状态 i 园点之后的符号为非终结符（例 i:X→α .Aβ），那么从状态 i 画一条 ε 弧到所有 k:A→.γ 状态。表示只有看到了...