《第四章语法分析优秀课件.ppt》由会员分享，可在线阅读，更多相关《第四章语法分析优秀课件.ppt（99页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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页句柄句柄(handle
2、s)q句柄是最左直接短语。q右句型的句柄是产生式A 和中的子串，且用A 代替得到的仍是右句型 qi.e.A is a handle of w at the location immediately after the end of,if:q句柄的右边仅含终结符。SAw4第4页，本讲稿共99页短语和句柄短语和句柄q设有上下文无关文法G=(VT,VN,S,P)，串是文法G的句型，若有A+，且串A也是文法G的句型，则称是句型中关于非终结符号A的短语短语。q若A ，则称为直接短语直接短语。q最左直接短语称为句柄句柄(handle)。5第5页，本讲稿共99页ExampleS aABe aAde aAbc
3、de 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 abbcdeIt
4、 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*id3中，句柄不唯一。
5、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页分析过程的特点分析过程的特点从输入串的开头依次读入(移进移进)单词。一旦发现可归约串可归约串(在上例中是句柄句柄)就立即归约归约。根据句柄对分析树进行修剪子树，剪去子树的叶子。若最终能归约成文法的开始符号，则分析成功。由于总是将句型的最左边的可归约串最左边的可归约串替换成非终结符号，该归约方法通常得到是最右推导的逆过程最右推导的逆过程。13第
7、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$移进$E+E*id3$按E id归约$
8、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栈顶形成句柄By，归约为A，达到状态格局
9、：栈输入$A z$SAz B y19第19页，本讲稿共99页q假设当前状态格局为：栈输入$xyz$q把句柄归约为B，达到状态格局：栈输入$B xyz$q移进x,y入栈中，达到格局：栈输入$Bxy z$q栈顶句柄y归约为A，达到状态格局：栈输入$Bx z$SzB x Ay20第20页，本讲稿共99页4.5.4 活前缀活前缀(Viable prefix)q出现在移进归约分析器栈中的右句型的前缀集合称为活前缀。q活前缀是右句型的前缀，不含右句柄之后的任何符号。q活前缀后加上终结符可以得到右句型。q只有输入串中已分析过的那部分能归约成活前缀，就没有语法错误。21第21页，本讲稿共99页4.5.5 冲突
10、冲突(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.26 关于过程调用和数组引用的下标的文法stmt id(pa
11、rameter_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 what to do?(it really depends on
12、 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通用通用q适用面广适用面广q效率高效率高27第27页，本讲稿共99页
13、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页LR(0)项目项目例如，产生式AXYZ对应四个项目：A XYZA XYZA
14、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的项目闭包closure(I)定义如下：I closure(I)若项目A B clo
15、sure(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第34页，本讲稿共99页E EE E+T|TT T*F|FF (E)|id如果 I
16、 是项目集合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页转移函数转移函数gotoq若I是文法G的一个LR(0)项目集，X是G中的文法符号，定义转移函数 goto(I,X
17、)=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 is in I;return closure(J)end goto的计算的计算39第39页，
18、本讲稿共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.28 设文法设文法G的产生式为的产生式为拓广文法G：E EE E+T|TT T*F|FF (E)|
19、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 43第43页，本讲稿共99页I4:=goto(I0,()F (E)E E+T E TT T FT FF
20、 (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 idI1:E E E E +TI2:E T T T *FI3:T F I4:F(E)E E+T E T
21、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页，本讲稿共99页4.6.3 LR分析器的模型分析器的模型输入LR分析驱动程序输出 栈ActionGotosmsm-1s0a1aia
22、n$分析表M动作表动作表 转向表转向表55第55页，本讲稿共99页LR语法分析器的行为语法分析器的行为q为描述LR语法分析的行为，引入概念格局(Configuration)，用二元组表示 (s0s1s2sm,aiai+1an$)栈的内容 尚未处理的输入代表右句型X1X2Xmaiai+1an，文法符号Xi是状态si代表的文法符号分析栈存放状态而不是文法符号56第56页，本讲稿共99页LR分析算法的动作分析算法的动作q语法分析器的下一动作由当前输入符号ai和栈顶状态sm查询分析表actionsm,ai 决定移进归约接受出错57第57页，本讲稿共99页移进之前移进之前(s0s1s2sm,aiai+1
23、an$)输入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=“r A”smsm-rs0a1aian$Gotosm-r,A=s 输入60第60页，本讲稿共99页归约归约 从栈中弹出|个符号LR分析程序输出 Actionsm,ai=“r A”sm-rs0a1aian$Got
24、osm-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输入栈63第63页，本讲稿共99页报错报错LR分析程序输出 Actions,a未定义a1ai an$Gotosmsm-rs0输入栈64第64页，本讲稿共99页初始格局初始格局LR分析程序输出 Actions,aGotos0a1ai an$输入栈65第65页，本讲稿共99页算法算
25、法4.7 LR分析算法分析算法输入：一个输入串w和文法G的一张LR分析表M。输出：若wL(G)，输出w的一个自底向上的分析；否则，报错。方法：初始状态s0 分别放在栈顶，w$放在输入缓冲区；语法分析器执行下面的程序，直至遇见接受或出错动作。66第66页，本讲稿共99页置ip指向w$的第一个符号；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
26、页，本讲稿共99页置ip指向w$的第一个符号；repeat forever begin令s是栈顶状态，a是ip所指向的符号if actions,a=“shift s”then begin将a和s先后压入栈内；让ip指向下一个输入符号；endend 70第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是
27、当前栈顶状态；把A和gotos,A先后入栈；输出产生式A endend 71第71页，本讲稿共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 endelse if actions,a=“acc”then returnend 72第72页，本讲稿共99页置ip指
28、向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 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 (
29、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页，本讲稿共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：你能否：你能否编程实现编程实现
30、4.30？q利用已学习的知识数据结构高级语言程序设计算法设计q广泛应用的编译器开发工具已实现了这一算法YaccBisonq原理、实践79第79页，本讲稿共99页思考思考3：如何构造动作表和分析表？如何构造动作表和分析表？输入LR分析程序输出 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
31、页，本讲稿共99页构造构造SLR分析表分析表q状态i从Ii构造，它的action函数确定如下：如果Aa在Ii中，并且goto(Ii,a)=Ij，那么置actioni,a为sj。如果A在Ii中，那么对FOLLOW(A)中的所有a，置actioni,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不能由上面两步定义的条目都置为
32、error。q分析器的初始状态是包含SS的项目集对应的状态。84第84页，本讲稿共99页算法算法4.32 SLR分析算法分析算法输入：一个拓广文法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.分析表其
33、余位置为error85第85页，本讲稿共99页FOLLOW(E)=$,+,)文法文法4.34的的SLR分析表分析表86第86页，本讲稿共99页例例4.33qI2:E TT T*Fq因为FOLLOW(E)=$,+,),所以action2,$=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
34、=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页，本讲稿共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页I1I0I3I2I6
35、I9I8I7I5I4startSRLid*=ididLLR*R识别产生式文法识别产生式文法(4-20)活前缀的活前缀的DFA91第91页，本讲稿共99页SLR(1)文法的描述能力有限文法的描述能力有限qI2:SL =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可行前缀是一个右句型的前缀，且该前缀没有越过该句型的句柄的右端。
36、q可以出现在移入-归约栈中的右句型的前缀93第93页，本讲稿共99页有效项目有效项目q有效项目：有效项目：如果存在规范推导 S*Aw 12w，则说项目A1 2对活前缀 1 是有效的。q对任何活前缀1，从项目A12有效这个事实可以知道如果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页，本讲稿共
37、99页有效项目有效项目q一个项目可能对好几个活前缀都是有效的。E E+T对 和(这两个活前缀都有效E E E+T(，1都为空)E E (E)(E+T)(=“(”，1为空)qDFA读入 和(后到达不同的状态，那么项目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页