一個編譯原理語法分析器的實現與設計一個編譯原理語法分析器的實現與設計—計算機畢業設計-資料下載頁

【導讀】在編譯原理的教學過程中，算法的講解都需要對算法進行詳細的分析，法的句子的分析過程等，這些過程往往需要占用大量時間來分析、制表等。所謂LL分析法是指語法分析是按自左至右的順序向前查看一個輸入字符串，

　　

【正文】 X ......................................................... IX .......................................................... X 4 特殊問題及解決方法 ...................................................... X4 Select集的求解 ...................................................... XI 問題描述 ........................................................ XI 解決方案 ........................................................ XI 解決結果 ........................................................ XI ListBox添加水平滾動條 ............................................ XI5 問題描述 ....................................................... XI5 解決方案 ....................................................... XI5 解決結果 ...................................................... XII6 5 結果測試 .............................................................. XII6 ....................................................... XII6 ......................................................... XV 結 論 ................................................................ XVI0 參考文獻 .............................................................. XVI0 致 謝 ............................................................... XVII1 聲 明 .............................................................. XVIII2 第 1 頁 共 22 頁 1 引言 項目背景 編譯原理是計算機專業中最難的一門課程 ,在理論上它要求學生掌握有關形勢語言和自動機的抽象概念 ,在技術上要求學生能夠熟練地利用各種數據結構進行編程。 編譯程序是現代計算機系統的基本組成部分之一。編譯程序一般由詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序、目標代碼生成程 序、代碼優化程序、表格管理程序和出錯處理程序等成分構成。 在編譯原理的教學過程中，語法和語義分析階段關于算法的講解都需要對算法進行詳細的分析，包括算法條件的判斷，文法分析表的構造過程，文法分析表的具體生成，針對文法的句子的分析過程等。這些過程往往需要占用大量時間來分析、制表等。教學主要是對這些過程的講解和分析，沒有必要花這么多的時間來做這些工作。本軟件的主要任務就是利用程序來完成算法的上述相關過程，節約教學時間。 《 一個編譯原理語法分析器的設計與實現》 ，并實現以 下相關操作： LL（ 1）的要求 select集（其中包括 first集和 follow集的求解）并判斷 select集是否符合 LL（ 1）算法的要求 select 集構造文法分析表 語法分析 ： 逐一分析詞法分析所得的屬性字，檢查其中的語法錯誤，如果沒有發現語法錯誤， 則給出正確的語法結構。 句子的分析 ：句子的分析實際就是分析源程序中的語句是否符合給定的文法。 文法 ：對語言結構的定 義和描述，即在形式上用于描述和規定語言結構。由若干條規則組成。 規則 ：為一個二元組，通常格式為 U：： =x 或 U→ x；其中 U 為規則的左部，是一個符號； x是規則的右部，是一貫有窮字符串。規則又稱為產生式。 BNF 表示法 ：即巴科斯范式表示法，它引進了符號“ |”，符號“ |”表示“或”。運用符號“ |”把相同左部的規則縮寫在一起，這樣顯得文法更為緊湊。 第 2 頁 共 22 頁 文法 G[Z]：規則的非空有窮集合，其中 Z 為文法的 識別符號 或 開始符號 ，它至少要在一條規則的左部出現。 字匯表 ：在文法中，由全部規則的左部和右部中的所有符號組成的符號集。 非 終結符 ：文法中出現在規則左部的符號，它們組成的集合稱為非終結符集。 終結符 ：文法中凡不屬于非終結符集的符號，它們組成的集合稱為終結符集。 遞歸 ：同一操作或一組操作的連續重復， 其實質上是處理過程的性質，在這種過程的每一步都要用到它自身的上一步或上幾步的結果。 遞歸定義 ：在定義某種事物時又用到其本身。 直接左遞歸規則 ：型如 U：： =Uy 的規則稱為直接左遞歸規則。 First 集 ：首符號集。 Follow 集 ：向前看集。 Select 集 ：可選集。 LL（ 1）文法 ：對于文法 G（ S），其每個非終結符的不同規則具有不相交的Select 集，則稱該文法為 LL（ 1）文法。 自頂向下分析 對于文法 G[Z]，給頂一個待分析的句子 (字符串 )，自頂向下分析的基本思想是從識別符號 Z 開始，根據文法試著建立一個推導序列，若得到所給的句子，則句子得到識別，表明其結構符合文法，如果經過各種推導都不能得到所分析的句子，則該符號串不符合文法。 或者說，從根結點出發，自上而下地建立一顆語法樹，其未端結點按從左到右的順序連接起來，構成給定的符號串，則符號串得到識別。 例：設有文法 G[N]和符號串 25 N N::=D|ND D::=0|1|2|?|9 根據文法有： N?ND?DD?2D?25； 因此我們說 25 符合此文法 圖 1 G[N]過程分析 自頂向下分析的難點及解決辦法： N D D 5 2 第 3 頁 共 22 頁 對于形如 :U::=x1|x2|? |xn 的規則 ,可能需 要對所有的規則都要試探。 該解決辦法是把文法中每個非終結符號 A 的右部稱為 A 的候選式，對候選式的選擇，則根據當前輸入符號來決定。 方法： 首先對文法的每個規則 A::=? 求可選集 Select(A::=?)。 當 ??? 時，則對于當前輸入的符號 a，若有 a?First(?)，則可以選用規則A::=? 進行推導。 若對于某非終止符號有 n條規則（即有 n 個候選式）的處理方法： 對于文法，有 A::=x1|x2|? |xn，其右部的 n個候選式的首符號集均不相同 : 即 First(xi) ∩ First(xj)=? (i?j)，對于待分析的符號串，如果最左的非終結符號為 A，若其句子中對應的下一個符號（當前輸入符號）為 a，且有a?First(xk)，則選擇規則 A::=xk 來作為推導的候選式。 例：設有文法 G[Z]，和句子 bbabaax Z::=aV|bZ V::=baZ|x Select(Z ::=aV)={a}。 Select(Z ::=bZ)=。 Select(V ::=baZ)=。 Select(V ::=x)={x}。 Z? bZ? bbZ? bbaV? bbabaZ? bbabaaV?bbabaax (babaax) (abaax) (baax) (ax) (x) 對于文法，有 A::= x1|x2|? |xn，若有 First(xi) ∩ First(xj) ??(i?j)，采用試探法：即從首字符中有輸入符號的多個候選式中任選一個來試探，如果不成功，就換另一個接著試。試探法有可能形成回溯現象。對于回溯現象，可以通過 “ 左提因子方法 ” 對文法進行修改來消除。 遞歸子程序 遞歸子程序方法： 這里講的遞歸子程序方法是一種自頂向下的編譯方法，其思想是通過對源程序的每個語法成分編制一個處理子程序，通過子程序調用來對源程序進行語法和 第 4 頁 共 22 頁 語義分析。 遞歸子程序及其調用： 常用的子程序的種類有 3 種： 簡單子程序， 嵌套子程序， 遞歸子程序。 三種子程序的返回地址保護方法： 返回地址保護單元。 ，不得隨意公用。 ，由于返回地址保護單元數目不明確，一般采用堆棧形式。方法是在內存中開辟一個保護棧，每次 進入遞歸子程序時，就把當前返回地址送入保護棧，相應地，每次退出遞歸子程序時，就取棧頂的返回地址作為其返回地址。同時入棧和出棧的還有相應的遞歸子程序中需要保護的工作單元。 遞歸子程序調用時，入口與出口的工作： (1)遞歸入口工作： ①當前返回地址送保護棧； ②遞歸子程序中（調用程序）不允許被破壞的工作單元內容送保護棧。 (2)遞歸出口工作： ①恢復保護在棧頂中的工作單元的原來內容，并上退保護棧； ②取保護在棧頂中的返回地址進行返回，并退保護棧。 LL（ K）分析方法 LL(K)分析方法是一種自頂向下 的分析技術。這種分析方法從左到右掃描源程序（輸入串），同時從識別符號開始生成句子的最左推導（規范推導），向前看 K 個符號，便能確定當前應選擇怎樣的規則。 當 K=1 時，既是 LL（ 1）分析方法。 LL（ 1）分析方法 （ 1）方法的思想：根據輸入串的當前輸入符號，確定用某規則進行推導，當推導的第一個符號與輸入串的當前符號匹配時，就把輸入串的下一個字符作為當前輸入字符，直到推導出輸入串。根據輸入串向前的 1個符號來確定推導規則時，就是 LL（ 1）方法。 (1)分析方法的邏輯結構 第 5 頁 共 22 頁 圖 2 LL(1)分析方法的邏輯結構 (1)分析表 LL(1)分析表是分析方法的核心 ,它確定了推導所使用的規則。 (1)分析過程 假設分析過程中當前句型的右端部分為： x1x2? xm， (xi?V) 輸入流（待分析串）的右端部分為： y1y2? yn， (yi?Vt) 此時有以下 3 種情況： (1)當 x1?Vn，則根據當前輸入符號 y1 選擇相應的規則去替換 x1。 (2)當 x1?Vt 時，則查看 x1 與 y1 是否相同，若 x1 與 y1 相同，則分別刪去x1和 y1，然后繼續向前分析；不 相同表示不相配，為出錯。 (3)若上述兩個字符串均為空，則表示全部匹配，輸入串被識別。 現在我們把句型的右端部分逆向放入一分析堆棧中，使 x1成為棧頂，利用分析棧，當棧頂符號與輸入串當前符號相匹配時，則從棧頂刪除該符號。然后再把相應的規則逆向壓入棧頂，替換原棧頂的非終結符。 (1)分析表的構造 LL(1)分析表：它是用來反映分析棧中的元素與輸入串中元素的一種匹配關系。如果分析棧中的元素為 A，輸入元素為 a，則其匹配關系記為 LL(A,a) LL(1)分析矩陣：一種用來反映這種匹配關系的矩陣表示，該矩陣 稱為 LL(1)分析矩陣。首先進行介紹與 LL(1)分析有關的 3個操作約定： (1)N 表示繼續下一個符號； (2)P 表示重讀當前符號，也即不讀入下一符號； (3)R(?)表示用 ? 的逆串替換棧頂符號。 構造 LL(1)分析表的方法如下： A::=a?， (a?Vt)，則 令 LL(A,a)=R(?)/N ＃ a1 a2 a3 … a i … a m 控制器 分析表 Xn1 …… .. x1 第 6 頁 共 22 頁