譯者序
由于我最近有一個(gè)計(jì)劃,就是寫一個(gè)適應(yīng)性很強(qiáng)的腳本語言,這個(gè)語言將主要用來處理劇情,希望能夠用于絕大多數(shù)需要劇情的游戲.于是最近開始找一些關(guān)于script的東西來看看,當(dāng)我在flipcode看到這篇的overview時(shí),見它提到了unreal的腳本系統(tǒng)和字節(jié)碼和虛擬機(jī),就開始在沒有完全讀完的情況下翻譯這一系列文章(共9篇).在翻譯中加一些注釋...希望不要誤導(dǎo)您,還有為了豐富原文我也加入了幾個(gè)自己的程序.因?yàn)檫@是我首次翻譯這種系列文章,在腳本引擎方面也缺乏經(jīng)驗(yàn),所以難免會有一些不當(dāng)之處,還請大家批評指正.?

目錄
Part I: 概述?
Part II: 詞法分析器?
Part III:語法分析器?
Part IV: 符號表 & 語法樹?
Part V: 語義檢查 & 中間代碼生成?
Part VI: 優(yōu)化?
Part VII:虛擬機(jī)(The Virtual Machine)?
Part VIII:可執(zhí)行代碼?
Part IX:高級主題?

版本列表
2000年2月至2000年3月 第一稿

聲明
原文發(fā)布時(shí)間是1999年5月至8月,原文作者是Jan Niestadt?
如果有中文版權(quán)的話版權(quán)屬譯者(即燕良)所有?
如果您覺得有用當(dāng)然可以轉(zhuǎn)載,不過請保持文章的全部內(nèi)容,如果您有什么修改意見請與譯者聯(lián)系?
暫時(shí)不可用作商業(yè)用途

Part I:概述
序言

OK,在你的引擎中你想有一個(gè)腳本語言.

首先,確定你需要那種腳本語言;Henry Robinson 已經(jīng)寫過了一個(gè)各種腳本語言區(qū)別的介紹(如果你還沒讀過就去讀一下吧),在這個(gè)系列教程中我將討論一個(gè)象虛幻腳本(Unreal script)那樣的編譯器/虛擬機(jī)系統(tǒng).

下一步,你需要知道兩件事:怎樣實(shí)現(xiàn)那樣一個(gè)腳本引擎,還有腳本引擎不僅僅是酷而且在實(shí)際中十分有用的一些理由.

這里是我想到的一些:

• 有用的新語言特性象狀態(tài),隱藏代碼(latent code),等等.
• 一個(gè)沙盤環(huán)境(sandbox environment)不會導(dǎo)致游戲引擎的崩潰.
• 不需要游戲內(nèi)部引擎的只是或者重新編譯游戲引擎就可以編寫游戲的內(nèi)容.
• 完全的獨(dú)立于平臺的腳本代碼

但是也有一些不利因素:

• 相對較慢--腳本的運(yùn)行至少比可執(zhí)行代碼的執(zhí)行慢15倍.
• 限制--腳本不能用來建立實(shí)際的視覺效果(部分原因是它速度的缺點(diǎn)).
• 編寫游戲內(nèi)容的人必須學(xué)習(xí)一種新的語言.

當(dāng)然我們不會因?yàn)檫@些就停下來,我們已經(jīng)準(zhǔn)備好實(shí)現(xiàn)我們的想法了.現(xiàn)在,從哪里開始呢?


必須閱讀的東西

在虛幻(Unreal)發(fā)布前很久我就開始了.我瀏覽他們的技術(shù)站點(diǎn),并且發(fā)現(xiàn)了虛幻腳本參考文檔(UnrealScript reference document).我當(dāng)然聽說過虛幻腳本,但是并不真正知道他是什么.我閱讀了這些文檔,覺得一個(gè)腳本語言的想法實(shí)在是很酷.我要自己寫一個(gè),然后連接到一個(gè)游戲引擎,以便我的游戲的整個(gè)世界都可以輕松的建立新的內(nèi)容.

幸運(yùn)的是我有一個(gè)學(xué)期的編譯器構(gòu)造課程(燕良注:我也剛學(xué)了一個(gè)學(xué)期的編譯原理,還考了92分,嘻嘻,不過Julien當(dāng)時(shí)竟然只用兩個(gè)月就考了98分,佩服,佩服),并且作為一個(gè)實(shí)際的任務(wù)我曾經(jīng)實(shí)現(xiàn)過一個(gè)非常非常簡單的Pascal編譯器.我開始并行工作,更好,編譯器.我已經(jīng)有一個(gè)接受C的子集的可工作的版本,但是我用了2周來編碼,其內(nèi)部結(jié)構(gòu)相當(dāng)?shù)目膳?...我不得不完整的重新設(shè)計(jì)那東西.我相信你在某些地方有與我相似的經(jīng)驗(yàn)...現(xiàn)在我依然在做這東西,并且學(xué)到了很多關(guān)于編譯器的知識.

現(xiàn)在,接觸一點(diǎn)有用的信息吧.

首先,我建議所有想要編寫一個(gè)編譯器的人弄一本龍之書.你們中的大多數(shù)(尤其是象我這樣的計(jì)算機(jī)系學(xué)生)可能已經(jīng)知道了這個(gè)(燕良注://shake).告訴那些不知道的人,我是在說Aho, Sethi 和 Ullman 所著的<<Compilers - Principles, Techniques and Tools?>>(ISBN 0-201-10194-7). 因?yàn)樗姆饷嬗幸粭l龍,所以得到了龍之書的名字.相信我,所有對編譯器有所了解的人都讀過這本書(燕良注:國內(nèi)有賣嗎?).

這本書從1986年就不曾修改過,這是因?yàn)閺?0年代編譯器的設(shè)計(jì)基本技術(shù)就沒有變過.當(dāng)然,這本書不涉及面向機(jī)器的優(yōu)化,但是有其他書.此外,我們想要編譯出字節(jié)碼(bytecode)而非機(jī)器碼.

其次,如果你想要得到一個(gè)快速實(shí)現(xiàn)字節(jié)碼腳本語言的預(yù)覽GamaSutra的一篇文章.那是一個(gè)值得一讀的關(guān)于實(shí)現(xiàn)Jedi騎士腳本語言的故事.那里的所有的東西我也將涉及,但是那仍然是值得一讀的.


我們需要什么

一個(gè)編譯器基本上包括一下這些組成部分:

• 一個(gè)符號表,其中存儲所有的符號及其信息,例如類型,范圍,等等.
• 一個(gè)詞法分析器,他的功能是將字符流(例如源文件)轉(zhuǎn)換為記號(例如關(guān)鍵詞,操作符等等).
• 一個(gè)語法分析器(parser),他的功能是讀取記號流,并建立語法樹.
• 一個(gè)語義檢查器,用來檢查語法樹的語義錯(cuò)誤.
• 一個(gè)中間代碼生成器,用來把語法樹轉(zhuǎn)換為中間代碼
• 一個(gè)優(yōu)化器,用來優(yōu)化中間代碼
• 一個(gè)代碼生成器,用來從中間代碼生成字節(jié)碼.
• 最后但不是最少,字節(jié)碼將要在其上執(zhí)行的虛擬機(jī)

如果你編寫完了所有這些組件,組合到一起,它們將成為一個(gè)完整的腳本語言系統(tǒng).


這是全部嗎?

受到了一點(diǎn)點(diǎn)打擊嗎?畢竟決定使用腳本不是那么酷,DLL真的是唯一的路嗎?沒關(guān)系,我將很快討論每一組件的細(xì)節(jié),它們的絕大多數(shù)并不是那么困難.建立一個(gè)完整的腳本引擎是一個(gè)巨大的工作,但是,本質(zhì)上是構(gòu)造你自己的代碼.

在這個(gè)教程的剩余部分我們將開發(fā)一個(gè)簡單的編譯器/虛擬機(jī)系統(tǒng).盡管他沒有地方象是一個(gè)完整的腳本語言,但是他實(shí)現(xiàn)了上面提到的所有組件.我在回想一個(gè)操作字符串的簡單語言.

現(xiàn)在檢查上面的連接,了解他們.順便提一下,感謝所有的評論.

Quote!
"But the plans were on display ..."
"On display? I eventually had to go down to the cellar to find them."
"That's the display department."
"With a torch."
"Ah, well the lights had probably gone."
"So had the stairs."
"But look, you found the notice didn't you?"
"Yes," said Arthur, "yes I did. It was on display in the bottom of a locked filing cabinet stuck in a disused lavatory with a sign on the door saying Beware of the Leopard."

HHG 1:1

Part II:詞法分析器
序言

我總是說在學(xué)一個(gè)東西的時(shí)候例子總是不能足夠簡單.這就是為什么當(dāng)我想要設(shè)計(jì)一個(gè)包含所有完整編譯器應(yīng)該有的特性的簡單的編譯器時(shí)感到很累.我拼湊了一個(gè)字符串處理語言,它使用象C那樣的語法,有BASIC那樣的功能.下面是用我們的語言的正確編寫的一個(gè)程序.

print "Please enter your name > "; input name; if (name == "Jan") { // string comparison ??? name = "my creator"; // string assignment ??? happy = "yes"; } print "Thank you, " + name + "!\n" + // string concatenation "You've just made a simple program very happy!";

就象你看到的,他沒有構(gòu)造象函數(shù),類等等那樣的功能,它甚至沒有數(shù)值類型.這就是最終的東西,但是,他是很容易擴(kuò)展的.

但是在接觸那個(gè)之前我們還一很長的路要走--記得上次的組件列表嗎?今天我們將實(shí)現(xiàn)第一個(gè):詞法分析器或稱短語分析器.這是一個(gè)很好的熱身,因?yàn)樗皇蔷幾g器中真正難的部分.

OK,準(zhǔn)備好了嗎?


是什么,為什么和怎么作

首先我猜你想要知道詞法分析器是什么和為什么我們要用它?詞法分析器的任務(wù)是把源文件的字符流轉(zhuǎn)換成記號流.本質(zhì)上它查看連續(xù)的字符然后把它們識別為"單詞".

我們當(dāng)然可以寫一個(gè)函數(shù)用來把源文件當(dāng)前位置取得的字符串與我們的所有關(guān)鍵字比較,但是這將是不可忍受的慢.所以我們使用有限自動機(jī)來識別單詞(燕良注:就是DFA了,設(shè)計(jì)過程是正則式==>NFA==>DFA==>最小化).如果你不知道它是什么,好吧,你不需要知道(燕良注:如果你想知道,請看本文最后的附注).

關(guān)于詞法分析器的一個(gè)基本情況是我們不需要作實(shí)際的艱苦的工作,我們使用一個(gè)叫作"LEX"的程序生成詞法分析器.這是一個(gè)標(biāo)準(zhǔn)的UNIX程序,他也有幾個(gè)win 32的版本(燕良注:我有一個(gè)FLEX.exe).這里有完整的LEX手冊的HTML版.

好的,現(xiàn)在你知道了詞法分析器作什么和我們將如何制作它.現(xiàn)在你可以下載?*tut2.zip*并且看一眼那些代碼.這部分的源程序是string.l(燕良注:LEX源程序)和main.cpp以及幾個(gè)頭文件.請注意ZIP文件中含有目錄結(jié)構(gòu),flex.exe在主目錄,這部分的代碼在tut2\目錄.


LEX規(guī)則

LEX需要一些簡單的規(guī)則來生成我們的詞法分析器.在介紹規(guī)則之前,先讓我們看一下LEX源程序的分段.

說明部分 %% 規(guī)則部分 %% 輔助程序部分

<說明部分>包含一些正則式(regular expression )的宏(正則式在LEX手冊中有解釋,想徹底了解它請看這里).這些告訴LEX我們使用的LETTER,DIGIT, IDENT(標(biāo)識符,通常定義為字母開頭的字母數(shù)字串)和STR(字符串常量,通常定義為雙引號括起來的一串字符)是什么意思.(燕良注:呵呵,多熟悉呀.)

這部分也可以包含一些初始化代碼.例如用#include來使用標(biāo)準(zhǔn)的頭文件和前向說明(forward references).這些代碼應(yīng)該再標(biāo)記"%{"和"%}"之間,你馬上將看到我include了一個(gè)lexsymb.h 文件.

<規(guī)則部分>可以包括任何你想用來分析的代碼;我們這里包括了忽略所有注釋中字符的功能,傳送ID名稱和字符串常量內(nèi)容到主調(diào)函數(shù)和main函數(shù)的功能.

lexsymb.h 文件聲明了詞法分析器函數(shù)將要返回的記號的符號.它還聲明了一個(gè)'yylval' 共用體(union),用來傳送額外的信息(例如標(biāo)識符的名字)到主調(diào)函數(shù);這里我們使用這個(gè)特殊的共用體可以使下一部分更清晰些.

現(xiàn)在讓我們看一下實(shí)際的規(guī)則.我使用/* */作注釋;LEX是一個(gè)相當(dāng)老的程序,所以它著支持//引導(dǎo)的注釋.順便提一下,我們將使用LEX生成C程序,C++版的LEX程序也有,但是標(biāo)準(zhǔn)的UNIX LEX產(chǎn)生C代碼.我們想要使這東西便攜,不是嗎? (燕良注: LEX源文件 .L--->FLEX--->C源文件,默認(rèn)文件名是lex.yy.c)

"if" {return IF;} "=" {return ASSIGN;} ";" {return END_STMT;} {IDENT} {Identifier (); /* identifier: copy name */ return ID;} {STR} {StringConstant (); /* string constant: copy contents */ return STRING;} "//" {EatComment();} /* comment: skip */ \n {lineno++;} /* newline: count lines */ {WSPACE} {} /* whitespace: (do nothing) */ . {return ERROR_TOKEN;} /* other char: error, illegal token */

我刪去了一些非常簡單的規(guī)則.就象你看到的那樣,每一條規(guī)則開始部分是LEX將要識別的樣式,接下來是一些代碼告訴LEX當(dāng)規(guī)則匹配后作什么(這部分代碼可以包含C++代碼,因?yàn)長EX只是簡單把它們的拷貝到輸出文件中).記住最頂端的規(guī)則被最優(yōu)先評估,這通常很重要.

頭3條規(guī)則十分的簡單,它們只是識別一個(gè)字符串,然后返回相對應(yīng)記號的符號.你可以改變這些字符串,例如你想使用":="來作賦值操作符.

第4行是第一條有趣的規(guī)則:它使用了IDENT宏,它識別不滿足前面的條件的字母/數(shù)字串.如果匹配,它將調(diào)用Identifier()函數(shù),此函數(shù)把yytext(保存當(dāng)前記號的文本)的內(nèi)容賦復(fù)制到一個(gè)新字符數(shù)組.詞法分析器返回ID記號,主調(diào)函數(shù)可以使用'yylval->str'指針來訪問標(biāo)識符非名稱.STR對于字符常量實(shí)現(xiàn)同樣的功能.

下一行規(guī)則處理注釋,換行和空白.注意行號將被計(jì)數(shù),將來我們在出錯(cuò)信息中將使用它.最后一行告訴LEX如果輸入不能滿足上面所有的規(guī)則(表達(dá)式"."的意思是:除了'\n'以外的所有字符),我們應(yīng)該返回一個(gè)錯(cuò)誤記號,然后讓主調(diào)函數(shù)決定作什么.

LEX的源程序可以使用下面的命令行來編譯成LEX.CPP:
????????flex -olex.cpp string.l

ZIP中還包含一個(gè)MSVC 6.0 (string.dsp)的Project文件,我相信它在5.0中也能工作,但是我不確定.Project為string.l設(shè)置了一個(gè)自定義命令行,所以它可以被自動編譯.

不幸的是LEX使用一個(gè)非標(biāo)準(zhǔn)的頭文件,unistd.h,它不能在windows中使用.在主目錄中有一個(gè)空的unistd.h文件,請?zhí)砑又髂夸浀絠nclude路徑中(in MSVC:Tools->Options->Directories->Include).

lex.cpp包含一個(gè)滿足我們規(guī)則的完整的詞法分析器.它是那么簡單!主程序只是使用詞法分析函數(shù)讀取一個(gè)記號,然后顯示記號的名字和值(它是ID還是STR).你可以試著加入一些測試數(shù)據(jù),然后觀察詞法分析器如何處理它們;隨機(jī)的字符序列通常被識別為ID,我們不使用的字符,例如'$'引發(fā)一個(gè)ERROR_TOKEN.你也可以試試example.str (在主目錄).


情況會變好的

好吧,我們現(xiàn)在有了一個(gè)可以"讀"的程序.遺憾的是它對它讀的是什么和這些是否符合我們的標(biāo)準(zhǔn)依然沒有概念.它只是接受它知道的一些記號.

看來它需要知道語法,驚人的巧合,語法正是我們下一部分將要討論的.下一個(gè)組件是語法分析器,它的功能是找出程序的結(jié)構(gòu)并且檢查語法.

這樣就變得真正有趣了.我們將能使程序成為一個(gè)編譯器,它將接受一些東西,并不只是因?yàn)樗梢越邮軒缀跛袞|西,而是因?yàn)樗肋@個(gè)程序的語法是正確的.我知道你肯定和我一樣激動,但是我不得不等到下一部分...

Quote!
"And so it was only with the advent of pocket computers that the startling truth became finally apparent, and it was this:

Numbers written on restaurant bills within the confines of restaurants do not follow the same mathematical laws as numbers written on any other pieces of paper in any other parts of the Universe.

This single fact took the scientific world by storm. It completely revolutionized it. So many mathematical conferences got held in such good restaurants that many of the finest minds of a generation died of obesity and heart failure and the science of maths was put back by years."

HHG 2:7

燕良的附注:詞法分析的手工設(shè)計(jì)舉例

程序的功能是把下面這些實(shí)常數(shù)轉(zhuǎn)換成相應(yīng)的科學(xué)計(jì)數(shù)表示:

• "Pi"轉(zhuǎn)換成0.314159265359E1
• "E"轉(zhuǎn)換成0.271828182846E1
• "Degree"轉(zhuǎn)換成0.174532E-1
• 一般的實(shí)常數(shù)按值轉(zhuǎn)換,例如456==>0.3456e4,0.0098==>0.98E-2

設(shè)計(jì)思路:

Pi,E,Degree可以當(dāng)作關(guān)鍵字來處理,不是本程序的主要部分,本程序的主要功能是識別一下各種形式的實(shí)常數(shù):

• a.
• b.
• a.b
• a.E[+/-]c
• .bE[+/-]c
• a.bE[+/-]c
• aE[+/-]c

識別上述形式實(shí)常數(shù)的DFA為:

參見程序:CONSTANT.zip

附送另一個(gè)程序,識別C語言源程序的LEX源程序.?

Part III:語法分析器
序言

前一部分的執(zhí)行可以作一件很好的工作:把程序轉(zhuǎn)換成記號.所有的關(guān)鍵詞,操作符,分隔符,標(biāo)識符和常量都被立即識別和報(bào)告.然而,你可以輸入:

{ this ) = "pointless" + ;

然后程序?qū)⒅皇墙邮芩?并且高高興興的產(chǎn)生一個(gè)記號的列表.因?yàn)樗磺宄覀兿胍试S什么東西(我不知道上面的"語句"要做什么).我們必須能夠識別輸入程序的語法結(jié)構(gòu)(或者它的缺點(diǎn)).

我們借助語法分析器來作這件事,語法分析器用來找出程序的結(jié)構(gòu)并且檢查所有的語法錯(cuò)誤.


一點(diǎn)語言理論

我們怎么告訴語法分析器我們的語言是什么樣呢?我們可以使用一個(gè)叫作BNF范式(Backus-Naur Form )的東西來描述語法(syntax或grammar).這種描述方法使用組成程序的基本概念.舉例說明,表達(dá)式可以是在其他任何東西之中,標(biāo)識符或者字符串常量(expressions can be, among other things, identifiers or string constants).在BNF范式中,它可以寫成下面的形式:

expression: identifier | string;

一個(gè)打印語句或者輸入語句:

statement
: PRINT expression END_STMT
| INPUT identifier END_STMT
;

(記住PRINT,INPUT和END_STMT都是詞法分析器返回的記號)

現(xiàn)在,一個(gè)程序可以被表示成下面這種語句列表的方式:

program: | program statement;

上式說明一個(gè)程序可以是空或者由程序加上一個(gè)語句構(gòu)成,這里說的語句是一個(gè)遞歸定義,它可以是一串語句(燕良注:這個(gè)文法是左遞歸的).

那么,我們已經(jīng)用BNF范式定義的語言包含下面的語句:

print a;
(燕良注:這個(gè)語句可以使用下面的推導(dǎo)過程:
program: program statement;
program: program statement;(應(yīng)用產(chǎn)生式? program: 空)
program: PRINT expression END_STMT;(應(yīng)用產(chǎn)生式 expression: identifier)
program: PRINT identifier END_STMT;
經(jīng)過詞法分析后上面的語句形成的記號流與此式匹配;
以上是最左推導(dǎo);下面是最右推導(dǎo)
program: program statement;
program: program PRINT expression END_STMT;
program: program PRINT identifier END_STMT;
program: PRINT identifier END_STMT;
根據(jù)上述推導(dǎo)可以畫出語法樹,對于無二義性的文法,所有的推導(dǎo)畫出的語法樹都是一樣的.)
print "Hello";
input name;

Not legal is:

input "Hello";

通過我們的定義,input語句(燕良注:指產(chǎn)生式statement:INPUT identifier END_STMT;)只能作用于一個(gè)標(biāo)識符,而不能是字符串常量.

我們可以使用BNF范式正規(guī)的描述我們的語言的整個(gè)語法.注意這些現(xiàn)在還不包含語義,于是這條語句:

a = (b == c);

縱使它沒有意義它也將被語法分析器接受(我們正在試圖把一個(gè)布爾值賦給一個(gè)字符串變量).語義將在下一階段作檢查.

太好了,我們現(xiàn)在知道的語言描述法足夠來建立我們語法分析器.


看上去很熟悉!

語法分析器也可以用一個(gè)外部程序來產(chǎn)生.這個(gè)叫作Yacc(一個(gè)標(biāo)準(zhǔn)的UNIX工具,就像是LEX);我們將使用一個(gè)叫作Bison的改良版(get it?).Bison的手冊有又可以在這里(http://www.monmouth.com/~wstreett/lex-yacc/lex-yacc.html)找到.Yacc文件(extension .y) 的分段實(shí)際上與LEX文件十分的相似.

說明部分 %% 規(guī)則部分 %% 輔助程序部分

<說明部分>包括記號的定義,類型信息,還有在前一部分我們看到的yylval共用體.那就是為什么我們使用一個(gè)共用體:Yacc使用同一共用體來在兩個(gè)不同的"語言概念"之間傳遞信息,例如表達(dá)式,語句,程序.根據(jù)這些定義,Yacc為我們產(chǎn)生lexsymb.h(實(shí)際上它建立的是parse.cpp.h文件,不過parser.bat把它改名了).

就象LEX文件一樣,在這部分同樣可以在標(biāo)記"%{"和"%}"之間包含一些初始化代碼.在這部分的教程中沒有用到這個(gè)功能,但還是可以增加一些你需要的附加的代碼.

規(guī)則是特定的一些BNF范式,用來解釋前一部分.

Yacc有一個(gè)惡劣的陷阱,那就是你的語言必須使用LR(1)文法描述...這究竟是什么意思在龍之書中有詳細(xì)的解釋(第4.5,關(guān)于自下向上分析),LR(1)文法基本的意思是語法分析器還必須能夠在查看當(dāng)前語法記號或者最多預(yù)讀一個(gè)符號就能說出使用什么樣的語法規(guī)則.下面的語法規(guī)則會產(chǎn)生一個(gè)移進(jìn)/歸約沖突(shift/reduce conflict).(關(guān)于更多的文法理論可以參見最后我加的附注)

A:
| B C
| B C D
| D E F

沖突產(chǎn)生在當(dāng)你從輸入文件中讀了一個(gè)'B',而預(yù)讀符號是'C'時(shí),因?yàn)樗麄兛梢员唤M合(這兩種產(chǎn)生式最終都將產(chǎn)生一個(gè)文法符號);問題是第2個(gè)產(chǎn)生式以'D'為結(jié)尾,而且第3個(gè)以它我起始:當(dāng)語法分析器讀取到了'C',而且預(yù)讀的是'D'時(shí),它不能決定是否歸類為A2或A1后面跟著一個(gè)A3(燕良注:請注意我們只預(yù)讀一個(gè)文法符號)!盡管這個(gè)完整的文法定義可能根本就沒有二義性,但是對于語法分析器它卻是有的,因?yàn)檎Z法分析器只能預(yù)讀一個(gè)文法符號.Yacc把這種不確定性稱為移進(jìn)/歸約沖突或歸約/歸約沖突.

呵呵,別讓這些嚇著你.看一下這些規(guī)則.最重要的一條可能就是這條語句規(guī)則了:

statement : END_STMT {puts ("Empty statement");} | expression END_STMT {puts ("Expression statement");} | PRINT expression END_STMT {puts ("Print statement");} | INPUT identifier END_STMT {puts ("Input statement");} | if_statement {puts ("If statement");} | compound_statement {puts ("Compound statement");} | error END_STMT {puts ("Error statement");}

你能看到,這里定義了我們的語言所有的語句類型,后面的代碼是告訴語法分析器當(dāng)發(fā)現(xiàn)了每個(gè)產(chǎn)生式時(shí)應(yīng)該作什么.我認(rèn)為這條規(guī)則是十分漂亮的.有一件事:"Errorstatement"告訴Yacc當(dāng)分析一條語句時(shí)如果它遇到了一個(gè)語法錯(cuò)誤后應(yīng)該作什么(例如一個(gè)非法的記號或者一個(gè)不合時(shí)宜的記號).在這種情況下它會查找下一個(gè)END_STMT記號,然后繼續(xù)分析后面的東西.語法錯(cuò)誤會始終報(bào)告到在main.cpp中定義的yyerror()函數(shù),所以我們的編譯器會使用一個(gè)恰當(dāng)?shù)姆椒▉硖幚硭?如果在你的.y文件中沒有提供任何一個(gè)錯(cuò)誤規(guī)則,那么你的語法分析器遇到語法錯(cuò)誤就會定下來,這可不是很好.

也許你在奇怪為什么會有這么多的表達(dá)式規(guī)則呢:expression, equal_expression, assign_expression, concat_expression 和 simple_expression.這是為了描述操作符的優(yōu)先級.如果語法分析器看到了這個(gè):

if (a == b + c)

它應(yīng)該知道它不應(yīng)該先計(jì)算a==b然后試著把這個(gè)布爾值計(jì)算結(jié)果與一個(gè)字符串變量c相加(燕良注:這里的側(cè)重點(diǎn)不是數(shù)據(jù)類型,而是算符的優(yōu)先級).這些不同的表達(dá)式規(guī)則確定了唯一的語句的語法分析方法.花點(diǎn)時(shí)間好好看看它;它能夠工作.

另外一個(gè)問題是當(dāng)分析下面的語句時(shí):

if (a == b) if (c == d) e = f; else g = h;

語法分析器不知道else屬于那個(gè)if語句(內(nèi)層的還是外層的);它可以認(rèn)為你的意思是:

if (a == b) {if (c == d) e = f;} else g = h;

但是作為一個(gè)所有語言都遵循的慣例,else與內(nèi)層的if匹配.

因?yàn)闆]有辦法通過改變我們的規(guī)則來解決這個(gè)問題,Yacc將會報(bào)告一個(gè)移進(jìn)/歸約沖突.這個(gè)沖突可以簡單的在說明部分加上這行來禁止:

%expect 1

這意味這Yacc應(yīng)該預(yù)期沖突1(Yacc should expect 1 conflict).Yacc將把else與最近的if配對,正象我們想要的那樣.這就是它發(fā)現(xiàn)任何沖突的默認(rèn)的解決方法.

一旦你理解了BNF范式,Yacc文件是非常的不解自明的.如果你還有什么不清楚的地方,你可以給我來mail或者在messageboard上提出問題.

Yacc的源文件可以使用這條命令來編譯:

bison --defines --verbose -o parse.cpp

如果你得出了什么沖突,看一下輸出的parse.cpp文件,那里包含沖動的細(xì)節(jié)(即使沒有錯(cuò)誤,那仍然是一個(gè)有趣的文件).如果你陷入了任何不能解決的沖突,可能把你的.y文件發(fā)給我,我會看一下的.

如果每件事都OK了(在樣例代碼中應(yīng)該是這樣的),那你在parse.cpp中就得到了一個(gè)可工作的語法分析器.我們的主程序要做的就是調(diào)用yyparse()函數(shù),這個(gè)輸入文件就會按我們的要求處理了.

再試試example.str文件,然后看一下它產(chǎn)生的錯(cuò)誤.錯(cuò)誤?是的,沒錯(cuò),我在第13行最后忘了一個(gè)';'.呵呵,它很棒吧?


Whew!?

今天我們作了很多事.我們學(xué)習(xí)了一些形式語言理論,如何使用Yacc,為什么Yacc對它支持的文法如此的挑剔,如何描述操作符的優(yōu)先級.在最后,我們制作了一個(gè)可以工作的語法分析器.

好吧,我想最難的部分就在后面.如果你理解了這些,休息一下吧.然而,我在LR(1)文法上忽略了很多.給我來信或者發(fā)到messageboard讓我來澄清那些問題.歡迎任何的問題和評論,讓我知道有人在讀這些東西.

下面是什么呢?下次我們大概要寫兩個(gè)新的組件:符號表和語法樹.到那之后,你有一周來試驗(yàn)這些代碼.提示:試著找到一個(gè)接受C風(fēng)格的while語句的編譯器.


Quote!?

"The major problem is quite simply one of grammar, and the main work to consult in this matter is Dr Dan Streetmentioner's Time Traveller's Handbook of 1001 Tense Formations. It will tell you for instance how to describe something that was about to happen to you in the past before you avoided it by time-jumping forward two days in order to avoid it. The event will be described differently according to whether you are talking about it from the standpoint of your own natural time, from a time in the further future, or a time in the further past and is further complicated by the possibility of conducting conversations whilst you are actually travelling from one time to another with the intention of becoming your own father or mother."

HHG 2:18


Downloads

Download the tutorial code (tut3.zip) (5k)


燕良的附注:說明一下文中的幾個(gè)名詞

• 關(guān)于BNF范式
  文中的
  expression: identifier | string;
  可以讀作expression定義為identifier或string.
  這個(gè)式子包括兩個(gè)產(chǎn)生式.
• 關(guān)于LR(1)分析原文中提到的不多,所以在這里補(bǔ)充一下.但是完整的語法分析理論恐怕您還是要找本書來看.不過,如果只是想使用工具的話我想看了原文和這里的補(bǔ)充應(yīng)該差不多了.
  LR(1)分析是自下向上分析的一種,自下向上的分析實(shí)際上是最右推導(dǎo)的逆過程,名字中的'L'表示自左向右讀入記號,'R'表示最后推導(dǎo),'1'表示預(yù)讀一個(gè)記號.
  實(shí)際上LR(1)分析也好,LL(1)等等各種分析也好,其最終目的都是得出一個(gè)狀態(tài)矩陣.通過這個(gè)矩陣程序才能知道下一步該怎么作,動作主要有兩種,一是移進(jìn),即讀入下一記號,二是歸約,就是用產(chǎn)生式的左部來代替產(chǎn)生式的右部,其中如果是規(guī)約,還要說明用那個(gè)產(chǎn)生式歸約.
  驗(yàn)證文法的LR(1)性是一件比較復(fù)雜的事.本文只講實(shí)現(xiàn)不講設(shè)計(jì),其實(shí)設(shè)計(jì)出好的文法我覺得很有挑戰(zhàn)性.:P
• 這篇文章還是挺不錯(cuò)的,語法中的兩個(gè)難點(diǎn):操作符優(yōu)先級和if-else問題都提到了.這是應(yīng)該注意的地方.

Part IV:符號表 & 語法樹
序言

如果我們想要用上兩部分我們建立的詞法分析器和語法分析器來作些有用的事的話,那么我們需要把我們從程序中收集的的信息存儲到數(shù)據(jù)結(jié)構(gòu)中.這就是下面我們要作的.這包括兩個(gè)重要的組件: 符號表和語法樹.

符號表,顧名思義,它是我們的程序中用來存儲所有符號的一個(gè)表;在我們這里,包括所有的字符串變量,還有常量字符串.如果你的語言含有函數(shù)和類,他們的符號也將被存儲的符號表.

語法樹是程序結(jié)構(gòu)的一個(gè)樹形表示;請看下圖.在下一部分中我們使用這個(gè)表示來生成中間代碼.盡管不是必須建立一個(gè)語法樹(我們已經(jīng)從語法分析器中得到了所有關(guān)于程序結(jié)構(gòu)的信息),但是我認(rèn)為這可以使編譯器更透明(燕良注:原文是tranparent,我猜是拼寫錯(cuò)誤,所以按transparent譯的,不知道那是否是什么術(shù)語...),這正是在這個(gè)系列文章中我所要達(dá)到的目標(biāo).



這是包括"真正的"代碼的第一部分,在我們觀察它之前請讓我澄清一點(diǎn):這些代碼在寫時(shí)應(yīng)該更易懂而不是結(jié)構(gòu)好.它對于我們這里制作的編譯器是合格的,但是如果是一個(gè)真正的編譯器,你需要作很多不同的東西.當(dāng)我們碰到這些問題時(shí)我會試著說明它們.


在規(guī)則之間傳遞信息

顯而易見,我們必須在我們的語法分析器中添加功能;例如,當(dāng)我們發(fā)現(xiàn)一個(gè)符號時(shí)我們把它送人符號表--但是我們還希望它的"父"規(guī)則(事實(shí)上使用此標(biāo)識符的規(guī)則)在符號描述中也要能夠被訪問.

我們在建立一個(gè)語法樹時(shí)需要某些近似的東西:我們需要父規(guī)則有一個(gè)指針指向他的"孩子結(jié)點(diǎn)"(構(gòu)成父規(guī)則的那些規(guī)則)

還記得yylval共用體嗎?Yacc也使用他在規(guī)則之間傳遞信息.每一個(gè)規(guī)則能夠使用yylval共用體的一個(gè)域;這是規(guī)則的類型.在string.y的頂部,你能看到類似下面的類型說明:

%type <symbol> identifier string
%type <tnode> statement expression

symbol和tnode是那個(gè)共用體的新成員;他們分別描述一個(gè)指向符號描述的指針和一個(gè)指向語法樹的指針.

現(xiàn)在語句的規(guī)則象下面這樣使用這些類型:

| expression END_STMT {$$ = new TreeNode (EXPR_STMT, $1);}

它的意思是:如果你發(fā)現(xiàn)了一個(gè)expression語句,構(gòu)造一個(gè)EXPR_STMT類型的新的樹結(jié)點(diǎn)(并且返回新的結(jié)點(diǎn)指針),他帶有一個(gè)"孩子":組成這個(gè)語句的表達(dá)式.$$代表一個(gè)規(guī)則的返回值,$1是規(guī)則定義中的第一個(gè)符號返回的值(expression).在這里$2沒有意義,因?yàn)樵~法分析器沒有為END_STMT記號設(shè)置一個(gè)yylval成員.

我希望這樣的解釋夠清楚了,因?yàn)檫@很重要.本質(zhì)上,規(guī)則是分層的,每一條規(guī)則能夠返回一個(gè)值到"更高層"的規(guī)則.

現(xiàn)在讓我們看一下符號表和語法樹使用什么樣的數(shù)據(jù)結(jié)構(gòu).


符號表

符號表在我們例子中至包含很少的信息;基本上它只是變量名和它第一次被聲明的行.后面我們會使用它來存儲更多的數(shù)據(jù).

實(shí)現(xiàn)非常的簡單:它只是當(dāng)我們?nèi)』匾粋€(gè)符號時(shí)(看一眼symtab.cpp)為符號的描述建立一個(gè)單鏈表(singly-linked list)并且線性的查找這個(gè)鏈表.對于一個(gè)真正的編譯器,符號表通常被實(shí)現(xiàn)為一個(gè)binary search tree 或 hash table,以便能夠更快的找到符號.

你要作的是當(dāng)語法分析器發(fā)現(xiàn)這個(gè)時(shí)把我們的符號送入那個(gè)表:

identifier : ID { $$ = st.Find ($1); if ($$ == NULL) { // doesn't exist yet; create it $$ = new SymDesc ($1, STR_VAR, NULL, lineno); st.Add ($$); } } ;

我們把字符串常量處理成常量,我們?yōu)樗麄兩梢粋€(gè)名字然后把他們送入那個(gè)表.注意:一個(gè)更高級些的編譯器可能會讓詞法分析器來存儲和取回標(biāo)識符.這是因?yàn)閺?fù)雜的語言中標(biāo)識符可能有很多不同的含義:變量,函數(shù),類型,等等.詞法分析器可以取回標(biāo)識符的描述,并直接把相應(yīng)的記號返回給語法分析器.因?yàn)槲覀儤?biāo)識符肯定是變量,所以我們只使用語法分析器來處理他們.


語法樹

我為語法樹建立了一個(gè)非常簡單的TreeNode類.它只存儲指向孩子的指針和一些附加信息(結(jié)點(diǎn)類型,如果可用還有一個(gè)符號的連接).看看吧,這沒什么復(fù)雜的.

象你前面看到的,我們可以從已經(jīng)驗(yàn)證的語法規(guī)則輕松的建立語法樹:

equal_expression : expression EQUAL assign_expression {$$ = newTreeNode(EQUAL_EXPR, $1, $3);} | assign_expression {$$ = $1;} ;

你會看到在某些時(shí)候我們只是無變化的從孩子規(guī)則到父規(guī)則傳遞信息;如果你的equal_expression 事實(shí)上就是一個(gè)assign_expression,就沒有必要為它建立一個(gè)新的結(jié)點(diǎn);你只使用在assign_expression中建立的那個(gè).記住我們使用這么多表達(dá)式規(guī)則的唯一的原因是為了清楚的處理操作符的優(yōu)先級.

編譯這部分(和下面的部分)使用與前面相同的方法.程序還是接受語法結(jié)構(gòu)上正確的程序,但是現(xiàn)在轉(zhuǎn)儲到它建立的符號表和語法樹中.


這真的很cool,但是...

OK,它讀程序并且分析它.但是它沒有對程序作任何真正聰明或有用的事,不是嗎?

是的,依然是.我們還有更多的組件要實(shí)現(xiàn).下一部分將涉及語義檢查和中間代碼的生成.這將是一條通向編譯程序的漫漫長路.

我希望你不要認(rèn)為它進(jìn)展的太慢,我只是想要集中到每一個(gè)分立的組件,而不是走馬觀花.如果你很快理解了這些東西,實(shí)驗(yàn)一下他們吧.

下次再見.


Quote!

(Part of the Guide entry on the Babel Fish)

"Now it is such a bizarrely improbable coincidence that anything so mindboggingly useful could have evolved purely by chance that some thinkers have chosen to see it as the final and clinching proof of the non-existence of God.

The argument goes something like this: `I refuse to prove that I exist,' says God, `for proof denies faith, and without faith I am nothing.'

`But,' says Man, `The Babel fish is a dead giveaway, isn't it? It could not have evolved by chance. It proves you exist, and so therefore, by your own arguments, you don't. QED.' "

HHG 1:6


Downloads

Download the tutorial code (tut4.zip) (8k)

Part V:語義檢查 & 中間代碼生成
序言

這次晚了一點(diǎn)...考試真是件可怕的事,它真的妨礙了一些有用的東西.

是的,上次我承諾了結(jié)果,你想要得到它們.也許多過你的希望 ;-)

首先是關(guān)于這個(gè)教程的一個(gè)備注.我是想要寫一個(gè)非常緊湊的解釋.所有的信息都在這里,但是常常是每個(gè)句子有兩個(gè)重要的事情..這樣作的缺點(diǎn)是是否有些事不大清楚,你可能沒有跟上這個(gè)教程.當(dāng)我進(jìn)行的太快時(shí)請告訴我,好讓我能夠把事情說清楚.

回到這部分.它是關(guān)于語義和中間代碼的.語義檢查將確認(rèn)你的程序是真正的正確,中間代碼將是向虛擬執(zhí)行(virtual executable)的一個(gè)巨大飛躍.

讓我們開始檢查吧!


檢查語法

語義檢查不單單是檢查程序語法的正確性,它還要確認(rèn)語句有意義.例如,提供給函數(shù)的參數(shù)的個(gè)數(shù)應(yīng)該是函數(shù)所預(yù)期的.

語義檢查的主要部分是類型檢查:決定表達(dá)式的類型和報(bào)告任何的不一致,如想要比較一個(gè)布爾值和一個(gè)字符串,或者傳給函數(shù)錯(cuò)誤的參數(shù).

當(dāng)然,也許你想要允許某些"不一致":例如有人使用了下面的語句

print "a and b equal: " + (a == b);

他的意思可能是表達(dá)式(a == b)應(yīng)該被自動轉(zhuǎn)換成一個(gè)字符串,最后成為字符串"true"或"false".這稱為強(qiáng)制類型轉(zhuǎn)換.在我們這個(gè)簡單的編譯器中我只允許布爾到字符串的強(qiáng)制轉(zhuǎn)換,但是如果你認(rèn)為字符串到布爾的強(qiáng)制轉(zhuǎn)換有用,你可以輕松的加上它.

我們的語義檢查器的代碼并不復(fù)雜.我為TreeNode加了一個(gè)名為Check()的成員函數(shù)(在synttree.cpp文件中),它檢查一個(gè)結(jié)點(diǎn)的語義,我們假定它的所有孩子結(jié)點(diǎn)都已經(jīng)被檢查了.Chech()在TreeNode的構(gòu)造函數(shù)中自動調(diào)用,所以這個(gè)假定是安全的.

檢查設(shè)置了一個(gè)名為rettype的新成員變量,表達(dá)式的"返回類型".例如,一個(gè)條件,當(dāng)一個(gè)字符串連接另一個(gè)字符串時(shí),布爾是它的返回類型.rettype用來檢查父結(jié)點(diǎn)的語義.CoerceToString函數(shù)通過插入一個(gè)作為被強(qiáng)制轉(zhuǎn)換的結(jié)點(diǎn)的父結(jié)點(diǎn)的新結(jié)點(diǎn),COERCE_TO_STR,來強(qiáng)制轉(zhuǎn)換任何的表達(dá)式為字符串類型(如果它還不是).

對一個(gè)簡單的編譯器這是很輕松,但是通常它不是這樣.如果你的語言包含更多的基本類型,索引(references),數(shù)組,類和(操作符)重載,事情很快就變得非常的可怕;如果你希望你的程序能夠運(yùn)行,那么你最好有一個(gè)堅(jiān)實(shí)的檢查系統(tǒng).

在一個(gè)真正的編譯器中它從事更多的工作:有更多的強(qiáng)制轉(zhuǎn)換,你必須計(jì)算出要使用哪個(gè)重載函數(shù),類型等價(jià)不是再是這么平常,等等.

在這兒它是很簡單,并且它對于用更多的類型來膨脹這個(gè)系統(tǒng)的學(xué)習(xí)經(jīng)驗(yàn)很有用,但是在一些地方你應(yīng)該更接近一般情況.

代碼應(yīng)該足夠說明它們.它只執(zhí)行一些簡單的事,如if條件應(yīng)該是布爾型,賦值表達(dá)式應(yīng)該是字符串,等等.


產(chǎn)生中間代碼

中間代碼在我們程序中表示為一個(gè)有序的圖:每一條指令有一個(gè)指向下一條指令的指針,跳轉(zhuǎn)有一個(gè)指向它的目標(biāo)指令的指針.

我能想出兩個(gè)這么做(使用指針)而不是立即產(chǎn)生代碼到一個(gè)大的數(shù)組的兩個(gè)好處:第一,使用指針便于把代碼片段的連接,而且去掉某些指令時(shí)不用更新所有的跳轉(zhuǎn),等等.優(yōu)化也因此相應(yīng)的簡單了.第二,如果你想要更改虛擬機(jī)的一些指令,這使你的編譯器更容易改寫來適應(yīng)新的VM,因?yàn)槟阒恍韪淖儚闹虚g代碼到最終代碼的翻譯步驟,這相對的簡單.

于是,基于上面的思想,我們設(shè)計(jì)了我們的中間代碼語言.這個(gè)語言的操作碼(opcode)將與我們的虛擬機(jī)要執(zhí)行的即使不完全一致也是十分的相似.看一下它們:

enum Opcode {
OP_NOP, // no operation
OP_PUSH, // push string [var]
OP_GETTOP, // get string from top of stack (=assign) [var]
OP_DISCARD, // discard top value from the stack
OP_PRINT, // print a string
OP_INPUT, // input a string [var]
OP_JMP, // unconditional jump [dest]
OP_JMPF, // jump if false [dest]
OP_STR_EQUAL, // test whether two strings are equal
OP_BOOL_EQUAL, // test whether two bools are equal
OP_CONCAT, // concatenate two strings
OP_BOOL2STR, // convert bool to string
JUMPTARGET // not an opcode but a jump target;
// the target field points to the jump instruction
};

你將看到我們的VM是一個(gè)堆棧機(jī)器(a stack machine):操作碼對堆棧中的值進(jìn)行操作,把值放回堆棧.我想對產(chǎn)生代碼和執(zhí)行代碼來說這是都最簡單的機(jī)器類型了.

一個(gè)關(guān)于JUMPTARGET操作碼的說明:每當(dāng)我們的代碼中有一個(gè)(條件)跳轉(zhuǎn)時(shí),它并不指向一條實(shí)際的指令而是指向一個(gè)有"JUMPTARGET"前綴的指令.這么做的原因是當(dāng)我們優(yōu)化時(shí)我們必須知道代碼中的每個(gè)跳轉(zhuǎn)的目的指針,或者我們也許會把一條目的指令優(yōu)化掉并且混亂(mess up)我們的程序.這些JUMPTARGET將不出現(xiàn)再我們最終的字節(jié)碼中.

一般而言,所有的操作碼操作堆棧頂端的項(xiàng)目.OP_STR_EQUAL從堆棧中彈出頂端的兩個(gè)項(xiàng)目(必須是字符串),檢查它們是否相等,然后把結(jié)果的布爾值進(jìn)棧.你的程序接著可以使用OP_JMPF指令來使用這個(gè)結(jié)果:如果棧頂?shù)牟紶栔凳莊alse跳轉(zhuǎn)到目標(biāo)指令(由本指令提供,而不是在棧中),如果棧頂是true就繼續(xù)執(zhí)行.

指令被存儲到一個(gè)非常簡單的中間指令類中,它只是保存操作碼,一個(gè)符號--操作數(shù)(例如OP_INPUT),如果需要還有一個(gè)跳轉(zhuǎn)目的指令,一個(gè)下一指令指針和一個(gè)行號.行號實(shí)際上只是在使用Show()函數(shù)時(shí)使代碼可讀.

現(xiàn)在讓我們看看如何產(chǎn)生中間代碼(intcode.cpp).通常我們?yōu)檎Z法樹中的所有子樹產(chǎn)生代碼.所以main以樹根來調(diào)用GenIntCode()函數(shù);GenIntCode處理并且返回一個(gè)中間代碼的起始指針.

先看個(gè)簡單的例子,INPUT_STMT結(jié)點(diǎn):

case INPUT_STMT:
return new IntInstr (OP_INPUT, root->symbol);

這產(chǎn)生一個(gè)新的OP_INPUT指令并且返回它.注意這個(gè)指令也是一個(gè)長度為1的指令塊(block of instructions) ,next指針默認(rèn)為NULL.

PRINT_STMT更困難一點(diǎn):

case PRINT_STMT:
blk1 = GenIntCode (root->child[0]);
blk2 = new IntInstr (OP_PRINT);
return Concatenate (blk1, blk2);

首先我們產(chǎn)生代碼來計(jì)算表達(dá)式提供給print語句(root->child[0]).接著我們產(chǎn)生一個(gè)新指令OP_PRINT來打印棧頂?shù)淖址?注意我們假設(shè)表達(dá)式把它的值放到棧頂.當(dāng)然,我們得自己來保證這一點(diǎn).最后我們連接兩個(gè)代碼塊,然后返回結(jié)果.

現(xiàn)在是一個(gè)真正難的:IFTHEN_STMT.我產(chǎn)生所有需要的塊,然后把它們都連到一起.它檢查條件,如果它是false調(diào)換到結(jié)尾,如果它是true就執(zhí)行then部分.

case IFTHEN_STMT:
// First, create the necessary code parts
cond = GenIntCode (root->child[0]);
jump2end = new IntInstr (OP_JMPF); // set target below
thenpart = GenIntCode (root->child[1]);
endif = new IntInstr (JUMPTARGET, jump2end);
jump2end->target = endif;

// Now, concatenate them all
Concatenate (cond, jump2end);
Concatenate (jump2end, thenpart);
Concatenate (thenpart, endif);
return cond;

記住root->child[0]是條件子樹,root->child[1]是then子樹.

好的,如果明白了那個(gè),對與剩余的代碼你就沒問題了.所有樹的結(jié)點(diǎn)都使用這個(gè)方法翻譯.Show()函數(shù)顯示我們產(chǎn)生的代碼.看一下所有這些:

Program:
if (a==b) a; else b;

Intermediate code:
1: OP_NOP
2: OP_PUSH a
3: OP_PUSH b
4: OP_STR_EQUAL
5: OP_JMPF 9
6: OP_PUSH a
7: OP_DISCARD
8: OP_JMP 12
9: JUMPTARGET 5
10: OP_PUSH b
11: OP_DISCARD
12: JUMPTARGET 8

這看上去非常的象匯編代碼,是吧?這是因?yàn)樗褪?它是虛擬匯編(Virtual Assembly),本質(zhì)上我們只需要寫一個(gè)匯編程序來產(chǎn)生虛擬執(zhí)行代碼.


Whoa, what happened?

那進(jìn)行的很快,不是嗎?剛才我們還想我們是否將作一些有趣的事,突然我們就產(chǎn)生了虛擬匯編代碼.我們幾乎完成了.

下次我們將看一下優(yōu)化(我確信如果你觀察這部分的輸出你能想到一些).很快我們將產(chǎn)生真正的虛擬機(jī)代碼--但是我猜我們最好先有一個(gè)虛擬機(jī)!我們將看到從那我們?nèi)ツ睦?歡迎你發(fā)給我一些想法或建議.

Bottom line: some interesting stuff is coming up. Stay tuned!

See you next time.


Quote!

The story so far:

In the beginning the Universe was created.

This has made a lot of people very angry and been widely regarded as a bad move.

HHG 2:1


Downloads

Download the tutorial code (tut5.zip) (10k)

Part VI:優(yōu)化?

你發(fā)現(xiàn)BUG了嗎?

注意到了前兩次的代碼的好笑的東西了嗎?可能有一個(gè)內(nèi)存漏洞(memory leak)?Emmanuel Astier發(fā)現(xiàn)了;他找出了符號表中的一個(gè)BUG:當(dāng)刪除符號表時(shí),我只是刪除了鏈表中的第一個(gè)實(shí)體,而沒有刪除其他...OK,雖然程序沒有崩潰,但是這不是很漂亮.這將在下一個(gè)教程中修改.多謝Emmanuel!


序言

我的考試結(jié)束了,我現(xiàn)在可能繼續(xù)了.

在這部分我將涉及優(yōu)化我們的中間代碼的方法.記得嗎,我們使用了一個(gè)非常簡單的代碼生成算法,所以那些代碼也許相當(dāng)?shù)男枰獌?yōu)化.

因?yàn)槲覀儗⒃谝粋€(gè)虛擬機(jī)上執(zhí)行,所以優(yōu)化變得格外的重要:我們的每一條指令將花費(fèi)20條CPU指令去執(zhí)行(很難更少),所以指令越少越好.

注意,我將只討論與機(jī)器無關(guān)(machine-independent)的優(yōu)化;面向機(jī)器的優(yōu)化是一個(gè)完全不同的話題,在那里我們必須考慮象流水線效率,寄存器的使用等等這些.并且,當(dāng)然的,面向機(jī)器的優(yōu)化只有當(dāng)你的代碼在硬件上運(yùn)行時(shí)才需要,這我們不需要.當(dāng)然,可能有很多的方法來加速執(zhí)行虛擬機(jī)本身,但是我們將在后面討論.

對不起,這部分沒有例子代碼.一些優(yōu)化的想法實(shí)現(xiàn)起來都是相當(dāng)?shù)暮唵?你將不會在這些問題上碰到麻煩.另外一些更復(fù)雜并且需要花大力氣來實(shí)現(xiàn).我沒有時(shí)間來作,所以我只是給出一般的概念.

有兩個(gè)重要的加速我們的代碼的途徑.一個(gè)是把代碼翻譯成更少的指令.另一個(gè)是制作更多強(qiáng)大的指令.


額外的操作碼(Extra Opcodes)

高級的指令(Higher-level instructions)可以在VM上執(zhí)行的更快,因?yàn)槎褩２僮骱透轮噶钪羔樀目傞_銷是(粗略)的相同的.所以我們將忽略RISC并且為外來的代碼(exotic instructions)而瘋狂!;)

讓我們觀察一些代碼.這是example.vasm的一部分,example.str的編譯后的版本:

1: OP_NOP
2: OP_PUSH strconst1
3: OP_GETTOP a
4: OP_DISCARD
5: OP_PUSH strconst2
6: OP_GETTOP b
7: OP_DISCARD
8: OP_PUSH a
9: OP_PUSH b
10: OP_CONCAT
11: OP_GETTOP s
12: OP_DISCARD
13: OP_PUSH s
14: OP_PRINT

我應(yīng)該注意它的一些事情.第一,在這個(gè)代碼中的三個(gè)地方有一個(gè)OP_DISCARD跟隨在一條OP_GETTOP的情況.我們將它它轉(zhuǎn)換成一條OP_POP來提高速度,這條指令取得棧頂?shù)闹挡⑶野阉鼜亩褩Ｖ幸谱?我可以在開始時(shí)這么做,但是我想現(xiàn)在這樣更簡單.

第二,我看到了OP_PUSH; OP_GETTOP; OP_DISCARD兩次.. 這是一個(gè)向"a = b"這樣的簡單賦值語句的代碼.我們可以為它提供一個(gè)特殊的操作碼OP_COPY,它把一個(gè)變量的值拷貝到另一個(gè)中.

第三,在這個(gè)程序的完整的代碼中有相當(dāng)多的"double pushes",兩個(gè)進(jìn)棧操作在一起.我們一個(gè)制作一個(gè)單獨(dú)的OP_PUSH2操作碼來加速它.

你或許能想出另外的高級指令.例如,一條連接一個(gè)現(xiàn)有字符串OP_CONCATTO操作碼(s += "foo";).如果仔細(xì)的挑選他們將能夠加速執(zhí)行,所以花寫時(shí)間來研究你的匯編代碼,然后發(fā)現(xiàn)優(yōu)化的可能.

代碼變形(Code Transformations)

優(yōu)化輸出代碼的另一個(gè)途徑是吧一部分代碼變形成更快的執(zhí)行同樣任務(wù)的某些東西.下面是一個(gè)例子.

Source	Assembly	Optimized
??s = a; ? ?if (s == d) ...	? ?OP_PUSH a ? ?OP_GETTOP s ? ?OP_DISCARD ? ?OP_PUSH s ? ?OP_PUSH d ? ?OP_STR_EQUAL ? ?...	? ?OP_PUSH a ? ?OP_GETTOP s ??? (cut away) ??? (cut away) ? ?OP_PUSH d ? ?OP_STR_EQUAL ? ?...

下面是一些變形代碼的算法,節(jié)約指令..(saving instructions and thus time)

絕大多數(shù)優(yōu)化集中在優(yōu)化一些被認(rèn)為是"基本模塊(basic blocks)"的一小段代碼.一個(gè)基本模塊有下面這些性質(zhì):你能夠在開始時(shí)跳轉(zhuǎn)到它里面,并且你只能在它的結(jié)尾跳出.所以在這些塊的中間沒有跳轉(zhuǎn)或者跳轉(zhuǎn)目標(biāo)(jump targets).這意味著在塊之內(nèi)我們能夠確定一件關(guān)于我們的變量的值的必然的事情,我們可以利用這個(gè)信息來優(yōu)化代碼.舉個(gè)例子,如果你可以跳轉(zhuǎn)到塊內(nèi)的某處,我們不能確定,t仍然保留著值(a * b - c).

指針帶給基本模塊優(yōu)化很多困難,因?yàn)槟惚仨毚_定變量沒有通過一個(gè)指針被修改,而不是了基本模塊的某處通過它的名字被修改.往往你不能確定這點(diǎn)(指向指針的指針就幾乎不可能知道什么變量被改變了).


代數(shù)上等同(Algebraic identities)

一個(gè)優(yōu)化代碼的簡單方法是使用產(chǎn)生相同結(jié)果的更快版本來替代原來的"天真的"計(jì)算.這些"天真的"計(jì)算的計(jì)算經(jīng)常采用一個(gè)簡單的代碼產(chǎn)生方案而不是象程序員指定的那樣.觀察下表,十分明顯.

Before	After
? ?x + 0 ? ?x * 1 ? ?x ** 2 ? ?2.0 * x ? ?x / 2	? ?x ? ?x ? ?x * x ? ?x + x ? ?x * 0.5

消除通用子表達(dá)式(Common subexpression elimination)

這種優(yōu)化利用某一表達(dá)式可能多次使用一小段代碼的事實(shí):

a = a + (b - 1);
c = c + (b - 1);

這里(b-1)是一個(gè)通用子表達(dá)式并且可被再次使用(第二個(gè)(b-1)表達(dá)式可以被"消除").

t = b - 1; // 把子表達(dá)式存儲到一個(gè)臨時(shí)變量中
a = a + t;
c = c + t;

為了檢測通用子表達(dá)式,你需要構(gòu)造一個(gè)出現(xiàn)在你表達(dá)式中基本模塊的有向無環(huán)圖(DAG,directed acyclic graph).每次你遇到一個(gè)新的表達(dá)式(例如,語法樹中一個(gè)更高的結(jié)點(diǎn)),你檢查在這個(gè)基本模塊的它是否已經(jīng)出現(xiàn)在表達(dá)式DAG中.當(dāng)這個(gè)圖完成時(shí)你能很容易的看出那個(gè)子表達(dá)式使用了多次,這樣你就可以把它們的值存入一個(gè)鏈?zhǔn)阶兞?并且再次使用它.上圖是一個(gè)例子.


循環(huán)的優(yōu)化(Loop optimizations)

一個(gè)眾所周知的程序員的格言"程序90%的時(shí)間花費(fèi)在執(zhí)行10%的代碼上",盡管這個(gè)百分比每個(gè)程序都不同,但是每個(gè)人都會同意絕大多數(shù)運(yùn)行時(shí)間花費(fèi)在一個(gè)內(nèi)層循環(huán)上.

所以如果我們能使用某種方法優(yōu)化這些循環(huán),我們就能節(jié)省很多的時(shí)間...好吧,有很多中優(yōu)化循環(huán)的方法;我將簡單的討論他們中的兩個(gè),代碼移動和變量歸納(code motion and induction variables).

代碼移動類似與子表達(dá)式消除,但是不是在一個(gè)基本模塊中,它在循環(huán)開始前計(jì)算表達(dá)式并且在循環(huán)的整個(gè)過程中使用這個(gè)值.

while ( i <= limit-2 )

變?yōu)?/span>

t = limit - 2;
while ( i <= t )

可是,循環(huán)也許沒有很多的不變的表達(dá)式.它們經(jīng)常使用的是一個(gè)循環(huán)技術(shù)器,并且這個(gè)技術(shù)器被頻繁的使用在計(jì)算中,例如數(shù)組下標(biāo),等等.那就是變量歸納能幫我們的了.

如果j是我們的循環(huán)技術(shù)器,并且每次循環(huán)中都計(jì)算j*4,我們可以使用一個(gè)變量歸納,然后把這個(gè)乘法替代為加法:

for (j = 0; j < n; j++) {
.... (j * 4) ....
}

變?yōu)?

t = 0;
for (j = 0; j < n; j++) {
.... t ....
t += 4;
}


跳轉(zhuǎn)的消除(Jump elimination)

有時(shí)你能夠通過觀察跳轉(zhuǎn)的目的塊來消去一個(gè)跳轉(zhuǎn).例如,你可能有:

1: jmp 7
...
7: str_equal
8: jmpf 10
9: ...

你可以從目的塊拷貝代碼,然后節(jié)省一個(gè)跳轉(zhuǎn)(如果條件為假):

1a: str_equal // | 目的塊的拷貝
1b: jmpf 10 // |
1c: jmp 9 // 如果條件為真,跳轉(zhuǎn)到9
...
7: str_equal
8: jmpf 10
9: ...

你要決定為了消除一個(gè)跳轉(zhuǎn)你將要復(fù)制多大一部分代碼,但是在內(nèi)層循環(huán)中它能省很多時(shí)間.

下次的東西...

這些信息使你的程序變得更有效率了.可是編譯器優(yōu)化是一個(gè)非常復(fù)雜的領(lǐng)域,我們只涉及到了非常少的一點(diǎn).龍之書討論了更多,所以如果你感興趣,就去看它吧 .

下次我們將建立我們虛擬機(jī),然后也許產(chǎn)生我們的虛擬機(jī)代碼吧.那時(shí)我們就終于可以執(zhí)行一個(gè)程序了.


Quote!

Somewhere on the wall a small white light flashed.

"Come," said Slartibartfast, "you are to meet the mice. Your arrival on the planet has caused considerable excitement. It has already been hailed, so I gather, as the third most improbable event in the history of the Universe."

"What were the first two?"

"Oh, probably just coincidences," said Slartibartfast carelessly.

HHG 1:30


Part VII:虛擬機(jī)(The Virtual Machine)

序言

我們已經(jīng)在Part V產(chǎn)生了中間代碼,并且我們想要把它轉(zhuǎn)換成可執(zhí)行代碼,好讓我們能夠執(zhí)行一個(gè)程序.但是我已經(jīng)決定要先建立一個(gè)虛擬機(jī),這樣我們可以知道該如何處理產(chǎn)生可執(zhí)行代碼.

虛擬機(jī)當(dāng)然是一個(gè)腳本引擎中非常重要的組件.我們的代碼將在它那里執(zhí)行,所以它最好快一些.但是這里我將不把焦點(diǎn)集中到速度上.

Oh yeah:這部分結(jié)束后,你將完全免費(fèi)的得到我那令人驚奇的堆棧模板(Amazing Stack Template),也不需要額外的小費(fèi).并且你將得到一個(gè)為這部分特別編寫的很酷的字符串類,它完成至少5個(gè)精密的工作.那是你的物有所值的東西.

但是,首先是一個(gè)不同機(jī)器類型的說明.在Part V我只是說了我們的VM將是什么種類,沒有說明其它的可能.Andy Campbell詢問我關(guān)于這方面的其它可能性,并且我想其他人也許會感興趣.


機(jī)器類型

以前說過,我們的機(jī)器將是一個(gè)堆棧機(jī)器(stack machine).在真實(shí)的機(jī)器中,堆棧CPU被用于早期的計(jì)算機(jī)(并且今天依然在一些簡單的設(shè)備中使用).缺點(diǎn)是需要很多的堆棧操作:每個(gè)操作數(shù)需要一個(gè)PUSH,每個(gè)結(jié)果需要一個(gè)POP.盡管你直接使用這個(gè)結(jié)果來進(jìn)行下面的計(jì)算,所以那不總是必須的.

現(xiàn)在的大多數(shù)CPU有寄存器(數(shù)量非常有限的存儲位置)來進(jìn)行操作而不是堆棧;堆棧依然在函數(shù)傳遞參數(shù)時(shí)使用.可以只在寄存器上操作的機(jī)器被稱為load/store機(jī)器,因?yàn)槟惚仨歭oad每個(gè)你用到的值,然后在你計(jì)算完后store每個(gè)結(jié)果.

某些處理器只操作內(nèi)存數(shù)據(jù);沒有堆棧,也沒有寄存器.使用這種處理器的機(jī)器被稱為三地址機(jī)器(three-address machines),因?yàn)榻^大多數(shù)指令有三個(gè)地址操作數(shù)(例如 ADD dest,src1,src2).由于內(nèi)存帶寬的限制,我認(rèn)為他們不會在很多硬件中使用,但是他是虛擬機(jī)的一個(gè)選擇.

對于虛擬機(jī),堆棧機(jī)器非常容易實(shí)現(xiàn),因?yàn)楫?dāng)你計(jì)算一個(gè)表達(dá)式時(shí)不需要臨時(shí)變量來存儲中間結(jié)果;你把所有東西放入堆棧(它與你處理一個(gè)后綴表達(dá)式的方法十分相似).雖然我將在這里使用臨時(shí)變量.后面還有更多內(nèi)容.

我不清楚三地址機(jī)器是否可能有一個(gè)優(yōu)點(diǎn);速度是最重要的一個(gè),盡管我嘗試了兩者,我能肯定的說出哪個(gè)在優(yōu)化中做了更少的計(jì)算...我想優(yōu)化三地址代碼更容易,所以也許這是這種機(jī)器的一個(gè)優(yōu)點(diǎn).

JAVA表面上使用一個(gè)堆棧機(jī)器(我聽說是這樣,我對JAVA VM不熟).


一件虛擬的非常容易的事(A Virtual Piece of Cake)

我們的虛擬機(jī)對象根本就不復(fù)雜.它的最重要的成員有:一個(gè)指令數(shù)組,一個(gè)字符串表和一個(gè)堆棧.它有三個(gè)主要的接口函數(shù):Reset,Read和Execute.

指令數(shù)組存儲我們的程序包含的指令.指令類簡單極了,看上去就像我們在Part 5中的中間代碼使用的一樣.

字符串表只是一個(gè)指針數(shù)組,它可以是NULL或者一個(gè)當(dāng)前使用的字符串.這可能是一個(gè)程序的變量,或者一個(gè)堆棧中的臨時(shí)變量.

我們的堆棧是由整數(shù)組成的.它們指向字符串表,使我們知道什么字符串現(xiàn)在在堆棧中.為什么我使用整數(shù),而不是字符串類的指針呢?因?yàn)槲蚁氡３质挛锏暮唵?為了讀者,也為了我自己):記住我們有時(shí)也想讓堆棧存儲布爾值,所以我們不得不建立一個(gè)存儲字符串指針或布爾值的'stack item'類...現(xiàn)在我們只是使用一個(gè)整數(shù):如果它是非負(fù)數(shù),我們知道它指向一個(gè)字符串,如果它是負(fù)數(shù)它就是一個(gè)布爾值.它是臟的代碼,但是他有利于工作并且每個(gè)人都可以理解它.不要在家試它,不要在一個(gè)真正的項(xiàng)目中使用它.

現(xiàn)在是接口函數(shù).'Reset'重新初始化VM.它是一個(gè)很簡單的函數(shù).

'Read'將要在程序中讀取.下次我們將改變這個(gè)函數(shù)讓他從stdin中讀取,但是現(xiàn)在它里面有一個(gè)測試程序.如果你喜歡就改寫它--只是小心的讓程序保持正確,不要讓我們的VM崩潰.

'Execute'執(zhí)行當(dāng)前在內(nèi)存中的程序.這也是一個(gè)簡單的函數(shù):它有一個(gè)指令指針,它察看一個(gè)指令,然后使用一個(gè)switch語句執(zhí)行正確的代碼.關(guān)于臨時(shí)變量的一個(gè)說明:每當(dāng)我們把一個(gè)變量放到堆棧,我們需要它的一個(gè)拷貝:我們不能只是把在字符串表中的變量的索引值進(jìn)棧,因?yàn)樗麄兊闹悼赡芨淖儾⑶医又褩Ｖ械闹狄矔淖?這就是為什么幾乎每個(gè)堆棧操作都使用NewTempCopy和DelTempCopy.

一點(diǎn)關(guān)于優(yōu)化VM的說明:我們應(yīng)該確保我們的堆棧操作盡可能的快;我們的堆棧模板不是特別的快.在字符串操作上也一樣.一般而言,我們應(yīng)該使通用的case快.最好把所有普通的優(yōu)化技術(shù)應(yīng)用到VM上.

關(guān)于VM還有很多要說:存儲分配(allocation schemes),垃圾收集(garbage collection),保持他們穩(wěn)定和高速,但是我想我將推延到下一部分.

下一次

下一次我們將最終執(zhí)行代碼.然后我們就完成了我們的簡單的腳本引擎.之后我可能給出一個(gè)復(fù)雜的真實(shí)的腳本引擎的概貌,并且討論所需的主題.


Quote!?

"Come," called the old man, "come now or you will be late."

"Late?" said Arthur. "What for?"

"What is your name, human?"

"Dent. Arthur Dent," said Arthur.

"Late, as in the late Dentarthurdent," said the old man, sternly. "It's a sort of threat you see." Another wistful look came into his tired old eyes. "I've never been very good at them myself, but I'm told they can be very effective."

HHG 1:22


Downloads

Download the tutorial code (tut7.zip) (5k)


Part VIII:可執(zhí)行代碼

序言

我們有了執(zhí)行我們的程序的所有需要的東西,除了...可執(zhí)行代碼.我們已經(jīng)有了中間代碼,并且它已經(jīng)非常接近我們的虛擬機(jī)能理解的東西了.所以我們必須作的是一個(gè)中間代碼和可執(zhí)行代碼之間的快速的翻譯步驟.

為什么這需要是一個(gè)分離的步驟?就象你看到的,翻譯實(shí)際上涉及到把我們的字符串放到一個(gè)數(shù)組中,并且為符號表提供他們的索引而不是指針.我們上次已經(jīng)做了跳轉(zhuǎn)目的,所以他們將不再改變.所以這是一個(gè)簡短的部分,代碼改變不大.

也許對于我們,建立中間代碼不是嚴(yán)格的需要.但是寫一個(gè)更高級的編譯器時(shí),有這樣一個(gè)分離是非常有用的,在實(shí)際的機(jī)器碼之前更多的'概念上的'階段:它簡化代碼優(yōu)化;你可以不困難的重新定義你的編譯器到另一個(gè)機(jī)器.


最后一步

當(dāng)你閱讀這部分的代碼時(shí),你將在幾個(gè)地方看到到我的懶惰,它使我寫了真正罪惡的代碼.

舉個(gè)例,我把編譯器和虛擬機(jī)組合到了一個(gè)程序中,并且我傳送"中間代碼"給虛擬機(jī),這不是很恰當(dāng)?shù)姆椒?你也許想要你的編譯器來處理每件事直到可執(zhí)行代碼產(chǎn)生,然后也許存儲可執(zhí)行代碼到一個(gè)文件,然后讓你的VM讀取&執(zhí)行這個(gè)文件.

在我們這里,VM中的Read()函數(shù)首先從我們的符號表中取得所有的字符串,然后把他們放入字符串?dāng)?shù)組.然后它線性的通覽代碼,并且一行接一行的翻譯它們.我們所使用的特殊的跳轉(zhuǎn)目的指令只被轉(zhuǎn)換成NOP指令,它應(yīng)該被優(yōu)化掉.

Oh,我做得一個(gè)顯著的可惡的事是我用來自編譯器的符號表來存儲虛擬機(jī)的字符串表索引(使用符號表的新成員PutNo()/GetNo())...它是非常簡單的找到字符索引的方法,但是我同意模塊化的程序設(shè)計(jì)是全然不同的...


它工作了!我簡直不能相信!

嗨,你真的可以使用這個(gè)編譯器/虛擬機(jī)的結(jié)合體來執(zhí)行一個(gè)程序!你大概幾乎放棄了它,不是嗎?好吧,繼續(xù)嘗試?yán)?這部分有源碼可以下載...他們應(yīng)該正確執(zhí)行.這很有趣吧.

好的,那就是我們曾經(jīng)為之工作的東西.一個(gè)小小的語言,盡管它自身不是很有用,但是它表現(xiàn)了很酷的東西--你現(xiàn)在學(xué)習(xí)了建立你自己的腳本引擎的足夠的東西.

現(xiàn)在發(fā)生了什么?

經(jīng)過了這樣一個(gè)難以置信的極限(啊咳)我相信你有一點(diǎn)感覺空虛和不知所措.我們將從這里去到哪里?

我將可能作一個(gè)或更多的part介紹一些高級的主題,也許談到為這個(gè)語言增加函數(shù),類,多態(tài),等等.讓我知道你對什么感興趣.

盡管將不再有代碼--每個(gè)人都可以取得這個(gè)簡單的編譯器并且擴(kuò)充它.或者,更好,寫一個(gè)你自己的.The world's your oyster!

Quote!

"More importantly, a towel has immense psychological value. For some reason, if a strag (strag: non-hitch hiker) discovers that a hitch hiker has his towel with him, he will automatically assume that he is also in possession of a toothbrush, face flannel, soap, tin of biscuits, flask, compass, map, ball of string, gnat spray, wet weather gear, space suit etc., etc. Furthermore, the strag will then happily lend the hitch hiker any of these or a dozen other items that the hitch hiker might accidentally have "lost". What the strag will think is that any man who can hitch the length and breadth of the galaxy, rough it, slum it, struggle against terrible odds, win through, and still knows where his towel is is clearly a man to be reckoned with."

HHG 1:3

Downloads

Download the tutorial code (tut8.zip) (15k)


Part IX:高級主題?

序言

現(xiàn)在你已經(jīng)玩了一下那個(gè)完成的腳本例子,也許你實(shí)現(xiàn)了一些新特性,或許當(dāng)我們將要接觸新東西時(shí)你在疑惑.

請?jiān)试S我提醒您,這些好東西里的絕大部分都需要大量的工作(這些我將不再提供例子代碼).我將討論幾個(gè)高級的腳本主題,給出如何實(shí)現(xiàn)(我的想法)的一般想法.

第一個(gè):


A lockup-resistent VM(不會翻,暈倒....)

前一段時(shí)間Joseph Hall給了我一個(gè)處理無限循環(huán)(infinite-looping)的腳本代碼的很好的想法.他的思想是:每次調(diào)用虛擬機(jī)時(shí)給他最大數(shù)量的操作碼去執(zhí)行,并且如果下一幀它還沒有完成時(shí)讓它繼續(xù)執(zhí)行;這是虛擬的等價(jià)與CPU優(yōu)先級多任務(wù).這種方法使你的游戲引擎在腳本代碼掛起時(shí)可以保持運(yùn)行;它可以自動檢測腳本是一個(gè)不變的循環(huán)并且重起VM.

現(xiàn)在,讓我們看看我們可以怎么樣擴(kuò)展我們的語言:


函數(shù)

在你的腳本語言中增加函數(shù)是非常困難的,它引入了參數(shù)和局部變量的概念.為了他們需要使用堆棧.在一個(gè)函數(shù)調(diào)用前程序把參數(shù)入棧.然后函數(shù)在同一堆棧中預(yù)留空間給它的局部變量.然后執(zhí)行函數(shù),使用預(yù)留的堆?？臻g來讀寫值.在我們的簡單的編譯器中,我們僅僅從棧頂進(jìn)棧和退棧,但是現(xiàn)在你也可以訪問堆棧中間的內(nèi)存地址.

你需要為函數(shù)使用兩個(gè)特殊的操作碼:CALL和RETURN.CALL是一個(gè)無條件的跳轉(zhuǎn),它吧指令指針保存到堆棧中.RETURN讀取那個(gè)被存儲的指令指針,然后跳回CALL后面的指令.

要做的一件最符合邏輯的事是讓調(diào)用者(不是該函數(shù))把參數(shù)從堆棧中移走參數(shù);畢竟最初是調(diào)用者把他們放進(jìn)來的.這也考慮到一個(gè)"輸出參數(shù)(output parameters)"的簡單機(jī)制:函數(shù)改變一個(gè)參數(shù)的然后調(diào)用者把這個(gè)值存入一個(gè)變量.一個(gè)函數(shù)的返回值也可以看作是一個(gè)輸出參數(shù).

函數(shù)的信息頭可以存儲到一個(gè)符號表中.使用他們,你可以存儲它的參數(shù)和局部變量(可以每個(gè)是一個(gè)分離的符號表實(shí)體).在代碼生成的過程中,你可以在符號表中存儲函數(shù)的起始地址.

重載(Overloading)
函數(shù)的重載可以是一個(gè)語言中非常好的特性,但是實(shí)現(xiàn)它可能很棘手的.問題是如何通過提供的參數(shù)類型來正確的從可能的函數(shù)頭信息中找到一個(gè)恰好匹配的函數(shù)來調(diào)用.在這種情況下,你將不得不強(qiáng)制某些參數(shù)到不同的類型來得到一個(gè)完全的匹配.問題是什么參數(shù)需要強(qiáng)制轉(zhuǎn)換和把它們轉(zhuǎn)換到什么類型.大多數(shù)編譯器試著比較調(diào)用和可能的選擇,然后選擇一個(gè)需要最少強(qiáng)制轉(zhuǎn)換的.一些編譯器允許雙重強(qiáng)制轉(zhuǎn)換(例如:bool->int,然后int->unsigned),這使麻煩更復(fù)雜,我建議保持簡單.

操作符可能看作是一個(gè)用不同語法調(diào)用的函數(shù);如果用這種方法來處理你的操作符(不要真把它們作成函數(shù)(慢),而是inline函數(shù)或者宏),你可以輕松的擴(kuò)展函數(shù)重載到操作符重載.

類

如果你想要在你的語言中實(shí)現(xiàn)類,正確的決定你想要支持那些特性.支持完整的C++類,包括多繼承,訪問控制,動態(tài)束定,虛函數(shù),等等是非常困難的,我建議不要在一開始就處理所有這些.一個(gè)帶有單繼承的簡單的類系統(tǒng)是一個(gè)很好的起點(diǎn),如果需要的話你以后可以擴(kuò)展它.

類和結(jié)構(gòu)體是符合數(shù)據(jù)類型:他們包含多個(gè)數(shù)據(jù)成員,并且連接到一定數(shù)量的方法或者成員函數(shù).你可以在你的符號表中存儲一個(gè)成員列表,它與其他分離的成員符號表實(shí)體相連接.這可以使你簡單的找到結(jié)構(gòu)中某個(gè)成員的偏移量.

繼承
單繼承相對的簡單:當(dāng)你在一個(gè)對象中查找一個(gè)成員時(shí),檢查這個(gè)成員是否在子類中;如果不是就檢查它的父類.子類的存儲布局很簡單:首先你存儲父類,然后是他的子類,其他子類,等等.這樣向下的束定被隱藏:你可以處理向處理一個(gè)Animal的指針一樣處理一個(gè)Cat的指針,這個(gè)的意思是你的程序可以訪問更少的成員,但是指針的地址不需要改變.

多繼承,當(dāng)調(diào)用一個(gè)成員函數(shù)或者訪問一個(gè)數(shù)據(jù)成員時(shí),它帶來了二義性問題.思考這個(gè):兩個(gè)類B和C是統(tǒng)一個(gè)類--類A的子類.然后建立一個(gè)類D源于類B和類C這兩個(gè)類.現(xiàn)在,如果類A有一個(gè)公有成員函數(shù)DoSomething,當(dāng)成員在一個(gè)D類型的對象中調(diào)用DoSomething時(shí),你不能知道調(diào)用兩個(gè)DoSomething中的哪個(gè):一個(gè)是B的A部分,另一個(gè)是C的A部分..好吧,也許看圖可以更清楚.

虛函數(shù)
虛函數(shù)是建立多態(tài)的一個(gè)方法;例如一個(gè)Animal類包含一個(gè)虛函數(shù)MakeSound(),一個(gè)子類Cat和Dog都各自用不同的方法實(shí)現(xiàn)一個(gè)這個(gè)函數(shù)(我想讓你考慮如何正確的實(shí)現(xiàn)他們).于是當(dāng)你調(diào)用一個(gè)Animal對象的MakeSound函數(shù)時(shí),你不知道(并且不需要知道)是那種動物在發(fā)出聲音.

虛函數(shù)函數(shù)使用一個(gè)所謂的vtable來實(shí)現(xiàn).當(dāng)父類聲明一個(gè)函數(shù)為virtual時(shí),它在那個(gè)類中增加了vtalbe.每個(gè)子類現(xiàn)在取得他們自己版本的vtable,這樣,不同的函數(shù)調(diào)用基于那個(gè)對象實(shí)際的類型,盡管在調(diào)用者看來這些table之間并沒有區(qū)別.

動態(tài)束定
動態(tài)束定可以很便利:例如,在UnrealScript中你不僅僅可以向下束定一個(gè)對象(把它束定到它的父類型),而且可以向上束定(束定一個(gè)對象到它的子類),如果這個(gè)對象的確是子類的對象.這意味著你需要一個(gè)方法來決定一個(gè)Parent類型的對象實(shí)際上是向下束定的一個(gè)Child1對象(在這種情況它可以被向上束定),或者是一個(gè)Child2對象(在這種情況它不可以被向上束定).在最新的C++編譯器中你可以使用dynamic_cast<...>操作符.怎么覺得這個(gè)呢?每個(gè)對象都將必須有一個(gè)獨(dú)一無二的號碼,也許是一個(gè)類的表和他們的父類的索引.使用這個(gè)號碼,你可以斷定它到底是那種對象.

類型變量(Type variables)
類型變量允許類型的變量.這允許你動態(tài)建立一個(gè)變量類型的對象.舉個(gè)例子,你有一個(gè)游戲,一個(gè)敵人走了進(jìn)來,兩個(gè)同樣的敵人走了出去.你可能會看到一個(gè)包含所有可能的敵人的巨大的switch語句,但是這不是很好擴(kuò)展.所以你可以存儲敵人的類型,告訴游戲使用這個(gè)類型建立一個(gè)怪物.這是一些假想的語言代碼:

TypeVar<Enemy> enemytype; // A type variable
enemytype = typeof (monster); // Get the monster's type
Enemy *newmonster = new enemytype; // Create a new monster of the same type

你可以傳遞類型變量到一個(gè)函數(shù);這將使得他們很有可塑性,你可以使用同一個(gè)函數(shù)來建立和處理很多不同類型的對象.

為了類型變量,你需要擴(kuò)充類和他們的父類的表來包含每個(gè)類型的大小;否則你將沒法動態(tài)建立他們.


Game-specific language constructs

UnrealScript(據(jù)我所知)是第一個(gè)提出了兩個(gè)在游戲中非常有用的特性的語言:狀態(tài)和隱藏代碼.

狀態(tài)
UnrealScript中的類可以有幾種狀態(tài);一個(gè)對象總是在一個(gè)確定的狀態(tài).基于對象處在那個(gè)狀態(tài),為這個(gè)對象執(zhí)行不同的函數(shù).所以如果這個(gè)對象是一個(gè)敵人并且它處在Angry的狀態(tài),Angry版本的SeePlayer函數(shù)將被執(zhí)行,這個(gè)敵人將可是攻擊玩家.如果這個(gè)敵人處在一個(gè)Frightened的狀態(tài),另一個(gè)SeePlayer函數(shù)(使用同樣的參數(shù)類型)將被調(diào)用,使得敵人逃跑.

狀態(tài)并不是非常難加入,盡管它的確需要一些工作;狀態(tài)是一個(gè)額外的類成員(不可見),并且每當(dāng)調(diào)用特定的狀態(tài)函數(shù)時(shí)恰當(dāng)?shù)暮瘮?shù)版本將被執(zhí)行.這可以使用一個(gè)使用狀態(tài)號碼為索引的跳轉(zhuǎn)表來輕松實(shí)現(xiàn).

狀態(tài)可以有它們自己的函數(shù)外的代碼,在UnrealScript中是狀態(tài)代碼.這可以方便的與下一個(gè)構(gòu)思相結(jié)合:隱藏的函數(shù).

隱藏的函數(shù)(latent code)
隱藏的函數(shù)相當(dāng)?shù)碾y實(shí)現(xiàn),但是非常的酷:一個(gè)隱藏的函數(shù)花費(fèi)一些游戲時(shí)間來執(zhí)行;換句話說,這個(gè)過程可以起動一個(gè)函數(shù)等待或者激活那個(gè)等待或者激活一個(gè)人物,當(dāng)這個(gè)動畫完成后代碼繼續(xù)執(zhí)行.這是一個(gè)AI腳本很好的特性.

隱藏代碼帶來的另一個(gè)問題是本質(zhì)上它與其他代碼并行執(zhí)行.偶爾隱藏代碼被執(zhí)行,然后它又被停止.所以我們必須記住隱藏代碼的指令指針.并且當(dāng)對象改變它的狀態(tài)時(shí),你將也需要執(zhí)行其他的隱藏代碼.

我們可以看到UnrealScript唯一提供隱藏代碼的原因是為了調(diào)用狀態(tài)代碼,而不是普通函數(shù):假設(shè)隱藏函數(shù)可以在任何地方被調(diào)用,每個(gè)對象本質(zhì)上可以有很多的并行執(zhí)行的"線程"..這可能需要大量的記錄并且將變慢.而且也將產(chǎn)生同步問題:一個(gè)對象的線程將把一個(gè)成員變量設(shè)為某個(gè)特定的值,然后一個(gè)其他的線程變?yōu)榛顒雍笤俅涡薷乃?..如果你想允許它將需要實(shí)現(xiàn)一個(gè)完整的多線程系統(tǒng).

That's it for now..?

我希望這可以激發(fā)你的想象力.有許多特性你的腳本語言可以實(shí)現(xiàn);如果你想完成它你將限制自己為某一個(gè).

這可能是這個(gè)系列教程的最后以部分.我樂于寫它.如果你覺得在一些地方還不夠,讓我知道,也許我將寫一個(gè)額外的部分.當(dāng)然,如果你有其他的一些問題我也樂于聽你說.

Good luck, and keep on scripting! ;-)


Quote!?
"He stared at it for some time as things began slowly to reassemble themselves in his mind. He wondered what he should do, but he only wondered it idly. Around him people were beginning to rush and shout a lot, but it was suddenly very clear to him that there was nothing to be done, not now or ever. Through the new strangeness of noise and light he could just make out the shape of Ford Prefect sitting back and laughing wildly.

A tremendous feeling of peace came over him. He knew that at last, for once and for ever, it was now all, finally, over."

HHG 5:25

總結(jié)

以上是生活随笔為你收集整理的实现一个脚本引擎的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。