很讚的遊戲編輯器

這篇文章是算式計算機系列的完結篇。 (E)BNF表示式 手工打造算式計算機 以lex/yacc實作算式計算機 以Boost.Spirit實作算式計算機 ; ( 下載範例 ) yardparser 在使用上雖然沒辨法像Boost Spirit 一樣那麼直覺便利，可以將EBNF 語法規則直接定義在程式裡建立解析器，但使用類似的手法一樣可以將EBNF語法規則轉換為程式定義，建立一個語法解析器。yardparser也沒辨法像Boos Spirit那樣，可以在執行時期(run-time)動態的改變或產生新的解析器。除了上述的不同處之外，最大的差異是 yardparser 的編譯時間非常短及以 yardparser建立的parser執行速度非常快，同時產生的目的碼大小(code size)也相對小很多。 Boost Spirit 因為大量使用了 C++ Template Meta-programming 的相關技術，很完美的將EBNF語法規則語句嵌入到C++程式碼內和我們所寫的程式碼結合在一起，相當直覺也相當神奇。只不過如果從得到的編譯時間和執行效率來看，只能說 Boost Spirit 為我們提供了相當出色的語法糖(syntactic sugar)，對於大型複雜的語法來說反而較難以適用。而 yardparser 雖然在使用上不如Boost Spirit那樣直覺便利，但至少在編譯時間和執行效率是大大滿足我們日常工作的需求。 底下同樣以簡單範例開始，介紹yardparser的基本使用。 A B 上面是原EBNF表示式的寫法，用來表示一個序列，在 A之後會有個B。而使用yardparser 則寫成如下的形式。 struct AB : CharSeq<'A', 'B'> { }; CharSeq 是 yardparser裡面事先定義好的 一個struct，作用是對輸入來源串流讀入字元來進行匹配動作。 (AB)* 以上定義了零個以上個AB序列的EBNF表示式的寫法，底下一樣轉換成yardparser的寫法。 struct StarAB : Star<AB> { }; AB是上一個例子裡定義，用來匹配 AB序列的規則。而Star是yardparser事先定義的一個struct，把A...

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 在上面我們所看...

前面我們透過 手工的方式 實作了一個簡易的算式計算機，現在我們要開始使用工具來作同樣的事，比較看看手工和使用工具有什麼不同的差別。首先要介紹的就是lex&yacc。 lex & yacc lex(Lexical Analyzar)及yacc(Yet Another Compiler Compiler)是用來輔助程式設計師製作語法剖析器的程式工具。lex的工作就是幫助我們將輸入的資料文字串流分解成一個個有意義的token，而yacc的工作就是幫我們分析這些token和我們定義的規則作匹配。下圖中所表示的是使用lex及yacc的一般工作流程。 首先看到yacc會讀入一個.y檔案，這裡.y檔案的內容就是我們使用類似(E)BNF語法定義的語法規則，yacc會分析這些語法規則後，幫我們產生可以用來解析這些規則的程式碼，而這個檔案一般名稱預設為y.tab.c，產生的程式碼裡面最重要的一個的函式叫作yyparse。 同yacc類似，lex也會讀入一個.l的檔案，這個檔案裡面定義的是如何從文字流裡解出token的規則，使用的方法是常規表示式(regular expression)。在圖的左側中間我們還可以看到有一個叫作y.tab.h的檔案從yacc產生出來並餵給lex作輸入，這個檔案是yacc根據在讀入的.y檔裡面所定義的token代號所產生出來的一個header，這樣yacc及lex產生出來的程式碼裡面就可以使用共通定義的代碼而不必各寫個的。lex分析過.l檔案後也會產生一個一般預設叫作lex.yy.c的原始碼檔案，裡頭最重要的一個函式叫作yylex。 最後，我們把yacc產生出來的y.tab.c還有lex產生出來的lex.yy.c，以及其它我們自己撰寫的原始碼檔案一起拿來編譯再作連結，最後產生出來的就是一個可以用來解析我們定義的語法的解析器工具。以上是整個lex及yacc的使用流程概觀。 常規表示式 在正式使用lex之前，我們首先來對常規表示法作一個基本的認識。常規表示法是一種用來表示字串樣式(pattern)的中繼語言，就好比前文所介紹的(E)BNF表示式一樣，都是用來描述其它語言的語言，只不過用途不太一樣罷了。 常規表示式使用一些中繼符號(meta-symbol)以及ASCII字元定義字串樣式，以下列出一些常規表示式所使用的符號。 . 表示除了換行字元...

前面已經對 (E)BNF表示式 作過一個簡介，現在要來看看怎麼樣實作一個可以處理簡單的整數四則運算的Parser。因為我們的重點將放在Parser的語法器(syntax analyser)上，所以忽略字彙剖析器(lexical scanner)不談，雖然一個Parser是由這二部份構成。 ; 許多Parser或Compiler相關的書籍資料上，都會拿簡單的算式計算機作為範例，可以找的到算式計算機的EBNF表示式，底下我們直接引用： expression = term ('+' term | '-' term)* term = factor ('*' factor | '/' factor)* factor = integer | group group = '(' expression ')' 上面的語法可以使用來解析如下的算式： 1+2-3*4 5*(6-(7+8)/9) ; 那麼要如何實作出能夠解析符合我們定義好的規則語法的資料的剖析器呢？ 一個剖析器的轉換工作主要分成二個部份：將讀入的資料串流分解為有意義的小單位 token，及處理這些token間的關係。將資料串流分解成小單位 token的工作我們不多作說明。我們現在直接假設我們已經能夠得到分解完畢的 token了，接下來的工作就是分析這些 token之間的關係，檢查它們是否符合我們定義的規則語法。 作法相當的直接。首先，我們從資料串流中獲取一個token，接著檢查這個token是否符合我們正在檢查的語法的第一個符號，如果比對結果是符合的話，那麼我們就把當前的 token 給丟棄並再讀入下一個token，接著再繼續拿這個token和規則的下一個符號作比對。在比對規則時，如果中間遇到了非終端符號，則這個非終端符號會再展開。一直重複這個動作直到讀完所有資料為止，比對的程序才結束。 拿我們定義的group規則來作說明，以下為虛擬碼。 // 檢查當前的token是否是我們所期望匹配的符號 void match(token) {   if (current_token == token)     current_token = get_next_token(); // 如果匹配成功則再讀入下一個符號   else   ...

BNF(Backus-Naur Form)是由John Backus所開發，可用來表示與上下文無關文法的語言，也就是一種用來描述語言的中繼語言(meta-language)。一個BNF表示式是由一個非終端符號(non-terminal)和它的產生式所組成，產生式可以是一個終端符號(terminal)和非終端符號組成的序列。(終端符號中的標點符號一般使用單引號括起來，而字串則使用雙引號) 底下為一個簡單的範例： sent := subj verb '.' subj := “Birds” verb := “sing” 在上面的例子裡面，如Birds、sing及句點('.')表示終端符號。而sent及verb表示為非終端符號。這條BNF句子定義了一條文法，表示的意思為，一個sent是由subj及verb再以一個句點為結尾所構成。 BNF表示式有以下幾種主要表示形式： (1) S := A B C (2) S := A | B | C (3) S := {A} 第一條表示說，S是由ABC三個符號所定義， 而ABC是以序列的形式依序出現，也就是說A之後一定跟著一個B，而B之後一定跟著一個C。第二條表示說，由S可推導出A或B或C其中之一。第三條表示說，由S可以推導出一個或多個A。 範例： S := x A A := y | z (1) xy (O) (2) xz (O) (3) xx (X) (4) yz (X) 以上4個範例中，只有(1)(2)是符合上面BNF文法定義的句子，因為x之後只能接y或z所以(3)不符合文法，因為S只能以x開頭為句子所以(4)也文法錯誤。 範例： id := alpha {alpha} alpha := a | b | c | d (1) aabbbcdd (O) (2) cabbbda (O) (3) baccab (O) (4) bdax (X) (5) 5acd (X) 在上面的5個範例裡面，其中(1)(2)(3)項是正確符合上面BNF的文法定義。而(4)因為alpha裡不包含x符號所以語法不正確。而(5)因為alpha裡面不包含5所以也不正確。 範例： S := '-' FN | FN FN := DL | DL '.' DL DL ...