【正文】 L 指的是由左向右的處理輸入，第 2 個 L 是它使用的是最左推導(dǎo)，而括號中的數(shù)字 1 表示它使用輸入中的一個符號來預(yù)測分析的方向，總之用一句話總結(jié) LL（ 1）分析法的基本思想，就是在從左到右掃描源程序的同時從識別符號生成句子的最左推導(dǎo)，并且只要向前查看一個輸入符號。 LL（ 1）分析要求計算First 集合 Follow 集。 LL（ 1）分析法的分析程序由一個總控程序、一個符號棧 S 和一個分析表 M 構(gòu)成。不同的 LL（ 1）分 析法分析的文法程序，它們總控程序都是相同的，但是分析表 M 是不同的。文法的符號由符號棧 S 存放。當文法和待分析符號串確定后，隨著語法分析過程符號棧的內(nèi)容也在不斷變化。由預(yù)先根據(jù)文法 G 設(shè)計的分析表 M 和符號棧 S 控制整個語法分析的過程。 事實上并不是所有的上下文無關(guān)文法都可以用 LL（ 1）進行語法分析，如果想要用LL（ 1）分析，必須滿足幾個條件：第一，文法必須是不含有多余規(guī)則的文法；第二，文法不能有回溯；第三，文法不能有左遞歸。所以，有些文法想要滿足 LL（ 1）文法的要求就要經(jīng)過一些等價變換。變換操作包括去掉多余規(guī)則，消 除能夠產(chǎn)生回溯的間接左遞歸，消除文法的直接左遞歸等。我們用符號串的推導(dǎo)的終結(jié)頭符號集 First（ x）和文法符號的后跟符號集 Follow（ U）來判斷一個文法是否是 LL（ 1）文法。除了 First 和Follow 集，還有一個表示 First 集或者 First 集和 Follow 集并集運算結(jié)果的 Select 集。判定文法是否是 LL（ 1）文法可以分為兩種情況：一種是當空符號串不屬于 First 集，只要每一條規(guī)則的不同右部的 First 集兩兩無交集這個條件滿足，那么可以判定這個文法北京郵電大學(xué)碩士學(xué)位論文 2021 19 是 LL（ 1）文法。第二種就是當空符號串屬于 First 集 ，空符號串 Z∈First（ x），如果文法滿足該文法符號的 Follow 集與 First 集無交集和同一非終結(jié)符的右部的 First 集兩兩無交集的話，那么該文法也是 LL（ 1）文法。 A. 計算 First 集 計算 First 集大致上分為兩種方法：第一種是根據(jù) First 集的定義，第二種是由關(guān)系圖求 First。 1) 根據(jù) First 集的定義計算的步驟有如下幾步 對每一個文法符號 X∈V 由 First 集的定義計算 First（ X）。 (1) 若 X∈ VT，那么 First（ X） ={X}。 (2) 若 X∈ VN，且有產(chǎn)生式 X→a?， a∈ VT，則 a∈First（ X）。 (3) 若 X∈ VN， X→ ε，則 ε ∈First（ X）。 (4) 若 X， Y1， Y2， ?， Yn都屬于 VN，而有產(chǎn)生式 X→ Y1Y2 ?Yn。當 Y1， Y2， ?， Yi?1都??ε時，其中 1≤ i ≤ n，則 First（ Y1） {ε}， First（ Y2） {ε}， ?， First{Yi?1}{ε}， First{Yi}都包含在 First（ X）中。 (5) 當 (4)中 i=1,2， ?， n 時，所有 Yi ?? ε，則 First（ X） =First(Y1) ∪First(Y2)∪ ?∪First(Yn)∪*ε+。 反復(fù)使用上述 2 至 5 步直到每個符號的 First 集不再增大為止。 若符號串 α ∈ V?， α=X1X2 ?Xn， 當 X1 ??ε， 則 First（ α） =First（ X1）。 若對任何 j（ 1≤ j ≤ i ?1， 2 ≤ i ≤n） ε ∈First（ Xj）； ε ?First（ Xi） ，則 First（ α）=? （ First(Xj)?*ε+）i?1j=1 ∪First（ Xi）。 當所有 First（ Xj）（ 1≤ j ≤n） 都含有 ε時，則 First（ α） =? (First(Xj))nj=1 ∪*ε+。 2) 由關(guān)系圖法求文法符號的 First 集的步驟有如下幾步： (1) 文法圖中的每個結(jié)點代表一個文法符號，對應(yīng)非終結(jié)符的結(jié)點用 First（ S） 來標記，其中 S 代表非終結(jié)符，對應(yīng)終結(jié)符的結(jié)點用符號本身標記。 (2) 如果有產(chǎn)生式 A→ αXβ， 并且 α ????，那么從結(jié)點 A 到 X 會有一條箭弧連接。 (3) 凡是從 First（ S） 結(jié)點可到達的終結(jié)符結(jié)點所標記的終結(jié)符都 是 First（ S） 的成員。 (4) 如果根據(jù)步驟 1 確定 ε是某非終結(jié)符 First 集 的成員，則將其加入該非終結(jié)符 的First 集中 B. 計算 follow 集 1) 根據(jù) follow 集的定義計算 計算文法中每一個 A∈ VN的 follow（ A）的方法如下 北京郵電大學(xué)碩士學(xué)位論文 2021 20 (1) 把 {}加入 follow（ S）中，其中 S 是文法的開始符號。 (2) 如果 A→ αBβ是一個產(chǎn)生式，那么在 follow（ B）中加入 first（ β）的非空元素。如果 β ??ε，那么在 follow（ B）中加入 follow（ A）的元素。 (3) 反復(fù)使用 (2)直到每個非終結(jié)符的 follow 集不再增大為止。 2) 用關(guān)系圖法求非終結(jié)符的 follow 集 (1) 關(guān)系圖中每一個結(jié)點對應(yīng)文法 G 中的每個符號和 “”，終結(jié)符和 “”就用符號本身標記對應(yīng)結(jié)點，非終結(jié)符用它的 follow 集或者 first 集對應(yīng)標記結(jié)點。 (2) 用一條箭弧鏈接開始符號 S 的 follow（ S）結(jié)點和 “”結(jié)點。 (3) 如果有類似 A→ αBβX的產(chǎn)生式在文法中，而且 β ??ε，那么用一條弧鏈接 follow（ B）結(jié) 點和 first（ X）結(jié)點，如果 X∈ VT，那么 follow（ B）結(jié)點與 X 相連。 (4) 如果有類似 A→ αBβ的產(chǎn)生式在文法中，而且 β ??ε，那么用一條箭弧鏈接 follow（ B）結(jié)點和 follow（ A）結(jié)點。 (5) 如果有類似 A→ αBβ的產(chǎn)生式對應(yīng) first（ A）結(jié)點，而且 α ??ε，那么用一條箭弧鏈接 first（ A）結(jié)點和 first（ X）結(jié)點。 (6) 如果有結(jié)點可以從 follow（ A）結(jié)點到達終結(jié)符或者 “”結(jié)點，那么 follow（ A）成員中應(yīng)該有其所標記的終結(jié)符或者 “”。 若文法中含有左公共因子或者含有直接或間接左遞歸，那么這個文法就不是 LL（ 1）文法，如果想要將其等價變換到 LL（ 1）文法，我們需要設(shè)法提取左公共因子，消除文法中的左遞歸。 1) 消除左遞歸 當文法含有如下產(chǎn)生式 (1) A→ Aβ A∈ ????,β ∈ ??? (2) A→ Bβ B→ Aα A,B∈ ????,α、 β ∈ ??? 第一種情況的產(chǎn)生式文法中含有直接左遞歸的規(guī)則，第二種情況的產(chǎn)生式可以形成推導(dǎo) A +? A?,文法中含有間接左遞歸的規(guī)則。只要文法中含有這兩種情況的任何一種那么該文法就是左遞歸的，它不是 LL（ 1）文法，也就不能采用自頂向下分析方法。對于這些情況可采用下列變換公式： A. 把直接左遞歸改為右遞歸： 一般情況下，若關(guān)于 A 的全部產(chǎn)生式是： A→ A??1|A??2|?|A????|??1|??2|?|????，其中????(1 ≤ ?? ≤ ??)不等于 ε， ????(1 ≤ ?? ≤ ??)不以 A 開頭，改寫成消除左遞歸的產(chǎn)生式是：A→ ??1??′|??2??′|?|??????′ 北京郵電大學(xué)碩士學(xué)位論文 2021 21 ??′ → ??1??′|??2??′|?|??????′|ε B. 消除間接左遞歸 對于間接左遞歸需先將間接左遞歸變?yōu)橹苯幼筮f歸，然后再消除直接左遞歸。 如有文法 G： (1) A→ aB (2) A→ Bb (3) B→ Ac (4) B→ d 把產(chǎn)生式 3 中的非終結(jié)符 A 用產(chǎn)生式 2 的右部置換得到左部為 B 的產(chǎn)生式： (1) B→ aBc (2) B→ Bbc (3) B→ d 消除左遞歸后： B → (aBc|d)??′ ??′ → ??????′|ε 再加入產(chǎn)生式 A→ aB， A→ Bb，得到最終文法： (1) A→ aB (2) A→ Bb (3) B→ (aBc|d)??′ (4) ??′ → ??????′|ε C. 消除文法中一切左遞歸的算法，即文法中不含形如 A→A 這樣的規(guī)則，和 A→ ε的空產(chǎn)生式。它的算法步驟如下： (1) 文法中的所有非終結(jié)符要按某一順序排序，比如 ??1,??2,?,???? (2) 從第一個非終結(jié)符開始消除左部為 A1的產(chǎn)生式的直接左遞歸，然后用左部為 A1的所有規(guī)則的右部替換左部為 A2右部以 A1開始的產(chǎn)生式中的 A1，消除左部為 A2的產(chǎn)生式中的直接左遞歸。用此方法把所有直接左遞歸消除。 (3) 去掉無用產(chǎn)生式 2) 提取左公因子 如果文法中含有形如 A→ αβ|αγ這樣的產(chǎn)生式，這就使得相同左部的產(chǎn)生式其右部的 First 集相交，也就是 Select（ A→ αβ） ∩ Select（ A→ αγ） ≠ ?，而這不滿足 LL（ 1）文法的條件。 如果將上述產(chǎn)生式 A→ αβ|αγ進行變換，變換為： A→ α(??|γ)，其中左右括號 ”(””)”北京郵電大學(xué)碩士學(xué)位論文 2021 22 是元符號，可以通過進一步引進新終結(jié)符來去掉它們，產(chǎn)生式變?yōu)椋? A → α??′ ??′ → ??|γ 將上述方法寫成一般形式就是： A → α??1|????2|?|??????，將其提取左公因子后： A → α(??1|??2|?|????)，然后消除括號： A → α??′ ??′ → ??1??2 ????? 如果在 ??1??2 ?????中仍然含有左公因子，那么可以再次提取，知道產(chǎn)生式再無左公因子為止。有的時候再對文法進行提取左公因子變換后可能會使某些產(chǎn)生式編程無用的產(chǎn)生式，這種情況就必須對文法重新化簡。 二、 遞歸子程序法 遞歸子程序法是不帶回溯的自頂向下的語法分析方法，這種方法在語法分析中廣為流行。它又是面向目標的分析方法，該方法直觀簡單易于構(gòu)造。遞歸子程序法的基本思想是：在對源程序的編譯過正中，用相應(yīng)的子程序來處理每一個語法成分，而子程序又可以進一步分為嵌套子程序、簡單子程序和遞歸子程序。嵌套子程序是指調(diào)用除自身子程序外的其它子程序，簡單子 程序值不調(diào)用任何子程序的子程序，而遞歸子程序則是會直接或者間接的調(diào)用自己子程序的子程序。遞歸子程序法是一些遞歸子程序的集合，它的名字也是由此得來的。遞歸子程序法的編譯思想十分簡單，在語法規(guī)則的支配下，從識別符號開始進行語法分析。分析的方法是逐個掃描源程序中的所有字符，在掃描過程中下一個語法成分 Y 是根據(jù)當前輸入字符和文法預(yù)測到的，當預(yù)測到 Y 后就以 Y 為目標開始調(diào)用分析和識別 Y 的子程序，以其他子程序或者以自身為目標的子程序在分析 Y的過程中又可能被調(diào)用，如此繼續(xù)指導(dǎo)識別完成識別源程序或者發(fā)現(xiàn)錯誤為止。 遞歸子程序要 求不可以回溯，換句話說就是它分析的文法也必須是 LL（ 1）文法。但是遞歸子程序法和 LL（ 1）分析法又有所不同， LL（ 1）分析法擁有相同的總控程序，不同 LL（ 1）文法只是分析表和分析棧不同，它們的總控程序是相同的。遞歸子程序法則要求每一個文法都要編寫其分析程序。由于遞歸子程序在退出它前還有可能再次進入它這個的特點，我們不能像編寫一般子程序那樣用一個固定單元存放返回地址，這就需要用一個棧來存放返回地址。這也是因為遞歸子程序遵循后進先出規(guī)律而選擇用棧這種數(shù)據(jù)結(jié)構(gòu)的。 自底向上分析方法 自底向上的方法由葉子結(jié)點開始，逐漸向根結(jié)點方向構(gòu)造語法樹。相似于 LL（ 1）北京郵電大學(xué)碩士學(xué)位論文 2021 23 分析法這個術(shù)語，最普通的自底向上分析法稱作 LR（ 1）分析，第一個 L 表示從左向右處理輸入，第二個 R 表示它使用最右推導(dǎo)，而括號中的數(shù)字 1 表示它使用輸入中的一個符號來預(yù)測分析的方向。自底向上分析使得 LR（ 0）分析具有了意義，因為自底向上分析可在先行符號出現(xiàn)在分析棧之后再分析它。一般而言，自底向上分析算法要比自頂向下分析所涉及到的構(gòu)造更為復(fù)雜。 總的說來，語法分析的任務(wù)是：在詞法分析的基礎(chǔ)上根據(jù)語言的語法規(guī)則把單詞符號串分解成如 “短語 ”、 “句 子 ”、 “程序段 ”和 “程序 ”等各類語法單位（語法范疇）。通過語法分析，確定整個輸入串是否構(gòu)成語法上正確的 “程序 ”。語言的語法規(guī)則通常用上下文無關(guān)文法描述，語法分析要依循語法規(guī)則。相比類似于線性分析的詞法分析，語法分析更類似于一種層次結(jié)構(gòu)分析。例如： Z = X? ?Y 代表一個賦值語句，而其中的 ”X ? ?Y”代表一個 “算術(shù)表達式 ”。因而，語法分析的任務(wù)就是識別 ”X ? ?Y”為算術(shù)表達式，同時，識別上述整個符號串屬于賦值語句這個范疇。 本課題語法分析擬用 Bison（ GNU 下的 Yacc）。 Bison Bison 用來識別語法，它先分析詞法分析器提供的記號，然后把記號基于邏輯進行組合。 Bison 程序也是由定義部分、規(guī)則部分和用戶子例程三部分構(gòu)成。這三部分也