编译原理与技术 自底向上分析.ppt
《编译原理与技术 自底向上分析.ppt》由会员分享,可在线阅读,更多相关《编译原理与技术 自底向上分析.ppt(102页珍藏版)》请在三一文库上搜索。
1、2019/10/25,编译原理与技术讲义,1,编译原理与技术,自底向上分析,2019/10/25,编译原理与技术讲义,2,自底向上分析,移进归约分析 分析树的构建 从叶子结点开始,逐步构造各内部结点直至根结点出现。 分析技术的关键句柄的识别 句柄(handle)是什么? 简单讲,句柄是一个产生式的右部;自底向上分析(移进归约分析)过程,其实就是发现句柄并将句柄(产生式右部)替换成相应左部非终结符的过程。该替换称为最左归约,它对应着某最右推导逆过程的一步。,2019/10/25,编译原理与技术讲义,3,自底向上分析,分析技术的关键句柄的识别 句柄(handle)是什么? 一般地,如果有以下最右推
2、导序列, 则产生式A及其在右句型中的位置称为右句型的句柄。,2019/10/25,编译原理与技术讲义,4,自底向上分析,e.g.17 文法G6 1)SaABe 2)AAbc 3)Ab 4)Bd,串abbcde$的分析过程。,输入串 a b b c d e $,a A b c d e $,a A d e $,a A B e $,S $,最左归约,最右推导,2019/10/25,编译原理与技术讲义,5,自底向上分析,e.g.17 文法G6 1)SaABe 2)AAbc 3)Ab 4)Bd,串abbcde$的对应分析树的建立过程。,输入串 a b b c d e $,2019/10/25,编译原理与
3、技术讲义,6,自底向上分析,e.g.17 文法G6 1)SaABe 2)AAbc 3)Ab 4)Bd,串abbcde$的对应分析树的建立过程。,输入串 a b b c d e $,2019/10/25,编译原理与技术讲义,7,自底向上分析,e.g.17 文法G6 1)SaABe 2)AAbc 3)Ab 4)Bd,串abbcde$的对应分析树的建立过程。,输入串 a b b c d e $,A,2019/10/25,编译原理与技术讲义,8,自底向上分析,e.g.17 文法G6 1)SaABe 2)AAbc 3)Ab 4)Bd,串abbcde$的对应分析树的建立过程。,输入串 a b b c d
4、e $,A,2019/10/25,编译原理与技术讲义,9,自底向上分析,e.g.17 文法G6 1)SaABe 2)AAbc 3)Ab 4)Bd,串abbcde$的对应分析树的建立过程。,输入串 a b b c d e $,A,A,2019/10/25,编译原理与技术讲义,10,自底向上分析,e.g.17 文法G6 1)SaABe 2)AAbc 3)Ab 4)Bd,串abbcde$的对应分析树的建立过程。,输入串 a b b c d e $,A,A,B,2019/10/25,编译原理与技术讲义,11,自底向上分析,e.g.17 文法G6 1)SaABe 2)AAbc 3)Ab 4)Bd,串ab
5、bcde$的对应分析树的建立过程。,输入串 a b b c d e $,A,A,B,S,2019/10/25,编译原理与技术讲义,12,移进归约分析,e.g.17 用栈来实现串abbcde$的分析(1),2019/10/25,编译原理与技术讲义,13,移进归约分析,e.g.17 用栈来实现串abbcde$的分析(2),分析成功!,2019/10/25,编译原理与技术讲义,14,移进归约分析,四种分析动作(action) 移进(shift)将当前输入符号移入栈顶top(why?) 归约(reduce)当“句柄”出现在栈顶(从栈中某处到栈顶top),则将“句柄”从栈顶弹弹出,并将相应产生式左部非终
6、结符置入栈顶top。(when?) 接受(accept)分析成功! 报错(error)出现语法错误,调错误恢复例程,2019/10/25,编译原理与技术讲义,15,移进归约分析,分析动作冲突 移进-归约冲突(shift-reduce conflict) 当“句柄”处于栈顶时,分析动作指示既可以将下一输入符号移入栈顶top,又可以实施归约操作。如何动作呢? 归约-归约冲突(reduce-reduce conflict) 位于栈顶的“句柄”,同时匹配两个(以上)产生式的右部。选谁呢?,怎么可能呢?,2019/10/25,编译原理与技术讲义,16,移进归约分析冲突,二义文法G不适合移进归约分析 e.
7、g. 18 移进-归约冲突 文法G7: S if E then S | if E then S else S S a,$. if E then S,“句柄”?,else. ,分析栈,输入串:,当前输入符号,2019/10/25,编译原理与技术讲义,17,$. if E then S else,栈顶,. ,分析栈,输入串:,$ S,else . ,分析栈,输入串:,归约动作,移进动作,文法G7: S if E then S | if E then S else S | a,期待新的“长句柄”,2019/10/25,编译原理与技术讲义,18,e.g.19 二义性文法G8如下: EE+E | E *
8、 E | (E) | id 输入串id+id+id$的最右推导: 1)EE+EE+idE+E+idE+id+idid+id+id 2)EE+EE+E+EE+E+idE+id+idid+id+id 带下划线的符号串是相应句型的句柄。,移进归约分析冲突,2019/10/25,编译原理与技术讲义,19,e.g.19输入串id+id+id$的栈分析过程,分析1) 输入串 分析2) $ id+id+id$ $ $id +id+id$ $id $E +id+id$ $E $E+ id+id$ $E+ $E+id +id$ $E+id $E+E +id$ $E+E $E +id$ id$ $E+E+,归约,
9、移进,2019/10/25,编译原理与技术讲义,20,e.g.19输入串id+id+id$的栈分析过程,分析1) 输入串 分析2) $E+E +id$ +id$ $E+E $E +id$ id$ $E+E+ $E+ id$ $ $E+E+id $E+id $ $ $E+E+E $E+E $ $ $E+E $E $ $ $E,2019/10/25,编译原理与技术讲义,21,移进归约分析冲突,归约-归约冲突 e.g.20 文法G9 1)Statid ( para_list ) | expr := expr 2)para_listpara_list , para | para 3)paraid 4)
10、exprid ( expr_list ) 5)exprid 6)expr_listexpr_list , expr | expr,2019/10/25,编译原理与技术讲义,22,e.g.20分析输入串id(id,id)$,分析栈 输入串 $ id ( id , id ) $ 1) $ id ( expr , id ) $ 2) $ id ( para , id ) $,paraid,目标:过程调用语句,exprid 目标:数组引用,2019/10/25,编译原理与技术讲义,23,LR分析器,高效易实现的自底向上的分析方法 文法限制少,适用于大多数CFG(包括含左递归、左因子的文法) LR(k)
11、分析器 L 从左自右读(read from Left to right) R 构造最右推导的逆(for constructing a Rightmost derivation in reverse) k 向前看符号的个数(the number of input symbols of lookhead),2019/10/25,编译原理与技术讲义,24,LR分析器,输入串,LR控制程序,LR分析表,状态 符号 栈,输出,Top,Bottom,动作表 Action,转移表 GOTO,2019/10/25,编译原理与技术讲义,25,格局: 状态符号栈 输入串 分析表 动作表(Action): S ($
12、) shift , reduce, accept, error 转移表(GOTO): S VN S,LR分析器,2019/10/25,编译原理与技术讲义,26,分析算法 初始,状态S0位于栈底(栈顶); 根据当前栈顶状态S和当前输入符号a,查action表,由actionS,a决定分析动作: si输入符a移入栈顶top(push a );状态i移入栈顶top(push i)。 rj 按第j个产生式(A)进行归约,首先将从栈顶top往栈中的|个状态和|个符号(计2|个)弹出分析栈;设此时栈顶状态为T,再将符号A和状态S=GOTOT,A 依次移入分析栈(S在栈顶top) acc 输入串被接受,分析
13、成功! error 输入串有错,调错误恢复程序,2019/10/25,编译原理与技术讲义,27,e.g.21 表达式文法G2的LR分析表,文法G2: (1)EE + T (2)ET (3)TT * F (4)TF (5)F( E ) (6)F id,2019/10/25,编译原理与技术讲义,28,e.g.21 表达式文法G2的LR分析表,2019/10/25,编译原理与技术讲义,29,e.g.21 表达式文法G2的LR分析表(续),2019/10/25,编译原理与技术讲义,30,e.g.21 id*(id+id)$的移进-归约分析过程,2019/10/25,编译原理与技术讲义,31,e.g.2
14、1 id*(id+id)$的移进-归约分析过程,2019/10/25,编译原理与技术讲义,32,e.g.21 id*(id+id)$的移进-归约分析过程,2019/10/25,编译原理与技术讲义,33,活前缀(viable prefix) 是规范(右)句型的前缀,它不包含句柄后的任何符号(即活前缀的长度不会超过句柄的最右端)。若AP,有如下规范推导, 则,的前缀为右句型的活前缀。,识别活前缀的DFA,2019/10/25,编译原理与技术讲义,34,活前缀与句柄 移进-归约分析过程中,分析栈内的符号串构成活前缀(这表明已扫描过的输入串没有语法错误;事实上,也只有形成活前缀的符号才会被移入分析栈;
15、分析的实质就是判断剩余输入串能否继续形成活前缀) 活前缀不包含或部分包含句柄 此时期待着“匹配”句柄的输入串并将之移入栈顶;,bottom,2019/10/25,编译原理与技术讲义,35,活前缀与句柄 活前缀已完全包含句柄 此时句柄位于栈顶,需要进行归约。,bottom,句柄,A,bottom,2019/10/25,编译原理与技术讲义,36,识别活前缀的DFA,LR(0)项目 产生式右部加 “” ; “”的左部表示已“看见”(分析识别过)的部分;而右部则是期望“看到”的部分。如:产生式AP,其LR(0)项目有: A 期望看到产生的串(移进项目) A 已分析期望看到产生的串(移进项目) A 、都
16、分析完了 ( 归约项目) 特别的,空产生式A 的LR(0)项目只有一个: A ( 归约项目),2019/10/25,编译原理与技术讲义,37,识别活前缀的NFA,拓展文法 引入新产生式SS , S为新的开始符号 NFA的状态: 各个产生式的LR(0)项目; 初态:SS 终态(唯一) : SS NFA的状态转换,i: AX,j: AX,X,h: AB,k: B ,XVTVN,BVN,2019/10/25,编译原理与技术讲义,38,采用子集构造法转换上述的NFA到DFA 闭包 closure(I) / I:NFA的状态子集即LR(0)项目集合 1)I closure(I) 2)若项目ABI,BP,
17、则项目 B closure(I) 3)重复2)直至closure(I)不再增大 转移 goto(I,X) / XVTVN J=goto(I,X)=closure(AX| AX I),2019/10/25,编译原理与技术讲义,39,DFA识别的活前缀从DFA初态I0到任一状态Ij的路径上所“读过”的符号串。状态Ij可以指示下一步的“动作”。 该DFA识别所有的活前缀;且只能识别活前缀。 LR(0)项目规范族C=DFA的状态 LR(0)有效项目 项目A,如果有 则项目A 对活前缀有效。 对同一活前缀有效的(多个)LR(0)项目均在同一个项目集合(状态)中;而且同一LR(0)项目可以对多个活前缀有效
18、(即该项目可以出现在不同的项目集合中)。,2019/10/25,编译原理与技术讲义,40,LR(0)有效项目 如果项目AB对活前缀有效,即有最右推导 如果BP 则有以下最右推导, 显然,项目B对活前缀也有效。 项目AB和B应在同一个状态(项目集合) 这就是closure()函数,2019/10/25,编译原理与技术讲义,41,LR(0)有效项目 如果项目AXI对活前缀有效,则项目 AXJ=goto(I,X)显然对活前缀X有效。,2019/10/25,编译原理与技术讲义,42,e.g.22 识别文法G2活前缀的DFA,拓展文法G2 (0)EE (1)EE + T (2)ET (3)TT * F
19、(4)TF (5)F( E ) (6)F id,DFA的初态I0= closure(EE) E E E E + T E T T T * F T F F ( E ) F id,2019/10/25,编译原理与技术讲义,43,I1:EE E E + T,I2:ET TT * F,I3:T F ,I4:F(E) EE + T ET TT * F TF F(E) Fid,I5:F id ,I0:E E E E + T E T T T * F T F F (E) F id,I7:TT * F F(E) Fid,I6:EE + T TT * F TF F(E) Fid,I8:F(E) EE + T,I11
20、:F(E) ,I9:EE + T TT * F,I10:TT*F,E,T,id,F,(,+,*,(,E,T,F,id,T,F,(,id,F,(,id,),+,*,2019/10/25,编译原理与技术讲义,44,e.g.23 对活前缀E+T*有效的LR(0)项目,E+T*的识别路径: I0E I1+ I6T I9* I7 项目集合(状态)I7中的项目对E+T*有效: TT *F F(E) Fid,EE+T E+T*F,EE+T E+T*F E+T*(E),EE+T E+T*F E+T*id,=E+ = T* =F,=E+T* = =(E) 或 id,2019/10/25,编译原理与技术讲义,45
21、,LR(0)分析仅取决于当前(栈顶)状态,由状态本身所包含的信息决定下一步动作。如,,LR(0)分析方法,I7:TT * F / 转移 F(E) / 移进下一输入符号 Fid / 移进下一输入符号 至于移入栈顶的符号不是 ( 或 id,则报错,I10:TT*F / 归约(不论下一输入符号是谁),2019/10/25,编译原理与技术讲义,46,LR(0)分析方法,LR(0)分析表的构造 若AaI,且goto(I,a)=J,则actionI,a=sJ 若A I,则actionI,a = r A,aVT或$ 若SS I,则actionI,$ = acc 若goto(I,B)=K,则GOTOI,B=K
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译原理与技术 自底向上分析 编译 原理 技术 向上 分析
链接地址:https://www.31doc.com/p-4175513.html