大學電腦科學與技術學院實驗報告
計算機基礎實驗教學中心編制
成績指導教師（簽字） （存檔）
★ 實驗課程名稱：編譯原理課程設計
★ 實驗專案：ll1語法分析程式開發
★ 實驗儀器：機房計算機
★ 實驗要求：
1 理解ll(1)分析法的主要原理
2 理解ll(1)分析法對文法的要求
3 熟練掌握predict集合的求法
4 通過程式設計熟練掌握ll(1)分析法的工作過程
★ 實驗步驟、分析設計與結果：
一、實驗步驟：
1．構造snl語言的ll(1)分析表
snl語法程式的實現採用手工操作構造ll(1)分析表。ll(1)分析錶用乙個二維矩陣表示，其中每個非終極符對應一行，每個終級符對應一列，乙個非終極符和乙個終極符可以確定矩陣中的乙個元素，元素的值表示該非終極符和該終極符對應的產生式。每個矩陣元素都是乙個整數，所有元素初始化為0；構造ll(1)表時，根據snl語言的文法和各個產生式的predict集，填寫ll(1)分析表的內容。
由於各產生式編號從1開始，所以用編號0表示error。在根據ll(1)分析表選擇產生式進行推導時，若查到的產生式編號為0表示無相應的產生式可選，不匹配錯誤；否則根據編號得到相應的產生式進行推導。
2．snl語法分析的資料結構
snl語言的ll(1)語法分析程式共用到四個棧，分別稱為：符號棧，語法樹棧，操作符棧和運算元棧。其中，符號棧用於進行snl的ll(1)語法分析；其它的棧是為了在語法分析的過程中同時生成與源程式結構對應的語法樹而設。
語法樹棧用於生成宣告部分和語句部分的語法樹；操作符棧和運算元棧用於生成表示式部分的語法樹。
3. 構造驅動程式
構造ll(1)驅動程式的演算法：
1. 分析開始時，首先將標誌符號#和文法開始符號s依次壓入符號棧；輸入流指標指向第乙個輸入符號，即由符號棧和輸入流構成的初始格局為：
s, a1a2...an#)
然後，反覆執行第2步所列的工作。
2. 設在分析的某一步，符號棧及剩餘的輸入流處於如下的格局
x1x2...xm-1xm, aiai+1...an#)
其中，x1x2...xm-1xm為分析過程中所得的文法符號，此時，可視棧頂符號xm的不同情況，分別作如下動作：
● 若xmvn，則以xm及ai組成的符號對(xm，ai)查分析表t。設t(xm，ai)為一產生式，假設是xmuvw，此時將xm從分析棧中退出，並將uvw壓入棧中，從而得到新的格局
x1x2...xm-1wvu, aiai+1...an#)
但若t(xm，ai)=error，則呼叫出錯處理程式進行處理；
● 若xm=ai#，則表明棧頂符號已經與當前掃瞄的輸入符號得到匹配，此時應將xm（即ai）從棧中退出，並將輸入流指標向前移動乙個位置。
● 若xm=ai=#，則表明輸入串已經完全得到匹配，此時即可宣告分析成功而結束分析。
其它情形，轉錯誤處理程式。
4．生成語法分析樹
用語法制導的方式生成語法分析樹時比較複雜，需要用到語法樹棧、操作符棧和運算元棧。
（1）處理宣告部分和語句部分的語法樹生成時，設定乙個語法樹棧，存放語法樹節點中指向兒子或者兄弟節點的指標的位址。在生成當前語法樹節點時，如果以後需要對其兒子節點或者兄弟節點賦值，則按照處理順序的逆序將這些兒子節點或者兄弟節點的指標的位址壓入語法樹棧，後面生成它的兒子節點或者兄弟節點時，只需彈棧，並對相應的指標進行賦值，就可以完成所需的語法樹節點的鏈結。
（2）處理表示式時，需要另外設定兩個棧，運算元棧和操作符棧，遇到運算元壓入運算元棧，遇到操作符，則進行判斷，如果當前操作符的優先順序高於操作符棧的棧頂操作符，直接壓入操作符棧；否則，彈出棧頂操作符，並彈出運算元棧頂的兩個運算元，生成相應的子樹，並對新生成的子樹的父節點（操作符節點）進行迴圈判斷。
二、分工部分
首先，大家先對課本的ll1語法分析部分進行複習，集體進行討論，研讀附帶的**，之後進行分工編寫，完成後進行整合除錯。
丁負責程式的視覺化和圖形檔案介面方面的工作，設計程式框架，編寫驅動程式，構造ll1分析表，部分產生式推導函式，最後將各個函式整合除錯，編寫實驗報告。
張負責設計資料結構，語法樹的處理部分，以及部分產生式推導函式，設計測試用例，測試語法分析程式的功能，修改bug，完善程式功能。
樊負責編寫大部分的產生式推導函式，以及檔案流的讀寫操作。
三、執行結果
我們的程式基本實現了ll1語法分析的功能：
1． 正確例子，輸出語法分析樹
2． 錯誤例子
這裡我們對錯誤的處理，只是在發現第乙個錯誤後就立即報錯，這樣操作實現比較方便，並且可以用更多的時間精力去處理其他的函式完成情況。對於程式設計師來說，第乙個錯誤的提示，其實就能提供最有效的資訊，這樣的處理，不會造成太大的資訊丟失，在一定程度上也是提高了編譯的速度。
1） 錯誤原因：沒有程式名稱
2）錯誤原因：賦值號不對
四、 心得體會：
（1） 通過複習以前的課程和研讀**，自己親自編寫，更深入了解了ll1語法分析的原理及實現過程；
（2） 進一步了解大程式的設計方法，良好的分工與合作是關鍵；
（3） 對老師提供的**進行了修改，運用了stl裡自帶的堆疊進行改寫，在這個過程中，加深了一些相關操作的熟悉程度，並且也使**更簡短易讀，比起原來的鍊錶模擬的堆疊實現，有了一定的提高；
（4） 程式**量大，掌握除錯技巧很重要，對這方面有了更深刻的認識。
編譯原理實驗報告LL 1 分析法
課程編譯原理實驗名稱實驗二 ll 1 分析法 實驗目的 1 掌握ll 1 分析法的基本原理 2 掌握ll 1 分析表的構造方法 3 掌握ll 1 驅動程式的構造方法。一.實驗內容及要求 根據某一文法編制除錯ll 1 分析程式，以便對任意輸入的符號串進行分析。本次實驗的目的主要是加深對 分析ll 1 ...
編譯原理實驗報告
通過編寫和除錯乙個詞法分析程式，掌握在對程式語言的源程式進行掃瞄的過程中，將字元形式的源程式流轉化為乙個由各類單詞符號組成的流的詞法分析方法。語言中具有的單詞包括五個關鍵字begin end if then else 識別符號 整型常數 六種關係運算子 乙個賦值符和四個算術運算子。參考實現方法簡述如...
編譯原理實驗報告
軟體學院驗證性實驗報告 專業 軟體開發 net方向 年級 班級 2010級 2012 2013學年第一學期 1 實驗目的及實驗專案簡介 運用編譯程式，完成下述源程式的編譯，了解源程式的預處理功能 即通過編譯程式，將高階語言程式 源程式 翻譯成低階語言程式 目標程式 源程式的輸入 設源程式如下所示，其...