語法分析技術簡介

06-04

語法分析技術簡介

語法分析（parsing or syntax analysis）最常用於實現編程語言的編譯器，它的作用是輸入一串詞法單元，驗證這些詞法單元組成句子的語法是否正確，並輸出語法分析樹。

這就好比假如詞法單元是單詞，語法分析就是分析一串單片語成的句子能否套入某類語法句型，並確定每個單詞的詞性，以便於進一步分析句子的語義。

然而語法分析不僅僅適用於編譯器實現，它是一項類似正則表達式般通用的技術。如《Parsing Techniques》介紹，語法分析廣泛應用於資料庫介面、自描述數據、人工智慧等領域。

語法分析技術的核心思想主要包括兩方面：

描述語法句型的方法——上下文無關文法。
根據文法分析語法的演算法——自頂向下分析演算法、自底向上分析演算法。

上下文無關文法（context-free grammar, CFG）

上下文無關文法是一種描述語法句型的方法，其概念與正則表達式非常類似。事實上正則表達式也是一類文法——正則文法（regular grammar），正則文法的表達能力與正則表達式完全等價。

上下文無關文法是正則文法的超集，正則文法只能表達線性語法結構，而上下文無關文法可以表達樹狀語法結構。諸如編程語言中的嵌套條件、循環等語法，因為是樹狀語法結構，所以需要用上下文無關文法表達。

一個上下文無關文法由一個四元組定義， $G=(V,Sigma,R,S)$ ：

$V$ 是一組非終結符（nonterminal symbol），它們表示句子或短語句型。
$Sigma$ 是一組終結符（terminal symbol），它們是構成句子的詞語。
$R$ 是一組產生式（production rule），它們定義了從 $V$ 到 $(VcupSigma)^*$ 的關係。
$S$ 是一個起始符（start symbol），它是 $V$ 中的一個元素，表示最頂層的句型。

比如，如下的上下文無關文法，定義了涵蓋加法、乘法和計算優先順序的表達式：

$egin{aligned} E& ightarrow E + T mid T\ T& ightarrow T * num mid num end{aligned}$

上述文法可推導出表達式： $ERightarrow1+2*3$ ，並構建如下語法分析樹：

編譯器的語法分析過程，實質就是根據編程語言定義的文法，構建語法分析樹的過程。不過要注意的是，雖然上下文無關文法能夠描述編程語言的大部分語法，但諸如標識符先聲明後使用這樣的約束，並不能通過上下文無關文法來描述。

再介紹幾個關於文法的重要概念：

二義性（ambiguity）：如果一個文法可以為某個句子構建多棵不同的語法樹，那麼這個文法就是二義性的。設計文法時需要注意消除文法的二義性。
左遞歸（left recursive）：如果一個文法中有一個非終結符A，它在經過一次或多次推導後，產生句型的最左邊也是非終結符A，那麼這個文法就是左遞歸的。LL分析演算法不能處理左遞歸文法，需要轉換消除。
推導（derivation）：使用一個產生式把一個非終結符替換為產生式右邊內容的過程。推導又分為最左推導和最右推導，最左推導總是選擇句型最左的非終結符推導（應用於自頂向下分析演算法），而最右推導則總是選擇句型最右的非終結符推導（應用於自底向上分析演算法）。
規約（reduction）：規約是推導的逆操作，它是使用一個產生式將產生式右邊內容替換為一個非終結符的過程。

語法分析演算法

語法分析演算法大致有三種類型：通用型、自頂向下型和自底向上型。通用型語法分析演算法適用於任意文法，但其分析效率非常低，實際並無太多應用，所以主要討論自頂向下型和自底向上型的語法分析演算法。

不論哪一種語法分析演算法，分析效率都是首要考慮的目標。因為一個文法可以構建無窮多種語法分析樹，如果在分析過程中需要遍歷語法分析樹，或者做很多無效的嘗試和回溯，那可想而知分析效率是無法接受的。

然而，任意設計的文法無法避免低效的分析回溯，而自頂向下型和自底向上型分析演算法就是在文法設計中加入一些設計約束，從而使語法分析過程不需要回溯，大大提高語法分析的效率。

自頂向下型語法分析演算法是從語法分析樹的根節點開始，使用最左推導的方法，推導構建完整的語法分析樹，適用於LL(k)文法。LL(k)文法的第一個L是輸入從左到右（left to right），第二個L是最左推導（leftmost derivation），k是前瞻符號（lookahead symbol）數量。

比如LL(1)文法，一個文法G是LL(1)的，當且僅當G的任意兩個不同的產生式 $A ightarrowalphamideta$ 滿足如下條件：

如果 $alpha$ 、 $eta$ 均不能推導出 $epsilon$ ，則 $FIRST(alpha)cap FIRST(eta)=emptyset$ 。
$alpha$ 和 $eta$ 最多只有一個可以推導出 $epsilon$ 。
如果 $etastackrel{*}{Rightarrow}epsilon$ ，則 $FIRST(alpha)cap FOLLOW(A)=emptyset$ 。

自底向上語法分析演算法是從語法分析樹的葉子節點開始，逐漸向上到達根節點，反向構造出一個最右推導序列，從而構建完整的語法分析樹，適用於LR(k)文法。LR(k)文法的L是輸入從左到右，R是反向最右推導（rightmost derivation in reverse），k是前瞻符號數量。

LR文法沒有嚴格的定義，一個文法只要能構造出語法分析表，適用移入—規約語法分析器解析，它就是LR文法。

LR文法相比LL文法更具備技術優勢，原因包括：

LR文法幾乎適用於所有編程語言。
LR分析演算法過程無回溯，是最高效的分析演算法之一。
LR分析演算法可儘早地檢測到語法錯誤。
LR文法是LL文法的超集，LR文法約束非常寬鬆。

參考文獻

[1] Alfred, V. A.等著．編譯原理（第2版）．趙建華等譯．北京：機械工業出版社，2009

[2] Dick Grune，Ceriel J.H. Jacobs著．Parsing Techniques (Second Edition)．New York：Springer，2008

[3] https://en.wikipedia.org/wiki/Context-free_grammar