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

2、左結(jié)合,4.6 二義文法的應(yīng)用,4.6.1 使用文法以外信息來解決分析動作沖突 例二義文法E E + E | E E | (E) | id 規(guī)定： 優(yōu)先級高于+，兩者都是左結(jié)合 LR(0)項目集I7 E E + E E E+ E E E E,4.6 二義文法的應(yīng)用,4.6.1 使用文法以外信息來解決分析動作沖突 例二義文法E E + E | E E | (E) | id 規(guī)定： 優(yōu)先級高于+，兩者都是左結(jié)合 LR(0)項目集I7 E E + E E E+ Eid + id + id E E E 面臨+，歸約,4.6 二義文法的應(yīng)用,4.6.1 使用文法以外信息來解決分析動作沖突 例二義文法E

3、E + E | E E | (E) | id 規(guī)定： 優(yōu)先級高于+，兩者都是左結(jié)合 LR(0)項目集I7 E E + E E E+ Eid + id + id E E E id + id id 面臨+，歸約面臨，移進(jìn),4.6 二義文法的應(yīng)用,4.6.1 使用文法以外信息來解決分析動作沖突 例二義文法E E + E | E E | (E) | id 規(guī)定： 優(yōu)先級高于+，兩者都是左結(jié)合 LR(0)項目集I7 E E + E E E+ Eid + id + id E E E id + id id 面臨+，歸約面臨，移進(jìn) 面臨 ) 和$，歸約,4.6 二義文法的應(yīng)用,4.6.1 使用文法以外信息來解

4、決分析動作沖突 例二義文法E E + E | E E | (E) | id 規(guī)定： 優(yōu)先級高于+，兩者都是左結(jié)合 LR(0)項目集I8 E E E E E+ E E E E,4.6 二義文法的應(yīng)用,4.6.1 使用文法以外信息來解決分析動作沖突 例二義文法E E + E | E E | (E) | id 規(guī)定： 優(yōu)先級高于+，兩者都是左結(jié)合 LR(0)項目集I8 E E E E E+ Eid id + id E E E 面臨+，歸約,4.6 二義文法的應(yīng)用,4.6.1 使用文法以外信息來解決分析動作沖突 例二義文法E E + E | E E | (E) | id 規(guī)定： 優(yōu)先級高于+，兩者都是

5、左結(jié)合 LR(0)項目集I8 E E E E E+ Eid id + id E E E id id id 面臨+，歸約面臨，歸約,4.6 二義文法的應(yīng)用,4.6.1 使用文法以外信息來解決分析動作沖突 例二義文法E E + E | E E | (E) | id 規(guī)定： 優(yōu)先級高于+，兩者都是左結(jié)合 LR(0)項目集I8 E E E E E+ Eid id + id E E E id id id 面臨+，歸約面臨，歸約 面臨 ) 和$，歸約,4.6 二義文法的應(yīng)用,4.6.2 特殊情況產(chǎn)生式引起的二義性 E E sub E sup E E E sub E E E sup E E E E c,4.

6、6 二義文法的應(yīng)用,4.6.2 特殊情況產(chǎn)生式引起的二義性 E E sub E sup E E E sub E E E sup E E E E c 從定義形式語言的角度說，第一個產(chǎn)生式是多余的,4.6 二義文法的應(yīng)用,4.6.2 特殊情況產(chǎn)生式引起的二義性 E E sub E sup E E E sub E E E sup E E E E c 聯(lián)系到語義處理，第一個產(chǎn)生式是必要的,4.6 二義文法的應(yīng)用,4.6.2 特殊情況產(chǎn)生式引起的二義性 E E sub E sup E E E sub E E E sup E E E E c 對a sub i sup 2，需要下面第一種輸出,4.6 二義文

7、法的應(yīng)用,4.6.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 E E E . . . E c 按前面一個產(chǎn)生式歸約,4.6 二義文法的應(yīng)用,4.6.3 LR分析的錯誤恢復(fù) 1、LR分析器在什么情況下發(fā)現(xiàn)錯誤 訪問動作表時若遇到出錯條目 訪問轉(zhuǎn)移表時它決不會遇到出錯條目 決不會把不正確的后繼移進(jìn)棧 規(guī)范的LR分析器甚至在報告錯誤之前決不做任何無效歸約,4.6 二義文法的應(yīng)用,2、緊急方式錯誤恢復(fù),4.6 二義文法的應(yīng)用,2、緊急方式錯誤恢復(fù) (1) 退棧，直至出現(xiàn)狀態(tài)s, 它有預(yù)先

8、確定的A的轉(zhuǎn)移,4.6 二義文法的應(yīng)用,2、緊急方式錯誤恢復(fù) (1) 退棧，直至出現(xiàn)狀態(tài)s, 它有預(yù)先確定的A的轉(zhuǎn)移 (2)拋棄若干輸入符號，直至找到a, 它是A的合法后繼,4.6 二義文法的應(yīng)用,2、緊急方式錯誤恢復(fù) (1) 退棧，直至出現(xiàn)狀態(tài)s, 它有預(yù)先確定的A的轉(zhuǎn)移 (2)拋棄若干輸入符號，直至找到a, 它是A的合法后繼 (3) 再把A和狀態(tài)gotos, A壓進(jìn)棧，恢復(fù)正常分析,本 章 要 點,文法和語言的基本知識 自上而下的分析方法：預(yù)測分析，非遞歸的預(yù)測分析，LL(1)文法 自下而上的分析方法：SLR(1)方法，規(guī)范LR(1)方法和LALR(1)方法 LR方法如何用于二義文法 語法

9、分析的錯誤恢復(fù)方法,例 題 1,下面的二義文法描述命題演算公式的語法， 為它寫一個等價的非二義文法 S S and S | S or S | not S | p | q | (S) 非二義文法的產(chǎn)生式如下： E E or T | T T T and F | F F not F | ( E) | p | q,例 題 1,下面的二義文法描述命題演算公式的語法， 為它寫一個等價的非二義文法 S S and S | S or S | not S | p | q | (S) 非二義文法的產(chǎn)生式如下： E E or T | T T T and F | F F not E | ( E) | p | q? n

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

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

12、bbabab aabbababaabbabab 非二義文法：S a B S | b A S | A a | b A A a abb abab B b | a B B aB S,例 題 3,試說明下面文法不是LR(1)的： L M L b | a M ,例 題 4,下面的文法不是LR(1)的，對它略做修改，使之成為 一個等價的SLR(1)文法 program begin declist ; statement end declist d ; declist | d statement s ; statement | s 該文法產(chǎn)生的句子的形式是 begin d ; d ; ; d ; s ; s ; ; s end 修改后的文法如下： program begin declist statement end declist d ; declist | d ; statement s ; st