《自顶向下语法.pptx》由会员分享,可在线阅读,更多相关《自顶向下语法.pptx(37页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、1.1.1.1.自底向上分析方法的概述自底向上分析方法的概述自底向上分析方法的概述自底向上分析方法的概述-思想思想-自下而上的语法分析过程是自下而上的语法分析过程是最右推导最右推导的逆过程(的逆过程(最左归约最左归约);即从输);即从输入串开始,朝着文法开始符号进行归约,直至到达文法开始符号为入串开始,朝着文法开始符号进行归约,直至到达文法开始符号为止的过程。止的过程。-核心核心-寻找句型中的寻找句型中的“句柄句柄”进行归约进行归约,用不同的方法寻找句柄,就可获得用不同的方法寻找句柄,就可获得不同的分析方法不同的分析方法第1页/共37页一、规范归约一、规范归约-归约归约 G=(VG=(VT T
2、,V,VN N,S,P),(V,S,P),(VT TVVN N)*,AP,)*,AP,Aw Aw ww 。归约的过程是归约的过程是:已知已知ww和产生式和产生式AA,用产生式,用产生式AA左左部部A A替换替换ww中的中的,得到符号串,得到符号串AwAw。规范推导规范推导(最右推导最右推导)右句型右句型(最右推导可得的句型,最右推导可得的句型,规范句型规范句型)。第2页/共37页-规范归约规范归约规范归约是最右推导的规范归约是最右推导的逆过程。逆过程。如果文法如果文法G G是无二义的,那么,规范推导是无二义的,那么,规范推导(最最右推导右推导)的逆过程必是规范归约的逆过程必是规范归约(最左归约
3、最左归约)。规范句型的特点:规范句型的特点:句柄后不会出现非终结符号。句柄后不会出现非终结符号。第3页/共37页例例 GS,GS,其产生式如下:其产生式如下:SSa aA Ac cB Be e A Ab b AAAAb b BBd d 对输入串对输入串abbcde#abbcde#进行分析进行分析 a ab bb bc cd de eA Aa ab bbcdebcdeA Aa aA Ab bcdecdeB BS Sa aA Ac cd de eaAcaAcB Be e最右推导最右推导S Sa ab bbcdebcdea aA Ab bcdecdea aA Ac cd de eaAcaAcB Be
4、 eb bAbAbd daAcaAcB Be e句型句型句柄句柄句柄后不会出现非终结符号。句柄后不会出现非终结符号。第4页/共37页 S SaAcaAcB Be e a aA Ac cd de e a aA Ab bcdecde a ab bbcdebcde输入串输入串 abbcdeabbcde a aA Abcdebcde a aA Acdecde a aA ACB Be e S Sa ab bb bc cd de eA ASaAcBeSaAcBeA ABdBdB BS SAAbAAbAbAb最右推导最右推导S SaAcaAcB Be ea aA Ac cd de ea aA Ab bcde
5、cdea ab bbcdebcdeaAcBeaAcBed dAbAbb b句型句型句柄句柄 归约用规则归约用规则AbAbAAbAAbBdBdSaAcBeSaAcBe例例 GS,GS,其产生式如下:其产生式如下:SSa aA Ac cB Be e A Ab b AAAAb b BBd d 对输入串对输入串abbcde#abbcde#进行分析进行分析 第5页/共37页二、自底向上分析方法二、自底向上分析方法-从一个给定的输入符号串本身出发从一个给定的输入符号串本身出发,试图逐步试图逐步归约为文法的开始符号。归约为文法的开始符号。-从树叶从树叶(底底)开始向上构造直到树根开始向上构造直到树根(顶顶)
6、。-从输入符号串出发从输入符号串出发,每次从被归约的句型中,每次从被归约的句型中找到找到最左边最左边的某个产生式的右部的某个产生式的右部,用其左部,用其左部替换之,得到新的句型替换之,得到新的句型 ,直至归约到文法的,直至归约到文法的开始符号。开始符号。-关键技术:关键技术:在自底向上分析中,如何寻找或确定在自底向上分析中,如何寻找或确定一个句型的句柄一个句型的句柄,是构造一个自左向右扫描、,是构造一个自左向右扫描、自底向上分析方法必须要解决的一个关键问自底向上分析方法必须要解决的一个关键问题。题。第6页/共37页-自底向上分析方法自底向上分析方法移进移进归约归约 “移进一归约移进一归约”分析
7、器使用一个栈和一个分析器使用一个栈和一个存放输入符号串存放输入符号串w w的缓冲器。的缓冲器。-分析器的初始状态为分析器的初始状态为:栈栈 剩余输入符号串剩余输入符号串#w#w#第7页/共37页-工作过程:工作过程:自左至右把串自左至右把串w w 的符号一一移进栈里,边移的符号一一移进栈里,边移进边归约。一旦栈顶形成句柄时,就进行归约。进边归约。一旦栈顶形成句柄时,就进行归约。这种归约可能持续多次,直至栈顶不再呈现句柄这种归约可能持续多次,直至栈顶不再呈现句柄为止。然后,继续向栈里移进符号,重复这个过为止。然后,继续向栈里移进符号,重复这个过程,直至程,直至分析器的终止状态为分析器的终止状态为
8、:栈栈剩余输入符号串剩余输入符号串#S#S#第8页/共37页GS:SGS:Sa aA Ac cB Be e A Ab b A Ab b B Bd d1#a23#ab4#aA5#aAb6#aA78#aAc#aAcd9#aAcB10#S11#aAcBeabbcdeaAbcdeaAcdeaAcBeabbcde#bbcde#bcde#bcde#cde#cde#de#e#e#移进移进移进移进归约归约A Ab b移进移进归约归约A AAbAb 移进移进移进移进归约归约B Bd d移进移进归约归约S SaAcBe aAcBe 接受接受栈中符号栈中符号串加上未串加上未扫描的输扫描的输入串即是入串即是一个(右)
9、一个(右)句型句型S第9页/共37页工作模型:工作模型:堆栈的初始状态与终止状态;堆栈的初始状态与终止状态;移进移进 归约归约接受接受出错出错,一共四种动作,一共四种动作 (暂不理会什么是可归约串)(暂不理会什么是可归约串)直观理解:直观理解:栈中符号串加上未扫描的输入串即是栈中符号串加上未扫描的输入串即是 一个(右)句型;一个(右)句型;可归约串:可归约串:最左素短语(算符优先分析法)最左素短语(算符优先分析法)句柄(句柄(LRLR分析法)分析法)模型要点:模型要点:可归约串总是在栈顶出现,绝不会出可归约串总是在栈顶出现,绝不会出 现在栈内部现在栈内部(一旦形成可归约串则必须一旦形成可归约串
10、则必须 立即归约立即归约)实现目标:实现目标:自左向右扫描一次输入串且在每一时自左向右扫描一次输入串且在每一时 刻仅需要看到一个单词。刻仅需要看到一个单词。第10页/共37页二二二二.算符优先分析法算符优先分析法算符优先分析法算符优先分析法概述概述 一、一、算符文法的定义算符文法的定义 二、二、算符优先分析法的基本思想算符优先分析法的基本思想第11页/共37页一、简单算符优先分析方法一、简单算符优先分析方法 按照文法符号按照文法符号(终结符或非终结符终结符或非终结符)的优先关系的优先关系确定句柄的。确定句柄的。1.1.优先关系优先关系 1)1)X X Y Y 表示表示X X和和Y Y的优先关系
11、相等的优先关系相等2)2)X X Y Y 表示表示X X的优先性比的优先性比Y Y的优先性大的优先性大第12页/共37页 1)1)X X Y Y 当且仅当文法中存在产生式当且仅当文法中存在产生式 A AXY.XY.P P+2)2)X X b b 当且仅当文法中存在产生式当且仅当文法中存在产生式A ABD.BD.P P 且且 (B (B X X 或或D Y)D Y)第13页/共37页例例 若文法若文法GS:GS:S SbAbbAb A A(B|a(B|a B BAa)Aa)(1).(1).求求关系关系:S SbAb b bAb b A,A bA,A b A A(B (B (BB B BAa)A
12、Aa)A a,a)a,a)第14页/共37页例例 若文法若文法GS:GS:S SbAbbAb A A(B|a(B|a B BAa)Aa)(2).(2).求求 关系关系:S SbAb bAb 由于由于A (A (,A a,A a 所以所以b b (,b(,b a a A A(B (B 由于由于B B A A,B (B,B a,B (B,B a 所以所以(A,(,(关系关系:S SbAb bAb 由于由于A A ),A ),A B,B,A a 所以所以)b,B b,B b,a b,a bb A AAa)Aa)由于由于A A ),A ),A B,B,A a 所以所以)a,B a,a a+第16页/共
13、37页这三种关系也可以有语法树来得到这三种关系也可以有语法树来得到SbAb(BSbAbaSbAb(BAa)(BAa)SbAb(BAa)a(1).(1).(1).(1).(和和和和B,bB,bB,bB,b和和和和A,AA,AA,AA,A和和和和b,A b,A b,A b,A 和和和和a,a,a,a,a a a a和和和和)将同时归约将同时归约将同时归约将同时归约,所以所以所以所以(B,B,B,B,b A,A b,A a,a)b A,A b,A a,a)b A,A b,A a,a)b A,A b,A a,a)第17页/共37页这三种关系也可以有语法树来得到这三种关系也可以有语法树来得到SbAb(B
14、SbAbaSbAb(BAa)(BAa)SbAb(BAa)a(2).b(2).b(2).b(2).b和和和和(,b(,b(,b(,b和和和和a,(a,(a,(a,(和和和和A,(A,(A,(A,(和和和和a,a,a,a,(和和和和(后面的符号比前面的先后面的符号比前面的先后面的符号比前面的先后面的符号比前面的先 归约归约归约归约,所以所以所以所以b b b b (,(,(,(,b b b b a,(a,(a,(a,(A,(A,(A,(A,(a,(a,(a,(a,(b,ab,ab,ab,a b,b,b,b,a a a a a,Ba,Ba,Ba,B a,)a,)a,)a,)a,)a,)a,)a,)b
15、b第19页/共37页S Sb bA A(B Ba a)#S S b b A A(a a )#第20页/共37页从矩阵表可以看出从矩阵表可以看出:(1).(1).矩阵元素要么只有一种关系,要么为矩阵元素要么只有一种关系,要么为 空,元素为空时表示该文法的任何句空,元素为空时表示该文法的任何句 型中不会出现该符号对的相邻关系,型中不会出现该符号对的相邻关系,在分析中若遇到这种相邻关系出现,在分析中若遇到这种相邻关系出现,则为错,也可以肯定输入符号串不是则为错,也可以肯定输入符号串不是 该文法的句子。该文法的句子。(2).#(2).#的优先级的优先级#(#(符号与符号与#相邻时相邻时)第21页/共3
16、7页简单优先文法的定义简单优先文法的定义简单优先文法的定义简单优先文法的定义若一个文法是简单优先文法必须满足以下条件若一个文法是简单优先文法必须满足以下条件若一个文法是简单优先文法必须满足以下条件若一个文法是简单优先文法必须满足以下条件:(1).(1).(1).(1).在文法符号集在文法符号集在文法符号集在文法符号集V V V V中,任意两个符号之间最多中,任意两个符号之间最多中,任意两个符号之间最多中,任意两个符号之间最多 只有一种优先关系只有一种优先关系只有一种优先关系只有一种优先关系成立。成立。成立。成立。(2).(2).(2).(2).在文法中任意的两个产生式在文法中任意的两个产生式在
17、文法中任意的两个产生式在文法中任意的两个产生式没有相同的右部没有相同的右部没有相同的右部没有相同的右部。第22页/共37页简单优先分析法算法简单优先分析法算法:首先构造相应优先关系矩阵首先构造相应优先关系矩阵(1).(1).将输入符号串将输入符号串a a1 1a a2 2a an n#依次逐个存入符号栈依次逐个存入符号栈S S中,中,直到遇到栈顶符号直到遇到栈顶符号a ai i的优先性的优先性 下一个待输入符号下一个待输入符号 a aj j为止。为止。(2).(2).栈顶当前符号栈顶当前符号a ai i为句柄尾,由此向左在栈中找句为句柄尾,由此向左在栈中找句 柄的头符号柄的头符号a ak k,
18、即找到即找到a ak-1k-1 a ak k为止。为止。(3).(3).由由句柄句柄a ak ka ai i在文法的产生式中查找右部为在文法的产生式中查找右部为a ak ka ai i 的产生式,若找到则用相应左部代替句柄,若找的产生式,若找到则用相应左部代替句柄,若找 不到则出错,这时可以断定输入符号不是不到则出错,这时可以断定输入符号不是的句子。的句子。(4).(4).重复上述重复上述(1)(1)、(2)(2)、(3)(3)步骤直到归约完输入符号步骤直到归约完输入符号 串,栈中只剩文法开始符号为止。串,栈中只剩文法开始符号为止。第23页/共37页自底向上分析方法是一种移进一归约过程,自底向
19、上分析方法是一种移进一归约过程,当分析的栈顶符号串形成句柄时就采取归约当分析的栈顶符号串形成句柄时就采取归约动作,因而自底向上分析法的关键问题是在动作,因而自底向上分析法的关键问题是在分析过程中如何确定分析过程中如何确定句柄句柄。三三三三 LRLRLRLR分析法分析法分析法分析法第24页/共37页LRLR分析法正是给出一种能根据当前分析栈分析法正是给出一种能根据当前分析栈中的符号串(通常以状态表示)和向右顺中的符号串(通常以状态表示)和向右顺序查看输入串的序查看输入串的K K个(个(K K0 0)符号就可唯)符号就可唯一地确定分析器的动作是移进还是归约和一地确定分析器的动作是移进还是归约和用哪
20、个产生式归约,因而也就能唯一地确用哪个产生式归约,因而也就能唯一地确定句柄。定句柄。LRLR分析法的归约过程是规范推导分析法的归约过程是规范推导的逆过程,所以的逆过程,所以LRLR分析过程是分析过程是规范归约过规范归约过程程。第25页/共37页1.LR1.LR分析的三个组成:分析的三个组成:1).1).总控程序总控程序:对所有对所有LRLR分析器都是相同的分析器都是相同的2).2).分析表或分析函数(分析表或分析函数(ACTIONACTION、GOTO)GOTO)不同文法分析表是不一样的不同文法分析表是不一样的,同一文法采用同一文法采用 的的LRLR分析器不一样分析器不一样,分析表也是不一样的
21、分析表也是不一样的.3).3).分析栈分析栈 文法符号栈和相应的状态栈文法符号栈和相应的状态栈.第26页/共37页输入串XXXXX.#总控程序ACTION表GOTO表Xn.X1#Sn.S1S0SP输出Si状态栈 Xi为文法符号栈第27页/共37页 ACTION ACTIONSi,aSi,a规定了栈顶状态为规定了栈顶状态为Si Si时时遇到输入符号遇到输入符号a a应执行的动作。动作有应执行的动作。动作有4 4种可能:种可能:1 1)移进:)移进:把把 Sj=GOTOSj=GOTOSi,aSi,a移入到状态栈,把移入到状态栈,把 a a移入到文法符号栈。其中移入到文法符号栈。其中i,j i,j表
22、示状态号。表示状态号。第28页/共37页2 2)归约:)归约:当在栈顶形成句柄为当在栈顶形成句柄为 时,则用时,则用 归约为相应归约为相应的非终结符的非终结符A A,即文法中有,即文法中有AA的产生式,若的产生式,若 的长度为的长度为r r(即(即|=r|=r)则从状态栈和文法符)则从状态栈和文法符号栈中自栈顶向下去掉号栈中自栈顶向下去掉r r个符号,即栈指针个符号,即栈指针SPSP减减去去r r。并把。并把A A移入文法符号栈内,移入文法符号栈内,Sj=GOTOSi,ASj=GOTOSi,A移进状态栈,其中移进状态栈,其中Si Si为修改指针后的栈顶状态。为修改指针后的栈顶状态。第29页/共
23、37页3 3)接受)接受 accacc:当归约到文法符号栈中只剩文法的开始符号当归约到文法符号栈中只剩文法的开始符号SS时,并且输入符号串已结束即当前输入符是时,并且输入符号串已结束即当前输入符是,则为分析成功。,则为分析成功。4 4)报错:)报错:当遇到状态栈顶为某一状态下出现不该遇到当遇到状态栈顶为某一状态下出现不该遇到的文法符号时,则报错,说明输入串不是该文的文法符号时,则报错,说明输入串不是该文法能接受的句子。法能接受的句子。第30页/共37页GSGS为:(1 1)SaAcBeSaAcBe (2 2)AbAb (3 3)AAbAAb (4 4)BdBd 对输入串 abbcdeabbcd
24、e用自底向上归约的方法进行分析,实例分析实例分析实例分析实例分析 第31页/共37页步骤步骤符号栈符号栈输入符号串输入符号串动作动作1 1#abbcde#abbcde#移进移进2 2#a#abbcde#bbcde#移进移进3 3#ab#abbcde#bcde#归约归约(A(A b)b)b)b)4 4#aA#aAbcde#bcde#移进移进5 5#aAb#aAbcde#cde#归约归约(AAbAAbAAbAAb)6 6#aA#aAcde#cde#移进移进7 7#aAc#aAcde#de#移进移进8 8#aAcd#aAcde#e#归约归约(BdBdBdBd)9 9#aAcB#aAcBe#e#移进移
25、进1010#aAcBe#aAcBe#归约归约(SaAcBeSaAcBeSaAcBeSaAcBe)1111#S#S#accacc第32页/共37页当归的到第当归的到第5)5)步时栈中符号串为步时栈中符号串为aAbaAb,我们采,我们采用了产生式(用了产生式(3 3)进行归约而不是用产生式()进行归约而不是用产生式(2 2)归约,而在第归约,而在第3 3)步归约时栈中符号串为)步归约时栈中符号串为abab时时却用产生式(却用产生式(2 2)归约,虽然在第)归约,虽然在第2 2)步和第)步和第5 5)步归约前栈顶符号都为步归约前栈顶符号都为b b,但归约所用产生式却,但归约所用产生式却不同,其原因在
26、于已分析过的部分在栈中的前缀不同,其原因在于已分析过的部分在栈中的前缀不同不同 对上表的总结对上表的总结对上表的总结对上表的总结第33页/共37页对上述文法输入abbcde#的分析过程 文法的LR(0)分析表实例分析第34页/共37页a ac ce eb bd d#S SA AB BACTIONACTIONGOTOGOTO0 0S S2 21 11 1accacc2 2S S4 43 33 3S S5 5S S6 64 4r r2 2r r2 2r r2 2r r2 2r r2 2r r2 25 5S S8 87 76 6r r3 3r r3 3r r3 3r r3 3r r3 3r r3 3
27、7 7S S9 98 8r r4 4r r4 4r r4 4r r4 4r r4 4r r4 49 9r r1 1r r1 1r r1 1r r1 1r r1 1r r1 1第35页/共37页步骤步骤步骤步骤状态栈状态栈符号栈符号栈输入串输入串ACTIONACTIONGOTOGOTO1 1 0 0#abbcde#abbcde#S S2 22 2 0202#a#abbcde#bbcde#S S4 43 3 024024#ab#abbcde#bcde#r2r23 34 4 023023#aA#aAbcde#bcde#S S6 65 5 02360236#aAb#aAbcde#cde#r r3 33 36 6 023023#aA#aAcde#cde#S S5 57 7 02350235#aAc#aAcde#de#S8S88 8 0235802358#aAcd#aAcde#e#r r4 47 79 9 0235702357#aAcB#aAcBe#e#S S9 91010 023579023579#aAcBe#aAcBe#r1r11 11111 0101#S#S#accacc第36页/共37页感谢您的观看!第37页/共37页
限制150内