本文中內容整理西安交通大學軟件學院吳曉軍老師的ppt中，僅供學習使用，請勿轉載或他用
參考教材：《程序設計語言 編譯原理》（第3版） 陳火旺等 國防工業出版社

文章目錄

• 語法分析的前提
• • 方法
  • • 自上而下（Top-down）
    • 自下而上（Bottom-up）
• 語法分析--自上而下分析
• • 語法分析的任務與分類
  • 面臨的問題
  • • 困難和問題
  • 問題的解決
  • • 區分三種類型的左遞歸
    • 1.消除左遞歸
    • • 直接左遞歸的消除
      • 間接和潛在左遞歸的消除
      • 消除一個文法一切左遞歸的算法
    • 2.消除回溯
    • • 回溯原因
      • 首符集定義
      • 定理
  • 遞歸下降分析程序構造
  • • 例子
  • 預測分析程序
  • • 預測分析程序的工作工程
    • • 預測分析程序
      • 分析程序的動作
    • 分析表的構造
    • • 定義首符集和后繼符集
      • 構造首符集
      • 構造后繼符集
      • 例子
      • 構造分析表
      • 例子：構造分析表
  • LL(1)分析法
  • 期末題！！！
  • • 2021 - A卷
    • 2021 - B卷

編譯程序的結構

中間箭頭不一定是單向的，有請求和響應，更多表現的是先后劃分的因果關系

表格管理和出錯處理是不可缺少的構建

紅色字體是輸入及輸出

語法分析：判斷若干個單詞符號串是不是一個合規的語法單元

語法分析的前提

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

• 采用正規式和有限自動機描述和識別語言的單詞符號
• 用上下文無關文法來描述語法規則

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

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

方法

這個的分析的方法是針對語法樹的

自上而下（Top-down）

• 從文法的開始符號出發，反復使用各種產生式，尋找匹配的推導
• 推導：根據文法的產生式的規則，把串中出現的產生式的左部符號替換成右部
• 從樹的根開始，構造語法樹
• 主要方法：遞歸下降分析法、預測分析程序

自下而上（Bottom-up）

• 從輸入串開始，逐步進行到規約，直到文法的開始符號
• 規約：根據文法的產生式規則，把串中出現的產生式的右部替換成左部符號
• 從樹葉節點開始，構造語法樹
• 主要方法：算符優先分析法、LR分析法

語法分析–自上而下分析

本章內容

• 語法分析的任務與分類
• 自上而下分析面臨的問題
• 遞歸下降分析程序構造
• 預測分析程序
• LL（1）文法

語法分析的任務與分類

$w$表示的是終結符串

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

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

一個單詞符號可能無法得到結果，然后會請求下一個單詞符號

語法分析的分類：自下而上和自上而下

面臨的問題

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

在該例子中有文法G：$S\to cAd,A\to ab,A\to a$

W：輸入串

input pointer：輸入字符指針

S：文法的開始符號

首先從開始字符開始生成語法樹，然后判斷當前輸入字符（IP指向的字符）是否與當前語法樹的左子節點匹配，如果匹配則進行下一步，如果不匹配就需要退回

c匹配上了之后IP向后移動，然后再次匹配，發現不一樣，這時候就需要展開A，到這里有兩種展開方法，一種展開為ab，一種展開為a，先按照ab來看

首先與第一個字符是a是匹配的，然后IP繼續向后走，這時候發現不匹配了。這里發現不匹配了之后要回退回去，即撤銷A展開為ab的過程。這種過程類似于超前搜索，讀了之后要還回去

再將A展開為a，就可以完成匹配了，最后語法樹如下：

上述分析方法的實現：

• 每一個非終結符對應于一個遞歸子程序，在只生成兩個串的文法過程中過程無需遞歸；但是，對于生成無數個串的文法而言，遞歸不可避免。
• 遞歸子程序是一個布爾過程，一旦它發現自己的某個候選式與輸入串匹配，它就按此式擴充語法樹，返回true，指針移過已匹配的子串；否則，返回false，保持原來的語法樹和指針不變

程序實現：使用兩個過程：S()和A()，他們送回true or false，決定于他們是否在輸入串匯總找到相應的終結符所構成的串

使用記號：

• input_symbol：當前符號內容
• input_pointer：輸入字符指針

使用過程：ADVANCE()，把input_pointer移到下一輸入符號位置，置input_symbol是當前符號內容

過程A的上半部分是去嘗試匹配ab，下半部分是去嘗試匹配a

困難和問題

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

問題：進行自上而下語法分析時，下列哪些問題必須首先解決否則無法有效生成語法樹？

• 回溯問題（√）
• 文法右遞歸問題
• 文法左遞歸問題（√）
• 多個候選式問題

解釋：多個候選式問題和回溯問題可以看成是相關的，但是存在多個候選式不一定會發生回溯

問題的解決

• 左遞歸問題
• 回溯問題

相對而言，左遞歸問題危害更大，因為會使程序陷入無線迭代

區分三種類型的左遞歸

• 直接左遞歸

  形如 $N\to N\alpha$

• 間接左遞歸

  形如 $N\to A\alpha ,A\to B\beta ,B\to N\gamma$

• 潛在左遞歸

  形如 $N\to \alpha N\beta ,而\alpha \stackrel{+}{?}\epsilon$

1.消除左遞歸

直接左遞歸的消除

直接左遞歸改造前不能有空字產生式，即右側不能含有$\epsilon$

消除方法：

• 如果$A\to A\alpha |\beta$，其中$\beta$不以A開頭
• 則修改規則為$A\to \beta A^{\prime }{A}^{\prime }\to \alpha A^{\prime }|\epsilon$

$\alpha$不能為空字，這是在開始就已經進行限制了，如果是空字了，那么通過吸收律可以得到$P\to P$，這樣就沒有意義了，式子可以直接轉換成$A\to \beta$

一般規則：

假定P的全部產生式是$P\to P{\alpha }_1|...|P{\alpha }_m|{\beta }_1|{\beta }_2|...|{\beta }_n$，其中每個$\alpha$都不等于$\epsilon$，每個$\beta$都不以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}$$
例子：

新的非終結符的記號最好與原非終結符對應上，即只在其右上角加個單引號

現有文法：
$$\begin{gathered} E\to E+T|T \\ T\to T?F|F \\ F\to (E)|i \end{gathered}$$
消去直接左遞歸后：
E→TE′E′→+TE′∣εT→FT′T′→?FT′∣εF→(E)∣i\begin{aligned} &E\to TE'\\ &E'\to +TE'|\varepsilon\\ &T\to FT'\\ &T'\to *FT'|\varepsilon\\ &F\to (E)|i \end{aligned} ?E→TE′E′→+TE′∣εT→FT′T′→?FT′∣εF→(E)∣i?

間接和潛在左遞歸的消除

一個文法消除左遞歸的條件

• 不含以$\epsilon$為右部的產生式
• 不含回路

即不會后面的式子不會成立$P\stackrel{+}{?}P$

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

例子

這里右部產生式有空字可以理解成是為了消除直接左遞歸時引入的，不然會與上面的消除左遞歸的條件發生沖突

$N\to a|Bc|\epsilon$在$S\to pNq$中的代入結果：$S\to paq|pBcq|pq$

間接和潛在左遞歸通常通過代入能轉換為直接左遞歸

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

一般是按照字母表的升序排序的

for循環是完成代入的

化簡在課本上有例題，可以嘗試著變一下排序的策略，看看做出來的文法有什么差異

例子

現有文法：
$$\begin{gathered} S\to Qc|c \\ Q\to Rb|b \\ R\to Sa|a \end{gathered}$$
方法一：排序順序為R、Q、S

將R帶入到Q中：

$Q\to Sab|ab|b$

將Q帶入到S中：

$S\to Sabc|abc|bc|c$

整個文法為：
$$\begin{gathered} S\to abc{S}^{\prime }|bc{S}^{\prime }|c{S}^{\prime } \\ {S}^{\prime }\to abc{S}^{\prime }|\epsilon \end{gathered}$$
方法二：排序順序為S、Q、R

將Q帶入到S中：

$S\to Rbc|bc|c$

將S帶入到R中：

$R\to Rbca|bca|ca|a$

整個文法為：
$$\begin{gathered} R\to bca{R}^{\prime }|ca{R}^{\prime }|a{R}^{\prime } \\ {R}^{\prime }\to bca{R}^{\prime }|\epsilon \end{gathered}$$

• 對文法G的所有非終結符進行排序

• 按上述順序對每一個非終結符$P_i$依次執行：

  • for(j = 1; j < i - 1; j++)

    將$P_j$代入$P_i$的產生式（若可代入的話）

  • 消除關于$P_i$的直接左遞歸

• 化簡上述所得的文法

2.消除回溯

回溯原因

若當前符號 = a，對A展開，而$A\to {\alpha }_1|{\alpha }_2|...|{\alpha }_m$，那么，要知道哪一個${\alpha }_i$是獲得以a開頭的串的唯一替換式。即：選擇哪一個${\alpha }_i$，亦即通過查看第一個（當前）符號來發現合適的替換式${\alpha }_i$

怎樣選擇${\alpha }_i$？

• 以a為頭的${\alpha }_i$
• 如有多個${\alpha }_i$以a為頭，則這是文法的問題

例如，有產生式：$語句\to 條件then語句else語句|while條件do語句|begin語句表end$

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

抽象地看問題：若問題不得回溯，文法G（當然G不含左遞歸）的必要條件是什么，也即對文法有什么要求？

若由${\alpha }_i\stackrel{+}{?}a???$，選該$\alpha$必中，但若${\alpha }_j\stackrel{+}{?}???$，就會導致無法百發百中。解決辦法是對文法本身提出要求：“不要出現以上情況”。把上述要求闡明清楚可以采用如下頂替的FIRST($\alpha$)，即$\alpha$的首符集

首符集定義

$FIRST(\alpha )=\{a|\alpha \stackrel{?}{?}a???,a\in V_T\}，若\alpha \stackrel{?}{?}\epsilon ，規定\epsilon \in FIRST(\alpha )$

$FIRST(\alpha )$不可以稱為首終結符集，因為有$\epsilon \in FIRST(\alpha )$

定理

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

于是，對輸入符號a，如果$a\in FIRST({\alpha }_i)$，則$a\in /FIRST({\alpha }_j),(j=i)$，因此，對A的展開無疑應選擇候選式${\alpha }_i$，否則無法命中

清除回溯的方法：使非終結符A所有候選式的首符集兩兩不相交

方法：提取公共左因子

例如：若$A\to \delta {\beta }_1|\delta {\beta }_2|???|\delta {\beta }_n|{\gamma }_1|{\gamma }_2|???|{\gamma }_m$（其中，每個$\gamma$不以$\delta$開頭）

那么，可以把這些規則改寫成
$$\begin{gathered} A\to \delta A^{\prime }|{\gamma }_1|{\gamma }_2|???|{\gamma }_m \\ {A}^{\prime }\to {\beta }_1|{\beta }_2|???|{\beta }_n \end{gathered}$$
問題：清楚回溯問題時，可以檢查多個候選式的首符集。請問，首符集被稱為終結首符集是否正確？

答案：首符集不能被稱為終結首符集或者首終結符集，因為其中可能會包含有$\epsilon$

遞歸下降分析程序構造

在不含左遞歸和每個非終結符的所有候選式的首符集都兩兩不相交的條件下，構造一個不帶回溯的自上而下分析程序，該分析程序由一組遞歸過程組成，每個過程對應文法的一個非終結符。也就是說前提條件已經消除了左遞歸和回溯。

這樣的一個的分析程序稱為遞歸下降分析器

例子

有如下文法：
E→TE′E′→+TE′∣εT→FT′T′→?FT′∣εF→(E)∣i\begin{aligned} &E\to TE'\\ &E'\to +TE'|\varepsilon\\ &T\to FT'\\ &T'\to *FT'|\varepsilon\\ &F\to (E)|i \end{aligned} ?E→TE′E′→+TE′∣εT→FT′T′→?FT′∣εF→(E)∣i?
每個非終結符所對應的遞歸子程序如下所示：

針對空串沒有給出任何的處理，老師給出的說法是不管它，hhh

例如對于$i_1+i_2?i_3$有如下分析過程：

注意

• 有$\epsilon$，自動匹配，不會失敗；
• 無成功/失敗消息返回
• 出錯位置不確切

問題：構造遞歸下降分析程序時，它由一組遞歸過程組成。每個遞歸過程對應文法的一個什么？

回答：非終結符

預測分析程序

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

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

上面的那個叫做遞歸下降分析程序

預測分析程序的工作工程

• 中間是預測分析程序的總控程序
• 預測分析表事先需要建好，在過程中需要去查找這個表
• 左邊的棧最下面需要放置一個界符#，在終結符串右側也有一個#

預測分析程序

預測分析程序包含有四部分：

一個輸入：含有要分析的終結符串，右端有#

一個棧：棧底是#，棧內是一系列的文法符號；開始時，#和S（開始符號）先進棧

分析表：二維數組M[A,a]，其中$a\in V_T;A\in V_N$，行數是文法非終結符的個數，列數是文法終結符的個數+1（有#號），這里一定不要忘了列數是終結符個數加1

輸出：根據分析表內元素作規定的語法分析動作

分析程序的動作

棧頂符號X和當前輸入符號a，由（X，a）決定程序動作，三種可能：

若$X=a=\#$，分析停止，宣告成功地完成分析

若$X=a=\#$ ，則X彈出棧，前移輸入指針

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

對于情況三，這里注意在替換的時候需要出棧之后將后面的元素反序壓棧

如$M[X，a]=\{X\to UVW\}$，就用WVU（U在頂）替換棧頂的X

如果$M[X,a]=error$，則調用error程序

下面這個表把出錯處理全部隱去了，實際上所有地方都有東西

記得開始一定要初始化棧底為一個#號，自己推的時候注意一下棧頂元素和當前輸入元素分別是什么

到17步，左#和右#相遇，這表示分析是成功的，根據輸出的順序生成最終的語法樹

結論：

• 輸出的產生式就是最左推導的產生式。棧中放右部，等待與$\alpha$匹配
• 分析表中出現（棧頂，a）時，指出如何擴充樹，并且能馬上發現錯誤

實質：

• 棧：殘缺規范句型
• 表：指出$V_N$按哪一條擴充，依賴于$V_T$

上述分析過程生成的語法樹：

分析表的構造

行對應的是非終結符，列對應的是終結符（以及#號）

定義首符集和后繼符集

先要構造兩個與G有關的集合：$FIRST(\alpha )和FOLLOW(A)$，（首符集和后繼符集）

定義：對于文法G，$\alpha \in V^{?},S,A\in V_N$

$FIRST(\alpha )=\{a|\alpha \stackrel{?}{?}a???,a\in V_T\},若\alpha \stackrel{?}{?}\epsilon ，規定\epsilon \in FIRST(\alpha )$

$FOLLOW(A)=\{a|S\stackrel{?}{?}\alpha Aa\beta ,a\in V_T,\alpha ,\beta \in V^{?}\}$，即句型當中的跟在非終結符后面的終結符

構造首符集

這里其實可以看一下書，非常清楚

復習整理時候在這里重新做了梳理，可以參考這個規則：

• 如果是終結符，則首符集就是自己，即$FIRST(X)$是$\{X\}$
• 如果是非終結符（$X\in V_N$），
  • 情況一：右側第一個是終結符（$X\to a\alpha$），則$\{a\}\cup FIRST(X)$
  • 情況二：右側是空串（$X\to \epsilon$），則$\{\epsilon \}\cup FIRST(X)$
• 如果是非終結符，并且右側的第一個元素是另一個非終結符（這里有個前提是，文法中已經不包括左遞歸了，所以這里只能是其他非終結符而不能是自己），Y中的首符集的非空串全部納入X的首符集中
  • 形式化語言描述是，若$X\in V_N,X\to Y???,Y\in V_N$，則$FIRST(Y)?\{\epsilon \}\cup FIRST(X)$
  • 如果Y的首符集包含空串$\epsilon$，則繼續看Y后面的元素，按照這三個規則繼續擴充X的首符集
• 如果右側所有字符的首符集都包含空串，則把空串也加入X的首符集中

先構造所有元素的首符集$FIRST(X),X\in V$

然后使用以下規則，直至再無終結符或$\epsilon$加入任一$FIRST$集為止

• 如果是終結符，則首符集就是自己，即$FIRST(X)$是$\{X\}$
• 如果是非終結符（$X\in V_N$），
  • 情況一：右側第一個是終結符（$X\to a\alpha$），則$\{a\}\cup FIRST(X)$
  • 情況二：右側是空串（$X\to \epsilon$），則$\{\epsilon \}\cup FIRST(X)$
• 如果是非終結符，并且右側的第一個元素是另一個非終結符（這里有個前提是，文法中已經不包括左遞歸了，所以這里只能是其他非終結符而不能是自己），Y中的首符集的非空串全部納入X的首符集中
  • 形式化語言描述是，若$X\in V_N,X\to Y???,Y\in V_N$，則$FIRST(Y)?\{\epsilon \}\cup FIRST(X)$

進而：$X\to Y_1{Y}_2?Y_{i?1}{Y}_i?Y_k,Y_j\in V_N$

如果$\epsilon \in FIRST(Y_j),1\le j\le i?1,即Y_1{Y}_2?Y_{i?1}\stackrel{?}{?}\epsilon$，則：
$$(\underset{j=1}{\overset{i?1}{?}}FIRST(Y_j)?\{\epsilon \})\cup FIRST(X)$$
只有當
$$\epsilon \in \underset{j=1}{\overset{k}{?}}FIRST(Y_j),則\{\epsilon \}\cup FIRST(X)$$

右部前$i?1$個都是非終結符

上面這個的意思是如果X推導出的所有非終結符中，如果對于$1\le j\le i?1$的所有$j$來說有$\epsilon \in FIRST(Y_j)$，那么把$FIRST(Y_j)$的所有非$\epsilon$元素都加入到$FIRST(X)$中

只有$?j\in [1,k],\epsilon \in {?}_{j=1}^{k}FIRST(Y_j)$來說（也就是X推出的所有文法符號的首字符集都包含$\epsilon$），才可以把$\{?\}$加到$FIRST(X)$中

進而再構造$FIRST(X_1{X}_2?X_n)$

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

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

大概意思就是當前面的文法字符的首字符集包含空串的時候，$\alpha$的首字符集才包括后面的文法字符的所有非$\alpha$的首字符集

只有當所有的元素的首字符集都包含空串的時候，$\alpha$的首字符集才包含空串

構造后繼符集

$FOLLOW(A)=\{a|S\stackrel{?}{?}\alpha Aa\beta ,a\in V_T,\alpha ,\beta \in V^{?}\}$，即句型當中的跟在非終結符后面的終結符

后繼符集只關注非終結符后面的終結符

#屬于FOLLOW（S），一定不能忘了

應用下列規則，直到再沒有什么加進任一$FOLLOW$為止

#屬于$FOLLOW(S)$

若存在$A\to aB\beta$，則$FIRST(\beta )?FOLLOW(B),\epsilon$除外

若有$A\to aB,或A\to aB\beta 且\epsilon \in FIRST(\beta ),則FOLLOW(B)?FOLLOW(A)$，把A的位置用$\alpha B$替換之后，原來跟在A后面的現在就跟在B的后面了

問題：構造首符集與后繼符集是實現預測分析程序的必要準備。請問，下列哪些選項可以求首符集？

• 終結符（終結符的首符集就是自己）
• 非終結符
• 文法符號串
• 候選式

答案：ABCD

首符集可以針對任何文法符號，后繼符集只能針對非終結符

例子

首符集的構造

觀察產生式的兩邊，F的首符集中非空串的元素都是T首符集的元素，T的首符集中非空串的元素都是E首符集的元素

后繼符集的構造

這里一定不要忘記了E（開始符號）的后繼符集中還有#

• 看看有沒有兩個非終結符挨著的，
• 看看左右兩邊有沒有都有非終結符的

各個推導用到的都是規則三

第一個是E的后繼符集都加入E‘的后繼符集

最終構造結果

求出所有非終結符的首符集就夠了，然后可以根據其他規則構造串的首符集

構造分析表

這個輸入不包含左遞歸以及回溯

• 對于文法的每一個產生式，確定填入的位置
• 這時候就要看產生式右部到底包含了什么終結符，第二條實現確定列，然后根據左部把他加入分析表中
• 下面這個$b\in FOLLOW(A) $可能有不止一個b

問題：構造預測分析表時，是否有必要專設 # 列？

• 沒必要
• 有必要（√）

例子：構造分析表

最終得到如下分析表

LL(1)分析法

因為把需要看多個（回溯）的情況已經排除了

有多個候選式，但是只能有一個候選式可以成為空串，不會有多個為空串，如果有多個，則他們的首符集都會包括空串這個元素，就不滿足第一個條件了

條件2中的alpha表示除beta外的任意一個。。。叫啥？？

A->alpha表示A可以直接推出來a，A->beta表示A后面跟著的第一個是a，這時候就不知道怎們操作了

答案：ABC

如果只是判斷一個文法能不能構成LL(1)文法則可以只求出首符集和后繼符集，然后檢查集合的關系

也可以構造分析表去查找有沒有多重入口，也就是一個各自會不會有兩個候選式

如果有嵌套的話，內層一定是多分支的，外層才有可能是單分支的

期末題！！！

2021 - A卷

一定不要忘了#！！

2021 - B卷

總結

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

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