用于消除語法分析沖突的YACC文法變換模式

1、用于消除語法分析沖突的YACC文法變換模式摘要：YACC是Unix/Linux上一個(gè)用來生成編譯器的編譯器（編譯器代碼生成器）。YACC生成的編譯器主要是用C語言寫成的語法解析器（Parser），需要與詞法解析器Lex一起使用，再把兩部份產(chǎn)生出來的C程序一并編譯。YACC本來只在Unix系統(tǒng)上才有，但現(xiàn)時(shí)已普遍移植往Windows及其他平臺(tái)。 本文分析了使用LAI R(1)分析程序生成系統(tǒng)YACC時(shí)經(jīng)常遇到的語法分析沖突問題及消除語法。分析沖突的策略，總結(jié)了一組文法變換模式，利用這些模式可以有效地解決語法分析沖突閹題。關(guān)鍵詞： YACC 語法分析 沖突文法變換 模式引言YACC(Yet Ano

2、ther Compiler Compiler)是美國(guó)貝爾實(shí)驗(yàn)室著名的編譯程序生成系統(tǒng)，用于開發(fā)以字符流輸入的，語法制導(dǎo)的軟件，如計(jì)算機(jī)語言的編(翻)譯程序、解釋程序、程序理解和白盒測(cè)試工具、語法制導(dǎo)的編輯器等近年來許多利用YACC的開發(fā)工作均指出了消除語法分析沖突的困難性，如開發(fā)CC+程序理解工具的前端_2 J、Fortran95至C+的翻譯程序、測(cè)試及測(cè)試控制標(biāo)記語言TTCN-3的語法分析程序L4 J、硬件描述語言VHDL的分析程序等本文借鑒軟件設(shè)計(jì)模式的研究方法，總結(jié)出7個(gè)用于消除語法分析沖突的文法變換模式下面介紹文中用到的幾個(gè)基本概念和有關(guān)約定一、概念和約定在本文中，術(shù)語“YACC”代表

3、采用u也R(1)分析方法的一大類語法分析程序生成系統(tǒng)，包括貝爾實(shí)驗(yàn)室的YACC“、自由軟件基金會(huì)(GNU)的BiSo一6 J及它們的所有變體，乙虬R(1)分析方法屬于移進(jìn)歸約分析方法所謂移進(jìn)，是指分析棧中移人新的終結(jié)符號(hào)歸約是指用一條產(chǎn)生式的左部符號(hào)替換若干個(gè)棧頂符號(hào)，出棧符號(hào)的數(shù)目取決于產(chǎn)生式右部的長(zhǎng)度文法的LALR(1)分析表記錄了當(dāng)分析器的狀態(tài)為s，當(dāng)前面臨的輸入符號(hào)為t時(shí)應(yīng)該執(zhí)行的分析動(dòng)作如果分析表的一個(gè)人口中記錄了兩個(gè)不同的分析動(dòng)作，則稱該文法包含一個(gè)語法分析突分析沖突有兩種：移進(jìn)一歸約沖突和歸約一歸約沖突，一個(gè)文法是LALR(1)文法，當(dāng)且僅當(dāng)它的LAI R(1)分析表中不含語法分

4、析沖突“UR(1)文法屬于無歧義的上下文無關(guān)文法子類若一個(gè)文法是歧義的。那么它的LALR(1)分析表一定含有語法分析沖突有關(guān)上下文無美文法、LR分析方法和YACC的知識(shí)，可參考編譯原理教材，如1或7在下文列舉的文法范例中，約定首字母大寫的英文字符串表示文法的非終結(jié)符號(hào)，全小寫的英文字符串代表文法的終結(jié)符號(hào)二、 YACC的沖突消除規(guī)則現(xiàn)今的程序設(shè)計(jì)語言的語法主要是采用上下文無關(guān)文法描述的，但是上下文無關(guān)文法并非能夠描述計(jì)算機(jī)語言的全部語法結(jié)構(gòu)，例如，C+、VHDL等語言的語法明顯帶有上下文相關(guān)性用YACC開發(fā)這些語言的分析器不可避免地會(huì)存在語法分析沖突另一方面，語言的設(shè)計(jì)者在設(shè)計(jì)一個(gè)語言的文法時(shí)

5、一般不考慮它的分析程序如何構(gòu)造，而是為了理解和維護(hù)語言的語義而設(shè)計(jì)如此設(shè)計(jì)出的文法稱為語義文法(semantic grammar)“標(biāo)準(zhǔn)”語言的文法可以從該語言的語言參考手冊(cè)中獲得，這樣得到的文法往往是歧義文法帶有歧義的語義文法需要被改寫為無語法分析沖突的分析文法(parsing grammar)，才能用來開發(fā)語言的分析程序?qū)τ陂_發(fā)者自定義的語言，特別是許多領(lǐng)域?qū)Ｓ谜Z言(domainspecificlanguage)，需要由開發(fā)者自行設(shè)計(jì)它們的文法，消除語法分析沖突YAcc支持用戶自定義上下文無關(guān)的消歧規(guī)則，用于消除語法分析沖突，所謂上下文無關(guān)的消歧規(guī)則，是指這種規(guī)則不依賴于被分析程序的上下文

6、環(huán)境果沒有在YACC的輸入文法規(guī)范中指定文法符號(hào)的優(yōu)先級(jí)和結(jié)合性，YACC將采用默認(rèn)規(guī)則消除所有的沖突：(1)遇到移進(jìn)一歸約沖突對(duì)選擇移進(jìn)；(2)遇到歸約一歸約沖突時(shí)按照在文法規(guī)范中先聲明的產(chǎn)生式歸約上述默認(rèn)規(guī)則認(rèn)為移進(jìn)動(dòng)作的優(yōu)先級(jí)總是高于歸約動(dòng)作，先聲明的產(chǎn)生式的優(yōu)先級(jí)總是高于后聲明的產(chǎn)生式，優(yōu)先級(jí)的高低與發(fā)生沖突時(shí)被分析程序的上下文無關(guān)所以默認(rèn)規(guī)則也是上下文無關(guān)的消歧規(guī)則理論上已經(jīng)證明，能用上下文無關(guān)的消歧規(guī)則解決的語法分析沖突，利用文法的等價(jià)變換也能解決，例如，圖1左側(cè)所示的簡(jiǎn)單表達(dá)式文法是一個(gè)歧義文法對(duì)輸入句子identify+identifyidentify，該文法的I，AIR(1)

7、分析器讀入串identify+identify后，有兩種可能的分析動(dòng)作：按產(chǎn)生式ExprExpr+Expr歸約，或移進(jìn)一個(gè)新的符號(hào)“*”如果在文法規(guī)范中指定“*”號(hào)的優(yōu)先級(jí)高于“十”號(hào)，便可消除該文法的歧義即使不規(guī)定優(yōu)先級(jí)，這個(gè)文法也可以被等價(jià)變換為圖1右側(cè)所示的無歧義文法總而言之，使用YACC等常用的確定性分析程序生成系統(tǒng)，文法變換是主要的并且是最強(qiáng)的語法分析沖突消除手段三、文法變換模式形式語言理論告訴我們，上下文無關(guān)文法的等價(jià)性、文法的歧義性都是不可判定問題也就是說，任給一個(gè)文法G，不存在一個(gè)算法能夠判斷G是否為一個(gè)無歧義的上下文無關(guān)文法，也不存在這樣的算法：該算法能夠?qū)自動(dòng)變換為G，使

8、得G為一個(gè)無歧義的文法且L(G)=L(G)實(shí)踐中，人們只能運(yùn)用那些經(jīng)過驗(yàn)證的文法變換經(jīng)驗(yàn)和技巧消除語法分析沖突設(shè)計(jì)模式是軟件工程領(lǐng)域的研究熱點(diǎn)，它記錄、提煉存在于軟件開發(fā)人員頭腦中反復(fù)出現(xiàn)的特定上下文中的共性問題及其經(jīng)過多次驗(yàn)證的成功解將3個(gè)文法變換技巧命名為3個(gè)I AIR(1)等價(jià)變換模式，但是沒有給出進(jìn)一步的定義和說明結(jié)合長(zhǎng)期以來的實(shí)踐經(jīng)驗(yàn)，我們將常用語法沖突消除技巧進(jìn)一步總結(jié)為7個(gè)文法變換模式模式的描述問題一直是模式研究的重點(diǎn)使用形式化的記號(hào)表示模式的名稱和解決方案，以便能夠被計(jì)算機(jī)自動(dòng)識(shí)別和抽取；用面向人的自然語言描述模式要解決的問題、問題出現(xiàn)的上下文和應(yīng)用實(shí)鍘，以便于交流和理解首先來

9、看最常用的關(guān)鍵字模式關(guān)鍵字(keyword)模式消除語法分析沖突的通用方法是在語言中增加終結(jié)符作為保留的關(guān)鍵字記為：introduce(keyword，X)，其含義是為文法符號(hào)x定義的語言增加一個(gè)保留的關(guān)鍵字keyword作為文法的終結(jié)符號(hào)，語法分析程序生成系統(tǒng)的一個(gè)重要應(yīng)用是支持軟件項(xiàng)目和組織中的普通開發(fā)人員設(shè)計(jì)和實(shí)現(xiàn)領(lǐng)域?qū)Ｓ谜Z言。也稱小語言(microlanguage或little language)關(guān)鍵字模式改變了語言的定義。用于在語言設(shè)計(jì)中避免語法分析沖突，圖2中的條件語句文法是歧義的，該文法關(guān)于句子ii exprl then if expr2 then stintl else stm

10、t2有兩棵不同的分析樹增加一個(gè)保留的關(guān)鍵宇endit"，不僅可以消除文法的歧義，還可以使文法變得清晰直觀加寬(widen)模式用語言范圍更“寬”的文法符號(hào)替換語言范圍較“窄”的文法符號(hào)，常常可以消除語法分析沖突widen模式記為：widen(r，X。珥玎"，Xb。叫)該式的含義是產(chǎn)生式r右部 被另一個(gè)符號(hào)Xb，“替換，L(xb)蘭L(Xnarrow)圖3給出了用widen模式消除Java文法的一個(gè)歸約一歸約沖突的實(shí)例widen模式擴(kuò)充了文法定義的語言有時(shí)文法的等價(jià)變換難以消除語法分析沖突。可以嘗試擴(kuò)充待分析的語言，在語義處理階段進(jìn)一步執(zhí)行合法性檢查，縮小分析程序接受的語言范

11、圍，保持語言的原始定義如果分析程序的輸人事先經(jīng)過錯(cuò)誤處理，則分析程序接受的語言范圍可以擴(kuò)大軟件再(逆向)工程工具一般要求被分析的程序必須事先正確通過編譯，待分析程序的語法錯(cuò)誤已經(jīng)在編譯階段被發(fā)現(xiàn)和糾正因此，即使工具前端接受的語言范圍被適當(dāng)擴(kuò)大，一般也不會(huì)對(duì)后端應(yīng)用造成顯著影響。優(yōu)先級(jí)(precedence)模式為產(chǎn)生式和文法符號(hào)設(shè)置優(yōu)先級(jí)和結(jié)合性，消除文法歧義優(yōu)先級(jí)和結(jié)合性是語言的設(shè)計(jì)者給出的，通常只在語言參考手冊(cè)或語言設(shè)計(jì)者規(guī)定了符號(hào)優(yōu)先級(jí)時(shí)才能應(yīng)用優(yōu)先級(jí)模式記為：precedence(z(a_e-SOC。)>y(asso)其含義是規(guī)定文法符號(hào)(產(chǎn)生式)的相對(duì)優(yōu)先級(jí)和符號(hào)的結(jié)合性詞法反

12、饋(1exical feedback)模式讓詞法分析程序區(qū)分歧義的語法成分，將消除語法分析沖突的任務(wù)從語法分析階段前移至詞法分析階段詞法反饋模式記為：lexicalfeedbaek(X，。1，5C2，zH)上式的含義是將一個(gè)引起歧義的終結(jié)符號(hào)或非終結(jié)符號(hào)x區(qū)分為n種可能的終結(jié)符號(hào)z1，5c2，z。，由詞法分析程序決定X的詞法解釋，詞法反饋模式的應(yīng)用范圍很廣舉一個(gè)例子，一些早期的計(jì)算機(jī)語言中關(guān)鍵字不是保留字，標(biāo)識(shí)符可以與關(guān)鍵字取相同的名字例如在PL1語言中，下列語旬是合法的條件語句s】：ifif=thenthenthen=if如果不區(qū)分if的詞法解釋，將會(huì)產(chǎn)生語法分析沖突可將if和then區(qū)分為

13、“關(guān)鍵字(keyword)”和“標(biāo)識(shí)符(identify)”；每遇到個(gè)if或then，讓詞法分析程序根據(jù)上下文返給語法分析程序關(guān)鍵字或標(biāo)識(shí)符內(nèi)嵌(inline)模式。inline模式用于減少分析方法展望的符號(hào)個(gè)數(shù)，使LALR(m)文法(m>1)等價(jià)變換為L(zhǎng)ALR(n)文法(n<m)，記為：inline(r，x，l，72，rn)上式中，非終結(jié)符號(hào)x出現(xiàn)在產(chǎn)生式r的右部，r1'r2，靠是定義x的其它產(chǎn)生式。用rl，r2，h右部的非終結(jié)符號(hào)替換r右部的X，往往可以消除語法分析沖突inline模式不應(yīng)改變語言的定義，圖4給出用inline模式消除移迸一歸約沖突的例子消除產(chǎn)生式是in

14、line模式的一個(gè)重要應(yīng)用e產(chǎn)生式的存在經(jīng)常引起移進(jìn)一歸約沖突利用inline模式可以消除由e產(chǎn)生式引起的語法分析沖突，圖5給出一個(gè)例子提因子(factor)模式factor模式將多條產(chǎn)生式的相同右部或右部相同的部分作為公因子提取出來，用另一個(gè)文法符號(hào)表示，并用這個(gè)符號(hào)替換上層產(chǎn)生式的右部符號(hào)，記為：factor(rl，72，R)其中，rl和r2是左部符號(hào)不同的兩條產(chǎn)生式，且它們的右部完全相同或部分相同R是被替換了右部符號(hào)的某一上層產(chǎn)生式歸約一歸約沖突在大多數(shù)情況下預(yù)示著文法的設(shè)計(jì)存在嚴(yán)重缺陷【1“factor模式用于消除歸約一歸約沖突，并且常與inline模式結(jié)合使用Factor模式不應(yīng)改變

15、文法定義的語言，圖6給出了factor模式的應(yīng)用實(shí)例：消除了由Boyschris和Girlschris引超的歸約一歸約沖突在文法被重構(gòu)之前，ch“s即可以是男孩，也可以是女孩文法的設(shè)計(jì)顯然存在缺陷，默認(rèn)(default)模式不改變文法，讓分析程序生成系統(tǒng)根據(jù)默認(rèn)的消歧規(guī)則解決沖突在某些情形下默認(rèn)規(guī)則恰好符合語言規(guī)約例如，ISOIEC C+標(biāo)準(zhǔn)規(guī)定：“else總是與它前面最近的if匹配成一個(gè)條件語句”這相當(dāng)于規(guī)定遇到“懸掛else7，'沖突時(shí)一律選擇移進(jìn)動(dòng)作開發(fā)者應(yīng)將有關(guān)的消歧規(guī)則注釋在文法規(guī)范中，否則文法規(guī)范將難以理解和維護(hù)Default模式可記為：default(r，s，ref)或default(r1，2，ref)該式的含義是：由產(chǎn)生式r和符號(hào)s(或由產(chǎn)生式r1和72)引起的移進(jìn)一歸約(或歸約一歸約)沖突由語法分析程序生成系統(tǒng)默認(rèn)的消歧規(guī)則解決，ref指出消歧規(guī)則的依據(jù)，如語言參考手冊(cè)中有關(guān)的消歧規(guī)則所在的章節(jié)號(hào)四、結(jié)束語YACC,Bison的應(yīng)用非常廣泛，是語法分析程序生成系統(tǒng)事實(shí)上的工業(yè)標(biāo)準(zhǔn)，被絕大多數(shù)編譯原理教材列為必修內(nèi)容在長(zhǎng)期使用娶渡m開發(fā)程序分析、理解、度量和泌