以Boost.Spirit實作算式計算機

Spirit是開源碼C++程式庫Boost裡的一個項目，大量使用了C++ Template Meta-Programming實作技術。它提供了一個用來實作語言剖析器的框架，就好像lex/yacc一樣是專門用來製作語言剖析器的工具。但是Spirit因為應用了C++ Template Meta-Programming的技術，使得我們可以在C++程式碼中寫出相當於EBNF 的描述且可直接編譯並執行，也因為如此Spirit是一套既神奇又威力強大的工具程式庫。

按照慣例，前面我們已經以手工的方法，以及lex/yacc的方式實作了算式計算機，這次我們要使用Spirit來作個簡單的算式計算機。

EBNF表示式

雖然前面我們已經提到過Spirit的神奇的能力，也就是可以直接把EBNF式直接以程式碼的形式寫在C++程式碼內，但是因為受限於C++程式語言的語言，有些表式法需要作些調動，這裡面主要有幾個地方的語法需要注意。

A B

上面是原EBNF表示式的寫法，用來表示一個序列，A之後會有個B。而在Spirit裡需改寫成如下的形式。

A >> B

看起來沒有什麼太大的不同，也可以很容易的理解這是表示在A之後跟著B的序列。再來是*號的用法。

A*

在EBNF內，在符號A之後加個*號，表示A的數量是可重複的，可以是0個以上的A所構成的序列。而在Spirit中需改寫成如下形式。

*A

正好相反，需要把*號擺到符號的前面，因為在C++裡面並沒有任何後序式的*號運算元。不過就算改成前置式也不會影響到原來所代表的意義，並不會造成什麼衝突，容易理解。

A?

這是表示符號A是可有可無，也就是A的數量可以是0個或一個。以下改成以Spirit的寫法。

!A

如你所見到的，問號變成驚嘆號，同時也提到前面變成前置式。那麼一個以上的表示式呢？一樣使用加號，也一樣改成前置式即可，如下所示。

+A

現在來看一個簡單的範例，如下所示是EBNF式，用來表示以逗號分隔的數字的EBNF表示式。

S := INTEGER (',' INTEGER)*

改成Spirit的形式。

S = INTEGER >> *(',' INTEGER);

很直接，也不需要再多作說明。不過上面的式子還不是最終可用的版本，底下還會再陸續交待清楚。

Parser

在上面我們所看到的EBNF表示S式中的INTEGER以及逗號是終端符號。根據我們在lex及yacc的教學中知道，這些終端符號是由lex或具有lex功能，也就是字彙剖析器所解析出來再傳遞給語法剖析器的。在Spirit中對應於yacc工具的語法剖析器功能就是在上一小節中，可以直接在C++程式碼中寫下EBNF表示式的功能，而對應lex的字彙剖析器的功能就是這一小節要介紹的內容。

在Spirit中提供了許多的Parser，這裡的Parser指的是字彙剖析器，像是整數的剖析器，浮點數的剖析器，字串的剖析器，或字元的剖析器等等，這些Parser可以和上面的EBNF表示式一樣混合在一起直接寫在程式碼內。例如上例的INTEGER就可以使用整數Parser來代換，而逗號就用字元的Parser來代換。

以下列出常用的Parser。

int_p             整數
real_p            浮點數
ch_p              字元
str_p             字串
range_p           字元範圍
chseq_p           字元集
anychar_p         任何字元
alnum_p           英數字元
alpha_p           英文字母
space_p           空白字元

底下舉幾個簡單的範例來作說明如何使用這些parser。左邊是常規表示式，而右邊是Spirit的寫法。

abc               ch_p('a') >> ch_p('b') >> ch_p('c')
abc*              ch_p('a') >> ch_p('b') >> *ch_p('c')
abc+              ch_p('a') >> ch_p('b') >> +ch_p('c')
a(bc)+            ch_p('a') >> +(ch_p('b') >> ch_p('c'))
a(bc)?            ch_p('a') >> !(ch_p('b') >> ch_p('c'))
[abc]             chseq_p("abc")
[a-z]             range_p('a','z')

看過以上幾個簡單的範例之後，相信對於Spirit的Parser有了基本的了解。現在我們可以把S寫成完整的Spirit式EBNF表示式了，如下所示。

S = int_p >> *(ch_p(',') >> int_p);

Spirit可以讓我們直接在C++程式裡面使用EBNF表示式，我們要怎麼在程式裡面使用S呢？S在程式裡面代表什麼？

在Spirit中S代表的是一個Rule，它的型別是rule<>，這是一般的表示式類型，事實上在Spirit裡一個rule<>已經是一個可以工作的Parser了。S完整的定義如下。

rule<> S = int_p >> *(ch_p(',') >> int_p);

在Spirit中有一個parse函數，使用parse函數我們就可以使用S來解析資料，使用方法如下。

bool parse_number(char const* str)
{
  return parse(str, S, space_p).full;
}

parse的第一個參數是文字串流來源，第二個參數就是我們提供的rule(parse)，而第三個參數也是個Rule，是專門使用來過濾空白字元的，一般我們直接拿space_p來使用就足夠了，如果還有更複雜的過濾需求的話再另外提供即可。

最後parse函數的回傳值是一個叫作parse_info的結構，我們在上例裡面只拿它的full欄位來使用。full可以告訴我們解析的動作是否正常完成，即從資料來源的開頭一直解析到資料結尾都沒有任何錯誤發生。

動作程式碼

現在我們已經知道怎麼使用Spirit來實作一個Parser了，不過這個Parser還不怎麼有用，因為它還只能夠檢查文字資料是不是符合我們的語法。至少還得像lex/yacc一樣還能插入我們自己的動作程式碼到Parser裡面，這樣這個Parser才能真正為我們作點什麼。

繼續拿上面的例子來作說明。

S = int_p >> *(',' >> int_p);

假如每當我們的Parser解析出一個數字時，我們的程式想要獲得通知以便把這個數字儲存起來或者直接拿它來作點運算。在yacc裡面我們會在二個int_p後面插入一段動作程式碼，而在Spirit中也是一樣的作法，而且也很直覺。

S = int_p[&f] >> *(',' >> int_p[&f]);

在二個int_p的後面我們各加了一對方括號，而在方括號中是個&f。f是個函數，我們使用這樣的語法告訴Spirit當解析到一個int時呼叫我們的動作程式碼f函數。f函數有一個int的參數，我們可以直接使用這個參數，如果我們現在是使用ch_p則參數變為char，依此類推。

而你也可以使用一般型的動作程式碼函數，它的原型如下。

template<typename Iterator>
void func(Iterator first, Iterator last);

Iterator對應資料流的類型，例如char*。這個函數帶有二個參數，分別是解析出來的token在資料流中的開始及結尾。

你也可以一次使用好幾個動作程式碼在同一個位置，像下面的例子一次呼叫三個函數。如果指定二個以上的動作程式碼的話，它們會以左至右的次序被呼叫。

S = int_p[&f1][&f2][&f3];

呼叫函式也能是個functor(仿函式)，它的原型如下。

struct myfunctor
{
  template<typename Iterator>
  void operator()(Iterator first, Iterator last) const;
};

使用方法如下。

S = int_p[myfunctor()];

實作

到此為此，我們已經學習了如何使用Spirit來製作Parser的相關知識，現在我們可以正式拿Spirit來實作一個算式計算機。

根據前面的介紹，首先我們把表示算式計算機的EBNF表示式改成以Spirit形式的表示式，工作就已經算是完成一大半，如下所示。

rule<> group, factor, term, expression;

group = ch_p(',') >> expression >> ch_p(',');
factor = int_p | group;
term = factor >> *((ch_p('*') >> factor) | (ch_p('/') >> factor);
expression = term >> *((ch_p('+' >> term) | (ch_p('-') >> term)

接著再加上parse函式的使用，就已經是一個可以運作的算式計算機程式了，剩下的只要再補上動作程式碼，用來處理真正的數值運算，整個程式就可以完成。底下列出不包含動作程式碼，但可以實際動作的程式列表。

#include <iostream>
using namespace std;

#include "boost/spirit/core.hpp"
using namespace boost::spirit;

int main()
{
  rule<phrase_scanner_t> group, factor, term, expression;

  group = ch_p('(') >> expression >> ch_p(')');
  factor = int_p | group;
  term = factor >> *((ch_p('*') >> factor) | (ch_p('/') >> factor));
  expression = term >> *((ch_p('+') >> term) | (ch_p('-') >> term));

  string str;
  while (getline(cin, str))
  {
    if (str.empty() || str[0] == 'q' || str[0] == 'Q')
      break;

    if (parse(str.c_str(), expression, space_p).full)
    { // Parsing succeeded
      cout << "Parsing succeeded\n";
    }
    else
    { // Parsing failed
      break;
    }
  }
  return 0;
}

把這個程式拿來編譯後執行起來看看，它可以用來檢驗一個算式的正確性。接著，我們要加上動作程式碼，讓它可以作真正的運算，計算出最後的結果。

前面我們學過動作程式碼的形式及如何撰寫動作程式碼，底下我們就以前面所學寫下四個分別用來計算加減乘除以及一個用來儲存得到的數字的動作程式碼，另外再配合一個用來模擬堆疊的vector容器。

vector<int> v;

void push_int(int i)
{
  v.push_back(i);
}

void do_add(char const* first, char const* last)
{
  int a, b;
  a = v.back(), v.pop_back();
  b = v.back(), v.pop_back();
  v.push_back(b + a);
}

void do_sub(char const* first, char const* last)
{
  int a, b;
  a = v.back(), v.pop_back();
  b = v.back(), v.pop_back();
  v.push_back(b - a);
}

void do_mul(char const* first, char const* last)
{
  int a, b;
  a = v.back(), v.pop_back();
  b = v.back(), v.pop_back();
  v.push_back(b * a);
}

void do_div(char const* first, char const* last)
{
  int a, b;
  a = v.back(), v.pop_back();
  b = v.back(), v.pop_back();
  v.push_back(b / a);
}

這裡所使用的方法和我們在學習資料結構與演算法時用來處理算式的方法一樣，也就是將算式由中序式轉換為後序式，然後再配合堆疊，就可以很容易的把算式結果計算出來。這部份的原理就不再這裡再複述一次，有興趣的話自行參考相關資料。

最後我們再把動作程式碼插入到rule內，整個Parser就完成。如下所示。

group = '(' >> expression >> ')';
factor = int_p[&push_int] | group;
term = factor >> *(('*' >> factor)[&do_mul] | ('/' >> factor)[&do_div]);
expression = term >> *('+' >> term)[&do_add] | ('-' >> term)[&do_sub]);

另外補充一下。在上面這幾行的rule裡面就沒有再看到ch_p的使用，那是因為Spirit已經有對一些operator作針對字元參數的覆載(overload)，所以我們就可以省略掉ch_p。不過在有些情況下，C++編譯器還是會找不到正確的operator函式，當這樣的情況發生時，我們只需明確的寫上ch_p即可。或者為了避免這樣的情況發生，你也可以一律都用統一的寫法加上ch_p。