朱朝霞

摘要：棧在計(jì)算機(jī)科學(xué)領(lǐng)域具有廣泛的應(yīng)用，正確理解語法分析中棧的原理對(duì)數(shù)據(jù)結(jié)構(gòu)中線性結(jié)構(gòu)的應(yīng)用以及編譯程序的教學(xué)具有重要意義。

關(guān)鍵詞：棧；后進(jìn)先出；語法分析；編譯器

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）17-0067-02

1概述

在計(jì)算機(jī)算法與數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)中，棧（stack）是一種非常重要的線性結(jié)構(gòu)，而棧是限定僅在表尾進(jìn)行插人和刪除操作的一種線性表。在棧中，允許進(jìn)行插人和刪除的一端稱為棧頂，不允許插入和刪除的一端稱為棧底，棧的修改是按后進(jìn)先出的原則進(jìn)行的，因此棧又稱為后進(jìn)先出的線性表，簡稱LIFO線性表。

棧在計(jì)算機(jī)科學(xué)領(lǐng)域具有廣泛的應(yīng)用，如求表達(dá)式的值及遞歸到非遞歸，只要問題滿足后進(jìn)先出原則，均可使用棧作為其數(shù)據(jù)結(jié)構(gòu)。在計(jì)算機(jī)系統(tǒng)軟件中，各種高級(jí)語言的編譯系統(tǒng)也離不開棧的使用，比如利用棧進(jìn)行語法檢查、函數(shù)的調(diào)用等，本文以棧在編譯程序語法分析的應(yīng)用為主線，對(duì)棧進(jìn)行剖析，希望對(duì)計(jì)算機(jī)相關(guān)課程的教學(xué)與應(yīng)用有所啟示。

2編譯程序的語法分析方法

編譯程序是現(xiàn)代計(jì)算機(jī)系統(tǒng)的基本組成部分，其基本任務(wù)是將源語言程序翻譯成等價(jià)的目標(biāo)語言程序。其中語法分析（syntax analysic）是編譯程序的核心部分，其功能是以詞法分析器生成的單詞符號(hào)序列作為輸入，根據(jù)語言的語法規(guī)則，識(shí)別出各種語法成分，并在分析過程中進(jìn)行語法檢查，檢查所給單詞符號(hào)序列是否是該語言文法的正確句子。在編譯程序中，常用的語法分析方法有：預(yù)測(cè)分析法、遞歸子程序法、算符優(yōu)先分析法、LR分析法。而各種語法分析方法中都使用了相應(yīng)的分析算法結(jié)合棧進(jìn)行語法分析。

2.1預(yù)測(cè)分析法

預(yù)測(cè)分析法是一種高效的自頂向下的語法分析方法，預(yù)測(cè)分析程序采用表驅(qū)動(dòng)的方式來實(shí)現(xiàn)，具有一個(gè)輸入緩沖區(qū)、一個(gè)先進(jìn)后出棧、一張預(yù)測(cè)分析表和一個(gè)輸出流。

預(yù)測(cè)分析程序的總體結(jié)構(gòu)如下圖：

從以上算法可知，預(yù)測(cè)分析程序是根據(jù)棧頂符號(hào)X和當(dāng)前輸入符號(hào)a來決定語法分析器的動(dòng)作，從而進(jìn)一步進(jìn)行語法分析。其中分析棧用來存放句型分析過程中動(dòng)態(tài)產(chǎn)生的文法符號(hào)序列，開始時(shí)，把識(shí)別符號(hào)置于分析棧頂，每當(dāng)分析棧頂是非終結(jié)符號(hào)，展開時(shí)把它出棧，然后按逆序下推入展開的規(guī)則的右部各個(gè)符號(hào)，因而，分析棧記錄了分析活動(dòng)經(jīng)歷。編譯程序的預(yù)測(cè)分析語法分析法的優(yōu)點(diǎn)是效率高、便于維護(hù)而且可以自動(dòng)生成。

2.2遞歸子程序法

遞歸子程序法是比較簡單直觀易于構(gòu)造的一種語法分析方法，是一種無回溯的自頂向下分析技術(shù)，其實(shí)現(xiàn)思想是讓相應(yīng)的識(shí)別程序由一組子程序組成，每個(gè)子程序的功能是識(shí)別由該非終結(jié)符推出的串，當(dāng)某非終結(jié)符的產(chǎn)生式有多個(gè)候選時(shí)能夠按LL（1）形式唯一地確定選擇某個(gè)產(chǎn)生式進(jìn)行推導(dǎo)。由于遞歸子程序法對(duì)每個(gè)過程可能存在直接或間接遞歸調(diào)用，所以對(duì)某個(gè)過程在退出之前可能又被調(diào)用，通常在入口時(shí)需保留某些信息，出口時(shí)恢復(fù)。遞歸過程遵循先進(jìn)后出規(guī)律，所以通常開辟先進(jìn)后出棧來處理。

采用遞歸下降子程序法構(gòu)造語法分析器的算法步驟如下：

1）構(gòu)造文法G；

2）改造文法G：包括消除文法二義性、消除左遞歸、提取左因子。

3）求每個(gè)產(chǎn)生式的FIRST集和語法變量的FOLLOW集；

4）檢查文法G是不是LL（1）文法，若是按照LL（1）文法繪制語法圖；如果不是LL（1）文法，需要進(jìn)行文法等價(jià)變換，附加新的“信息”。

5）化簡語法圖；按照語法圖為每個(gè)語法變量設(shè)置一個(gè)子程序。

遞歸子程序法實(shí)現(xiàn)思想簡單清晰明了，各子程序的流程圖幾乎就是文法規(guī)則的圖解描述，并且能靈活在各子程序中添加語義處理工作。遞歸子程序法易于手工實(shí)現(xiàn)，許多高級(jí)程序設(shè)計(jì)語言，如C、PASCAL等語言都采用遞歸子程序法。但缺點(diǎn)是對(duì)文法的要求較高，必須是LL（1）文法，且遞歸調(diào)用較多，運(yùn)行速度較慢。

2.2算符優(yōu)先分析法

算符優(yōu)先分析法是仿照算術(shù)表達(dá)式的四則運(yùn)算而提出的一種語法分析文法，其基本思想是將句型中的終結(jié)符當(dāng)作“算符”，通過比較相鄰算符的優(yōu)先次序來確定句型的可歸約串并進(jìn)行歸約。

令S為分析棧，用于存放以寄存歸約或待形成最左素短語的符號(hào)串，k為棧S的深度，工作單元a存放當(dāng)前讀入的終結(jié)符號(hào)，文法G算符優(yōu)先分析法的算法可描述為：

在算符優(yōu)先識(shí)別算法的實(shí)現(xiàn)中，須同時(shí)考慮分析棧的實(shí)現(xiàn)和優(yōu)先關(guān)系的確定，其實(shí)現(xiàn)思想簡單直觀，所需存儲(chǔ)容量小，且速度快被廣泛應(yīng)用于識(shí)別各類表達(dá)式。算符優(yōu)先文法并不適合所有的文法，要求文法必須是滿足算符優(yōu)先文法才能用此方法進(jìn)行語法分析。

2.3 LR分析法

LR分析法是一種自下而上進(jìn)行規(guī)范歸約的語法分析文法。LR分析器的基本原理是將句柄（產(chǎn)生式右部）的識(shí)別過程劃分為若干狀態(tài)，分析器根據(jù)當(dāng)前的狀態(tài)確定是否找到了句柄。

一個(gè)LR分析器由3個(gè)部分組成：總控程序、分析表、分析棧（包括文法符號(hào)棧和相應(yīng)的狀態(tài)棧），分析器的動(dòng)作由棧頂狀態(tài)和當(dāng)前輸入符號(hào)決定是否需向前查看輸入符號(hào)。LR分析器的工作過程如下圖所示：