形式語(yǔ)言與語(yǔ)法分析第1頁(yè)，共65頁(yè)，2023年，2月20日，星期四第三章語(yǔ)法分析介紹第2頁(yè)，共65頁(yè)，2023年，2月20日，星期四第3章outline語(yǔ)法分析概述1.功能需求(輸入，輸出，主要功能)2.分析算法+數(shù)據(jù)結(jié)構(gòu)3.構(gòu)造語(yǔ)法分析器的通用過(guò)程上下文無(wú)關(guān)文法語(yǔ)法分析樹(shù)和抽象語(yǔ)法樹(shù)二義性文法文法變換算法語(yǔ)法錯(cuò)誤處理第3頁(yè)，共65頁(yè)，2023年，2月20日，星期四知識(shí)關(guān)系圖開(kāi)發(fā)語(yǔ)法分析程序語(yǔ)法定義基于上下文無(wú)關(guān)文法使用實(shí)現(xiàn)自頂向下自底向上第4頁(yè)，共65頁(yè)，2023年，2月20日，星期四3.1語(yǔ)法分析概述部分語(yǔ)法分析程序的功能輸入：詞法分析程序輸出的Token/TokenList輸出：語(yǔ)法結(jié)構(gòu)的內(nèi)部表示(抽象語(yǔ)法樹(shù)，AST)

或語(yǔ)法錯(cuò)誤信息分析過(guò)程：從左到右掃描Token序列，根據(jù)上下文無(wú)關(guān)文法，建立語(yǔ)法結(jié)構(gòu)的內(nèi)部表示，檢查語(yǔ)法錯(cuò)誤。語(yǔ)法分析Token序列抽象語(yǔ)法樹(shù)語(yǔ)法錯(cuò)誤第5頁(yè)，共65頁(yè)，2023年，2月20日，星期四語(yǔ)法分析過(guò)程C程序：Parser輸入：Parser輸出：if

(x=y)

{z=1;}else{z=0;}

IFLparenidEQidRparenLGidEQnumsemiRGelseLGidEQnumsemiRGIF_Stmt=idid=idnum=idnum第6頁(yè)，共65頁(yè)，2023年，2月20日，星期四程序設(shè)計(jì)語(yǔ)言的語(yǔ)法結(jié)構(gòu)(1)程序(2)聲明

-常量聲明

-類型聲明

-變量聲明

-過(guò)程/函數(shù)聲明(3)程序體(4)語(yǔ)句（賦值語(yǔ)句，條件語(yǔ)句，循環(huán)語(yǔ)句，函數(shù)調(diào)用語(yǔ)句）(5)表達(dá)式(算術(shù)表達(dá)式，邏輯表達(dá)式，關(guān)系表達(dá)式)第7頁(yè)，共65頁(yè)，2023年，2月20日，星期四語(yǔ)法錯(cuò)誤語(yǔ)法錯(cuò)誤的類型語(yǔ)法結(jié)構(gòu)的開(kāi)始單詞錯(cuò)誤表達(dá)式E的開(kāi)始單詞是id,(,n---其他Token則出錯(cuò)語(yǔ)法結(jié)構(gòu)的后繼單詞錯(cuò)誤語(yǔ)句；語(yǔ)句----語(yǔ)句，語(yǔ)句標(biāo)識(shí)符或者常量錯(cuò)id

:=E----begin:=E或123:=E關(guān)鍵字錯(cuò)ifEthen語(yǔ)句else

語(yǔ)句----其他關(guān)鍵字則出錯(cuò)括號(hào)配對(duì)錯(cuò)（（）（））----）（（）第8頁(yè)，共65頁(yè)，2023年，2月20日，星期四語(yǔ)法錯(cuò)誤的例子intGetMax(intx;inty){if(x>y){returnx}elsereturny;}}vodmain(){real10,y;10+;GetMax(x,y);}后繼單詞錯(cuò)括號(hào)配對(duì)錯(cuò)關(guān)鍵字錯(cuò),開(kāi)始單詞錯(cuò)標(biāo)識(shí)符錯(cuò)開(kāi)始單詞錯(cuò)第9頁(yè)，共65頁(yè)，2023年，2月20日，星期四語(yǔ)法分析方法自頂向下的分析從上往下生成樹(shù)的過(guò)程自底向上的分析從下往上生成樹(shù)的過(guò)程IF_Stmt=idid=idnum=id0遞歸下降分析LL(1)分析LR(0),SLR(1),LR(1),LALR(1)第10頁(yè)，共65頁(yè)，2023年，2月20日，星期四語(yǔ)法分析與詞法分析的比較階段（Phase）輸入（Input）輸出（Output）詞法分析（scanner）字符序列Token序列語(yǔ)法分析（parser）Token序列抽象語(yǔ)法樹(shù)第11頁(yè)，共65頁(yè)，2023年，2月20日，星期四第3章outline語(yǔ)法分析概述1.功能需求(輸入，輸出，主要功能)2.分析算法+數(shù)據(jù)結(jié)構(gòu)3.構(gòu)造語(yǔ)法分析器的通用過(guò)程上下文無(wú)關(guān)文法語(yǔ)法分析樹(shù)和抽象語(yǔ)法樹(shù)二義性文法文法變換算法語(yǔ)法錯(cuò)誤處理√第12頁(yè)，共65頁(yè)，2023年，2月20日，星期四3.2上下文無(wú)關(guān)文法

不是所有的Token串都是合法的程序，因此需要一個(gè)工具來(lái)描述合法的Token串。一般地，程序設(shè)計(jì)語(yǔ)言的結(jié)構(gòu)都是遞歸結(jié)構(gòu)(recursivestructure)例如：表達(dá)式，上下文無(wú)關(guān)文法非常適合描述這種結(jié)構(gòu)變量是表達(dá)式（表達(dá)式）是表達(dá)式表達(dá)式+表達(dá)式是表達(dá)式第13頁(yè)，共65頁(yè)，2023年，2月20日，星期四3.2上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法是一個(gè)四元組(VT,VN,S,P)VT是有限的終極符集合VN是有限的非終極符集合S是開(kāi)始符，SVNP是產(chǎn)生式的集合，且具有下面的形式：

AX1X2…Xn

其中AVN，Xi(VTVN)符號(hào)約定：非終極符用大寫(xiě)字母表示終極符用小寫(xiě)字母表示開(kāi)始符是第一條產(chǎn)生式左部的符號(hào)不絕對(duì)！第14頁(yè)，共65頁(yè)，2023年，2月20日，星期四上下文無(wú)關(guān)文法的例子例1：簡(jiǎn)單算術(shù)表達(dá)式的上下文無(wú)關(guān)文法，EidE(E)EE+EEE*EEid|(E)|E+E|E*EEid|(E)|E+E|E*EVT:{id,(,),+,*}VN:ES:E第15頁(yè)，共65頁(yè)，2023年，2月20日，星期四上下文無(wú)關(guān)文法的例子例2：語(yǔ)句的上下文無(wú)關(guān)文法：

VT：{id，（，），+，*,=,if,else,while,;}VN：E,StmtS：StmtStmt

id=EStmtifEStmtelseStmtStmtwhileEStmtStmtStmt;Stmt

EidE(E)EE+EEE*E第16頁(yè)，共65頁(yè)，2023年，2月20日，星期四上下文無(wú)關(guān)文法的例子例3：變量聲明的上下文無(wú)關(guān)文法：

變量聲明變量聲明一個(gè)變量定義;變量聲明一個(gè)變量定義;變量聲明變量定義類型標(biāo)識(shí)符序列標(biāo)識(shí)符序列一個(gè)標(biāo)識(shí)符標(biāo)識(shí)符序列一個(gè)標(biāo)識(shí)符,標(biāo)識(shí)符序列VarDecVarDecVarDef;VarDecVarDef;VarDecVarDefTypeIdListIdListidIdListid,IdList第17頁(yè)，共65頁(yè)，2023年，2月20日，星期四上下文無(wú)關(guān)文法是怎樣定義語(yǔ)言的？第18頁(yè)，共65頁(yè)，2023年，2月20日，星期四與上下文無(wú)關(guān)文法有關(guān)的一些概念直接推導(dǎo)()：如果A是一個(gè)產(chǎn)生式，則有A,其中表示一步推導(dǎo)(用A→)。這時(shí)稱是由A直接推導(dǎo)的。“”的含義是，使用一條規(guī)則，代替左邊的某個(gè)符號(hào)，產(chǎn)生右端的符號(hào)串推導(dǎo)(+)：若通過(guò)一步或多步推導(dǎo)可從串導(dǎo)出串,則稱為的推導(dǎo),并記為+星推導(dǎo)(*):稱*當(dāng)且僅當(dāng)=或+第19頁(yè)，共65頁(yè)，2023年，2月20日，星期四例子(E)(E+T)(應(yīng)用產(chǎn)生式2)(E)(T)(應(yīng)用產(chǎn)生式1)E直接推導(dǎo)出E+T或E直接推導(dǎo)出TETF（E）（E+T）（T+T）（F+T）（i+T）（i+F）（i+n),記作E+(i+n)E經(jīng)過(guò)多步推導(dǎo)出i+nE*EE*i+(i）E經(jīng)過(guò)若干步推導(dǎo)出i+(i）P:(1)ET(2)EE+T(3)TF(4)TT*F(5)F(E)(6)Fi(7)Fn第20頁(yè)，共65頁(yè)，2023年，2月20日，星期四與上下文無(wú)關(guān)文法有關(guān)的一些概念句型：如果有S*,S是文法的開(kāi)始符,∈(VTVN)*，則稱是G的句型句子：如果有S+,S是文法的開(kāi)始符,∈VT*，則稱是G的句子語(yǔ)言：

L(G)={|S+,∈VT*}即文法G的所有句子的集合文法等價(jià)：

G1和G2兩個(gè)文法,若L(G1)=L(G2),則稱G1和G2等價(jià)第21頁(yè)，共65頁(yè)，2023年，2月20日，星期四例子句型:E,T,E+T,F,T*F,i,n,(E),

…….句子:i,n,(i),(n),i+i,i+n,……

語(yǔ)言:{i,n,(i),(n),i+i,i+n,……}P:(1)ET(2)EE+T(3)TF(4)TT*F(5)F(E)(6)Fi(7)Fn第22頁(yè)，共65頁(yè)，2023年，2月20日，星期四與上下文無(wú)關(guān)文法有關(guān)的一些概念最左(右)推導(dǎo)：在推導(dǎo)過(guò)程中，總是對(duì)當(dāng)前符號(hào)串中最左(右)邊的非終極符進(jìn)行替換，稱為最左(右)推導(dǎo),記為l(r)m規(guī)范推導(dǎo)：最右推導(dǎo)左(右)句型：通過(guò)最左(右)推導(dǎo)得到的句型，稱為左(右)句型規(guī)范句型：右句型第23頁(yè)，共65頁(yè)，2023年，2月20日，星期四例子最左推導(dǎo):i+T*n+Flmi+F*n+F最右推導(dǎo): i+T*n+F

rmi+T*n+i左句型:i+i*F右句型:E+(i)P:(1)ET(2)EE+T(3)TF(4)TT*F(5)F(E)(6)Fi(7)Fn第24頁(yè)，共65頁(yè)，2023年，2月20日，星期四特別注意例如文法G:ND|NDD0|1|2|…|9

NrmNDrm

N8rmND8rm

N98rm

D98rm198,句子198的最右推導(dǎo)

NrmNDNDD,句型NDD不存在最右推導(dǎo)每個(gè)句子一定有最右(規(guī)范)推導(dǎo)每個(gè)句型不一定有最右(規(guī)范)推導(dǎo)第25頁(yè)，共65頁(yè)，2023年，2月20日，星期四上下文無(wú)關(guān)文法小結(jié)ContextFreeGrammar,CFG(VT,VN,S,P)推導(dǎo)，句型，句子，語(yǔ)言的概念及含義語(yǔ)言與文法第26頁(yè)，共65頁(yè)，2023年，2月20日，星期四Chomsky文法分類第27頁(yè)，共65頁(yè)，2023年，2月20日，星期四Chomsky文法分類上下文無(wú)關(guān)文法只是文法的一種。文法有很多種。Chomsky將文法分為四類：0型文法：短語(yǔ)文法。產(chǎn)生式：，中至少有一個(gè)非終極符。0型語(yǔ)言。1型文法：上下文相關(guān)文法。產(chǎn)生式：A,,可為。1型語(yǔ)言(上下文有關(guān)語(yǔ)言)。2型文法：上下文無(wú)關(guān)文法。產(chǎn)生式：A，可為。2型語(yǔ)言(上下文無(wú)關(guān)語(yǔ)言)。3型文法：正則文法。產(chǎn)生式：AaB,Aa。3型語(yǔ)言(正則語(yǔ)言)。第28頁(yè)，共65頁(yè)，2023年，2月20日，星期四Chomsky文法分類描述能力：0型文法〉1型文法〉2型文法〉3型文法對(duì)應(yīng)自動(dòng)機(jī)：0型文法對(duì)應(yīng)圖靈機(jī)1型文法對(duì)應(yīng)線性有屆自動(dòng)機(jī)2型文法對(duì)應(yīng)下推自動(dòng)機(jī)3型文法對(duì)應(yīng)有限自動(dòng)機(jī)第29頁(yè)，共65頁(yè)，2023年，2月20日，星期四第3章outline語(yǔ)法分析概述1.功能需求(輸入，輸出，主要功能)2.分析算法+數(shù)據(jù)結(jié)構(gòu)3.構(gòu)造語(yǔ)法分析器的通用過(guò)程上下文無(wú)關(guān)文法語(yǔ)法分析樹(shù)和抽象語(yǔ)法樹(shù)二義性文法文法變換算法語(yǔ)法錯(cuò)誤處理√√第30頁(yè)，共65頁(yè)，2023年，2月20日，星期四3.3語(yǔ)法分析樹(shù)和抽象語(yǔ)法樹(shù)問(wèn)題:推導(dǎo)是從開(kāi)始符產(chǎn)生句型的一種方法;對(duì)同一個(gè)句型存在多個(gè)推導(dǎo)：NNDNDDND8N98…或N9DN98…

或DDDDD8D98198

或D9DD98198或1DD19D198或1D8198

……

即線性推導(dǎo)不能唯一地表示句子的結(jié)構(gòu)語(yǔ)法分析樹(shù):(SyntaxAnalysisTree)用于表示句型結(jié)構(gòu)的一種較好方法;第31頁(yè)，共65頁(yè)，2023年，2月20日，星期四例子P:(1)ET(2)EE+T(3)TF(4)TT*F(5)F(E)(6)Fi(7)Fn句型（句子）:i+i*n該句型存在多個(gè)推導(dǎo)：語(yǔ)法分析樹(shù)：第32頁(yè)，共65頁(yè)，2023年，2月20日，星期四語(yǔ)法分析樹(shù)語(yǔ)法分析樹(shù)是針對(duì)某個(gè)特定CFG的帶標(biāo)號(hào)的樹(shù)樹(shù)的每個(gè)節(jié)點(diǎn)都標(biāo)記一個(gè)符號(hào)：樹(shù)的根節(jié)點(diǎn)標(biāo)記文法的開(kāi)始符;樹(shù)的每個(gè)葉子節(jié)點(diǎn)標(biāo)記一個(gè)終極符;若有樹(shù)的中間節(jié)點(diǎn)標(biāo)記為A,它有n個(gè)兒子節(jié)點(diǎn)，從左到右標(biāo)記為B1,……,Bn,則G中定存在產(chǎn)生式AB1…Bn;第33頁(yè)，共65頁(yè)，2023年，2月20日，星期四抽象語(yǔ)法樹(shù)(AST)語(yǔ)法分析樹(shù)存在的問(wèn)題包含很多不必要(對(duì)語(yǔ)義分析和代碼生成而言)的節(jié)點(diǎn)抽象語(yǔ)法樹(shù)只包含必要的節(jié)點(diǎn)作為語(yǔ)法分析程序輸出句型(句子):i+i*nP:(1)ET(2)EE+T(3)TF(4)TT*F(5)F(E)(6)Fi(7)Fn第34頁(yè)，共65頁(yè)，2023年，2月20日，星期四第3章outline語(yǔ)法分析概述1.功能需求(輸入，輸出，主要功能)2.分析算法+數(shù)據(jù)結(jié)構(gòu)3.構(gòu)造語(yǔ)法分析器的通用過(guò)程上下文無(wú)關(guān)文法語(yǔ)法分析樹(shù)和抽象語(yǔ)法樹(shù)二義性文法文法變換算法語(yǔ)法錯(cuò)誤處理√√√第35頁(yè)，共65頁(yè)，2023年，2月20日，星期四3.4二義性文法二義性文法(ambiguousgrammar)

如果文法的一個(gè)句子有兩棵或兩棵以上不同的語(yǔ)法分析樹(shù)，則稱該句子是二義性的。

包含二義性句子的文法，稱為二義性文法。第36頁(yè)，共65頁(yè)，2023年，2月20日，星期四二義性文法的例子P:ExpExp+ExpExpExp–ExpExpExp*ExpExpExp/ExpExp(Exp)ExpidExpnumid+id*id第37頁(yè)，共65頁(yè)，2023年，2月20日，星期四

<Stm>if<Exp>then<Stm>else<Stm> <Stm>if<Exp>then<Stm> <Stm>......假設(shè)有條件語(yǔ)句

ife1thenife2thens1elses2則可有下圖所示的兩棵不同的語(yǔ)法分析樹(shù)：

if語(yǔ)句的二義性ififthen<Stm><Stm><Stm><Stm>elsethen<Exp><Exp>e1e2s1s2<Stm><Stm><Stm><Stm>elsethenifthenif<Exp><Exp>e1e2s1s1第38頁(yè)，共65頁(yè)，2023年，2月20日，星期四二義性文法(ambiguousgrammar)二義性會(huì)給語(yǔ)法分析帶來(lái)不確定性，應(yīng)盡量避免寫(xiě)出二義性的文法。但有時(shí)用二義性文法定義語(yǔ)法結(jié)構(gòu)更簡(jiǎn)單直觀。文法二義性問(wèn)題是不可判定的，也就是不存在一種算法，能在有限步內(nèi)確切的判定一個(gè)文法不是二義性文法。若要證明文法是二義性的，只要舉出一個(gè)有兩棵以上語(yǔ)法分析樹(shù)的句子即可。若能控制文法的二義性，即加入人為的附加條件，則二義文法的存在并非壞事，有時(shí)二義性文法可以簡(jiǎn)化文法的表示。消除文法二義性的常用方法

1、規(guī)定符號(hào)的優(yōu)先級(jí)

2、規(guī)定符號(hào)的結(jié)合性第39頁(yè)，共65頁(yè)，2023年，2月20日，星期四表達(dá)式的無(wú)二義性文法有二義性的表達(dá)式文法:ExpExp+ExpExpExp–ExpExpExp*ExpExpExp/ExpExp(Exp)ExpidExpnum無(wú)二義性的表達(dá)式的文法：ETEE+T|E-TTFTT*F|T/FF(E)FidFnum第40頁(yè)，共65頁(yè)，2023年，2月20日，星期四If語(yǔ)句的無(wú)二義性文法定義

StmtMatched_stmt|Unmatched_stmtMatched_stmtifEthenMatched_stmtelseMatched_stmt|otherUnmatched_stmtifEthenStmt|ifEthenMatched_stmt

elseUnmatched_stmt第41頁(yè)，共65頁(yè)，2023年，2月20日，星期四第3章outline語(yǔ)法分析概述1.功能需求(輸入，輸出，主要功能)2.分析算法+數(shù)據(jù)結(jié)構(gòu)3.構(gòu)造語(yǔ)法分析器的通用過(guò)程上下文無(wú)關(guān)文法語(yǔ)法分析樹(shù)和抽象語(yǔ)法樹(shù)二義性文法文法變換算法語(yǔ)法錯(cuò)誤處理√√√√第42頁(yè)，共65頁(yè)，2023年，2月20日，星期四文法變換有些語(yǔ)法分析方法要求被分析的文法滿足一定的約束條件，當(dāng)被分析的文法不滿足這些條件時(shí)，常常要進(jìn)行文法變換。文法變換必須保證變換前后的兩個(gè)文法G1和G2是等價(jià)的，即L(G1)=L(G2)常用文法變換方法增補(bǔ)文法去除空產(chǎn)生式消除無(wú)用產(chǎn)生式消除特型產(chǎn)生式消除公共前綴消除左遞歸(直接，間接)第43頁(yè)，共65頁(yè)，2023年，2月20日，星期四文法變換算法（1）何時(shí)需要增補(bǔ)：在自底向上(bottomtoup)的語(yǔ)法分析方法中，要求文法開(kāi)始符不能出現(xiàn)在產(chǎn)生式的右部.否則，需要對(duì)文法進(jìn)行增補(bǔ)。變換方法：在原產(chǎn)生式基礎(chǔ)上，增加一條產(chǎn)生式：ZS，S為原文法的開(kāi)始符，Z為增補(bǔ)文法的開(kāi)始符第44頁(yè)，共65頁(yè)，2023年，2月20日，星期四文法變換算法（2）文法中空產(chǎn)生式的存在常常給語(yǔ)法分析帶來(lái)困難，因此最好將空產(chǎn)生式消除掉。變換依據(jù)：文法G中除了S以外的空產(chǎn)生式(A)可以消除;

變換方法：找出所有可以推導(dǎo)出的非終極符,記為S;對(duì)于所有產(chǎn)生式AX1X2……Xi-1XiXi+1……XnXiS增加AX1X2……Xi-1Xi+1……Xn直到?jīng)]有新的產(chǎn)生式產(chǎn)生刪除對(duì)應(yīng)空產(chǎn)生式,除了S不可以刪除第45頁(yè)，共65頁(yè)，2023年，2月20日，星期四消除空產(chǎn)生式的例子S|AaBBABB|aB|bS={S,B,A}ABABB

SaBBSAaBB

SAaBSAaSa

SaB

變換后得到的文法：S|AaBB|aBB|AaB|aB|Aa|aABB|B|aBb第46頁(yè)，共65頁(yè)，2023年，2月20日，星期四文法變換算法（3）無(wú)用產(chǎn)生式:A,A不出現(xiàn)在任何句型中;消除方法：關(guān)鍵是找到這樣的非終極符，how?生成會(huì)出現(xiàn)在句型中的非終極符集合SSSS={S}SiSS,Si1,……,Sin把1,……,n中的所有非終極符加入SS中;重復(fù)直到?jīng)]有新的非終極符加入;不屬于SS的非終極符,它們的產(chǎn)生式是無(wú)用產(chǎn)生式,刪除掉;第47頁(yè)，共65頁(yè)，2023年，2月20日，星期四消除無(wú)用產(chǎn)生式的例子S|AaBBABB|aB|bCcSS={S}SS={S,A,B}SS={S,A,B}Cc是無(wú)用產(chǎn)生式第48頁(yè)，共65頁(yè)，2023年，2月20日，星期四文法變換算法（4）特型產(chǎn)生式:AB消除算法對(duì)每個(gè)非終極符A,構(gòu)造SA={B|A+B,BVN}如果CSA,而且C不是特型產(chǎn)生式,則增加A;刪除特型產(chǎn)生式;刪除無(wú)用產(chǎn)生式;第49頁(yè)，共65頁(yè)，2023年，2月20日，星期四消除特型產(chǎn)生式的例子S|AAB|aBbSS={A,B}SA={B}SaSbAbS|a|bAa|bBbSB={}第50頁(yè)，共65頁(yè)，2023年，2月20日，星期四文法變換算法（5）消除公共前綴(leftfactoring)公共前綴A1|…|n|1|…|m提取公因子AA’|1|…|mA’

1|…|n第51頁(yè)，共65頁(yè)，2023年，2月20日，星期四文法變換算法（6-1）消除左遞歸(leftrecursion)

遞歸分為直接左遞歸和間接左遞歸直接左遞歸:A

A1|…|An|1|…|m消除方法:A1A’|…|mA’A’

1A’|…|nA’|第52頁(yè)，共65頁(yè)，2023年，2月20日，星期四消除左遞歸的例子P:(1)ET(2)EE+T(3)TF(4)TT*F(5)F(E)(6)Fi(7)Fn

ETE’E’+TE’|

EE+T|T

=+T1=T第53頁(yè)，共65頁(yè)，2023年，2月20日，星期四文法變換算法（6-2）消除左遞歸(leftrecursion)間接左遞歸:

消除方法:非終極符排序消元法

SAb

ASa|b

1:S2:AAAba|bAbA’A’baA’|第54頁(yè)，共65頁(yè)，2023年，2月20日，星期四文法變換算法（6-2）消除左遞歸(leftrecursion)間接左遞歸:

消除方法:非終極符排序消元法

SQc|

cQRb|b

RSa|a

1:R2:Q3:SRSa|aQRb|bSab|ab|bSQc|cSabc|abc|bc|cS(abc|bc|c)S’S’abcS’|第55頁(yè)，共65頁(yè)，2023年，2月20日，星期四文法變換算法（6-2）消除左遞歸(leftrecursion)間接左遞歸:

排序不同，變換后文法也不同

SQc|

cQRb|b

RSa|a

1:S2:Q3:RSQc|cQRb|bRSa|a(Qc|c)a|aQca|ca|a

(Rb|b)ca|ca|a

SQc|cQRb|bR(bca|ca|a)R’R’bcaR’|第56頁(yè)，共65頁(yè)，2023年，2月20日，星期四第3章outline語(yǔ)法分析概述1.功能需求(輸入，輸出，主要功能)2.分析算法+數(shù)據(jù)結(jié)構(gòu)3.構(gòu)造語(yǔ)法分析器的通用過(guò)程上下文無(wú)