《第四章语法分析优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第四章语法分析优秀PPT.ppt（99页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章语法分析第四章语法分析1第一页，本课件共有99页4.5 自底向上分析自底向上分析q移进归约分析法(Shift-reduce parsing)q一般的移进归约法LR parsingLR(0)SLRLR(1)LALRq自动的语法分析器的生成器（YACC）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第三页，本课件共有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第四页，本课件共有99页短语和句柄短语和句柄q设有上下文无关文法G=(VT,VN,S,P)，串是文法G的句型，若有A+，且串A也是文法G的句型，则称是句型中关于非终结符号A的短语短语。q若A ，则称为直接短语直接短语。q最左直接短语称为句柄句柄(handle)。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第六页，本课件共有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第七页，本课件共有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第八页，本课件共有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第九页，本课件共有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第十页，本课件共有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第十一页，本课件共有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第十二页，本课件共有99页分析过程的特点分析过程的特点从输入串的开头依次读入(移进移进)单词。一旦发现可归约串可归约串(在上例中是句柄句柄)就立即归约归约。根据句柄对分析树进行修剪子树，剪去子树的叶子。若最终能归约成文法的开始符号，则分析成功。由于总是将句型的最左边的可归约串最左边的可归约串替换成非终结符号，该归约方法通常得到是最右推导的逆过
7、程最右推导的逆过程。13第十三页，本课件共有99页4.5.3 用栈实现移进归约分析用栈实现移进归约分析q必须解决两个问题确定右句型中将要归约的子串（句柄）如何确定选择哪一个产生式q一般方法用栈保存文法符号输入缓冲区存放待分析的串移进(shift)输入符号入栈，直至栈顶出现句柄归约(reduce)句柄，用产生式左部的非终结符替代栈中的句柄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$移进$E
8、+E*id3$按E id归约$E+E*E$按E E*E归约$E+E$按E E+E归约$E$接受 例例4.2415第十五页，本课件共有99页q初始状态格局栈输入$w$q接受状态格局栈输入$S$16第十六页，本课件共有99页动作动作q有四种动作移进：把下一个输入符号移进栈顶归约：在栈中确定句柄，选择正确的非终结符替代句柄接受报错17第十七页，本课件共有99页q句柄总会出现在栈顶，而不会在栈的里面。q考察任意最右推导中连续两步的可能形式：18第十八页，本课件共有99页q假设当前状态格局为：栈输入$yz$q把句柄归约为B，达到状态格局：栈输入$B yz$q移进y入栈中，达到格局：栈输入$By z$q栈
9、顶形成句柄By，归约为A，达到状态格局：栈输入$A z$S Az B y 19第十九页，本课件共有99页q假设当前状态格局为：栈输入$xyz$q把句柄归约为B，达到状态格局：栈输入$B xyz$q移进x,y入栈中，达到格局：栈输入$Bxy z$q栈顶句柄y归约为A，达到状态格局：栈输入$Bx z$S zB x A y20第二十页，本课件共有99页4.5.4 活前缀活前缀(Viable prefix)q出现在移进归约分析器栈中的右句型的前缀集合称为活前缀。q活前缀是右句型的前缀，不含右句柄之后的任何符号。q活前缀后加上终结符可以得到右句型。q只有输入串中已分析过的那部分能归约成活前缀，就没有语法
10、错误。21第二十一页，本课件共有99页4.5.5 冲突冲突(Conflicts)q如果形成这样的格局：根据栈中的内容和下一个输入符号不能决定是移进还是归约（移进归约冲突），或不能决定用那一条产生式进行归约（归约归约冲突）。22第二十二页，本课件共有99页移进移进 归约冲突归约冲突例例4.25 stmt if expr then stmt|if expr then stmt else stmt|other存在移进归约冲突。一般地，任何二义性文法都不是LR(k)文法。假设当前状态格局为：栈输入 if expr then stmtelse$23第二十三页，本课件共有99页归约归约 归约冲突归约冲突例
11、例4.26 关于过程调用和数组引用的下标的文法stmt id(parameter_list)|expr:=exprparameter_list parameter_list,parameter|parameterparameter idexpr id(expr_list)|idexpr_list expr_list,expr|expr24第二十四页，本课件共有99页例例4.26 关于过程调用和数组引用的下标关于过程调用和数组引用的下标的文法的文法q考察输入串A(I,J)，对应记号流形式id(id,id)。q假设当前状态格局为：栈输入 id(id,id$qReduce/Reduce Confli
12、ct what to do?(it really depends on what is A,an array?or a procedure?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第二十六页，本课件共有99页LR分析器的特点分析
13、器的特点q通用通用q适用面广适用面广q效率高效率高27第二十七页，本课件共有99页LR分析器的特点分析器的特点q通用通用一般的移进归约法q适用面广适用面广适合大多数的上下文无关文法q效率高效率高实用28第二十八页，本课件共有99页4.6.2 LR(0)项目（项目（Item）q在产生式右部加上，表示分析过程中的状态,指示产生式右部符号已经被识别了多少之前的子串已经出现在栈中之后的子串是下一步将看到的q在文法产生式右部某个位置标有 的产生式，称为文法的一个LR(0)项目。形如 A 的项目称为归约项目；形如 A B 的项目称为待约项目(基本项目)；形如 A a 的项目称为移进项目。29第二十九页，本
14、课件共有99页LR(0)项目项目例如，产生式AXYZ对应四个项目：A XYZA XYZA XYZA XYZ注意，产生式A只对应一个项目：A 30第三十页，本课件共有99页LR(0)项目集族项目集族q对文法G，构造一个有限自动机，它能识别G的所有活前缀。在这个基础上，把自动机转变成LR分析表。NFA/DFAq首先构造一个NFA，它能识别G的所有活前缀。qNFA的状态是下面定义的一个“项目”。31第三十一页，本课件共有99页增广文法增广文法q对文法GS增加S SS S 是唯一动作为accept的状态。32第三十二页，本课件共有99页闭包运算闭包运算closureq项目闭包：设I是文法G的一个LR(
15、0)项目集合，I的项目闭包closure(I)定义如下：I closure(I)若项目A B closure(I)，且 B 是G的产生式，则项目B closure(I)closure(I)仅包含上述两条规则确定的LR(0)项目。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 Jendc
16、losure的计算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第三十五页，本课件共有99页核心项目和非核心项目核心项目和非核心项目q可以把项目集中的项目分为两类：核心项目(Kernel items)：初始项S S和所有点不在左端的项目非核心项目(Non-kernel items)：点在左端的非初始项目非核心项目可以通过求核心项目集的闭包得到。36第三十六页，本课件共有9
17、9页转移函数转移函数gotoq若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第三十七页，本课件共有99页例例 4.27q若项目集 I=E E,E E +T，计算 goto(I,+)得到以下项目集：E E+TT T*F T F F (E)F id 38第三十八页，本课件共有99页function goto(I,X)begin let J be the set of items A
18、X such that A X is in I;return closure(J)end goto的计算的计算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第
19、四十页，本课件共有99页例例4.28 设文法设文法G的产生式为的产生式为拓广文法G：E EE E+T|TT T*F|FF (E)|id的LR(0)项目集规范族为：41第四十一页，本课件共有99页构造构造LR(0)项目集规范族项目集规范族 I0:E E(核心项目核心项目)E E+T E T(非核心项目，非核心项目，T T F 通过对核心项目求闭包通过对核心项目求闭包T F 而获得而获得)F (E)F id42第四十二页，本课件共有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 id
20、I3:=goto(I0,F)T F 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第四十四页，本课件共有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第四十五页，本课件共有99页文法的文法的LR(0)项目集规范族项目集规范族I0:E E E E
21、+T E T T T*F T F F(E)F 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第四十六页，本课件共有99页47第四十七页，本课件共有99页48第四十八页，本课件共有99页49第四十九页，本课件共有99页50第五十页，本课件共有99页51第五十一页，本课件共有99页52第五十二页，本课件共有
22、99页53第五十三页，本课件共有99页54第五十四页，本课件共有99页4.6.3 LR分析器的模型分析器的模型输入输入LR分析驱动程序分析驱动程序输出输出 栈栈ActionGotosmsm-1s0a1ai an$分析表分析表M动作表动作表转向表转向表55第五十五页，本课件共有99页LR语法分析器的行为语法分析器的行为q为描述LR语法分析的行为，引入概念格局(Configuration)，用二元组表示 (s0s1s2sm,aiai+1an$)栈的内容 尚未处理的输入代表右句型X1X2Xmaiai+1an，文法符号Xi是状态si代表的文法符号分析栈存放状态而不是文法符号56第五十六页，本课件共有9
23、9页LR分析算法的动作分析算法的动作q语法分析器的下一动作由当前输入符号ai和栈顶状态sm查询分析表actionsm,ai 决定移进归约接受出错57第五十七页，本课件共有99页移进之前移进之前(s0s1s2sm,aiai+1an$)输入输入LR分析程序分析程序输出输出 Actionsm,ai=“shift s”Gotosmsm-1s0a1aian$栈栈58第五十八页，本课件共有99页移进之后移进之后(s0s1s2sms,ai+1an$)LR分析程序分析程序输出输出 Actionsm,ai=“shift s”Gotosm sm-1s0a1aian$s输入输入栈栈59第五十九页，本课件共有99页归
24、约之前归约之前LR分析程序分析程序输出输出 栈栈Actionsm,ai=“r A”smsm-rs0a1aian$Gotosm-r,A=s 输入输入60第六十页，本课件共有99页归约归约 从栈中弹出|个符号LR分析程序分析程序输出输出 Actionsm,ai=“r A”sm-rs0a1aian$Gotosm-r,A=s|输入输入栈栈61第六十一页，本课件共有99页归约归约 从栈中弹出|个符号，再进栈LR分析程序分析程序输出输出 Actionsm,ai=“r A”ssm-rs0a1aian$Gotosm-r,A=s|输入输入栈栈62第六十二页，本课件共有99页接受接受LR分析程序分析程序输出输出
25、Actions,$=“accept”ss0a1aian$Goto输入输入栈栈63第六十三页，本课件共有99页报错报错LR分析程序分析程序输出输出 Actions,a未定义a1aian$Gotosmsm-rs0输入输入栈栈64第六十四页，本课件共有99页初始格局初始格局LR分析程序分析程序输出输出 Actions,aGotos0a1aian$输入输入栈栈65第六十五页，本课件共有99页算法算法4.7 LR分析算法分析算法输入：一个输入串w和文法G的一张LR分析表M。输出：若wL(G)，输出w的一个自底向上的分析；否则，报错。方法：初始状态s0 分别放在栈顶，w$放在输入缓冲区；语法分析器执行下面
26、的程序，直至遇见接受或出错动作。66第六十六页，本课件共有99页置ip指向w$的第一个符号；a1ai an$ip67第六十七页，本课件共有99页置ip指向w$的第一个符号；repeat forever beginend 68第六十八页，本课件共有99页置ip指向w$的第一个符号；repeat forever begin令s是栈顶状态，a是ip所指向的符号end ss0a1a an$iptop69第六十九页，本课件共有99页置ip指向w$的第一个符号；repeat forever begin令s是栈顶状态，a是ip所指向的符号if actions,a=“shift s”then begin将a和
27、s先后压入栈内；让ip指向下一个输入符号；endend 70第七十页，本课件共有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”then begin从栈顶弹出|个符号；令s是当前栈顶状态；把A和gotos,A先后入栈；输出产生式A endend 71第七十一页，本课件共有99页置ip指向w$的第一个符号；repeat forever begin令s是栈顶状态，a
28、是ip所指向的符号if actions,a=“shift s”then begin将a和s先后压入栈内；让ip指向下一个输入符号；endelse if actions,a=“reduce A”then begin从栈顶弹出|个符号；令s是当前栈顶状态；把A和gotos,A先后入栈；输出产生式A endelse if actions,a=“acc”then returnend 72第七十二页，本课件共有99页置ip指向w$的第一个符号；repeat forever begin令s是栈顶状态，a是ip所指向的符号if actions,a=“shift s”then begin将a和s先后压入栈内；
29、让ip指向下一个输入符号；endelse if actions,a=“reduce A”then begin从栈顶弹出|个符号；令s是当前栈顶状态；把A和gotos,A先后入栈；输出产生式A endelse if actions,a=“acc”then return else error()end 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
30、第七十四页，本课件共有99页图图4.37 表达式文法的表达式文法的LR分析表分析表75第七十五页，本课件共有99页图图4.38 关于关于id*id的的LR分析过程分析过程76第七十六页，本课件共有99页补充补充:关于关于id(*id的的LR分析过程分析过程77第七十七页，本课件共有99页思考思考1：考虑算法：考虑算法4.30的效率的效率q时间复杂度O(|w|)无回溯78第七十八页，本课件共有99页思考思考2：你能否：你能否编程实现编程实现4.30？q利用已学习的知识数据结构高级语言程序设计算法设计q广泛应用的编译器开发工具已实现了这一算法YaccBisonq原理、实践79第七十九页，本课件共有
31、99页思考思考3：如何构造动作表和分析表？如何构造动作表和分析表？输入输入LR分析程序分析程序输出输出 sm sm-1 s0a1aian$栈栈ActionGoto80第八十页，本课件共有99页q后续的内容围绕动作表和分析表的构造原理展开q事实上，算法4.30是通用的，不同的动作表和分析表的构造决定了不同的LR分析方法SLR(1)LR(1)LALR(1)81第八十一页，本课件共有99页4.6.4 构造构造SLR分析表分析表q简单LR分析（Simple LR）82第八十二页，本课件共有99页构造构造SLR分析表分析表q状态i从Ii构造，它的action函数确定如下：如果Aa在Ii中，并且goto(
32、Ii,a)=Ij，那么置actioni,a为sj。如果A在Ii中，那么对FOLLOW(A)中的所有a，置actioni,a为rj，j是产生式A的编号。如果SS在Ii中，那么置actioni,$为接受accept。如果出现动作冲突，那么该文法就不是SLR(1)的。83第八十三页，本课件共有99页从从DFA构造构造SLR分析表分析表q使用下面规则构造状态i的goto函数：对所有的非终结符A，如果goto(Ii,A)=Ij,那么gotoi,A=j。q不能由上面两步定义的条目都置为error。q分析器的初始状态是包含SS的项目集对应的状态。84第八十四页，本课件共有99页算法算法4.32 SLR分析算
33、法分析算法输入：一个拓广文法G输出：对于G 的分析表的action子表和goto子表方法：1.构造G 的LR(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第八十五页，本课件共有99页FOLLOW(E)=$,+,)文法文法4.34的的SLR分析表分析表
34、86第八十六页，本课件共有99页例例4.33qI2:E TT T*Fq因为FOLLOW(E)=$,+,),所以action2,$=action2,+=action2,)=r2action2,*=s787第八十七页，本课件共有99页例例4.34q每个SLR(1)文法都不是二义的，但是，有许多非二义的文法不是SLR(1)。q例如，下面的产生式文法S L=RS RL *RL idR L88第八十八页，本课件共有99页拓广文法拓广文法G 的的LR(0)项目集规范族为：项目集规范族为：I0:S SS L=RS RL *RL idR LI1:SS I2:SL =RRL I3:SR I4:L*RR L L
35、*RL idI5:Lid I6:SL=RR LL *RL idI7:L*R I8:RL I9:SL=R 89第八十九页，本课件共有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第九十页，本课件共有99页I1I0I3I2I6I9I8I7I5I4startSRLid*=ididLLR*R识别产生式文法识别产生式文法(4-
36、20)活前缀的活前缀的DFA91第九十一页，本课件共有99页SLR(1)文法的描述能力有限文法的描述能力有限qI2:SL =RRL q第一个项目使得action2,=为shift q第二个项目使得action2,=为reduce，FOLLOW(R)=,$=是R的一个后继符S L=R *R=R qI2存在移进归约冲突！q但是，实际不存在以R=开始的右句型92第九十二页，本课件共有99页4.6.5 可行前缀（可行前缀（viable prefix）q可行前缀是一个右句型的前缀，且该前缀没有越过该句型的句柄的右端。q可以出现在移入-归约栈中的右句型的前缀93第九十三页，本课件共有99页有效项目有效项目
37、q有效项目：有效项目：如果存在规范推导 S*Aw 12w，则说项目A1 2对活前缀 1 是有效的。q对任何活前缀1，从项目A12有效这个事实可以知道如果2，应该移进如果2=，应该用产生式A1归约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第九十五页，本课件共有99页有效项目有效项目q一个项目可能对好几个活前缀都是有效的。E E+T对
38、和(这两个活前缀都有效E E E+T(，1都为空)E E (E)(E+T)(=“(”，1为空)qDFA读入 和(后到达不同的状态，那么项目E E+T就出现在不同的项目集中96第九十六页，本课件共有99页有效项目有效项目q一个活前缀可能有多个有效项目。存在动作冲突q活前缀的有效项目集就是从这个DFA的初态出发，沿着标记为的路径到达的那个项目集（状态）。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第九十八页，本课件共有99页习题习题P153 练习q4.6.2q4.6.3q4.6.5q4.6.699第九十九页，本课件共有99页