文章目錄

• 第四章 語法分析——自上而下分析
• • 語法分析的任務與分類
  • 自上而下分析面臨的問題
  • 自上而下分析的問題如何解決
  • • 區分三種類型的左遞歸
    • 直接左遞歸的消除
    • 間接和潛在左遞歸的消除
    • 消除一個文法一切左遞歸的算法
    • 消除回溯、提左因子
  • 遞歸下降分析程序構造
  • 預測分析程序
  • • 預測分析程序的工作過程
    • • 預測分析程序有四部分
      • 分析程序的動作
      • 分析表格式
      • 舉例說明
    • 分析表的構造[考點]
    • • ?舉例1?
      • ?舉例2?
  • LL(1)文法
  • • LL(1)文法
    • LL(1)文法的條件
  • 參考資料

第四章 語法分析——自上而下分析

語法分析的前提

對語言的語法結構進行描述

采用正規式和有限自動機描述和識別語言的單詞符號

用上下文無關文法來描述語法規則

語法分析的任務:分析一個文法的句子的結構

語法分析器的功能:按照文法的產生式(語言的語法規則)，識別輸入符號串是否為一個句子(合式程序)

語法分析的方法

1?? 自上而下Top-down

從文法的開始符號出發,反復使用各種產生式，尋找"匹配"的推導

推導：根據文法的產生式規則,把串中出現的產生式的左部符號替換成右部

從樹的根開始，構造語法

遞歸下降分析法、預測分析程序

2?? 自下而上Bottom-up

從輸入串開始， 逐步進行歸約,直到文法的開始符

歸約：根據文法的產生式規則,把串中出現的產生式的右部替換成左部符號

從樹葉節點開始,構造語法樹

算符優先分析法、LR分析法

語法分析的任務與分類

語法分析的任務：$對任一給定w\in V_T^{?},判斷w\in L(G)$

w表示終結符串

句子的全體是一個語言，記作L(G)

語法分析器是一個程序，它按照P，做識別w的工作

自上而下分析面臨的問題

主旨：從文法開始符號出發，自上而下地為輸入串建立一棵語法樹。

舉例：文法G1: S -> cAd A -> ab|a，輸入串：w=cad，為它建立語法樹

上述分析方法的實現：

1?? 每一非終結符對應一個遞歸子程序，在只生成兩個串的文法中過程無須遞歸;但是，對于生成無數個串的文法而言，遞歸不可避免。

2?? 遞歸子程序是一個布爾過程，一旦它發現自己的某個候選式與輸入串匹配，它就按此式擴充語法樹，返回true,指針移過已匹配子串;否則，返回false,保持原來的語法樹和指針不變。

程序實現

使用兩個過程: S()和A()， 它們送回true or false,決定于它們是否在輸入串中找到相應的終結符所構成的串。

使用記號

input_ symbol:當前符號內容
input_ pointer: 輸入字符指針

使用過程

ADVANCE():把input_ pointer移 到下一輸入符號位置，置input_symbol是當前符號內容。

procedure S(); begin if input_symbol = 'c' thenbeginADVANCE();if A() then//A擴展if input_symbol = 'd'then beginADVANCE();//指針后移return true;end;end;return false; end;procedure A(); beginisave := input_pointer;//記錄輸入指針，防止回滾if input_symbol = 'a' thenbeginADVANCE();if input_symbol = 'b' thenbeginADVANCE();return true;end;end; /* 匹配ab失敗，則匹配a*/input_pointer := isave//將之前記錄的輸入指針賦值給輸入指針if input_symbol = 'a' thenbeginADVANCE();return true;end;elsereturn false; end;

困難和問題

• 文法的左遞歸
• 回溯
• 使用候選式的順序會影響所接受的語言: 如: A -> ab|a改為A->a|ab
• 難以報告出錯的確切位置
• 窮舉試探法一 低效的分析方法

自上而下分析的問題如何解決

消除文法左遞歸以及回溯問題

區分三種類型的左遞歸

1?? 直接左遞歸

形如：N->Nα

2?? 間接左遞歸

形如：N->Aα A->Bβ B->Nγ

3?? 潛在左遞歸

形如：N->α N β，而$\alpha \stackrel{+}{?}\epsilon$

直接左遞歸的消除

候選式：A->Aα|β，可以得到文法符號串：βα、βαα、βααα……

? A->βA’ A’->α A’|ε，也可以得到文法符號串：βα、βαα、βααα……

一般化可以得到直接左遞歸的消除方法

若：A->Aα|β，其中β不以A開頭，則修改規則為A->βA’ A’->α A’|ε

可以進行推廣：假定P的全部產生式為
$$P\to P{\alpha }_1|P{\alpha }_2|...|P{\alpha }_m|{\beta }_1|{\beta }_2|...|{\beta }_n$$
每個α都不等于ε，每個β都不以P開頭

則將左遞歸變為右遞歸如下
$$\begin{gathered} P\to {\beta }_1{P}^{\prime }|{\beta }_2{P}^{\prime }|...|{\beta }_n{P}^{\prime } \\ {P}^{\prime }\to {\alpha }_1{P}^{\prime }|{\alpha }_2{P}^{\prime }|...|{\alpha }_m{P}^{\prime }|\epsilon \end{gathered}$$

舉例：文法：E->E+T|T T->T*F|F F->(E)|i

消除直接左遞歸后

E->TE’

E’->+TE’|ε

T->FT’

T’->*FT’|ε

F->(E)|i

間接和潛在左遞歸的消除

一個文法消除左遞歸的條件：不含以ε為右部的產生式；不含回路$P\stackrel{+}{?}P$

代入法

將一個產生式規則右部的a中的非終結符N替換為“N的候選式”。如果N有n個候選式，則右邊的a重復n次，而且每一次重復都用N的不同候選式來代替N。

舉例：（改寫之后的）N->a|Bc|ε在S->pNq中的代入結果：S->paq|pBcq|pq

消除一個文法一切左遞歸的算法

1?? 對文法G的所有非終結符進行排序；

2?? 按上述順序對每一個非終結符Pi依次執行：

for(j=1;j< i-1；j++)將Pj代入Pi的產生式（若可代入的話); 消除關于Pi的直接左遞歸;

3?? 化簡上述所得文法。

舉例

對于文法：S->Qc|c Q->Rb|b R->Sa|a

雖然沒有直接左遞歸，但是S,Q,R都是左遞歸的，比如有S=>Qc=>Rbc=>Sabc

1?? 將非終結符排序為：R、Q、S

2?? 對于R，不存在直接左遞歸，將R帶入到Q的有關候選后，我們把Q的規則變為Q->Sab|ab|b

現在的Q同樣不含有直接左遞歸，把它帶入到S的有關候選后，S變為S->Sabc|abc|bc|c，消除S的直接左遞歸，可以得到整個文法

S->abcS’|bcS’|cS’

S’->abcS’|ε

Q->Sab|ab|b

R->Sa|a

其中Q和R的規則已經多余，化簡以后可以得到

S->abcS’|bcS’|cS’

S’->abcS’|ε

由于排序不同，最后得到的文法在形式上可能不一樣，但是都是等價的

消除回溯、提左因子

回溯原因

若當前符號 = a，對 A 展開，而 A -> α1|α2|…|αm那么，要知道哪一個αi是獲得以a開頭的串的唯一替換式。

即：選擇哪一個αi，亦即通過查看第一個（當前）符號來發現合適的替換式α。

如何選擇αi？

以a為開頭的αi

如果有多個αi以a開頭，則這是文法的問題

舉例

有產生式

語句->if 條件 then 語句 else 語句|while 條件 do 語句|begin 語句表 end

若要尋找一個語句，那么關鍵字if，while，begin就提示我們哪一個替換式是最右可能成功的替換式

若要求不得回溯，文法G（不含有左遞歸）的必要條件是什么？

若由${\alpha }_i\stackrel{+}{?}a...$(某個文法符號串經過若干步推導可以得到以a（終結符）開頭的串)，選該αi必中，但若${\alpha }_j\stackrel{+}{?}a...$,就會導致無法百發百中。解決辦法是對文法本身提出要求:不要出現以上情況”。把上述要求闡明清楚可以采用如下定義的FIRST(α),即α的首符集。由于空串的存在，不能稱為首終結符集。

首符集定義FIRST(α)
$$\begin{gathered} FIRST(\alpha )=\{a|\alpha \stackrel{?}{?}a\dots ，a\in V_T\} \\ if\alpha \stackrel{?}{?}\epsilon ,define\epsilon \in FIRST(\alpha ) \end{gathered}$$

定理

若一個$A\in V_N$有許多$FIRST({\alpha }_i)$。如果A的任何兩個候選式${\alpha }_i$和${\alpha }_j$之間均滿足
$$FIRST({\alpha }_i)\cap FIRST({\alpha }_j)=?$$
意味著，A的每一候選式α推導后所得的字符串第一個$V_T$均不同。

于是，對輸入符號α,如果α∈FIRST(αi), 則α not∈FIRST(αj), (j≠i)。因此，對A的展開無疑應選候選式αi,否則無法命中。

消除回溯目的

使非終結符A所有候選式的首符集兩兩不相交

方法：提取公共因子

若：$A?>\delta {\beta }_1|\delta {\beta }_2|...|\delta {\beta }_n|{\gamma }_1|{\gamma }_2|...|{\gamma }_m$，其中每個γ不以δ開頭

那么可以把這些規則改寫成
$$\begin{gathered} A\to \delta A^{\prime }|{\gamma }_1|{\gamma }_2|...|{\gamma }_m \\ {A}^{\prime }\to {\beta }_1|{\beta }_2|...|{\beta }_n \end{gathered}$$

遞歸下降分析程序構造

在不含左遞歸和每個非終結符的所有候選式的首符集都兩兩不相交條件下，構造一個不帶回溯的自上而下分析程序,該分析程序由一組遞歸過程組成，每個過程對應文法的一個非終結符。這樣的一個分析程序稱為遞歸下降分析器。

舉例

文法G:

E->TE’

E’=>+TE’|ε

T->FT’

T’->*FT’|ε

F->(E)|i

每個非終結符對應的遞歸子程序如下：

面臨輸入：i1+i2*i3的分析步驟如下

構造語法樹時，注意點

有ε，自動匹配，不會失敗

無成功/失敗消息返回

出錯位置不確切

構造遞歸下降分析程序時，它由一組遞歸過程組成。每個遞歸過程對應文法的一個非終結符。

預測分析程序

? 問題：
用遞歸子程序描寫遞歸下降分析器，要求實現該編譯程序的語言（高級或匯編）允許遞歸。

🚗 改進：
使用一張分析表和一個棧同樣可實現遞歸下降分析。用這種方法實現的語法分析程序叫預測分析程序。

預測分析程序的工作過程

預測分析表事先已經準備好了。

預測分析程序有四部分

1?? 一個輸入:含有要分析的終結符串，右端有#。

2?? 一個棧:棧底是#，棧內是一系列文法符號;開始時，#和S先進棧。

3?? 分析表:二維數組M[A, a], 其中$a\in V_T;A\in V_N$，#要占一列，多了一列

4?? 輸出:根據分析表內元素做規定的語法分析動作。

分析程序的動作

程序測定棧頂符號X和當前輸入符號a,由(X, a)決定程序動作，三種可能:

1?? 若X=a=#，分析停止，宣告成功地完成分析;

2?? 若X=a≠#,則X彈出棧，前移輸入指針;

3?? 若$X\in V_N$,則去查分析表M的元素M[X,a],該元素或為X的產生式，或為一個出錯元素。

對第3)條，$X\in V_N$，查分析表M的元素M[X, a]后

如:M[X,a]={X->UVV},就用WVU(U在頂)替換棧頂的X;

如: M[X, a]=error,則調用error程序。

分析表格式

文法G:

E->TE’

E’=>+TE’|ε

T->FT’

T’->*FT’|ε

F->(E)|i

id+*()#

E	E->TE’			E->TE’
E’		E’->TE’			E’->ε	E’->ε
T	T->FT’			T->FT’
T’		T’->ε	T’->*FT’		T’->ε	T’->ε
F	F->id			F->(E)

#（界符）視為特殊的終結符

所有的行跟非終結符對應，所有的列跟終結符對應

隱去了出錯處理

舉例說明

按照預測分析程序，對于輸入id+id*id所作

結論

①輸出的產生式就是最左推導的產生式。棧中放右部，等待與α匹配；

②分析表中出現（棧頂，a）時，指出如何擴充樹，并且能馬上發現錯誤。

實質

棧：殘缺規范句型

表：指出$V_N$按哪一條擴充，依賴于$V_T$

分析表的構造[考點]

按照$\alpha \stackrel{?}{?}？$將產生式分成兩種

$\alpha \stackrel{?}{?}a\dots \dots$

$\alpha \stackrel{?}{?}\epsilon$

先要構造兩個與G有關的集合：FIRST(α)首符集和FOLLOW(A)后繼符集(跟在非終結符A后面的終結符)

1?? 定義：對于文法G，$\alpha \in V?$，S、A$\in V_N$
KaTeX parse error: No such environment: align at position 8: \begin{?a?l?i?g?n?}? &\text{FIRST}(…

2?? 構造FIRST(α)

🍎 對于單符號：先構造$FIRST(X),X\in V_T\cup V_N$

連續應用以下規則，直到再無終結符或ε加入任一FIRST集為止

① 若$X\in V_T$，則FIRST(X)={X}

② 若$X\in V_N,且X\to a\alpha$，則{a}∪FIRST(X)；若$X\in V_N,且X\to \epsilon$，則{ε}∪FIRST(X)

③ 若$X\in V_N,且X\to Y\dots ，Y\in V_N$，則FIRST(Y)\{ε}∪FIRST(X)；若$X\to Y_1{Y}_2\dots Y_k，Y_1,...,Y_{i?1}\in V_N$是一個產生式，而且對于任何j，$1\le j\le i?1$，$FIRST(Y_j)$中都含有ε，即$Y_1...Y_{i?1}\stackrel{?}{?}\epsilon$,則把$FIRST(Y_i)$中的所有非ε元素加入到FIRST(X)中；如果所有的$FIRST(Y_j)，j=1,2,...,k$都有ε，則把ε也加入FIRST(X)

所有的非終結符最后都會變成終結符串

🍎 對于符號串：再進而構造$FIRST(X_1{X}_2...X_n)即FIRST(\alpha )$

① $FIRST(X_1)$的非ε終結符加入$FIRST(\alpha )$

② 若$$\epsilon \in FIRST(X_1)$$,則$FIRST(X_2)$的所有非ε終結符加入$FIRST(\alpha )$

③ 若$$\epsilon \in FIRST(X_1)，\epsilon \in FIRST(X_2)$$,則$FIRST(X_3)$的所有非ε終結符加入$FIRST(\alpha )$

最后，若$\epsilon \in FIRST(X_i),i=1,...,n$，則{ε}加入$FIRST(\alpha )$

終結符、非終結符、文法符號串、候選式都可以構造首符集；后繼符集只能用終結符定義！

3?? 構造FOLLOW(A)

對于文法G的每個非終結符A構造FOLLOW(A)的辦法是，連續使用下面的規則，直到每個FOLLOW不再增大為止

① 對于文法的開始符號S，置#于FOLLOW(S)中——#不能忽視！

② 若$A\to \alpha B\beta$，則把FIRST(β)\{ε}加入到FOLLOW(B)中

③ 若有$A\to \alpha B$。或者$A\to \alpha B\beta$是一個產生式而$B?\epsilon$(即ε∈FIRST(β))，則把FOLLOW(A)加入到FOLLOW(B)中

?舉例1?

已知文法G:
E->TE’ T’->*FT’|ε E’->+TE’|ε F->(E)|i T->FT’
求它的FIRST(α)，FOLLOW(A)

1?? 構造首符集

首先看產生式右邊，如果第一個符號是終結符，則把其加入非終結符的首符集中，再看一下候選式中有沒有ε，有的話也加入首符集中，如由F->(E)|i可知$FIRST(F)=\{(,i\}$

還有一些推到關系，如T->FT’,E->TE’，則F首符集中非ε的元素也是T中首符集的元素,T首符集中非ε的元素也是E中首符集的元素:FIRST(F)={ ( , i }=FIRST(T)=FIRST(E)

2?? 構造非終后繼符集

由法則①：FOLLOW(E)={#}

由法則②

E->TE’，則將 FIRST(E’) \ {ε} 加入 FOLLOW(T)：FOLLOW(T)={+}

T->FT’，則將 FIRST(T’) \ {ε} 加入 FOLLOW(F)：FOLLOW(F)={*}

F->(E)，則將FIRST( ) )加入FOLLOW(E)：FOLLOW(E)={ # , ) }

由FISRT①，FIRST( ) )=）

由法則③

E->TE’，將FOLLOW(E)加入到FOLLOW(E’)中:FOLLOW(E’)={ ) , #}}

E->TE’，且E’->ε，則將FOLLOW(E)加入到FOLLOW(T)中：FOLLOW(T)={ + , ) , #}

T->FT’，將FOLLOW(T)加入到FOLLOW(T’)中：FOLLOW(T’)={ + , ) , #}

T->FT’，且T’->ε，將FOLLOW(T)加入到FOLLOW(F)中：FOLLOW(F)={*, + , ) , #}

首符集后繼符集

FIRST(E)={ ( , i }	FOLLOW(E)={ ) , #}
FIRST(E’)={+ , ε}	FOLLOW(E’)={ ) , #}}
FIRST(T)={ ( , i }	FOLLOW(T)={ + , ) , #}
FIRST(T’)={* , ε}	FOLLOW(T’)={ + , ) , #}
FIRST(F)={ ( , i }	FOLLOW(F)={*, + , ) , #}

4?? 分析表的構造

算法：輸入：G1文法，輸出：分析表M

① 對文法的每一個A->α，做②和③

② 對于任一a∈FIRST(α)，把A->α加入到M[A，a]（可能不止一個）

③ 若ε∈FIRST(α)，則把A->α加入M[A，b]，b∈FOLLOW(A)；若ε∈FIRST(α)，#∈FOLLOW(A)，則把A->α加進M[A,#]

④ 把所有無定義的M[A，a]標上“出錯標志”

?舉例2?

將算法應用于上述文法G：E->TE’ T’->*FT’|ε E’->+TE’|ε F->(E)|i T->FT’

① E->TE’

因為FIRST(TE’)=FIRST(T)={(,i)}，即產生式E->TE’保證了M[E，i]和M[E, (]中持有E->TE’

所以M[E，(]={E->TE’} M[E，id]={E->TE’}

② E’->+TE’

因為FIRST(+TE’)={+}，所以M[E’，+]={E’->+TE’}

③ E’->ε

因為有ε，需要去看產生式的左部非終結符的FOLLOW集中有哪些終結符

FOLLOW(E’)={),#}，所以M[E’,)]={E’->ε}，M[E’，#]={E’->ε}

最終可以得到如下分析表

id+*()#

E	E->TE’			E->TE’
E’		E’->TE’			E’->ε	E’->ε
T	T->FT’			T->FT’
T’		T’->ε	T’->*FT’		T’->ε	T’->ε
F	F->id			F->(E)

上述算法可應用于任何文法G以構造它的分析表M。但對于某些文法，有些M[A,a]可能持有若干個產生式，或者說有些M[A,a]可能是多重定義的。如果G是左遞歸或二義的，那么，M至少含有一個多重定義人口。因此，消除左遞歸和提取左因子將有助于獲得無多重定義的分析表M。

可以證明，一個文法G的預測分析表M不含多重定義入口，當且僅當該文法為LL(1)的。

LL(1)文法

LL：第一個L表示從左到右掃描輸入串；第二個L表示最左推導

(1)：表示分析時每一步只需要向前查看一個符號

LL(1)文法

一個文法G，若它的分析表M不含多重定義入口(同一個格子里面有兩個產生式)，則稱它為一個LL(1)文法

LL(1)文法的條件

文法G式LL(1)的，則對于G的每一個非終結符A的任何兩個不同產生式A->α|β，有：

1?? FIRST(α)∩FIRST(β)=Φ

2?? 若某一個候選式$\beta \stackrel{?}{?}\epsilon$，則FIRST(α)∩FOLLOW(A)=Φ

🍌 說明

使用LL(1)文法，一定可以實現不帶回溯的自上而下分析

若某文法G為LL（1)文法，則下列那些描述正確？

?該文法的預測分析表必無多重入口。

?所有非終結符各候選式的首符集兩兩之間交集必為空。

?非終結符的某個候選式的首符集中有空串時，該非終結符的后繼符集與其余各個候選式首符集交集必為空。

但是，條件語句文法不能改造成LL(1)文法

語句->if 條件 then 語句 else 語句|if 條件 then 語句

例如：S->iCtS|iCtSeS|a C->b

提公因子以后，文法變為S->iCtSS’|a S’->eS|ε C->b

計算該文法的FIRST集和FOLLOW集如下：

FIRST(S)={i，a} FIRST(S’)={e，ε} FIRST?={b}

FOLLOW(S)={#，e} FOLLOW(S’)={#，e} FOLLOW?={t}

分析表如下：

abeit#

S	S->a			S->iCtSS’
S’			S’->eS
C		C->b

上表未填滿

對于候選式S’->ε，因為ε∈FIRST(S’)={e，ε}，而FOLLOW(S’)={#，e}，所以S’->ε填入M[S’,#]和M[S’，e]，有多重入口，不是LL(1)文法

解決：強制令M[S’，e]={S’->eS}，即堅持將e與最近的t相結合，從程序語言來看，相當于規定ELSE堅持與最近的THEN相結合

參考資料

[1] 西安交通大學軟件工程專業編譯原理 吳曉軍 2022春

[2] 陳火旺，劉春林，譚慶平，趙克佳，劉越. 程序設計語言編譯原理（第3版）. 北京：國防工業出版社，2010

總結

以上是生活随笔為你收集整理的[XJTUSE编译原理]第四章 语法分析——自上而下分析的全部內容，希望文章能夠幫你解決所遇到的問題。

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