編譯原理第四章語法分析4.6

二義文法的應(yīng)用二義文法的特點(diǎn)：二義文法決不是LR文法簡潔、自然例二義文法 EE+E|E

E|(E)|id

非二義的文法：

EE+T|T

TT

F|F

F(E)

|id

該文法有單個(gè)非終結(jié)符為右部的產(chǎn)生式4.6

二義文法的應(yīng)用二義文法的特點(diǎn)：二義文法決不是LR文法簡潔、自然可以用文法以外的信息來消除二義語法分析的效率高（基于消除二義后得到的分析表）4.6

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

使用文法以外信息來解決分析動作沖突例 二義文法 EE+E|EE|(E)|id 規(guī)定：優(yōu)先級高于+，兩者都是左結(jié)合4.6

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

使用文法以外信息來解決分析動作沖突例 二義文法 EE+E|EE|(E)|id 規(guī)定：優(yōu)先級高于+，兩者都是左結(jié)合LR(0)項(xiàng)目集I7EE

+E·EE·+EEE·

E

4.6

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

使用文法以外信息來解決分析動作沖突例 二義文法 EE+E|EE|(E)|id 規(guī)定：優(yōu)先級高于+，兩者都是左結(jié)合LR(0)項(xiàng)目集I7EE+E·EE·+E id+id +id

EE·

E

面臨+，歸約 4.6

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

使用文法以外信息來解決分析動作沖突例 二義文法 EE+E|EE|(E)|id 規(guī)定：優(yōu)先級高于+，兩者都是左結(jié)合LR(0)項(xiàng)目集I7EE+E·EE·+E id+id +id

EE·

E id+id id

面臨+，歸約 面臨，移進(jìn)4.6

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

使用文法以外信息來解決分析動作沖突例 二義文法 EE+E|EE|(E)|id 規(guī)定：優(yōu)先級高于+，兩者都是左結(jié)合LR(0)項(xiàng)目集I7EE+E·EE·+E id+id +id

EE·

E id+id id

面臨+，歸約 面臨，移進(jìn) 面臨)和$，歸約4.6

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

使用文法以外信息來解決分析動作沖突例 二義文法 EE+E|EE|(E)|id 規(guī)定：優(yōu)先級高于+，兩者都是左結(jié)合LR(0)項(xiàng)目集I8EE

E·EE·+E EE·

E

4.6

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

使用文法以外信息來解決分析動作沖突例 二義文法 EE+E|EE|(E)|id 規(guī)定：優(yōu)先級高于+，兩者都是左結(jié)合LR(0)項(xiàng)目集I8EE

E·EE·+E idid +id

EE·

E

面臨+，歸約 4.6

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

使用文法以外信息來解決分析動作沖突例 二義文法 EE+E|EE|(E)|id 規(guī)定：優(yōu)先級高于+，兩者都是左結(jié)合LR(0)項(xiàng)目集I8EE

E·EE·+E idid +id

EE·

E idid id 面臨+，歸約 面臨，歸約 4.6

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

使用文法以外信息來解決分析動作沖突例 二義文法 EE+E|EE|(E)|id 規(guī)定：優(yōu)先級高于+，兩者都是左結(jié)合LR(0)項(xiàng)目集I8EE

E·EE·+E idid +id

EE·

E idid id

面臨+，歸約 面臨，歸約 面臨)和$，歸約4.6

二義文法的應(yīng)用4.6.2特殊情況產(chǎn)生式引起的二義性E

EsubEsupEE

EsubEE

EsupEE{E}E

c4.6

二義文法的應(yīng)用4.6.2特殊情況產(chǎn)生式引起的二義性E

EsubEsupEE

EsubEE

EsupEE{E}E

c

從定義形式語言的角度說，第一個(gè)產(chǎn)生式是多余的4.6

二義文法的應(yīng)用4.6.2特殊情況產(chǎn)生式引起的二義性E

EsubEsupEE

EsubEE

EsupEE{E}E

c

聯(lián)系到語義處理，第一個(gè)產(chǎn)生式是必要的4.6

二義文法的應(yīng)用4.6.2特殊情況產(chǎn)生式引起的二義性E

EsubEsupEE

EsubEE

EsupEE{E}E

c

對asubisup2，需要下面第一種輸出4.6

二義文法的應(yīng)用4.6.2特殊情況產(chǎn)生式引起的二義性E

EsubEsupE I11:E

EsubE E

EsubEsupE·E

EsupE E

EsupE·E{E} ...E

c

按前面一個(gè)產(chǎn)生式歸約4.6

二義文法的應(yīng)用4.6.3LR分析的錯(cuò)誤恢復(fù)

1、LR分析器在什么情況下發(fā)現(xiàn)錯(cuò)誤訪問動作表時(shí)若遇到出錯(cuò)條目訪問轉(zhuǎn)移表時(shí)它決不會遇到出錯(cuò)條目決不會把不正確的后繼移進(jìn)棧規(guī)范的LR分析器甚至在報(bào)告錯(cuò)誤之前決不做任何無效歸約4.6

二義文法的應(yīng)用2、緊急方式錯(cuò)誤恢復(fù)s......棧........a..A發(fā)現(xiàn)錯(cuò)誤s:C·AA·b...s1:CA·...AAb·...b4.6

二義文法的應(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:CA·...AAb·...b4.6

二義文法的應(yīng)用2、緊急方式錯(cuò)誤恢復(fù)(1)退棧，直至出現(xiàn)狀態(tài)s,它有預(yù)先確定的A的轉(zhuǎn)移(2)拋棄若干輸入符號，直至找到a,

它是A的合法后繼s...棧........a..As:C·AA·b...s1:CA·...AAb·...b4.6

二義文法的應(yīng)用2、緊急方式錯(cuò)誤恢復(fù)(1)退棧，直至出現(xiàn)狀態(tài)s,它有預(yù)先確定的A的轉(zhuǎn)移(2)拋棄若干輸入符號，直至找到a,

它是A的合法后繼(3)再把A和狀態(tài)goto[s,A]壓進(jìn)棧，恢復(fù)正常分析ss1...棧........a..As:C·AA·b...s1:CA·...AAb·...b4.7

分析器的生成器4.7.1分析器的生成器Yacc

Yacc編譯器Yacc源程序translate.yy.tab.cC編譯器y.tab.ca.outa.out輸入輸出4.7

分析器的生成器4.7.2用Yacc處理二義文法

例 簡單計(jì)算器輸入一個(gè)表達(dá)式并回車，顯示計(jì)算結(jié)果也可以輸入一個(gè)空白行4.7

分析器的生成器%{#include<ctype.h>#include<stdio.h>#defineYYSTYPEdouble/將棧定義為double類型/%}

%tokenNUMBER%left‘+’‘’%left‘’‘/’%rightUMINUS%%4.7

分析器的生成器lines :linesexpr‘\n’{printf(“%g\n”,$2)} |lines‘\n’ |/

/ ;expr :expr‘+’expr {$$=$1+$3;} |expr‘’expr {$$=$1$3;} |expr‘’expr {$$=$1$3;} |expr‘/’expr {$$=$1/$3;} |‘(’expr‘)’ {$$=$2;} |‘’expr%precUMINUS {$$=$2;} |NUMBER ;%%4.7

分析器的生成器lines :linesexpr‘\n’{printf(“%g\n”,$2)} |lines‘\n’ |/

/ ;expr :expr‘+’expr {$$=$1+$3;} |expr‘’expr {$$=$1$3;} |expr‘’expr {$$=$1$3;} |expr‘/’expr {$$=$1/$3;} |‘(’expr‘)’ {$$=$2;} |‘’expr%precUMINUS {$$=$2;} |NUMBER ;%%

-5+10看成是-(5+10),還是(-5)+10?取后者4.7

分析器的生成器yylex(){ intc; while((c=getchar())==‘’); if((c==‘.’)||(isdigit(c))){ ungetc(c,stdin); scanf(“%lf”,&yylval); returnNUMBER; } returnc;}4.7

分析器的生成器4.7.3Yacc的錯(cuò)誤恢復(fù)編譯器設(shè)計(jì)者的工作決定哪些“主要的”非終結(jié)符將有錯(cuò)誤恢復(fù)與它們相關(guān)聯(lián)為各主要非終結(jié)符A加入形式為Aerror的錯(cuò)誤產(chǎn)生式，其中是文法符號串為這樣的產(chǎn)生式配上語義動作Yacc把錯(cuò)誤產(chǎn)生式當(dāng)作普通產(chǎn)生式處理4.7

分析器的生成器遇到語法錯(cuò)誤時(shí)s......棧........

...A發(fā)現(xiàn)錯(cuò)誤s:C1·A2A·error...s1:C1A·2...As2:Aerror·...error4.7

分析器的生成器遇到語法錯(cuò)誤時(shí)從棧中彈出狀態(tài)，直到發(fā)現(xiàn)棧頂狀態(tài)的項(xiàng)目集包含形為A·error的項(xiàng)目為止s...棧........

...A發(fā)現(xiàn)錯(cuò)誤s:C1·A2A·error...s1:C1A·2...As2:Aerror·...error4.7

分析器的生成器遇到語法錯(cuò)誤時(shí)從棧中彈出狀態(tài)，直到發(fā)現(xiàn)棧頂狀態(tài)的項(xiàng)目集包含形為A·error的項(xiàng)目為止把虛構(gòu)的終結(jié)符error“移進(jìn)”棧ss2...棧........

...A發(fā)現(xiàn)錯(cuò)誤s:C1·A2A·error...s1:C1A·2...As2:Aerror·...error4.7

分析器的生成器遇到語法錯(cuò)誤時(shí)從棧中彈出狀態(tài)，直到發(fā)現(xiàn)棧頂狀態(tài)的項(xiàng)目集包含形為A·error的項(xiàng)目為止把虛構(gòu)的終結(jié)符error“移進(jìn)”棧忽略若干輸入符號，直至找到，把移進(jìn)棧棧........

...As:C1·A2A·error...s1:C1A·2...As2:Aerror·...errorss2......4.7

分析器的生成器遇到語法錯(cuò)誤時(shí)從棧中彈出狀態(tài)，直到發(fā)現(xiàn)棧頂狀態(tài)的項(xiàng)目集包含形為A·error的項(xiàng)目為止把虛構(gòu)的終結(jié)符error“移進(jìn)”棧忽略若干輸入符號，直至找到，把移進(jìn)棧把error歸約為A，恢復(fù)正常分析ss1...棧........

...As:C1·A2A·error...s1:C1A·2...As2:Aerror·...error4.7

分析器的生成器增加錯(cuò)誤恢復(fù)的簡單計(jì)算器lines :linesexpr‘\n’ {printf(“%g\n”,$2)} |lines‘\n’ |/

/ |error‘\n’{yyerror(“重新輸入上一行”);

yyerrok;} ;本章要點(diǎn)文法和語言的基本知識自上而下的分析方法：預(yù)測分析，非遞歸的預(yù)測分析，LL(1)文法自下而上的分析方法：SLR(1)方法，規(guī)范LR(1)方法和LALR(1)方法LR方法如何用于二義文法語法分析的錯(cuò)誤恢復(fù)方法例題1 下面的二義文法描述命題演算公式的語法，為它寫一個(gè)等價(jià)的非二義文法

SSandS|SorS|notS|p|q|(S) 非二義文法的產(chǎn)生式如下：

EEorT|T TTandF|F FnotF|(E)|p|q例題1 下面的二義文法描述命題演算公式的語法，為它寫一個(gè)等價(jià)的非二義文法

SSandS|SorS|notS|p|q|(S) 非二義文法的產(chǎn)生式如下：

EEorT|T TTandF|F FnotE|(E)|p|q ?

notpandq有兩種不同的最左推導(dǎo)例題1 下面的二義文法描述命題演算公式的語法，為它寫一個(gè)等價(jià)的非二義文法

SSandS|SorS|notS|p|q|(S) 非二義文法的產(chǎn)生式如下：

EEorT|T notpandq TTandF|F notpandq FnotE|(E)|p|q ?

notpandq有兩種不同的最左推導(dǎo)例題2 設(shè)計(jì)一個(gè)文法:字母表{a,b}上a和b的個(gè)數(shù)相等的所有串的集合二義文法： S

aSbS|bSaS|

aabbabab

aabbabab SS SS例題2 設(shè)計(jì)一個(gè)文法:字母表{a,b}上a和b的個(gè)數(shù)相等的所有串的集合二義文法： S

aSbS|bSaS|

aabbabab aabbabab二義文法： S

aB|bA|

A

aS|bAA

B

bS|aBBaabbabab

aabbabab

aabbabab

BB BB BB例題2 設(shè)計(jì)一個(gè)文法:字母表{a,b}上a和b的個(gè)數(shù)相等的所有串的集合二義文法： S

aSbS|bSaS|

aabbabab aabbabab二義文法： S

aB|bA|

A