堆棧在語法分析中的應(yīng)用

張 媛

(天津市河?xùn)|區(qū)職工大學(xué) 天津 300162)

計算機的應(yīng)用中有多種高級語言，把這些高級語言翻譯成對應(yīng)的機器語言，這一過程就是編譯。眾所周知，編譯原理在整個工作過程中通常分為詞法分析、語法分析、語義分析和中間代碼生成，代碼優(yōu)化以及目標(biāo)代碼生成這幾個階段，每一個階段都會實現(xiàn)不同的功能。在整個編譯過程中，堆棧都起著重要的作用，以下將就堆棧在語法分析中的應(yīng)用進(jìn)行說明。

所謂語法分析，就是在詞法分析的基礎(chǔ)上，通過分析輸入串對高級語言的語法結(jié)構(gòu)進(jìn)行分析，分為自上而下的語法分析和自下而上的語法分析兩種方法。

1 自上而下語法分析中堆棧的應(yīng)用

在自上而下的語法分析中，從文法開始符號出發(fā)，利用所有的產(chǎn)生式，通過最左推導(dǎo)，為輸入符號串自上而下地建立一棵語法樹。在消除回溯和直接左遞歸后，即可利用棧來進(jìn)行分析。自上而下語法分析中的一種有效方法是預(yù)測分析法，需要用到總控程序、預(yù)測分析表和一個先進(jìn)后出棧，如圖1所示。

圖1 預(yù)測分析模型圖Fig.1 Forecasting analysis model

在預(yù)測分析法中，棧底中最初存放“#”和文法開始符號，總控程序每次都要根據(jù)棧頂元素和新輸入的符號來進(jìn)行工作，若棧頂元素為終結(jié)符號，則：

①若棧頂元素＝輸入終結(jié)符號≠“#”，則匹配成功，此時將棧頂元素彈出，將指針指向新的輸入符號進(jìn)行分析。②若棧頂元素＝輸入終結(jié)符號＝“#”，說明整個輸入符號串分析完成，結(jié)束分析過程。③若棧頂元素是非終結(jié)符號，則需要查看預(yù)測分析表，找到相應(yīng)的產(chǎn)生式，將棧頂元素彈出后，產(chǎn)生式右部的所有符號按照反序依次壓入堆棧中，形成新的棧頂元素。

假設(shè)有文法 G[S]：S→S＋S│S*S│a，該文法存在直接左遞歸，消除直接左遞歸得到新的文法：S→aS’，S’→＋SS’│*SS’│ε對輸入符號串 a＋a*a 的優(yōu)先分析過程如表1所示，其中棧存放分析過程中出現(xiàn)的文法符號序列。

表1 自上而下語法分析對符號串a(chǎn)＋a*a的分析過程表Tab.1 Table of analysis process for String a＋a*a via topdown syntax analysis

2 自下而上語法分析中堆棧的應(yīng)用

自下而上的語法分析同樣也是要建立一棵語法樹，但它是從葉結(jié)點出發(fā)，利用所有產(chǎn)生式，逐步向上構(gòu)造子樹，直至得到根結(jié)點，也就是文法的開始符號。它的主導(dǎo)思想是“移進(jìn)—規(guī)約”，是推導(dǎo)的逆過程，自上而下分析法是要為輸入符號串找一個最左推導(dǎo)，而自下而上分析法則是要找到輸入符號串的句柄，每次都對句柄進(jìn)行規(guī)約，從而得到一個規(guī)范規(guī)約的過程。自下而上分析法中最常用的就是 LR分析法。在LR分析法中，需要用到LR分析程序、分析表和分析棧，如圖2所示。

圖2 LR分析模型圖Fig.2 LR analysis model diagram

在該模型中，分析棧分為狀態(tài)棧和符號棧兩部分，狀態(tài)棧中存放輸入過程中的不同狀態(tài)，棧頂元素為當(dāng)前狀態(tài)，而符號棧中存放的是現(xiàn)行輸入符號，由當(dāng)前狀態(tài)棧的棧頂元素和現(xiàn)行輸入符號來決定下一個動作。分析棧主要包括4種情況：

① 移進(jìn)。在這種情況下，當(dāng)前輸入符號進(jìn)入符號棧，而下一個輸入符號則變?yōu)楫?dāng)前輸入符號，查action表，將下一狀態(tài)進(jìn)入狀態(tài)棧，作為新的棧頂元素。

② 規(guī)約。按照相應(yīng)的產(chǎn)生式進(jìn)行規(guī)約，若產(chǎn)生式右端共有n個字符，則同時將狀態(tài)棧和符號棧兩個棧頂彈出 n個元素，并將規(guī)約后的符號進(jìn)入符號棧，作為新的棧頂元素，再查goto表，得到新的狀態(tài)進(jìn)入狀態(tài)棧。

③ 接受。根據(jù)輸入符號串進(jìn)行移進(jìn)和規(guī)約操作后，在符號棧中得到了開始符號及“#”號，則分析完成，整個字符串匹配成功。

④ 報錯。除了以上動作外，其余都屬于出錯情況，此時應(yīng)中止分析，調(diào)用出錯處理程序，進(jìn)行出錯處理。

對于文法 G[E]：S→S＋L│L，L→L*M│M，M→(S)│a及輸入符號串 a*a＋a，我們用 LR 分析法的分析過程，如表2所示。

3 結(jié) 論

棧在整個編譯原理的各個過程中都起著重要的作用。進(jìn)行語法分析時，在自上而下分析方法中用來存放分析過程中出現(xiàn)的字符串序列，在自下而上分析法中分為狀態(tài)棧和符號棧，分別存放分析過程中的狀態(tài)及即將輸入的字符串序列。

［1］ 黃賢英，曹瓊，王珂珂. 編譯原理及實踐教程(2版)[M]. 北京：清華大學(xué)出版社，2012.

［2］ 王曉斌，陳文宇. 程序設(shè)計語言與編譯(3版)[M]. 北京：電子工業(yè)出版社，2009.

［3］ 何炎祥，伍春香，王漢飛. 編譯原理[M]. 北京：機械工業(yè)出版社，2010.

［4］ 李文生. 編譯原理與技術(shù)[M]. 北京：清華大學(xué)出版社，2009.

［5］ Alfred V Aho，Monica S，etc.Compilers：Principles，Techniques，and Tools(2,nd ed.)[M]. 北京：機械工業(yè)出版社，2011.