基於現代C++的四則運算語法分析器（上）

01-28

大約八年前，輪子哥曾經寫過一篇文章，論述了如何用當時的C++來實現一個四則運算語法分析器——它會把四則運算表達式創建為一顆語法樹（AST），然後將其轉換為LISP語言風格的表達式。文章地址如下：如何手寫語法分析器

最近一段時間，因為工作上某些暫時不能說的原因，我在這篇文章的基礎上又做了一點工作——主要是用C++ 11的寫法重寫了這篇文章中的代碼，並給出了AST的聲明。這裡把目前不需要遮蓋的部分放出來，也算是我在續乎寫的第一篇技術類文章了……

本文將分為上下兩個部分——上半部分會以Expression類的形式，給出AST在C++中的聲明，而下半部分將使用C++ 11，重寫原文中的語法分析器，使其可以用上半部分給出的聲明，建立AST的模型。

首先，對於一個四則運算表達式（形如1*(2+3)），我們有若干條語法約束。以下引用原文：

Operator=」+」
Operator=」-「

Operator=」*」
Operator=」/」
Expression=<數字>
Expression= 「(」 Operator Expression Expression 「)」
Expression=「(」Expression 「)」
這樣寫的話覺得很煩，我們可以追加多兩種定義語法的語法：
1、A | B代表A或者B都可以，並且如果字元串被A匹配成功的話將不會考慮B
2、[ A ]代表A是可以存在或者不存在的，但是盡量使其存在
於是我們可以把上面的語法改寫成如下形式：

Operator=」+」 | 「-」 | 「*」 | 「/」

Expression=<數字> | 「(「 Expression 「)」 | 「(「 Operator Expression Expression 「)」

第一條語法規則說的是Operator，也就是操作符，可以是加號、減號、乘號或者除號。第二條語法規則說的是一條表達式可以只由數字構成、一個加了括弧的表達式或者一個加上了括弧的操作符和兩個參數。

需要注意的是，對於本文來說，我們直接使用四則運算表達式原本的格式（而非原文的LISP格式），所以對於語法規則2，應該改為這樣的形式：

Expression=<數字> | 「(「 Expression 「)」 | 「(「 Expression Operator Expression 「)」

基於這樣的形式，我們可以把表達式簡單地分成兩種類型：數字表達式，和二元運算表達式。它們恰好對應語法分析器所得到的語法樹上的兩種不同的節點——以上文提到的表達式1*(2+3)為例，如圖所示：

圖中藍色結點對應二元運算表達式，而綠色節點對應數字表達式。從語法樹上，我們可以看到，對於四則運算表達式，其語法樹有這麼幾個特點：

語法樹恰好是一顆二叉樹。
一個數字表達式的節點一定是一個葉子節點，沒有左右孩子節點。
而一個二元運算表達式，則恰好相反——它有，且一定有兩個孩子節點（因為二元運算符號左右兩邊必然都要有表達式）。
這兩個葉子節點的類型，是籠統的「表達式」，既可以是二元運算表達式，也可以是數字表達式。

此外，不難看出對於兩個具有父子關係的節點來說，子節點的運算優先順序要高於父節點——這個運算優先順序，跟數學上的四則運算的運算優先順序規則完全一致。

基於此，我們可以很容易地採用這樣一種方式，設計兩種表達式在C++中的類的結構：

我們首先定義一個Expression類作為基類——這是所有表達式類型的公共基類，然後再在基類的基礎上，對其進行擴展，得到兩種表達式派生類：NumberExpression，表示數字表達式，以及BinaryExpression，表示二元運算表達式。

這裡我們首先給出Expression類的基礎代碼——裡面目前還是空的：

class Expressionn{npublic:ntnn};n

接下來我們給出NumberExpression類的定義——為了方便起見，這裡把所有成員都設置為公有：

class NumberExpression :public Expressionn{npublic:ntint Value;ntNumberExpression(int number)nt{nttValue = number;nt}nn};n

我們可以看到，NumberExpression只有一個整型成員value（這裡只考慮整數），以及對應的構造函數。

最後我們給出BinaryExpression的定義：

class BinaryExpression :public Expressionn{npublic:ntshared_ptr<Expression> First;ntshared_ptr<Expression> Second;ntBinaryOperator Op;ntBinaryExpression(BinaryOperator theOp, shared_ptr<Expression> theLeft, shared_ptr<Expression> theRight) :nttOp(theOp), First(theLeft), Second(theRight) {nnt}n};n

我們可以看到，BinaryExpression的成員包括運算符Op，以及兩個表達式成員First和Second——《如何》原文使用的是裸指針，而這裡使用了C++11提供的智能指針shared_ptr。正如我們上文所說，BinaryExpression的孩子節點，既可以是數字，也可以是二元運算，所以這裡shared_ptr對應的類型，只能是兩種表達式的基類Expression——這樣就可以確保孩子節點的類型不受限制。

BinaryExpression的構造函數使用初始化列表定義三個成員變數，其中Op是一個定義好的enum class，代碼如下：

enum class BinaryOperatorn{ntPlus,ntMinus,ntMultiply,ntDivide,n};n

到這一步，對AST的聲明所需的三種Expression類的構造，就基本完成了——注意是「基本」，因為我們還有些工作，不能就這麼結束。

毫無疑問，在AST的構造過程中，會在堆上建立對象——《如何》原文手動使用delete來負責回收內存，而這裡將全程使用shared_ptr，所以不需要手動回收內存，堆對象什麼時候需要回收，由shared_ptr進行管理。但是這樣一來，就引出了一個問題——以我們目前的代碼，當一個BinaryExpression結點對象需要析構的話，會發生什麼呢？

我們知道，當我們需要對一個類的對象進行析構的時候，我們還需要對這個類的成員對象（如果有）進行析構——比如說，對於以下代碼：

class Basen{n};nnclass Derived : Basen{n string s {"This is a very long string that force std::string to allocate a buffer."};n};n

這裡std::string初始化的時候保存了一個非常長的字元串，所以它就必須申請額外的內存來保存它。如果我們現在要銷毀Derived類的某個實例對象的話，那麼我們就必須首先銷毀它的std::string成員對象。

本來，這個過程是由Derived類的析構函數自動完成的——它在調用的時候，首先會調用std::string的析構函數來回收它放在堆內存上的字元串，然後才會銷毀自己。整個過程非常安全，不會產生內存泄露——如下代碼所示：

Derived* obj = new Derived;n delete obj;n

但是這個安全的過程，有一個非常重要的前提條件：我們調用的是Derived自己的析構函數。當這個條件不滿足，比如這樣的情況，又會怎麼樣呢？

Base* obj = new Derived;n delete obj;n

毫無疑問，delete語句不可能知道obj到底是不是Derived，所以就只調用了Base的析構函數。這完全是因為我們new Derived後把指針的類型轉換成了Base*。

在這種情況下，由於我們只調用了Base函數的析構函數，卻沒有調用Derived類的析構函數，所以字元串就沒有釋放。而delete了之後，我們也丟掉了對這個對象的引用——於是就產生了內存泄露，堆上的字元串沒人管了。

現在，再回過頭來看我們的BinaryExpression類——大家不難看出問題在哪。沒錯，為了保證First和Second可以指向兩種表達式類，我們將其定義成了Expression類型的shared_ptr——於是在目前的情況下，就會出現析構的時候無法調用正確的析構函數，進而產生內存泄露問題的隱患。

而要解決這個問題，方法也比較簡單——我們需要給Expression基類，添加一個虛析構函數：

class Expressionn{npublic:ntbool IsLeft;ntExpression() {nttIsLeft = false;nt}ntvirtual ~Expression() = default;n};n

當shared_ptr認為某個對象需要回收的時候，它就會首先調用基類的析構函數——而這是一個虛析構函數，已經被派生類的析構函數給覆蓋掉了。這樣一來，我們就能保證當對象析構時，調用的是正確的析構函數。

這裡需要說明的是——我們額外添加了一個bool類型變數IsLeft，它的作用是，標記對象是否為左表達式。這個變數的作用是——如果我們需要從AST還原回正確的四則運算表達式的話，那麼這個變數可以幫助我們，對於是否需要給表達式加上括弧，做出正確的判斷（因為減法和除法不允許交換律）。

上篇的內容就先寫這些——改寫語法分析器的部分留到下篇再講。作為一名弱渣，貿然開坑，壓力實在很大——如果有什麼疏漏，還請各位大神不吝賜教。

下篇地址：

https://zhuanlan.zhihu.com/p/23139200