loop_in_codes

游戲資源包簡(jiǎn)單設(shè)計(jì)

     摘要: 一般的資源包文件格式基本上是由包文件頭和包內(nèi)容組成。文件頭描述資源包內(nèi)打包的文件
信息，例如文件名、在資源包里的偏移、大小、壓縮加密相關(guān)信息等；包內(nèi)容則是實(shí)際文件
打包在一起后的內(nèi)容，可能直接是未打包前文件連續(xù)存放在一起的內(nèi)容，也可能是相同類型
文件除掉文件頭的內(nèi)容（例如某個(gè)資源包里打包的全部是相同格式的圖片文件，那么這些圖
片文件被打包后包內(nèi)只需要保存一個(gè)圖片文件頭，包內(nèi)容全部是直接的圖片數(shù)據(jù)）。   閱讀全文

posted @ 2010-06-19 14:59 Kevin Lynx 閱讀(4712) | 評(píng)論 (5) | 編輯 收藏

基于棧的虛擬機(jī)的實(shí)現(xiàn)

在上次的編譯原理練習(xí)中，生成的目標(biāo)代碼是別人寫的一個(gè)基于寄存器的簡(jiǎn)單虛擬機(jī)。這

回這個(gè)簡(jiǎn)單的基于棧的虛擬機(jī)，純碎是為了彌補(bǔ)上回的練習(xí)不足。

基于寄存器(register based)的虛擬機(jī)和基于棧(stack based)的虛擬機(jī)主要的不同在于

對(duì)指令運(yùn)算的中間值的保存方式。這些中間值包括各種運(yùn)算的結(jié)果值，傳給各個(gè)指令的參

數(shù)等等。前者一般會(huì)設(shè)置幾個(gè)寄存器，如累加寄存器；后者則沒有寄存器，只有一個(gè)用來(lái)

保存這些值的棧。例如，這里我實(shí)現(xiàn)的SM（stack based machine）中的ADD指令：

ADD：從棧中依次彈出兩個(gè)數(shù)a和b，然后將b+a壓棧（b是左操作數(shù)）?；谶@樣一個(gè)方

式，SM中大部分指令都不需要操作數(shù)，其操作數(shù)都直接從棧頂取。因?yàn)檫@個(gè)虛擬機(jī)僅僅是

用于上回設(shè)計(jì)的簡(jiǎn)單語(yǔ)言的運(yùn)行，即沒有函數(shù)、只有數(shù)字類型、有if和while。在這回練習(xí)中

我甚至把邏輯運(yùn)算符給閹割了，只保留了大于小于之類的關(guān)系運(yùn)算符。以下是該語(yǔ)言計(jì)算階

乘的例子：

read x;
if( x > 0 )
{
fac = 1;
while( x > 0 )
{
  fac = fac * x;
  x = x - 1;
}
write fac;
}
else
{
write 0;
}

基本上同《編譯原理與實(shí)踐》里的例子一樣，這樣省得我去琢磨語(yǔ)言文法。

不過，SM中還是有一個(gè)寄存器，即指令指針寄存器(pc)，永遠(yuǎn)指向?qū)⒁獔?zhí)行的指令。在實(shí)現(xiàn)中，

所有指令都被保存一個(gè)數(shù)組里，所以pc就是一個(gè)指向數(shù)組索引的整數(shù)值。

SM中有一個(gè)簡(jiǎn)單的內(nèi)存，只用于保存程序中的全局變量（只有全局變量）。同樣，這個(gè)虛擬的

內(nèi)存也被簡(jiǎn)單地用一個(gè)數(shù)組來(lái)實(shí)現(xiàn)，所以，指令中的所有地址，都是數(shù)組索引值。

SM的代碼文件直接就是指令序列的二進(jìn)制表示。在這個(gè)二進(jìn)制文件中，內(nèi)容依次為：操作碼（1

字節(jié)），操作數(shù)（4字節(jié)，如果有的話），操作碼，操作數(shù)，。。。SM讀取這樣的文件，將這些

指令放進(jìn)指令數(shù)組，然后逐條解釋執(zhí)行，直到遇到空指令。

代碼中的test是上面簡(jiǎn)單提到的編程語(yǔ)言的編譯程序，該程序?qū)⒃创a編譯為SM可執(zhí)行的二進(jìn)制

文件（sm后綴）。為了方便調(diào)試，SM本身可以根據(jù)命令行參數(shù)輸出二進(jìn)制文件對(duì)應(yīng)的反匯編代碼，

這可以方便我調(diào)試編譯程序的代碼生成是否正常工作。同時(shí)，當(dāng)初為了測(cè)試SM的正確性，還寫了

個(gè)簡(jiǎn)單的匯編程序（sasm），可以把SM的匯編代碼轉(zhuǎn)換為二進(jìn)制文件。

這回我特地在文法中間插入action丟給yacc處理，在賦值語(yǔ)句中一切正常。但是在if中yacc依然

提示警告，看起來(lái)應(yīng)該跟if中的懸掛else二義性有關(guān)系。不過通過添加空的文法符號(hào)，居然解決了。

不清楚為什么上回死活有問題，詭異了。

 

下載SM

posted @ 2010-04-15 19:56 Kevin Lynx 閱讀(7794) | 評(píng)論 (0) | 編輯 收藏

[總結(jié)]中間/目標(biāo)代碼生成

語(yǔ)法制導(dǎo)翻譯、中間代碼生成、目標(biāo)代碼生成在很多時(shí)候并不存在嚴(yán)格的劃分。對(duì)于目標(biāo)
代碼是某個(gè)簡(jiǎn)單的虛擬機(jī)代碼而言，中間代碼完全可以就是目標(biāo)代碼。中間代碼生成中結(jié)
合了語(yǔ)法制導(dǎo)翻譯，講述了大部分常規(guī)的編程語(yǔ)言結(jié)構(gòu)是怎樣被翻譯成一種接近目標(biāo)代碼
的形式（所謂的中間代碼形式）。本身，匯編代碼就是對(duì)應(yīng)于機(jī)器碼的一種字符表示形式，
而中間代碼的大部分表示形式--三地址碼，也是一種接近匯編代碼的形式。

簡(jiǎn)單來(lái)說(shuō)，詞法分析階段將字符整理為單詞；語(yǔ)法分析則將這些代碼整理為一種層次結(jié)構(gòu)
（識(shí)別了程序代碼要表達(dá)的意思）；那么，在接下來(lái)的階段里，則是將這些層次結(jié)構(gòu)翻譯
為線性結(jié)構(gòu)。也就是類似于匯編代碼這種格式。這種格式容易被機(jī)器識(shí)別：機(jī)器只需要順
序地一條一條地取指令并執(zhí)行之即可。這種簡(jiǎn)單直接性也使得要實(shí)現(xiàn)類似的虛擬機(jī)變得容
易。

翻譯過程并不需要先生成語(yǔ)法樹，在語(yǔ)法分析階段的語(yǔ)法識(shí)別過程中，即可以對(duì)應(yīng)地翻譯。
因?yàn)闊o(wú)論是自頂向下還是自底向上的語(yǔ)法分析，都可以先去識(shí)別葉子節(jié)點(diǎn)。在自頂向下中，
可以使用語(yǔ)法樹（并不真實(shí)存在）的后續(xù)遍歷，使得葉子節(jié)點(diǎn)先于父節(jié)點(diǎn)翻譯；而在自底
向上的分析中，因?yàn)槠浔旧砭褪窍茸R(shí)別葉子節(jié)點(diǎn)（所謂的規(guī)約），所以可以更自然地翻譯。

因?yàn)槲乙彩窍雽?shí)踐下這些東西，所以還是使用lex/yacc來(lái)進(jìn)行練習(xí)，省得自己去寫詞法和
語(yǔ)法分析。不過在使用yacc的過程中，經(jīng)常會(huì)出現(xiàn)一些shift/reduce conflicts的警告/錯(cuò)
誤，解決這些問題也費(fèi)了不少時(shí)間。不過，也可能是我對(duì)LALR細(xì)節(jié)不熟悉，加之于文法本
身寫的有問題，才弄得如此折騰?，F(xiàn)在我覺得上下文無(wú)關(guān)文法在整個(gè)編譯原理理論中非常
重要。一個(gè)好的文法可以準(zhǔn)確無(wú)誤地描述一種編程語(yǔ)言的語(yǔ)法，還可以指導(dǎo)編譯器的開發(fā)。
當(dāng)然，大部分常規(guī)的語(yǔ)言都可以找到現(xiàn)成的文法。

例子程序構(gòu)造了一個(gè)簡(jiǎn)單的翻譯程序，支持簡(jiǎn)單的算術(shù)表達(dá)式、整數(shù)變量、if、while、以
及僅用于if和while的邏輯表達(dá)式。為了省力，虛擬機(jī)用的是《編譯原理與實(shí)踐》中現(xiàn)成的。
目標(biāo)代碼也就直接是該虛擬機(jī)對(duì)應(yīng)的代碼。該虛擬機(jī)主要有5個(gè)寄存器：指令指針寄存器、
2個(gè)累加寄存器、全局變量基址寄存器、臨時(shí)變量基址寄存器。這里的臨時(shí)變量不同于編
程語(yǔ)言說(shuō)的臨時(shí)變量，它是表達(dá)式計(jì)算的臨時(shí)值，例如a+b+c，a+b的結(jié)果值就可以被實(shí)現(xiàn)
為存儲(chǔ)到一個(gè)臨時(shí)值中。

對(duì)于算術(shù)表達(dá)式，其實(shí)翻譯起來(lái)很簡(jiǎn)單。主要是if/while和邏輯表達(dá)式的翻譯。邏輯表達(dá)
式的翻譯例子中我甚至沒有處理短路代碼：a && func(1)中如果已經(jīng)計(jì)算出a為false了，
就沒必要計(jì)算func(1)了。這可能是受限于yacc，暫不深究。對(duì)于if和while，則主要涉及
到所謂的“回填”技術(shù)。

回填主要是應(yīng)對(duì)向前跳轉(zhuǎn)這種問題。例如在if的代碼生成中，需要測(cè)試if的邏輯表達(dá)式的
真假，如果為假，則需要跳轉(zhuǎn)到then-part之后。這里的then-part也就是if為真時(shí)要執(zhí)行
的代碼序列。而這個(gè)跳轉(zhuǎn)指令具體要跳到哪里，則需要在生成完then-part之后才能確定。
回填的解決方法，就是預(yù)留下這個(gè)跳轉(zhuǎn)指令的位置，等到then-part生成完了，得到了具
體的跳轉(zhuǎn)位置，再回去填寫那個(gè)跳轉(zhuǎn)指令。

在這個(gè)問題上，yacc也讓我折騰了一番。在if文法中：

selection_statement
: IF '(' logical_or_expr ')' {
  // 本來(lái)想在這里預(yù)留這個(gè)跳轉(zhuǎn)指令的位置
} statement %prec IFX {
   }

結(jié)果，yacc又給我conflicts和never reduced之類的警告，并且最終生成的代碼也不正常
（果然是無(wú)法忽略的警告）。看起來(lái)，yacc似乎不支持在文法內(nèi)部添加action。通過一個(gè)
空文法符號(hào)效果一樣。對(duì)于這個(gè)問題，我甚至莫名其妙地在某個(gè)晚上的夢(mèng)里當(dāng)面問了yacc
的作者。他肯定地告訴我：支持，當(dāng)然支持（中文）。今天仔細(xì)地在yacc文檔里找了下，
還真支持。而且對(duì)于空符號(hào)的使用，似乎也有些規(guī)則：$Sign: {action }。

后來(lái)解決這個(gè)問題的方法，算是我取巧了：
selection_statement
: IF '(' logical_or_expr IfBracket statement %prec IFX { ....}
IfBracket
: ')' {
     // 邪惡地利用了這個(gè)括號(hào)
   }
另外，因?yàn)樾枰С智短椎膇f/while，還專門使用了一個(gè)棧，用于保存這些需要回填的預(yù)留地址。

 

下載例子

posted @ 2010-04-09 20:22 Kevin Lynx 閱讀(8136) | 評(píng)論 (2) | 編輯 收藏

[總結(jié)]語(yǔ)法制導(dǎo)翻譯/語(yǔ)義分析

語(yǔ)義分析理論中并沒有語(yǔ)法和詞法分析階段中那么多算法。如同整個(gè)編譯原理里大部分理論
一樣，其都是為實(shí)踐編碼提供理論支持，從而可以讓實(shí)現(xiàn)簡(jiǎn)單機(jī)械地進(jìn)行---語(yǔ)法制導(dǎo)翻譯
也正是出于這個(gè)目的：通過建立理論，使得從語(yǔ)法樹翻譯到中間代碼（或者虛擬機(jī)代碼）更
為簡(jiǎn)單。

個(gè)人理解，語(yǔ)法制導(dǎo)翻譯就是在文法中加上屬性和各種動(dòng)作，這些動(dòng)作基本也就是這里的“
翻譯”；而語(yǔ)義分析，則是在整個(gè)過程所要進(jìn)行的一些上下文相關(guān)的分析動(dòng)作（如類型檢查
）。

羅列一些概念：

- 屬性：就是語(yǔ)法樹各個(gè)節(jié)點(diǎn)上所需要的“值”，例如對(duì)于算術(shù)表達(dá)式a=b+c，在其語(yǔ)法樹
中，每一個(gè)節(jié)點(diǎn)都會(huì)有一個(gè)數(shù)字屬性。屬性明顯不止包含數(shù)字/值這些東西，某個(gè)節(jié)點(diǎn)包含
哪些具體屬性完全取決于編譯器實(shí)現(xiàn)的需要。對(duì)于表達(dá)式a=b如果需要檢查a和b的類型是否
可以賦值（如在c語(yǔ)言中，struct XXX b就無(wú)法傳給int a），就需要在其節(jié)點(diǎn)中附加類型屬
性。---這里舉的例子也正是一種語(yǔ)義分析行為。

- 綜合屬性：某個(gè)節(jié)點(diǎn)的屬性依賴于其子節(jié)點(diǎn)的屬性，這種屬性計(jì)算起來(lái)很簡(jiǎn)單，尤其在遞
歸下降分析程序中。

- 繼承屬性：某個(gè)節(jié)點(diǎn)的屬性依賴于其父節(jié)點(diǎn)或者其兄弟節(jié)點(diǎn)。這個(gè)屬性計(jì)算起來(lái)要稍微麻
煩一些，需要一種屬性傳遞機(jī)制。在上一篇LL分析法的練習(xí)程序中，就使用了一個(gè)“值?！?br>來(lái)傳遞屬性。

- 依賴圖：上面提到屬性之間的依賴，在一棵語(yǔ)法中，通過箭頭描繪出這種依賴關(guān)系就得到
依賴圖，說(shuō)白了就是拿來(lái)方便看的，無(wú)視。

- 語(yǔ)法制導(dǎo)定義（SDD）：學(xué)編譯原理最煩的就是這些定義，一句話里總覺得有若干未知概
念，尤其在翻譯比較爛的時(shí)候。我覺得這個(gè)SDD就是在文法中穿插了若干屬性和翻譯動(dòng)作的
表示。

- S屬性的SDD：如果一個(gè)SDD的每一個(gè)屬性都是綜合屬性，那它就是S屬性的。

- L屬性的SDD：無(wú)視了，就是夾雜著綜合屬性和繼承屬性的SDD，不過繼承屬性有諸多條件
限制，大致上就是其某個(gè)屬性的依賴關(guān)系僅限于其左兄弟或者父節(jié)點(diǎn)。

其實(shí)這一切都并非它看上去的那么繁雜。在有了語(yǔ)法分析的基礎(chǔ)上，因?yàn)轳R上涉及到翻譯為
中間代碼（甚至?xí)苯臃g為虛擬機(jī)代碼），在這個(gè)階段直接把代碼中會(huì)做的事情書寫到文
法里，就得到了SDD。按照這個(gè)SDD，就可以較為機(jī)械地對(duì)應(yīng)寫出代碼。另一方面，在實(shí)際中
為了處理不同的翻譯問題，如類型檢查、各種控制語(yǔ)句的翻譯，直接參考相關(guān)的資料，看看
別人怎么處理的就行了。

練習(xí)程序是一個(gè)簡(jiǎn)單地處理c語(yǔ)言定義變量、定義struct類型的代碼。因?yàn)閏語(yǔ)言里的變量會(huì)
附帶類型屬性，用于類型檢查之類的問題，所以程序中保存這些變量的符號(hào)表自然也要保存
其類型。定義新的struct類型我這里直接建立了一個(gè)類型表，用于存儲(chǔ)所有的類型：基本類
型和程序員自定義類型。

練習(xí)程序直接使用了lex和yacc來(lái)生成詞法和語(yǔ)法分析模塊，通過直接在文法文件里(*.y)的
文法中穿插各種動(dòng)作來(lái)完成具體的處理邏輯。本來(lái)我最開始是想個(gè)類型檢查程序的，起碼可
以檢查一般的類型不匹配錯(cuò)誤/警告，不過后來(lái)僅僅做了變量/類型定義，就發(fā)現(xiàn)有一定代碼
量了，索性就懶得做下去了。

下載例子

posted @ 2010-03-28 20:19 Kevin Lynx 閱讀(10195) | 評(píng)論 (3) | 編輯 收藏

[總結(jié)]LL(1)分析法及其實(shí)現(xiàn)

LL(1)分析法和遞歸下降分析法同屬于自頂向下分析法。相對(duì)于遞歸下降而言，LL通過顯示
地維護(hù)一個(gè)棧來(lái)進(jìn)行語(yǔ)法分析，遞歸下降則是利用了函數(shù)調(diào)用棧。

LL分析法主要由分析棧、分析表和一個(gè)驅(qū)動(dòng)算法組成。其實(shí)LL的分析算法還是很容易懂的，
主要就是一個(gè)匹配替換的過程。而要構(gòu)造這里的分析表，則還涉及計(jì)算first集和follow集
的算法。

個(gè)人覺得龍書在解釋這些算法和概念時(shí)都非常清楚細(xì)致，雖然也有人說(shuō)它很晦澀。

first集和follow集的計(jì)算，拋開書上給的嚴(yán)密算法，用人的思維去理解（對(duì)于compiler
compiler則需要用程序去構(gòu)造這些集合，這是讓計(jì)算機(jī)去理解），其實(shí)很簡(jiǎn)單：

1、對(duì)于某個(gè)非終結(jié)符A的first集（first(A)），簡(jiǎn)單地說(shuō)就是由A推導(dǎo)得到的串的首符號(hào)的
集合：A->aB，那么這里的a就屬于first(A)，很形象。
2、follow(A)，則是緊隨A的終結(jié)符號(hào)集合，例如B->Aa，這里的a就屬于follow(A)，也很形
象。

當(dāng)然，因?yàn)槲姆ǚ?hào)中有epsilon，所以在計(jì)算上面兩個(gè)集合時(shí)則會(huì)涉及到一種傳遞性。例
如，A->Bc, B->epsilon，B可以推導(dǎo)出epsilon，也就是基本等同于沒有，那么first(A)中
就會(huì)包含c符號(hào)。

在了解了first集和follow集的計(jì)算方法后，則可以通過另一些規(guī)則構(gòu)造出LL需要的分析表。

編譯原理里總有很多很多的理論和算法。但正是這些理論和算法，使得編譯器的實(shí)現(xiàn)變得簡(jiǎn)
單，代碼易維護(hù)。

在某個(gè)特定的編程語(yǔ)言中，因?yàn)槠湮姆ㄒ欢?，所以?duì)于其LL(1)實(shí)現(xiàn)中的分析表就是確定的
。我們也不需要在程序里動(dòng)態(tài)構(gòu)造first和follow集合。

那么，要實(shí)現(xiàn)一個(gè)LL(1)分析法，大致步驟就集中于：設(shè)計(jì)文法->建立該文法的分析表->編
碼。

LL分析法是不能處理左遞歸文法的，例如：expr->expr + term，因?yàn)樽筮f歸文法會(huì)讓對(duì)應(yīng)
的分析表里某一項(xiàng)存在多個(gè)候選式。這里，又會(huì)涉及到消除左遞歸的方法。這個(gè)方法也很簡(jiǎn)
單，只需要把文法推導(dǎo)式代入如下的公式即可：

A -> AB | C 等價(jià)于：A -> CX, X -> BX | epsilon

最后一個(gè)問題是，如何在LL分析過程中建立抽象語(yǔ)法樹呢？雖然這里的LL分析法可以檢查文
法對(duì)應(yīng)的語(yǔ)言是否合法有效，但是似乎還不能做任何有意義的事情。這個(gè)問題歸結(jié)于語(yǔ)法制
導(dǎo)翻譯，一般在編譯原理教程中語(yǔ)法分析后的章節(jié)里。

LL分析法最大的悲劇在于將一棵在人看來(lái)清晰直白的語(yǔ)法樹分割了。在遞歸下降分析法中，
一個(gè)樹節(jié)點(diǎn)所需要的屬性（例如算術(shù)運(yùn)算符所需要的操作數(shù)）可以直接由其子節(jié)點(diǎn)得到。但
是，在為了消除左遞歸而改變了的文法式子中，一個(gè)節(jié)點(diǎn)所需要的屬性可能跑到其兄弟節(jié)點(diǎn)
或者父節(jié)點(diǎn)中去了。貌似這里可以參考“繼承屬性”概念。

不過，綜合而言，我們有很多業(yè)余的手段來(lái)處理這種問題，例如建立屬性堆棧。具體來(lái)說(shuō)，
例如對(duì)于例子代碼中計(jì)算算術(shù)表達(dá)式，就可以把表達(dá)式中的數(shù)放到一個(gè)棧里。

例子中，通過在文法表達(dá)式中插入動(dòng)作符號(hào)來(lái)標(biāo)識(shí)一個(gè)操作。例如對(duì)于文法：
expr2->addop term expr2，則可以改為：expr2->addop term # expr2。當(dāng)發(fā)現(xiàn)分析棧的棧
頂元素是'#'時(shí)，則在屬性堆棧里取出操作數(shù)做計(jì)算。例子中還將操作符壓入了堆棧。

下載例子，例子代碼最好對(duì)照arith_expr.txt中寫的文法和分析表來(lái)看。

PS，最近在云風(fēng)博客中看到他給的一句評(píng)論，我覺得很有道理，并且延伸開來(lái)可以說(shuō)明我們
周圍的很多現(xiàn)象：

”很多東西，意識(shí)不到問題比找不到解決方法要嚴(yán)重很多。比如one-pass 這個(gè)，覺得實(shí)現(xiàn)
麻煩不去實(shí)現(xiàn)，和覺得實(shí)現(xiàn)沒有意義不去實(shí)現(xiàn)就是不同的。“

對(duì)于以下現(xiàn)象，這句話都可以指明問題：
1、認(rèn)為造輪子沒有意義，從不考慮自己是否能造出；
2、常告訴別人某個(gè)技術(shù)復(fù)雜晦澀不利于團(tuán)隊(duì)使用，卻并不懂這個(gè)技術(shù)；
3、籠統(tǒng)來(lái)說(shuō)，【覺得】太多東西沒有意義，雖然并不真正懂這個(gè)東西。

posted @ 2010-03-15 21:33 Kevin Lynx 閱讀(9654) | 評(píng)論 (2) | 編輯 收藏

修改tolua++代碼支持插入預(yù)編譯頭文件

tolua++自動(dòng)生成綁定代碼時(shí)，不支持插入預(yù)編譯頭文件。雖然可以插入直接的C++代碼例如
，如$#include xxxx，但插入位置并沒有位于文件頭。對(duì)于使用預(yù)編譯頭的大型工程而言，
尤其是某個(gè)綁定代碼依賴了工程里其他很多東西，更萬(wàn)惡的是預(yù)編譯頭文件里居然包含很多
自己寫的代碼時(shí)，支持插入預(yù)編譯頭文件這個(gè)功能很重要。

說(shuō)白了，也就是要讓tolua++在生成的代碼文件開頭插入#include "stdafx.h"。

修改代碼其實(shí)很簡(jiǎn)單。tolua++分析pkg文件及生成代碼文件其實(shí)都是通過lua代碼完成的。
在src/bin/lua目錄下，或者在源代碼里toluabind.c里（把對(duì)應(yīng)的lua代碼直接以ASCII碼值
復(fù)制了過來(lái)）即為這些代碼。

首先修改package.lua里的classPackage::preamble函數(shù)，可以看出該函數(shù)會(huì)生成一些代碼
文件頭，模仿著即可寫下如下代碼：

if flags['I'] then
   output( '#include "..flags['I'] )
end

從上下文代碼可以看出flags是個(gè)全局變量，保存了命令行參數(shù)。

然后修改tolua.c代碼文件，讓其往lua環(huán)境里傳入命令行參數(shù)：

case 'I':setfield(L,t,"I",argv[++i];break;

本來(lái)，這樣修改后基本就可以讓tolua++支持通過命令行指定是否插入預(yù)編譯頭：
tolua++ -o test.cpp -H test.h -I stdafx.h test.pkg

不過事情并非很順利，通過開啟TOLUA_SCRIPT_RUN宏來(lái)讓tolua++通過src/bin/lua下的lua
代碼來(lái)完成功能，結(jié)果后來(lái)發(fā)現(xiàn)basic.lua似乎有問題。無(wú)奈之下，只好用winhex之類的工
具把修改過的package.lua轉(zhuǎn)換為unsigned char B[]置于toluabind.c里，即可正常處理。

posted @ 2010-02-28 20:58 Kevin Lynx 閱讀(4948) | 評(píng)論 (0) | 編輯 收藏

簡(jiǎn)要實(shí)現(xiàn)正則表達(dá)式匹配字符串

之所以說(shuō)是“簡(jiǎn)要實(shí)現(xiàn)”一方面是因?yàn)樗惴ú凰愀呱?，算法的?shí)現(xiàn)也不精致，甚至連我對(duì)其的理解也不夠本質(zhì)。

我只不過不想在工作若干年后還是一個(gè)只會(huì)打字的程序員。學(xué)點(diǎn)什么東西，真正精通點(diǎn)什么東西才對(duì)得起喜歡

技術(shù)的自己。

 

附件中的代碼粗略實(shí)現(xiàn)了《編譯原理》龍書中的幾個(gè)算法。包括解析正則表達(dá)式，建立NFA，然后用NFA去匹

配目標(biāo)字符串；或者從NFA建立DFA，然后匹配。解析正則表達(dá)式我用了比較繁瑣的方法，有詞法和語(yǔ)法分析

過程。詞法分析階段將字符和一些操作符整理出來(lái)，語(yǔ)法分析階段在建立語(yǔ)法樹的過程中對(duì)應(yīng)地建立NFA。

當(dāng)然，因?yàn)檎Z(yǔ)法樹在這里并沒有用處，所以并沒有真正地建立。

 

從正則表達(dá)式到NFA比較簡(jiǎn)單，很多編譯原理書里都提到過，如：s|t表達(dá)式對(duì)應(yīng)于下面的NFA:

代碼中用如下的結(jié)構(gòu)描述狀態(tài)和狀態(tài)機(jī)中的轉(zhuǎn)換：

#define E_TOK (0)

/* transition */
struct tran
{
    char c;
    struct state *dest;
    struct tran *next;
};

struct state
{
    /* a list of transitions */
    struct tran *trans;
    /* inc when be linked */
    int ref;
};

即，每一個(gè)狀態(tài)都有一個(gè)轉(zhuǎn)換列表，每個(gè)轉(zhuǎn)換都有一個(gè)目標(biāo)狀態(tài)（即該轉(zhuǎn)換指向的狀態(tài)）以及轉(zhuǎn)換字符。

貌似通過以上方法建立出來(lái)的狀態(tài)機(jī)每個(gè)狀態(tài)最多只會(huì)有2個(gè)轉(zhuǎn)換？

 

建立好NFA后，由NFA匹配目標(biāo)字符串使用了一種構(gòu)造子集法（《編譯原理》3.7.2節(jié)）：

這個(gè)算法里針對(duì)NFA的幾個(gè)操作，如e-closure、move等在由NFA轉(zhuǎn)換DFA時(shí)也被用到，因此代碼里單獨(dú)

做了封裝（state_oper.c）。這個(gè)算法本質(zhì)上貌似就是一次步進(jìn)（step）多個(gè)狀態(tài)。

 

至于由NFA轉(zhuǎn)DFA,則是相對(duì)簡(jiǎn)單的子集構(gòu)造法：

在我以前編譯原理課考試的前一天晚上（你懂的）我就對(duì)這些算法頗為疑惑。在以后看各種編譯

原理教材時(shí)，我始終不懂NFA是怎么轉(zhuǎn)到DFA的。就算懂了操作步驟（我大學(xué)同學(xué)曾告訴我這些步驟，雖然

不知道為什么要那樣做），一段時(shí)間后依然搞忘。很喜歡《編譯原理》龍書里對(duì)這個(gè)算法最本質(zhì)的說(shuō)明：

 

 

源代碼我是用GCC手工編譯的，連makefile也沒有。三個(gè)test_XXX.c文件分別測(cè)試幾個(gè)模塊。test_match.c

基本依賴除掉test外所有c文件，全部鏈接在一塊即可。當(dāng)然，就經(jīng)驗(yàn)而言我知道是沒幾個(gè)人會(huì)去折騰我的這些

代碼的。這些在china的領(lǐng)導(dǎo)看來(lái)對(duì)工作有個(gè)鳥用的代碼讀起來(lái)我自己也覺得費(fèi)力，何況，我還不倫不類地用了

不知道算哪個(gè)標(biāo)準(zhǔn)的c寫了這些。

 

你不是真想下載。對(duì)于這種代碼，有BUG是必然的，你也不用在此文若干個(gè)月后問我多少行是什么意思，因?yàn)?/p>

那個(gè)時(shí)候我也忘了:D。

posted @ 2010-02-20 14:53 Kevin Lynx 閱讀(5856) | 評(píng)論 (4) | 編輯 收藏

靜態(tài)庫(kù)中全局變量的初始化問題

 

在我自己寫的一個(gè)工廠類實(shí)現(xiàn)中，每個(gè)產(chǎn)品會(huì)注冊(cè)創(chuàng)建接口到這個(gè)工廠類。工廠類使用這些
注冊(cè)進(jìn)來(lái)的創(chuàng)建接口來(lái)完成產(chǎn)品的創(chuàng)建。其結(jié)構(gòu)大致如下：

product *factory::create( long product_type )
{
    creator c = m_creators[product_type];
    return c();
}

factory::instance().register( PRODUCT_A_TYPE, productA::create );
...
factory::instance().create( PRODUCT_A_TYPE );

這個(gè)很普通的工廠實(shí)現(xiàn)中，需要寫上很多注冊(cè)代碼。每次添加新的產(chǎn)品種類時(shí)，也需要修改
這些的注冊(cè)代碼。而恰好，這些注冊(cè)代碼可能會(huì)被放在一個(gè)統(tǒng)一的地方。為了消除這個(gè)地方
，我使用了偶然間看到的<Modern C++ design>里的做法：

const bool _local = factory::instance().register( PRODUCT_A_TYPE,...

也就是說(shuō)，通過對(duì)全局常量_local的自動(dòng)初始化，來(lái)自動(dòng)完成對(duì)該產(chǎn)品的注冊(cè)。

結(jié)果，因?yàn)檫@些代碼全部被放置于一個(gè)靜態(tài)庫(kù)。最終的代碼文件結(jié)構(gòu)大致為：

lib
    - product_a.cpp : 定義了全局常量_local
    - product_a.h
    - factory.cpp
    - factory.h
exe
    - main.cpp

現(xiàn)在看起來(lái)世界很美，因?yàn)閒actory甚至不知道世界上還有個(gè)跟上層邏輯相關(guān)的product_a。
這種模塊耦合幾乎為0的結(jié)構(gòu)讓我竊喜。

悲劇的事情首先發(fā)生于，開VC調(diào)試器，發(fā)現(xiàn)打在product_a.cpp里的斷點(diǎn)失效。就是那個(gè)總
是提示說(shuō)沒有為該文件加載調(diào)試符號(hào)。開始還不在意，以為又是代碼和調(diào)試符號(hào)文件不匹配
的原因，折騰了好久，不得其果。

后來(lái)分析了下，發(fā)現(xiàn)這個(gè)調(diào)試提示，就像我開著調(diào)試器打開了一個(gè)非本工程的代碼文件，而
斷點(diǎn)就打在這個(gè)文件里一樣。也就是說(shuō)，VC把我product_a.cpp當(dāng)成不是這個(gè)工程里的代碼
文件。

按照這個(gè)思路寫些實(shí)驗(yàn)代碼，最終發(fā)現(xiàn)問題所在：VC鏈接器根本沒鏈接進(jìn)product_a.cpp里
的代碼。表現(xiàn)出來(lái)的情況就是，該編譯單元里的全局常量（全局變量一樣）根本沒有得到初
始化，因?yàn)槲腋絝actory::register并沒有被調(diào)用到。為什么VC不鏈接這個(gè)編譯單元對(duì)應(yīng)
的目標(biāo)文件？或者說(shuō)，為什么VC不初始化這個(gè)全局常量？

原因就在于，product_a.cpp太獨(dú)立了。一個(gè)在整個(gè)編譯鏈接階段都無(wú)法確定該文件是否被
使用的文件，VC就直接不鏈接了。相反，當(dāng)在factory.cpp里寫下類似代碼：

void test()
{
    product_a obj;
}

雖然說(shuō)test函數(shù)不會(huì)被調(diào)用，一切情況也變得正常了。好了，不扯了，給最后我的結(jié)論：

1、如果靜態(tài)庫(kù)中某個(gè)編譯單元在編譯階段被確認(rèn)為它并沒有被外部使用，那么當(dāng)這個(gè)靜態(tài)
庫(kù)被鏈接進(jìn)可執(zhí)行文件時(shí)，鏈接器忽略掉該編譯單元里的代碼，那么，鏈接器自然也不會(huì)為
該編譯單元里出現(xiàn)的全局變量常量生成初始化代碼（關(guān)于這部分初始化代碼可以閱讀
<linker and loader>一書）；
2、上面那條結(jié)論存在一種傳染性，意思是，當(dāng)可執(zhí)行文件里的代碼使用到靜態(tài)庫(kù)中文件A里
的代碼，A里又有地方使用到B里的代碼，那么B依然會(huì)被鏈接。這種依賴性，應(yīng)該可以讓編
譯器在編譯階段就發(fā)現(xiàn)（顯然，上面我舉的例子里，factory只有在運(yùn)行期間才會(huì)依賴到
product_a.cpp里的代碼）

posted @ 2010-01-17 19:34 Kevin Lynx 閱讀(15724) | 評(píng)論 (19) | 編輯 收藏

lua_yield為什么就必須在return表達(dá)式中被調(diào)用

 

很早前在折騰掛起LUA腳本支持時(shí)，接觸到lua_yield這個(gè)函數(shù)。lua manual中給的解釋是：

This function should only be called as the return expression of a C function。

而這個(gè)函數(shù)一般是在一個(gè)注冊(cè)到LUA環(huán)境中的C函數(shù)里被調(diào)用。lua_CFunction要求的原型里
，函數(shù)的返回值必須返回要返回到LUA腳本中的值的個(gè)數(shù)。也就是說(shuō)，在一個(gè)不需要掛起的
lua_CFunction實(shí)現(xiàn)里，也就是一個(gè)不需要return lua_yield(...的實(shí)現(xiàn)里，我應(yīng)該return
一個(gè)返回值個(gè)數(shù)。

但是為什么調(diào)用lua_yield就必須放在return表達(dá)式里？當(dāng)時(shí)很天真，沒去深究，反正發(fā)現(xiàn)
不按照l(shuí)ua manual里說(shuō)的做就是不行。而且關(guān)鍵是，lua manual就不告訴你為什么。

最近突然就想到這個(gè)問題，決定去搞清楚這個(gè)問題。侯捷說(shuō)了，源碼面前了無(wú)秘密。我甚至
在看代碼之前，還琢磨著LUA是不是操作了堆棧（系統(tǒng)堆棧）之類的東西。結(jié)果隨便跟了下
代碼真的讓我很汗顏。有時(shí)候人犯傻了真的是一個(gè)悲劇。諾簡(jiǎn)單的一個(gè)問題會(huì)被人搞得很神
秘：

解釋執(zhí)行調(diào)用一個(gè)注冊(cè)進(jìn)LUA的lua_CFunction是在ldo.c里的luaD_precall函數(shù)里，有如下
代碼：

    n = (*curr_func(L)->c.f)(L);  /* do the actual call */
    lua_lock(L);
    if (n < 0)  /* yielding? */
      return PCRYIELD;
    else {
      luaD_poscall(L, L->top - n);
      return PCRC;
    }

多的我就不說(shuō)了，別人注釋寫得很清楚了，注冊(cè)進(jìn)去的lua_CFunction如果返回值小于0，這
個(gè)函數(shù)就向上層返回PCRYIELD，從名字就可看出是告訴上層需要YIELD。再找到lua_yield函
數(shù)的實(shí)現(xiàn)，恰好該函數(shù)就返回-1。

要再往上層跟，會(huì)到lvm.c里luaV_execute函數(shù)，看起來(lái)應(yīng)該就是虛擬機(jī)在解釋執(zhí)行指令：

      case OP_CALL: {
        int b = GETARG_B(i);
        int nresults = GETARG_C(i) - 1;
        if (b != 0) L->top = ra+b;  /* else previous instruction set top */
        L->savedpc = pc;
        switch (luaD_precall(L, ra, nresults)) {
          case PCRLUA: {
            nexeccalls++;
            goto reentry;  /* restart luaV_execute over new Lua function */
          }
          case PCRC: {
            /* it was a C function (`precall' called it); adjust results */
            if (nresults >= 0) L->top = L->ci->top;
            base = L->base;
            continue;

對(duì)于PCRYIELD返回值，直接忽略處理了。

posted @ 2010-01-17 19:32 Kevin Lynx 閱讀(3862) | 評(píng)論 (0) | 編輯 收藏

低耦合模塊間的通信組件：兩個(gè)模板

用途

在一個(gè)UI與邏輯模塊交互比較多的程序中，因?yàn)椴⒉幌胱寖蓚€(gè)模塊發(fā)生太大的耦合，基本目標(biāo)是
可以完全不改代碼地?fù)Q一個(gè)UI。邏輯模塊需要在產(chǎn)生一些事件后通知到UI模塊，并且在這個(gè)通知
里攜帶足夠多的信息（數(shù)據(jù)）給接收通知的模塊，例如UI模塊。邏輯模塊還可能被放置于與UI模
塊不同的線程里。

最初的結(jié)構(gòu)

最開始我直接采用最簡(jiǎn)單的方法，邏輯模塊保存一個(gè)UI模塊傳過來(lái)的listener。當(dāng)有事件發(fā)生時(shí)，
就回調(diào)相應(yīng)的接口將此通知傳出去。大致結(jié)構(gòu)如下：

 

但是，在代碼越寫越多之后，邏輯模塊需要通知的事件越來(lái)越多之后，EventNotify這個(gè)類開始
膨脹：接口變多了、不同接口定義的參數(shù)看起來(lái)也越來(lái)越惡心了。

改進(jìn)

于是我決定將各種事件通知統(tǒng)一化：

 

 

這樣，邏輯模塊只需要?jiǎng)?chuàng)建事件結(jié)構(gòu)，兩個(gè)模塊間的通信就只需要一個(gè)接口即可：

void OnNotify( const Event &event );

但是問題又來(lái)了，不同的事件類型攜帶的附屬參數(shù)（數(shù)據(jù)）不一樣。也許，可以使用一個(gè)序列化
的組件，將各種數(shù)據(jù)先序列化，然后在事件處理模塊對(duì)應(yīng)地取數(shù)據(jù)出來(lái)。這樣做總感覺有點(diǎn)大動(dòng)
干戈了。當(dāng)然，也可以使用C語(yǔ)言里的不定參數(shù)去解決，如：

void OnNotify( long event_type, ... )

其實(shí)，我需要的就是一個(gè)可以表面上類型一樣，但其內(nèi)部保存的數(shù)據(jù)卻多樣的東西。這樣一想，
模塊就能讓事情簡(jiǎn)單化：

 

 

在上面這個(gè)例子中，雖然通過Param的包裝，邏輯模塊可以在事件通知里放置任意類型的數(shù)據(jù)，但
畢竟只支持2個(gè)參數(shù)。實(shí)際上為了實(shí)現(xiàn)支持多個(gè)參數(shù)（起碼得有15個(gè)），還是免不了自己實(shí)現(xiàn)多個(gè)
參數(shù)的Param。

幸虧我以前寫過宏遞歸產(chǎn)生代碼的東西，可以自動(dòng)地生成這種情況下諸如Param1、Param2的代碼。
如：

 

 

即可生成Param1和Param2的版本。其實(shí)這樣定義了Param1、Param2的東西之后，又使得OnNotify
的參數(shù)不是特定的了。雖然可以把Param也泛化，但是在邏輯層寫過多的模板代碼，總感覺不好。

于是又想到以前寫的一個(gè)東西，可以把各種類型包裝成一種類型---對(duì)于外界而言：any。any在
boost中有提到，我只是實(shí)現(xiàn)了個(gè)簡(jiǎn)單的版本。any的大致實(shí)現(xiàn)手法就是在內(nèi)部通過多態(tài)機(jī)制將各
種類型在某種程度上隱藏，如：

 

這樣，any類通過一個(gè)base_type類，利用C++多態(tài)機(jī)制即可將類型隱藏于var_holder里。那么，
最終的事件通知接口成為下面的樣子：

void OnNotify( long type, any data );

OnNotify( ET_ENTER_RGN, any( create_param( player, rgn_id ) ) );其中，create_param
是一個(gè)輔助函數(shù)，用于創(chuàng)建各種Param對(duì)象。

事實(shí)上，實(shí)現(xiàn)各種ParamN版本，讓其名字不一樣其實(shí)有點(diǎn)不妥。還有一種方法可以讓Param的名字
只有一個(gè)，那就是模板偏特化。例如：

 

 

這種方法主要是通過組合出一種函數(shù)類型，來(lái)實(shí)現(xiàn)偏特化。因?yàn)槲矣X得構(gòu)造一個(gè)函數(shù)類型給主模版，
并不是一種合情理的事情。但是，即使使用偏特化來(lái)讓Param名字看起來(lái)只有一個(gè)，但對(duì)于不同的
實(shí)例化版本，還是不同的類型，所以還是需要any來(lái)包裝。

實(shí)際使用

實(shí)際使用起來(lái)讓我覺得非常賞心悅目。上面做的這些事情，實(shí)際上是做了一個(gè)不同模塊間零耦合
通信的通道（零耦合似乎有點(diǎn)過激）?，F(xiàn)在邏輯模塊通知UI模塊，只需要定義新的事件類型，在
兩邊分別寫通知和處理通知的代碼即可。

PS:
針對(duì)一些評(píng)論，我再解釋下。其實(shí)any只是用于包裝Param列表而已，這里也可以用void*，再轉(zhuǎn)成
Param*。在這里過多地關(guān)注是用any*還是用void*其實(shí)偏離了本文的重點(diǎn)。本文的重點(diǎn)其實(shí)是Param：

 

下載相關(guān)代碼

posted @ 2009-08-23 09:55 Kevin Lynx 閱讀(6385) | 評(píng)論 (18) | 編輯 收藏