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

第1页共8页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第1页共8页第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.2LR分析法的基本原理㈠前缀㈡活前缀㈢LR分析法的基本思想㈣LR(0)项目（简称项目）第2页共8页第1页共8页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第2页共8页在产生式右部的某个位置添加一个园点“.”。特例，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→.γ状态。表示只有看到了从A推出的全部符号，状态i:X→α.Aβ才可经A弧进入状态j:X→αA.β。接上例，构造识别文法活前缀的NFA，如下所示：εA→.cAA→c.AAA→cA.cεεA→.ddA→d.εE→.aAaE→a.AAE→aA.εS'→.EES'→E.εE→.ddE→d.第3页共8页第2页共8页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第3页共8页其中称为初态（含有S'→.E的项目），状态、、、和称为句柄识别态（含有形如A→γ.的项目），其中又称为接受态（含有S'→E.的项目）。㈥构造识别活前缀的DFA5:7:cA→c.AAA→cA.A→.cAA→.dd6:A→d.2:cE→a.Ad4:A→.cAAE→aA.A→.d0:aS'→.E1:E→.aAES'→E.E→.dd3:E→d.其中0是初态，1为接受态，3、4、6和7是句柄识别态。㈦项目分类㈧LR(0)项目集规范族（简称项目集规范族）㈨活前缀识别工作原理5.3项目集规范族的构造㈠文法拓广㈡项目集I的闭包（CLOSURE(I)）㈢状态转换函数（GO(I,X)）㈣项目集规范族构造算法第4页共8页第3页共8页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第4页共8页5.5LR(0)分析表的构造㈠预备工作①引入产生式S'→S，将文法拓广成G'。②对G'的产生式进行编号。③构造文法G'的状态转换函数GO(I,X)和项目集规范族C。㈡构造法设项目集规范族C={I0、I1、……In}，将I0、I1、……In视为分析表状态0、1、……n。LR(0)分析表存放在二维数组M中，第一维为状态，第二维为文法符号。①若移进项目A→α.aβI∈i且GO(Ii,a)=Ij，其中aV∈T，则置M[i][a]=sj（s表示移进）。②若归约项目A→α.I∈i，对于任何aV∈T{#}∪，置M[i][a]=rk（k是产生式A→α的编号，r表示归约）。③若接受项目S'→S.I∈i，则置M[i]['#']=Acc（Acc表示接受）。④若待约项目A→α.BβI∈i且G...