第四章語法分析和語法分析程序

• 4.1_自頂向下的語法分析
• • 4.1.1_自頂向下分析過程的基本特點
  • • ①消除文法直接左遞歸
    • ②回溯的消除及LL(1)文法
  • 4.1.2_遞歸下降法
  • 4.1.3_預測分析法（也叫LL1法，注意分析過程中非終結符號逆序入棧）
• 4.2_自底向上的語法分析
• • 4.2.1_算符優先分析法
  • 4.2.2_LR分析法
  • • （1）LR分析器由四部分組成（分析表）：
    • （2）主程序分析過程：
    • 4.2.2.1_LR（0）文法
    • • （1）LR（0）項目
      • （2）識別所有的規范句型全部活前綴的DFA
      • （3）LR(0)分析表的構造
    • 4.2.2.2_SLR（1）文法
    • • （1）LR（0）可能發生的沖突
      • （2）SLR（1）分析表的構造
    • 4.2.2.3_LR（1）文法
    • • （1）SLR（0）的沖突
      • （2）LR（1）的解決方法及DFA的構建

自頂向下：遞歸下降法、LL(1)分析法 自底向上：算符優先法、LR分析法

4.1_自頂向下的語法分析

自頂向下：遞歸下降法、LL(1)分析法

4.1.1_自頂向下分析過程的基本特點

自頂向下分析過程的基本特點：
①如果文法是左遞歸的，則自頂向下分析會陷入無限循環；（消除左遞歸）
②每步推到的試探會形成大量的回溯；（消除回溯LL1文法）
③分析失敗難于指出錯誤的具體情況（錯誤位置和錯誤類型）；（LL1文法）

①消除文法直接左遞歸

方法：將A→Aα|β形式的產生式改寫為A→βA’和A’→αA’|ε的形式

例題：E->EAT|T
消除左遞歸：E->TE’,E’->ATE’|ε

②回溯的消除及LL(1)文法

對于一個已化簡且不含左遞歸的文法G，當進行自頂向下的語法分析時，不會出現回溯的充要條件是，對G中形如A→γ1|γ2|…|γm的產生式，若其候選式γi 和γj 滿足：(其中1≤i,j≤m；i≠j)
(1) FIRST(γi)∩FIRST(γj)=Φ
(2) 若ε∈FIRST(γj)，則
FIRST(γi)∩FOLLOW(A)=Φ
則稱G為LL(1)文法。

• FIRST(γ)：γ可以退出的開頭的終結符號（或ε）

（1）若x∈VT，則FIRST(x)={x}；
（2）若X∈VN，且G中有形如 X->aα (a∈VT)或（和）X->ε 的產生式，
則把 a 或（和）ε 添加到FIRST(X)中；
（3）設G中有形如 X->Y1Y2…Yi…Yk 的產生式，
若Y1∈VN，則將FIRST(Y1)中一切非 ε 符號加入到FIRST(X)中；
若Y1、Y2、… 、Yi (1≤i≤k-1)均為非終結符，且其FIRST集中均有ε ,
則將FIRST(Y1)、FIRST(Y2) 、… 、FIRST(Yi+1)中一切非 ε 終結
符加入FIRST(X)中；
若Y1、Y2、… 、Yk的FIRST集中均有ε，則將ε加入FIRST(X)中。

• FOLLOW(A)：在所有句型中可能直接跟在A之后的終結符號

（1）對文法的開始符S，#∈FOLLOW(S)；
（2）若G中有形如B->αAβ的產生式，
則將FIRST(β)中一切非ε符號加入FOLLOW(A)；
（3）若G中有形如B->αAβ的產生式，并且ε∈FIRST(β)，
或者有形如B->αA的產生式，
則將FOLLOW(B)中一切符號加入FOLLOW(A)。
圖一

4.1.2_遞歸下降法

• 思路：為文法的每一非終結符號，依相應的候選式結構，編寫一子程序識別其表示的語法范疇。

  例：
  

4.1.3_預測分析法（也叫LL1法，注意分析過程中非終結符號逆序入棧）

若一文法為LL（1）文法，進行最左推導時，當一非終結符A有多個候選式時，只需檢查當前正掃視的輸入符號α屬于那個候選式的首符集;或若某候選式yi的首字符集含e，且當前輸入符號α屬于FOLLOW
(A)，便可準確的選取候選式。這種分析方法稱為預測分析法。
若一文法為LL（1）文法，可以為之構造一無回溯的語法分析程序，稱為LL（1）分析程序或LL（1)分析器。

例如：使用預測分析法推導圖一文法：

①構造First和Follow表

②構造此文法對應的預測分析表

③分析過程

分析開始，將棧底符號#和文法開始符S入棧，各指示器置初值：

分析中，設某一時刻的分析格局為：

根據棧頂Xm的不同情況，分別作如下處理：
a）Xm->V_T（Xm是終結符號） ，若Xm=ai，則Xm出棧，輸入串指針移到下一位置；若Xm ≠ ai，則進行語法錯誤處理。
b） Xm->V_N （Xm是非終結符號），以(Xm，ai)查分析表： 若表元素為ERROR轉出錯處理；若表元素為Xm->Y1Y2…Yk，則Xm退棧，Y1Y2…Yk反向入棧。
c）Xm=ai=#，分析成功。

假若輸入的字符串為“i+i*i”

參考分析表（后面簡述表），判斷余留輸入串的第一個，首先是i，那么通過表知道分析棧中的E通過E->TE’才能得到i，所以E出棧，E’T入棧，繼續分析通過表發現T通過T->FT’才能得到i，那么T出棧，T’F入棧，通過表知F通過F->i可以直接得到i，所以F出棧，到此余留輸入串第一個字符識別完畢，開始下一個字符的識別

4.2_自底向上的語法分析

4.2.1_算符優先分析法

定義4.2：若文法中不含有兩個非終結符相鄰的產生式，則稱為算符文法。（廣義運算符: 文法的終結符號 廣義運算對象: 非終結符）
定義4.6：對一算符文法G，若任何一對終結符號間至多只有一種優先關系，
則稱G為算符優先文法。

步驟：
①構造算符優先矩陣
算符優先矩陣的構造方法
根據以下三種優先關系的定義，找全優先關系，構造優先關系矩陣。
定義4.3 a=b ：存在產生式 U→…ab… 或 U→…aAb… 時。
定義4.4 a<b ：存在產生式 U→…aA… 且 A 能推導出以 b 為第一個終結符號的符號串。
定義4.5 a>b ：存在產生式 U →…Ab… 且 A 能推導出以 a 為最后一個終結符號的符號串。
注意是第一個/最后一個 終結符號

例如：

（1）首先看“=”有哪些，因為相等的兩個終結符號滿足形式“U→…aAb…”，所以找“aAb”形式的發現只有"(E)"，所以“(” = “)”
（2）其次找“<”的有哪些，因為若終結符號a<b滿足形式“U→…aA…且A-⁺->b”，所以先找“aA”形式的，再找A的FirstV_T（A）集合（第一個終結符號,不是LL1中的first集）,則a<FirstV_T（A）

FirstV_T（T） = {“(”,“i”,“”}，FirstV_T（F）= {“(”，“i”},FirstV_T（E）= {“+”,“(”,“i”,“”}
（3）找“>”
（4）#<firstVT(E) #>lastVT(E)

②規約過程

1)尋找最左素短語：w = #N1a1N2a2…NnanNn+1#（ai ?VT , Ni ?VN∪{?}）從左到右掃描 w，找到第一個ai > ai+1，再回掃找到第一個aj-1 < aj此時 Nj aj Nj+1 aj+1 … Ni ai Ni+1 就是應被歸約的最左素短語。
2)歸約策略：在文法中找形如 A? Uj aj Uj+1 aj+1 …Ui ai Ui+1 的產生式，其中 Ui 與 Ni 不一定相同，但每個 ai 必須相同， 若存在這樣的產生式，則按此產生式歸約；否則報錯。

4.2.2_LR分析法

LR（K）文法的特性：
每一LR(K)文法都是無二義性文法
某一由LR(K)文法產生的語言也可由某一LR(1)文法產生

LR分析器的邏輯結構及工作原理：

（1）LR分析器由四部分組成（分析表）：

①分析棧：其中狀態和符號順序一致（換言之數量也一致）
②分析表：分析表由不同的LR（k）文法特制
action表：
其中行名S1,S2…Sn為分析器的各個狀態，列名a1,a2…al是全部終結符號和句子界符（句子界符即#）
goto表:
其中行名S1,S2…Sn為分析器的各個狀態，列名X1,X2…Xp是全部文法符號（終結符號、非終結符號等，所以p>l）
兩個表合并:
其中行名S1,S2…Sn為分析器的各個狀態，列名a1,a2…al是全部終結符號和句子界符（句子界符即#）列名Xl,Xl+1…Xp是非終結符號

③輸入符號串
④主程序

（2）主程序分析過程：

以上算法主要是（1）（2），其中（1）是不能規約的情況，直接將分析的輸入符號ai推入棧，并且將新狀態同時入棧
（2）其實就是已經入棧的有一部分已經可以規約了，按照指定的產生式進行規約并出棧，同時選擇下一狀態

4.2.2.1_LR（0）文法

（1）LR（0）項目

①規范句型的活前綴：指規范句型中不含句柄之右的符號的前綴。（如A→xBz的活前綴是ε和x）
② LR(0)項目：指右部某位置上標有圓點的產生式。
LR(0)項目可分為四類：
歸約項目(A→ a.) 因為A的產生式全部在“.”前面（即都分析完畢了），所以可以規約
接受項目(S→ a.)因為從開始符已經將終結符號推出完了，所以歸約成功
移進項目(A→ a.xβ 其中x為終結符)因為后面還有終結符，所以不能規約，要繼續移進
待約項目(A→ a.Xβ其中X為非終結符)

產生式A→xyz對應有四個項目：

A→·xyz 活前綴不含句柄符號（意味著還沒有識別出來A產生式右部的任何的一個符號） A→x·yz 活前綴含部分句柄符號（已經識別出來一個符號x） A→xy·z A→xyz· 活前綴含句柄所有符號 特別的：A→ε產生式的項目為A→.

（2）識別所有的規范句型全部活前綴的DFA

（3）LR(0)分析表的構造

4.2.2.2_SLR（1）文法

（1）LR（0）可能發生的沖突

沖突種類：移進規約項目、歸約歸約沖突
I8同時出現了移進項目和規約項目（移進規約沖突），進而其LR（0）分析表出現以下沖突

（2）SLR（1）分析表的構造

SLR（1）的DFA構造與LR（0）一模一樣，接下來重點討論其分析表的構造

消除沖突：
如果集合{a1, a2 ……, am},FOLLOW(B1), ………… FOLLOW(Bn)兩兩不相交，則隱含在I中的動作沖突可通過檢查現行輸入符號a屬于上述n+1個集合中的哪一個而得到解決：
若a是某個ai ，i=1,2,………,m，則移進；
若a ∈ FOLLOW（Bi），i=1,2,……………,n，則用產生式Bi ->α歸約；
此外報錯

SLR(1)分析表構造步驟（標黃字段是與LR（0）構表過程的不同之處）
(1)將文法拓廣
(2)構造識別文法全部規范句型活前綴的DFA
(3)求非終結符號Follow( )集合
(4)對每個項目集按以下四條規則填表：
① 若項目集Ii中有S’->S ·置[i,#]=acc
② 若項目集Ii中有A-> α· 的項目， A-> α 為第j個產生式，則將Follow(A)元素所在列置歸約動作為rj
③ 若項目集Ii中形如A-> α·xβ的項目，若Go(Ii,x)=Ij,x為終結符，置[i,x]為Sj，x為非終結符，置[i,x]為j
④ 分析表中無定義的元素均表示”出錯”

4.2.2.3_LR（1）文法

（1）SLR（0）的沖突

（2）LR（1）的解決方法及DFA的構建

方法：將Follow集合按屬性拆分為最小單位
①重新定義項目：使每個項目后面附帶一個終結符a [A->α·β,a ]。這樣的項目稱為LR（1）項目，a稱為向前搜索符號。a的求法如下

【注意：向前搜索符號僅對歸約項目有意義，對移進/待約項目無作用】
向前搜索符號解法：
? 對S’－>.S，向前搜索符號為＃；
? 對**[A->α·Bβ,a ]** ∈Closure（I），
[B-> ·η,first(βa)] ∈ Closure（I）
【注意“，”只是分隔符，用來分開搜索符號，搜索符號為βa的first集】

②識別LR（1）文法全部活前綴的DFA構造方法

對LR（1）項目集的Closure（I）定義如下： ?I中任何LR（1）項目都屬于Closure（I）；
?若項目[A->α·Bβ,a ]屬于Closure（I），B->η是一產生式，則 對FIRST（βα）中每個終結符b，若[B->· η,b ]不在Closure（I）中則加入之；
?重復2直到Closure（I）不再增大為止。

③LR(1)分析表的構造（標黃為不同之處）
?若項目[S’->S·,#] ∈Ii，則置ACTION[i,#]=acc
?若歸約項目[A->α ·,a ] ∈Ii,A->α為文法第j個產生式，則置ACTION[i,a] =rj
? 對每個項目集Ii中形如[A->α ·xβ,a ]的項目，若GO（Ii,x） =Ij，且x為一終結符b時，置ACTION[i,b]=Sj，若x為一非終結符，則置GOTO[I,x]=j
?其余error
對給定文法用上述方法構造的LR（1）分析表，不含多重定義元素，稱G為LR（1）文法。
【注意：向前搜索符號僅對歸約項目有意義，對移進/待約項目無作
用】

總結

以上是生活随笔為你收集整理的第四章语法分析和语法分析程序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。