第四章语法分析精选PPT.ppt

《第四章语法分析精选PPT.ppt》由会员分享，可在线阅读，更多相关《第四章语法分析精选PPT.ppt（99页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章语法分析第四章语法分析1第1页，此课件共99页哦4.5 自底向上分析自底向上分析q移进归约分析法(Shift-reduce parsing)q一般的移进归约法LR parsingLR(0)SLRLR(1)LALRq自动的语法分析器的生成器（YACC）2第2页，此课件共99页哦4.5.1 归约归约例4.21考虑文法S aABe A Abc|bB d句子abbcde的归约步骤如下：abbcde aAbcdeaAdeaABeS 对应最右推导的逆过程：S rm aABe rm aAde rm aAbcde rm abbcdeSa A B edA b cb3第3页，此课件共99页哦句柄句柄(han

2、dles)q句柄是最左直接短语。q右句型的句柄是产生式A 和中的子串，且用A 代替得到的仍是右句型 qi.e.A is a handle of w at the location immediately after the end of,if:q句柄的右边仅含终结符。S Aw 4第4页，此课件共99页哦短语和句柄短语和句柄q设有上下文无关文法G=(VT,VN,S,P)，串是文法G的句型，若有A+，且串A也是文法G的句型，则称是句型中关于非终结符号A的短语短语。q若A ，则称为直接短语直接短语。q最左直接短语称为句柄句柄(handle)。5第5页，此课件共99页哦ExampleS aABe aA

3、de aAbcde abbcde考虑文法S aABe A Abc|bB dIt follows that:A b is a handle of abbcde in location 2.rmrmrmrmSa A B edA b cb6第6页，此课件共99页哦ExampleS aABe aAde aAbcde abbcdeIt follows that:A Abc is a handle of aAbcde in location 2.rmrmrmrmSa A B edA b c考虑文法S aABe A Abc|bB d7第7页，此课件共99页哦ExampleS aABe aAde aAbcde

4、 abbcdeIt follows that:B d is a handle of aAde in location 3.rmrmrmrmSa A B ed考虑文法S aABe A Abc|bB d8第8页，此课件共99页哦ExampleS aABe aAde aAbcde abbcdeIt follows that:S aABe is a handle of aABe in location 1.rmrmrmrmSa A B e考虑文法S aABe A Abc|bB d9第9页，此课件共99页哦 例例4.22E E+E|E*E|(E)|idq如果文法二义，那么句柄可能不唯一。q在句型E+E*

5、id3中，句柄不唯一。E rm E+E rm E+E*E rm E+E*id3 rm E+id2*id3 rm id1+id2*id3E rm E*E rm E*id3 rm E+E*id3 rm E+id2*id3 rm id1+id2*id3 10第10页，此课件共99页哦4.5.2 句柄剪枝句柄剪枝(Handle Pruning)qA rightmost derivation in reverse can be obtained by“handle-pruning.”q从被分析的终结符号串w开始，如果w是文法的句子，那么记w=n，其中n是最右推导的第n步句型：q构造最右推导的逆过程，在n

6、中找句柄进行归约得到右句型n-1。11第11页，此课件共99页哦例例4.23右句型句柄归约产生式id1 id2*id3E id2*id3E E*id3E E*E E EEid1id2id3E*EE+E E id E id E id E E*E E E+E12第12页，此课件共99页哦分析过程的特点分析过程的特点从输入串的开头依次读入(移进移进)单词。一旦发现可归约串可归约串(在上例中是句柄句柄)就立即归约归约。根据句柄对分析树进行修剪子树，剪去子树的叶子。若最终能归约成文法的开始符号，则分析成功。由于总是将句型的最左边的可归约串最左边的可归约串替换成非终结符号，该归约方法通常得到是最右推导的逆

7、过程最右推导的逆过程。13第13页，此课件共99页哦4.5.3 用栈实现移进归约分析用栈实现移进归约分析q必须解决两个问题确定右句型中将要归约的子串（句柄）如何确定选择哪一个产生式q一般方法用栈保存文法符号输入缓冲区存放待分析的串移进(shift)输入符号入栈，直至栈顶出现句柄归约(reduce)句柄，用产生式左部的非终结符替代栈中的句柄14第14页，此课件共99页哦栈 输 入 动 作$id1+id2*id3$移进$id1 +id2*id3$按E id归约$E +id2*id3$移进$E+id2*id3$移进$E+id2 *id3$按E id归约$E+E *id3$移进$E+E*id3$移进$

8、E+E*id3$按E id归约$E+E*E$按E E*E归约$E+E$按E E+E归约$E$接受 例例4.2415第15页，此课件共99页哦q初始状态格局栈输入$w$q接受状态格局栈输入$S$16第16页，此课件共99页哦动作动作q有四种动作移进：把下一个输入符号移进栈顶归约：在栈中确定句柄，选择正确的非终结符替代句柄接受报错17第17页，此课件共99页哦q句柄总会出现在栈顶，而不会在栈的里面。q考察任意最右推导中连续两步的可能形式：18第18页，此课件共99页哦q假设当前状态格局为：栈输入$yz$q把句柄归约为B，达到状态格局：栈输入$B yz$q移进y入栈中，达到格局：栈输入$By z$q

9、栈顶形成句柄By，归约为A，达到状态格局：栈输入$A z$S Az B y 19第19页，此课件共99页哦q假设当前状态格局为：栈输入$xyz$q把句柄归约为B，达到状态格局：栈输入$B xyz$q移进x,y入栈中，达到格局：栈输入$Bxy z$q栈顶句柄y归约为A，达到状态格局：栈输入$Bx z$S zB x A y20第20页，此课件共99页哦4.5.4 活前缀活前缀(Viable prefix)q出现在移进归约分析器栈中的右句型的前缀集合称为活前缀。q活前缀是右句型的前缀，不含右句柄之后的任何符号。q活前缀后加上终结符可以得到右句型。q只有输入串中已分析过的那部分能归约成活前缀，就没有语

10、法错误。21第21页，此课件共99页哦4.5.5 冲突冲突(Conflicts)q如果形成这样的格局：根据栈中的内容和下一个输入符号不能决定是移进还是归约（移进归约冲突），或不能决定用那一条产生式进行归约（归约归约冲突）。22第22页，此课件共99页哦移进移进 归约冲突归约冲突例例4.25 stmt if expr then stmt|if expr then stmt else stmt|other存在移进归约冲突。一般地，任何二义性文法都不是LR(k)文法。假设当前状态格局为：栈输入 if expr then stmtelse$23第23页，此课件共99页哦归约归约 归约冲突归约冲突例例4

11、.26 关于过程调用和数组引用的下标的文法stmt id(parameter_list)|expr:=exprparameter_list parameter_list,parameter|parameterparameter idexpr id(expr_list)|idexpr_list expr_list,expr|expr24第24页，此课件共99页哦例例4.26 关于过程调用和数组引用的下关于过程调用和数组引用的下标的文法标的文法q考察输入串A(I,J)，对应记号流形式id(id,id)。q假设当前状态格局为：栈输入 id(id,id$qReduce/Reduce Conflict

12、what to do?(it really depends on what is A,an array?or a procedure?25第25页，此课件共99页哦4.6 LR语法分析器语法分析器q本节介绍LR(k)分析技术“L”：left-to-right scanning 自左向右扫描“R”：rightmost derivation in reverse 最右推导的逆“k”：the number of input symbols of lookahead，when(k)is omitted,k is assumed to be 126第26页，此课件共99页哦LR分析器的特点分析器的特点q

13、通用通用q适用面广适用面广q效率高效率高27第27页，此课件共99页哦LR分析器的特点分析器的特点q通用通用一般的移进归约法q适用面广适用面广适合大多数的上下文无关文法q效率高效率高实用28第28页，此课件共99页哦4.6.2 LR(0)项目（项目（Item）q在产生式右部加上，表示分析过程中的状态,指示产生式右部符号已经被识别了多少之前的子串已经出现在栈中之后的子串是下一步将看到的q在文法产生式右部某个位置标有 的产生式，称为文法的一个LR(0)项目。形如 A 的项目称为归约项目；形如 A B 的项目称为待约项目(基本项目)；形如 A a 的项目称为移进项目。29第29页，此课件共99页哦L

14、R(0)项目项目例如，产生式AXYZ对应四个项目：A XYZA XYZA XYZA XYZ注意，产生式A只对应一个项目：A 30第30页，此课件共99页哦LR(0)项目集族项目集族q对文法G，构造一个有限自动机，它能识别G的所有活前缀。在这个基础上，把自动机转变成LR分析表。NFA/DFAq首先构造一个NFA，它能识别G的所有活前缀。qNFA的状态是下面定义的一个“项目”。31第31页，此课件共99页哦增广文法增广文法q对文法GS增加S SS S 是唯一动作为accept的状态。32第32页，此课件共99页哦闭包运算闭包运算closureq项目闭包：设I是文法G的一个LR(0)项目集合，I的项

15、目闭包closure(I)定义如下：I closure(I)若项目A B closure(I)，且 B 是G的产生式，则项目B closure(I)closure(I)仅包含上述两条规则确定的LR(0)项目。33第33页，此课件共99页哦function closure(I)begin j:=I;repeat for each A B in J and each production B of G such that B is not in J do ADD B to J until no more items can be added to J return Jendclosure的计算34

16、第34页，此课件共99页哦E EE E+T|TT T*F|FF (E)|id如果 I 是项目集合E E，那么closure(I)包括下列项目：E EE E+T E TT T*F T FF (E)F id例例 4.26 考虑拓广的表达式文法：考虑拓广的表达式文法：35第35页，此课件共99页哦核心项目和非核心项目核心项目和非核心项目q可以把项目集中的项目分为两类：核心项目(Kernel items)：初始项S S和所有点不在左端的项目非核心项目(Non-kernel items)：点在左端的非初始项目非核心项目可以通过求核心项目集的闭包得到。36第36页，此课件共99页哦转移函数转移函数goto

17、q若I是文法G的一个LR(0)项目集，X是G中的文法符号，定义转移函数 goto(I,X)=closure(J)其中 J=A X|A X I q项目A X 称为项目A X的后继。q如果I是对某个活前缀的有效项目集，那么goto(I,X)是对活前缀X的有效项目集。37第37页，此课件共99页哦例例 4.27q若项目集 I=E E,E E +T，计算 goto(I,+)得到以下项目集：E E+TT T*F T F F (E)F id 38第38页，此课件共99页哦function goto(I,X)begin let J be the set of items A X such that A X

18、is in I;return closure(J)end goto的计算的计算39第39页，此课件共99页哦procedure items(G)begin C:=closureS S repeat for C 的每个项目集 I 和每个文法符号 X 若 goto(I,X)is not empty and not in Cdo add goto(I,X)to C until no more sets of items can be added to CendThe sets-of-Items construction构造构造LR(0)项目集规范族项目集规范族40第40页，此课件共99页哦例例4.2

19、8 设文法设文法G的产生式为的产生式为拓广文法G：E EE E+T|TT T*F|FF (E)|id的LR(0)项目集规范族为：41第41页，此课件共99页哦构造构造LR(0)项目集规范族项目集规范族 I0:E E(核心项目核心项目)E E+T E T(非核心项目，非核心项目，T T F 通过对核心项目求闭包通过对核心项目求闭包T F 而获得而获得)F (E)F id42第42页，此课件共99页哦I0:I1:=goto(I0,E)E EE E E E+T E E+T E TT T F I2:=goto(I0,T)T FE T F (E)T T F F idI3:=goto(I0,F)T F 4

20、3第43页，此课件共99页哦I4:=goto(I0,()F (E)E E+T E TT T FT FF (E)F id I5:=goto(I0,id)F id I6:=goto(I1,+)EE+TT T F T F F(E)F id 44第44页，此课件共99页哦I7:=goto(I2,*)T T*F F(E)F idI8:=goto(I4,E)F(E)E E +T I9:=goto(I1,+)E E+T T T *F I10:T T*F I11:F(E)45第45页，此课件共99页哦文法的文法的LR(0)项目集规范族项目集规范族I0:E E E E+T E T T T*F T F F(E)F

21、 idI1:E E E E +TI2:E T T T *FI3:T F I4:F(E)E E+T E T T T*F T F F(E)F idI5:F id I6:E E+T T T*F T FF(E)F idI7:T T*F F(E)F idI8:F(E)E E +T I9:E E+T T T *F I10:T T*F I11:F(E)46第46页，此课件共99页哦47第47页，此课件共99页哦48第48页，此课件共99页哦49第49页，此课件共99页哦50第50页，此课件共99页哦51第51页，此课件共99页哦52第52页，此课件共99页哦53第53页，此课件共99页哦54第54页，此课件

22、共99页哦4.6.3 LR分析器的模型分析器的模型输入输入LR分析驱动程序分析驱动程序输出输出 栈栈ActionGotosmsm-1s0a1ai an$分析表分析表M动作表动作表转向表转向表55第55页，此课件共99页哦LR语法分析器的行为语法分析器的行为q为描述LR语法分析的行为，引入概念格局(Configuration)，用二元组表示 (s0s1s2sm,aiai+1an$)栈的内容 尚未处理的输入代表右句型X1X2Xmaiai+1an，文法符号Xi是状态si代表的文法符号分析栈存放状态而不是文法符号56第56页，此课件共99页哦LR分析算法的动作分析算法的动作q语法分析器的下一动作由当前

23、输入符号ai和栈顶状态sm查询分析表actionsm,ai 决定移进归约接受出错57第57页，此课件共99页哦移进之前移进之前(s0s1s2sm,aiai+1an$)输入输入LR分析程序分析程序输出输出 Actionsm,ai=“shift s”Gotosmsm-1s0a1aian$栈栈58第58页，此课件共99页哦移进之后移进之后(s0s1s2sms,ai+1an$)LR分析程序分析程序输出输出 Actionsm,ai=“shift s”Gotosm sm-1s0a1aian$s输入输入栈栈59第59页，此课件共99页哦归约之前归约之前LR分析程序分析程序输出输出 栈栈Actionsm,ai

24、=“r A”smsm-rs0a1aian$Gotosm-r,A=s 输入输入60第60页，此课件共99页哦归约归约 从栈中弹出|个符号LR分析程序分析程序输出输出 Actionsm,ai=“r A”sm-rs0a1aian$Gotosm-r,A=s|输入输入栈栈61第61页，此课件共99页哦归约归约 从栈中弹出|个符号，再进栈LR分析程序分析程序输出输出 Actionsm,ai=“r A”ssm-rs0a1aian$Gotosm-r,A=s|输入输入栈栈62第62页，此课件共99页哦接受接受LR分析程序分析程序输出输出 Actions,$=“accept”ss0a1ai an$Goto输入输入

25、栈栈63第63页，此课件共99页哦报错报错LR分析程序分析程序输出输出 Actions,a未定义a1aian$Gotosmsm-rs0输入输入栈栈64第64页，此课件共99页哦初始格局初始格局LR分析程序分析程序输出输出 Actions,aGotos0a1ai an$输入输入栈栈65第65页，此课件共99页哦算法算法4.7 LR分析算法分析算法输入：一个输入串w和文法G的一张LR分析表M。输出：若wL(G)，输出w的一个自底向上的分析；否则，报错。方法：初始状态s0 分别放在栈顶，w$放在输入缓冲区；语法分析器执行下面的程序，直至遇见接受或出错动作。66第66页，此课件共99页哦置ip指向w$

26、的第一个符号；a1ai an$ip67第67页，此课件共99页哦置ip指向w$的第一个符号；repeat forever beginend 68第68页，此课件共99页哦置ip指向w$的第一个符号；repeat forever begin令s是栈顶状态，a是ip所指向的符号end ss0a1a an$iptop69第69页，此课件共99页哦置ip指向w$的第一个符号；repeat forever begin令s是栈顶状态，a是ip所指向的符号if actions,a=“shift s”then begin将a和s先后压入栈内；让ip指向下一个输入符号；endend 70第70页，此课件共99页

27、哦置ip指向w$的第一个符号；repeat forever begin令s是栈顶状态，a是ip所指向的符号if actions,a=“shift s”then begin将a和s先后压入栈内；让ip指向下一个输入符号；endelse if actions,a=“reduce A”then begin从栈顶弹出|个符号；令s是当前栈顶状态；把A和gotos,A先后入栈；输出产生式A endend 71第71页，此课件共99页哦置ip指向w$的第一个符号；repeat forever begin令s是栈顶状态，a是ip所指向的符号if actions,a=“shift s”then begin将a

28、和s先后压入栈内；让ip指向下一个输入符号；endelse if actions,a=“reduce A”then begin从栈顶弹出|个符号；令s是当前栈顶状态；把A和gotos,A先后入栈；输出产生式A endelse if actions,a=“acc”then returnend 72第72页，此课件共99页哦置ip指向w$的第一个符号；repeat forever begin令s是栈顶状态，a是ip所指向的符号if actions,a=“shift s”then begin将a和s先后压入栈内；让ip指向下一个输入符号；endelse if actions,a=“reduce A”

29、then begin从栈顶弹出|个符号；令s是当前栈顶状态；把A和gotos,A先后入栈；输出产生式A endelse if actions,a=“acc”then return else error()end 73第73页，此课件共99页哦例例 4.33 算法表达式文法算法表达式文法(1)E E+T (4)T E(2)E T (5)F (E)(3)T T*F (6)F id 各个动作的编码的含义：1.si表示把当前输入符号和状态i进栈2.rj表示用第j条产生式归约3.acc表示接受4.空白项表示出错74第74页，此课件共99页哦图图4.37 表达式文法的表达式文法的LR分析表分析表75第75

30、页，此课件共99页哦图图4.38 关于关于id*id的的LR分析过程分析过程76第76页，此课件共99页哦补充补充:关于关于id(*id的的LR分析过程分析过程77第77页，此课件共99页哦思考思考1：考虑算法：考虑算法4.30的效率的效率q时间复杂度O(|w|)无回溯78第78页，此课件共99页哦思考思考2：你能否：你能否编程实现编程实现4.30？q利用已学习的知识数据结构高级语言程序设计算法设计q广泛应用的编译器开发工具已实现了这一算法YaccBisonq原理、实践79第79页，此课件共99页哦思考思考3：如何构造动作表和分析表？如何构造动作表和分析表？输入输入LR分析程序分析程序输出输出

31、 sm sm-1 s0a1aian$栈栈ActionGoto80第80页，此课件共99页哦q后续的内容围绕动作表和分析表的构造原理展开q事实上，算法4.30是通用的，不同的动作表和分析表的构造决定了不同的LR分析方法SLR(1)LR(1)LALR(1)81第81页，此课件共99页哦4.6.4 构造构造SLR分析表分析表q简单LR分析（Simple LR）82第82页，此课件共99页哦构造构造SLR分析表分析表q状态i从Ii构造，它的action函数确定如下：如果Aa在Ii中，并且goto(Ii,a)=Ij，那么置actioni,a为sj。如果A在Ii中，那么对FOLLOW(A)中的所有a，置a

32、ctioni,a为rj，j是产生式A的编号。如果SS在Ii中，那么置actioni,$为接受accept。如果出现动作冲突，那么该文法就不是SLR(1)的。83第83页，此课件共99页哦从从DFA构造构造SLR分析表分析表q使用下面规则构造状态i的goto函数：对所有的非终结符A，如果goto(Ii,A)=Ij,那么gotoi,A=j。q不能由上面两步定义的条目都置为error。q分析器的初始状态是包含SS的项目集对应的状态。84第84页，此课件共99页哦算法算法4.32 SLR分析算法分析算法输入：一个拓广文法G输出：对于G 的分析表的action子表和goto子表方法：1.构造G 的LR(

33、0)项目集规范族。2.对于状态Ii的分析动作如下：(a)若A.aB Ii且 goto(Ii,a)=Ij actioni,a=“shift j”(b)若A.Ii,对于所有a FOLLOW(A)actioni,a=“reduce A”,A S (c)若SS.Ii,actioni,$=“accept”3.若goto(Ii,A)=Ij,AVN,则 gotoi,A=j4.分析表其余位置为error85第85页，此课件共99页哦FOLLOW(E)=$,+,)文法文法4.34的的SLR分析表分析表86第86页，此课件共99页哦例例4.33qI2:E TT T*Fq因为FOLLOW(E)=$,+,),所以ac

34、tion2,$=action2,+=action2,)=r2action2,*=s787第87页，此课件共99页哦例例4.34q每个SLR(1)文法都不是二义的，但是，有许多非二义的文法不是SLR(1)。q例如，下面的产生式文法S L=RS RL *RL idR L88第88页，此课件共99页哦拓广文法拓广文法G 的的LR(0)项目集规范族为：项目集规范族为：I0:S SS L=RS RL *RL idR LI1:SS I2:SL =RRL I3:SR I4:L*RR L L *RL idI5:Lid I6:SL=RR LL *RL idI7:L*R I8:RL I9:SL=R 89第89页，

35、此课件共99页哦idS SS L=RS RL *RL idR LL id S L=RR L S S I0I1I2I3S R I4L *RR LL idL *RI5SL*idRS L=RR LL *RL idI6=RS L=R R L LLI7idI3*L *R RI8I9识别产生式文法识别产生式文法(4-20)活前缀的活前缀的DFA90第90页，此课件共99页哦I1I0I3I2I6I9I8I7I5I4startSRLid*=ididLLR*R识别产生式文法识别产生式文法(4-20)活前缀的活前缀的DFA91第91页，此课件共99页哦SLR(1)文法的描述能力有限文法的描述能力有限qI2:SL

36、=RRL q第一个项目使得action2,=为shift q第二个项目使得action2,=为reduce，FOLLOW(R)=,$=是R的一个后继符S L=R *R=R qI2存在移进归约冲突！q但是，实际不存在以R=开始的右句型92第92页，此课件共99页哦4.6.5 可行前缀（可行前缀（viable prefix）q可行前缀是一个右句型的前缀，且该前缀没有越过该句型的句柄的右端。q可以出现在移入-归约栈中的右句型的前缀93第93页，此课件共99页哦有效项目有效项目q有效项目：有效项目：如果存在规范推导 S*Aw 12w，则说项目A1 2对活前缀 1 是有效的。q对任何活前缀1，从项目A1

37、2有效这个事实可以知道如果2，应该移进如果2=，应该用产生式A1归约94第94页，此课件共99页哦有效项目有效项目q若项目A1 B2 对活前缀1 是有效的，且 B 是产生式，则项目 B 对活前缀1 也是有效的。据假设，存在一个规范推导S*Aw 1B2w设2w*xw，则对任何B 有规范推导S*Aw 1 B 2w 1 Bxw 1 xw所以 B .对活前缀 1 也是有效的。95第95页，此课件共99页哦有效项目有效项目q一个项目可能对好几个活前缀都是有效的。E E+T对 和(这两个活前缀都有效E E E+T(，1都为空)E E (E)(E+T)(=“(”，1为空)qDFA读入 和(后到达不同的状态，

38、那么项目E E+T就出现在不同的项目集中96第96页，此课件共99页哦有效项目有效项目q一个活前缀可能有多个有效项目。存在动作冲突q活前缀的有效项目集就是从这个DFA的初态出发，沿着标记为的路径到达的那个项目集（状态）。97第97页，此课件共99页哦例例4.35qE+T*是活前缀，读完它后，DFA处于状态I7 I7:TT*F,F(E),F idq对应了所有可能的三种最右推导形式:E E E+T E+T*FE E E+T E+T*F E+T*(E)E E E+T E+T*F E+T*id98第98页，此课件共99页哦习题习题P153 练习q4.6.2q4.6.3q4.6.5q4.6.699第99页，此课件共99页哦