二義文法的應(yīng)用

1、二義文法的應(yīng)用 二義文法的應(yīng)用 二義文法的特點(diǎn)：二義文法決不是LR文法簡(jiǎn)潔、自然例 二義文法E E + E | E E | (E) | id非二義的文法：E E + T | TT T F | FF (E) | id該文法有單個(gè)非終結(jié)符為右部的產(chǎn)生式 二義文法的應(yīng)用 二義文法的特點(diǎn)：二義文法決不是LR文法簡(jiǎn)潔、自然可以用文法以外的信息來(lái)消除二義語(yǔ)法分析的效率高基于消除二義后得到的分析表 二義文法的應(yīng)用 .1 使用文法以外信息來(lái)解決分析動(dòng)作沖突例二義文法E E + E | E E | (E) | id 規(guī)定： 優(yōu)先級(jí)高于+，兩者都是左結(jié)合 二義文法的應(yīng)用 .1 使用文法以外信息來(lái)解決分析動(dòng)作沖突例

2、二義文法E E + E | E E | (E) | id 規(guī)定： 優(yōu)先級(jí)高于+，兩者都是左結(jié)合LR(0)工程集I7E E + EE E+ EE E E 二義文法的應(yīng)用 .1 使用文法以外信息來(lái)解決分析動(dòng)作沖突例二義文法E E + E | E E | (E) | id 規(guī)定： 優(yōu)先級(jí)高于+，兩者都是左結(jié)合LR(0)工程集I7E E + EE E+ Eid + id + id E E E 面臨+，歸約 二義文法的應(yīng)用 .1 使用文法以外信息來(lái)解決分析動(dòng)作沖突例二義文法E E + E | E E | (E) | id 規(guī)定： 優(yōu)先級(jí)高于+，兩者都是左結(jié)合LR(0)工程集I7E E + EE E+ E

3、id + id + id E E E id + id id 面臨+，歸約面臨，移進(jìn) 二義文法的應(yīng)用 .1 使用文法以外信息來(lái)解決分析動(dòng)作沖突例二義文法E E + E | E E | (E) | id 規(guī)定： 優(yōu)先級(jí)高于+，兩者都是左結(jié)合LR(0)工程集I7E E + EE E+ Eid + id + id E E E id + id id 面臨+，歸約面臨，移進(jìn)面臨 ) 和$，歸約 二義文法的應(yīng)用 .1 使用文法以外信息來(lái)解決分析動(dòng)作沖突例二義文法E E + E | E E | (E) | id 規(guī)定： 優(yōu)先級(jí)高于+，兩者都是左結(jié)合LR(0)工程集I8E E E E E+ EE E E 二義文

4、法的應(yīng)用 .1 使用文法以外信息來(lái)解決分析動(dòng)作沖突例二義文法E E + E | E E | (E) | id 規(guī)定： 優(yōu)先級(jí)高于+，兩者都是左結(jié)合LR(0)工程集I8E E E E E+ Eid id + id E E E 面臨+，歸約 二義文法的應(yīng)用 .1 使用文法以外信息來(lái)解決分析動(dòng)作沖突例二義文法E E + E | E E | (E) | id 規(guī)定： 優(yōu)先級(jí)高于+，兩者都是左結(jié)合LR(0)工程集I8E E E E E+ Eid id + id E E E id id id面臨+，歸約面臨，歸約 二義文法的應(yīng)用 .1 使用文法以外信息來(lái)解決分析動(dòng)作沖突例二義文法E E + E | E E

5、 | (E) | id 規(guī)定： 優(yōu)先級(jí)高于+，兩者都是左結(jié)合LR(0)工程集I8E E E E E+ Eid id + id E E E id id id 面臨+，歸約面臨，歸約面臨 ) 和$，歸約 二義文法的應(yīng)用 .2 特殊情況產(chǎn)生式引起的二義性E E sub E sup EE E sub EE E sup EE EE c 二義文法的應(yīng)用 .2 特殊情況產(chǎn)生式引起的二義性E E sub E sup EE E sub EE E sup EE EE c從定義形式語(yǔ)言的角度說(shuō)，第一個(gè)產(chǎn)生式是多余的 二義文法的應(yīng)用 .2 特殊情況產(chǎn)生式引起的二義性E E sub E sup EE E sub EE

6、E sup EE EE c聯(lián)絡(luò)到語(yǔ)義處理，第一個(gè)產(chǎn)生式是必要的 二義文法的應(yīng)用 .2 特殊情況產(chǎn)生式引起的二義性E E sub E sup EE E sub EE E sup EE EE c對(duì)a sub i sup 2，需要下面第一種輸出 二義文法的應(yīng)用 .2 特殊情況產(chǎn)生式引起的二義性E E sub E sup EI11:E E sub E E E sub E sup E E E sup E E E sup EE E . . . E c 按前面一個(gè)產(chǎn)生式歸約 二義文法的應(yīng)用 .3 LR分析的錯(cuò)誤恢復(fù) 1、LR分析器在什么情況下發(fā)現(xiàn)錯(cuò)誤訪問(wèn)動(dòng)作表時(shí)假設(shè)遇到出錯(cuò)條目訪問(wèn)轉(zhuǎn)移表時(shí)它決不會(huì)遇到出錯(cuò)條

7、目決不會(huì)把不正確的后繼移進(jìn)棧標(biāo)準(zhǔn)的LR分析器甚至在報(bào)告錯(cuò)誤之前決不做任何無(wú)效歸約 二義文法的應(yīng)用 2、緊急方式錯(cuò)誤恢復(fù)s.棧. . . . . . . . a . .A發(fā)現(xiàn)錯(cuò)誤s :C AA b. . .s1 :C A. . .AAb. . .b 二義文法的應(yīng)用 2、緊急方式錯(cuò)誤恢復(fù)(1) 退棧，直至出現(xiàn)狀態(tài)s, 它有預(yù)先確定的A的轉(zhuǎn)移s.棧. . . . . . . . a . .A發(fā)現(xiàn)錯(cuò)誤s :C AA b. . .s1 :C A. . .AAb. . .b 二義文法的應(yīng)用 2、緊急方式錯(cuò)誤恢復(fù)(1) 退棧，直至出現(xiàn)狀態(tài)s, 它有預(yù)先確定的A的轉(zhuǎn)移(2)拋棄假設(shè)干輸入符號(hào)，直至找到a, 它

8、是A的合法后繼s.棧. . . . . . . . a . .As :C AA b. . .s1 :C A. . .AAb. . .b 二義文法的應(yīng)用 2、緊急方式錯(cuò)誤恢復(fù)(1) 退棧，直至出現(xiàn)狀態(tài)s, 它有預(yù)先確定的A的轉(zhuǎn)移(2)拋棄假設(shè)干輸入符號(hào)，直至找到a, 它是A的合法后繼(3) 再把A和狀態(tài)gotos, A壓進(jìn)棧，恢復(fù)正常分析ss1.棧. . . . . . . . a . .As :C AA b. . .s1 :C A. . .AAb. . .b本 章 要 點(diǎn)文法和語(yǔ)言的根本知識(shí)自上而下的分析方法：預(yù)測(cè)分析，非遞歸的預(yù)測(cè)分析，LL(1)文法自下而上的分析方法：SLR(1)方法，標(biāo)準(zhǔn)

9、LR(1)方法和LALR(1)方法LR方法如何用于二義文法語(yǔ)法分析的錯(cuò)誤恢復(fù)方法例 題 1下面的二義文法描繪命題演算公式的語(yǔ)法，為它寫一個(gè)等價(jià)的非二義文法S S and S | S or S | not S | p | q | (S)非二義文法的產(chǎn)生式如下：E E or T | TT T and F | FF not F | ( E) | p | q例 題 1下面的二義文法描繪命題演算公式的語(yǔ)法，為它寫一個(gè)等價(jià)的非二義文法S S and S | S or S | not S | p | q | (S)非二義文法的產(chǎn)生式如下：E E or T | TT T and F | FF not E |

10、( E) | p | q?not p and q有兩種不同的最左推導(dǎo)例 題 1下面的二義文法描繪命題演算公式的語(yǔ)法，為它寫一個(gè)等價(jià)的非二義文法S S and S | S or S | not S | p | q | (S)非二義文法的產(chǎn)生式如下：E E or T | T not p and qT T and F | F not p and qF not E | ( E) | p | q?not p and q有兩種不同的最左推導(dǎo)例 題 2設(shè)計(jì)一個(gè)文法:字母表a, b上a和b的個(gè)數(shù)相等的所有串的集合二義文法：S a S b S | b S a S | aabbababaabbabab S S S

11、 S例 題 2設(shè)計(jì)一個(gè)文法:字母表a, b上a和b的個(gè)數(shù)相等的所有串的集合二義文法：S a S b S | b S a S | aabbababaabbabab二義文法：S a B | b A | A a S | b A AB b S | a B Baabbabab aabbababaabbabab B B B B B B例 題 2設(shè)計(jì)一個(gè)文法:字母表a, b上a和b的個(gè)數(shù)相等的所有串的集合二義文法：S a S b S | b S a S | aabbababaabbabab二義文法：S a B | b A | A a S | b A AB b S | a B Baabbabab aabbab

12、abaabbabab非二義文法：S a B S | b A S | A a | b A A a abb abab B b | a B B aB S例 題 3試說(shuō)明下面文法不是LR(1)的：L M L b | aM MbLLLLaMbMb句子abbb的分析樹例 題 4下面的文法不是LR(1)的，對(duì)它略做修改，使之成為一個(gè)等價(jià)的SLR(1)文法program begin declist ; statement enddeclist d ; declist | dstatement s ; statement | s該文法產(chǎn)生的句子的形式是begin d ; d ; ; d ; s ; s ; ; s end修改后的文法如下：program begin declist statement enddeclist d ; declist | d ;statem