呼叫上次實驗編寫的詞法分析程式,實現「類pascal語言子集」的語法分析功能。該語言的語法元素包括以下幾條:
●程式開始符號:program ***
●變數定義:varint/string a,b,c, …
●賦值語句:x:=a*(b+c); …
●復合語句:以begin … end作為開始和結束的語句
●分支語句:if… then,if … then … else
●迴圈語句:while… do
本次實驗使用自上而下的語法分析方法,其實現的語法分析程式應能準確識別上述語法元素。鑑於還沒有完成語義分析程式,故可以通過輸出相應的提示資訊來表明語法分析的正確性。程式應能識別出各種語法錯誤,並對錯誤所在的行列編號進行較準確的提示。
(1) 理解語法分析在編譯過程中的作用、輸入以及輸出,學習它與編譯器其他模組之間的協作關係。
(2) 掌握語法分析的兩類基本方法:自上而下的分析與自下而上的分析。並通過對自上而下的語法分析的編碼實現,理解其執行過程以及相關限制。
通過對待分析語言的語法進行分析後可知,該語言的語法符合上下文無關文法的基本要求,可以用它來進行描述。另外,由於要使用自上而下的語法分析方法進行程式設計,因此要使得該文法盡可能符合ll(1)文法的基本要求。最後得到的文法如下所示:
(帶下劃線的是終結符)
p→program label;def**uls.
defs→vardefst;defs|ε
defst→intdefvars|stringdefvars
defvars→label defvarslast
defvarslast→, label defvarslast|ε
muls→begin ss end
ss→expr ; ss|ε
expr→sa|sif|sw
sa→label:=alg
alg→algmdalgpm
algpm→+alg|-alg|ε
algmd→labelalgre|numberalgre|conststringalgre|(alg) algre
algre→*algmd|/algmd|ε
bool→boolnotboolao
boolao→and bool|orbool|ε
boolnot→not boolre|boolre
boolre→(bool)|algboolrem|true|false
boolrem→>alg|=alg|<=alg|<>alg
sif→if bool then iff
iff→expr ifl|muls ifl
ifl→ε|else siml
siml→expr|muls
sw→while bool do siml
事實上,針對該語言的文法並不唯一,上述文法在某些方面也並不符合ll(1)文法的要求。但是,這種寫法的好處是,該文法是消除了左遞迴的,並且大多數非終結符號都有明確的語法含義,這對於語法結構的識別與報錯是十分有利的。該文法的部分非終結符號的含義如下所示:
在寫出了描述語法的文法之後,下一步,需要構建**分析表,供自上而下語法分析程式使用。在此之前,需要計算該文法的first集以及follow集。求解如下:
(注意:如果first集裡沒有,那麼follow將沒有必要計算,用/表示)
由上表提供的資訊,結合文法表示式,就可以得出**分析表了。該錶如下所示:
由上表可見,在boolre和ifl處均出現了多重入口的現象。這表明上述文法不是ll(1)文法。在程式實現部分,本文對程式進行了特別處理,從而保證了自上而下的語法分析可以進行下去。
本語法分析器遵循自上而下語法分析的基本演算法。其核心思想是將每個非終結符組織成函式的形式,並在每個函式中依據相應的產生式右部的符號串行,對讀進的符號串進行匹配。如果在產生式右部遇到終結符,那麼新讀進的符號必須與該終結符一致;如果遇到非終結符,那麼則根據**分析表,呼叫相應的非終結符對應的函式繼續匹配。
如果不能滿足以上兩點,則認為源程式出現了語法錯誤。演算法的流程圖如下所示:
本語法分析器使用c#語言編寫,在windows 7 + visual studio 2010下開發完成。
語法分析器以詞法分析器的輸出作為其輸入。而語法分析器的輸出又會作為語義分析的輸入。為了實現這種結構,乙個比較簡單的方法是先執行詞法分析器,得到其輸出檔案,在將此檔案作為語法分析器的輸入。
不過,這樣使得語法分析需要掃瞄原始檔兩遍,效率較低。本文採用另一種策略,即以語法分析器為中心,在需要時呼叫詞法分析器取得輸入,並在恰當的時候呼叫語義分析器輸出。
當然,本次實驗並未完成語義分析,而是用一條提示文字表明語法元素已經識別,可以開始語義分析了。
為了體現以語法分析為中心的結構,必須對上次實驗完成的詞法分析器加以改造。改造專案如下所示。
●新增advance函式
該函式的主要作用是每執行一次,便從原始檔中取得乙個詞法元素加以分析。為了提高效率,這裡使用了緩衝機制。其核心**如下所示:
publiclexnode advance()
●修改詞法輸出
之前的詞法分析器輸出乙個二元組。但是為了準確報出語法錯誤,還要提供詞法元素的行號和列號。這樣詞法分析器的輸出就變成了四元組。核心**如下:
privatevoid output(string type, string content, int col)
, >", type, content));
lexnodetmp = newlexnode();
tmp.type = type.toupper();
= content;
tmp.line = linecode;
tmp.x = col;
lexbuf.enqueue(tmp);
} ●新增乙個用於超前搜尋的函式
下面將會看到,為了解決**分析表中多重入口的問題,本程式採用的超前搜尋的技術。這就要求詞法分析器對其提供支援。以下是乙個函式的示例,它用來查詢第乙個可以用來區分布林表示式和算術表示式的詞法元素:
publiclexnodefirstentity() //超前搜尋
{inti = 0;
while (true)
if (i>=
if (!sr.endofstream)
數值分析實驗報告 樣例
日期 2006.9.20 學號 2314130 班級信科41 姓名劉建煒 實驗課題 捨入誤差對計算的影響 數值微分精度與步長的關係 實驗目標 1.理解數值計算中的兩類主要誤差的概念 截斷誤差與捨入誤差。2.初步了解 演算法的選擇帶來不同的截斷誤差,從而使得計算結果的精度不同。3.初步體會捨入誤差對計...
實驗二遞迴下降語法分析
實現乙個遞迴下降語法分析程式,識別使用者輸入的算術表示式。1 文法如下 ete e te te tft t ft ft f e i 2 求取各非終結符的first及follow集合 3 程式設計實現下降遞迴分析法,識別從鍵盤輸入的關於整數或浮點數的算術表示式 在此,上述文法中的i代表整數或浮點數 4...
實驗報告規範及樣例
資料結構 是一門實踐性很強的軟體基礎課程,上課講授可以使學生對資料結構和演算法有一定了解,但為了學好這門課,每個學生必須完成一定數量的上機實驗作業。上機實驗可使學生深刻理解各種邏輯結構 儲存結構的特性。上機實驗是對學生的一種全面綜合訓練,是與課堂聽講 自學和練習相結合的乙個必要教學環節。實驗題中所要...