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

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

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

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

Part I:概述
序言

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

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

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

這里是我想到的一些:

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

但是也有一些不利因素:

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

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


必須閱讀的東西

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

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

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

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

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

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


我們需要什么

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

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

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


這是全部嗎?

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

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

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

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:詞法分析器
序言

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

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

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

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


是什么,為什么和怎么作

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

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

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

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


LEX規(guī)則

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

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

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

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

lexsymb.h 文件聲明了詞法分析器函數(shù)將要返回的記號(hào)的符號(hào).它還聲明了一個(gè)'yylval' 共用體(union),用來(lái)傳送額外的信息(例如標(biāo)識(shí)符的名字)到主調(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)

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

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

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

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

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

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

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

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


情況會(huì)變好的

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

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

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

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)鍵字來(lái)處理,不是本程序的主要部分,本程序的主要功能是識(shí)別一下各種形式的實(shí)常數(shù):

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

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

參見(jiàn)程序:CONSTANT.zip

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

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

{ this ) = "pointless" + ;

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

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


一點(diǎn)語(yǔ)言理論

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

expression: identifier | string;

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

statement
: PRINT expression END_STMT
| INPUT identifier END_STMT
;

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

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

program: | program statement;

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

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

print a;
(燕良注:這個(gè)語(yǔ)句可以使用下面的推導(dǎo)過(guò)程:
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)過(guò)詞法分析后上面的語(yǔ)句形成的記號(hào)流與此式匹配;
以上是最左推導(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)可以畫(huà)出語(yǔ)法樹(shù),對(duì)于無(wú)二義性的文法,所有的推導(dǎo)畫(huà)出的語(yǔ)法樹(shù)都是一樣的.)
print "Hello";
input name;

Not legal is:

input "Hello";

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

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

a = (b == c);

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

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


看上去很熟悉!

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

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

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

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

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

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

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

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

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

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

if (a == b + c)

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

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

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

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

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

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

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

%expect 1

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

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

Yacc的源文件可以使用這條命令來(lái)編譯:

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

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

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

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


Whew! 

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

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

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


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)


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

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

Part IV:符號(hào)表 & 語(yǔ)法樹(shù)
序言

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

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

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

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


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

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

我們?cè)诮⒁粋€(gè)語(yǔ)法樹(shù)時(shí)需要某些近似的東西:我們需要父規(guī)則有一個(gè)指針指向他的"孩子結(jié)點(diǎn)"(構(gòu)成父規(guī)則的那些規(guī)則)

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

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

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

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

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

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

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

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


符號(hào)表

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

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

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

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


語(yǔ)法樹(shù)

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

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

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

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


這真的很cool,但是...

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

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

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

下次再見(jià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:語(yǔ)義檢查 & 中間代碼生成
序言

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

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

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

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

讓我們開(kāi)始檢查吧!


檢查語(yǔ)法

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

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

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

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

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

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

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

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

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

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

代碼應(yīng)該足夠說(shuō)明它們.它只執(zhí)行一些簡(jiǎn)單的事,如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)的簡(jiǎn)單了.第二,如果你想要更改虛擬機(jī)的一些指令,這使你的編譯器更容易改寫(xiě)來(lái)適應(yīng)新的VM,因?yàn)槟阒恍韪淖儚闹虚g代碼到最終代碼的翻譯步驟,這相對(duì)的簡(jiǎn)單.

于是,基于上面的思想,我們?cè)O(shè)計(jì)了我們的中間代碼語(yǔ)言.這個(gè)語(yǔ)言的操作碼(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):操作碼對(duì)堆棧中的值進(jìn)行操作,把值放回堆棧.我想對(duì)產(chǎn)生代碼和執(zhí)行代碼來(lái)說(shuō)這是都最簡(jiǎn)單的機(jī)器類(lèi)型了.

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

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

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

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

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

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

這產(chǎn)生一個(gè)新的OP_INPUT指令并且返回它.注意這個(gè)指令也是一個(gè)長(zhǎng)度為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)生代碼來(lái)計(jì)算表達(dá)式提供給print語(yǔ)句(root->child[0]).接著我們產(chǎn)生一個(gè)新指令OP_PRINT來(lái)打印棧頂?shù)淖址?span lang="EN-US">.注意我們假設(shè)表達(dá)式把它的值放到棧頂.當(dāng)然,我們得自己來(lái)保證這一點(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]是條件子樹(shù),root->child[1]是then子樹(shù).

好的,如果明白了那個(gè),對(duì)與剩余的代碼你就沒(méi)問(wèn)題了.所有樹(shù)的結(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)樗褪?span lang="EN-US">.它是虛擬匯編(Virtual Assembly),本質(zhì)上我們只需要寫(xiě)一個(gè)匯編程序來(lái)產(chǎn)生虛擬執(zhí)行代碼.


Whoa, what happened?

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

下次我們將看一下優(yōu)化(我確信如果你觀察這部分的輸出你能想到一些).很快我們將產(chǎn)生真正的虛擬機(jī)代碼--但是我猜我們最好先有一個(gè)虛擬機(jī)!我們將看到從那我們?nèi)ツ睦?span lang="EN-US">.歡迎你發(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)了;他找出了符號(hào)表中的一個(gè)BUG:當(dāng)刪除符號(hào)表時(shí),我只是刪除了鏈表中的第一個(gè)實(shí)體,而沒(méi)有刪除其他...OK,雖然程序沒(méi)有崩潰,但是這不是很漂亮.這將在下一個(gè)教程中修改.多謝Emmanuel!


序言

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

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

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

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

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

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


額外的操作碼(Extra Opcodes)

高級(jí)的指令(Higher-level instructions)可以在VM上執(zhí)行的更快,因?yàn)槎褩２僮骱透轮噶钪羔樀目傞_(kāi)銷(xiāo)是(粗略)的相同的.所以我們將忽略RISC并且為外來(lái)的代碼(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來(lái)提高速度,這條指令取得棧頂?shù)闹挡⑶野阉鼜亩褩Ｖ幸谱?span lang="EN-US">.我可以在開(kāi)始時(shí)這么做,但是我想現(xiàn)在這樣更簡(jiǎn)單.

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

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

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

代碼變形(Code Transformations)

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

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

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

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


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

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

消除通用子表達(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á)式存儲(chǔ)到一個(gè)臨時(shí)變量中
a = a + t;
c = c + t;

 

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


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

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

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

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

while ( i <= limit-2 )

變?yōu)?/span>

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

可是,循環(huán)也許沒(méi)有很多的不變的表達(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)?span lang="EN-US">:

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


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

有時(shí)你能夠通過(guò)觀察跳轉(zhuǎn)的目的塊來(lái)消去一個(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).龍之書(shū)討論了更多,所以如果你感興趣,就去看它吧 .

下次我們將建立我們虛擬機(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è)為這部分特別編寫(xiě)的很酷的字符串類(lèi),它完成至少5個(gè)精密的工作.那是你的物有所值的東西.

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


機(jī)器類(lèi)型

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

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

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

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

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

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


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

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

指令數(shù)組存儲(chǔ)我們的程序包含的指令.指令類(lèi)簡(jiǎn)單極了,看上去就像我們?cè)?span lang="EN-US">Part 5中的中間代碼使用的一樣.

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

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

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

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

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

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

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

下一次

下一次我們將最終執(zhí)行代碼.然后我們就完成了我們的簡(jiǎn)單的腳本引擎.之后我可能給出一個(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ù)組中,并且為符號(hào)表提供他們的索引而不是指針.我們上次已經(jīng)做了跳轉(zhuǎn)目的,所以他們將不再改變.所以這是一個(gè)簡(jiǎn)短的部分,代碼改變不大.

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


最后一步

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

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

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

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


它工作了!我簡(jiǎn)直不能相信!

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

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

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

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

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

盡管將不再有代碼--每個(gè)人都可以取得這個(gè)簡(jiǎn)單的編譯器并且擴(kuò)充它.或者,更好,寫(xiě)一個(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:高級(jí)主題 

序言

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

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

第一個(gè):


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

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

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


函數(shù)

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

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

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

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

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

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

類(lèi)

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

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

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

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

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

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

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

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

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

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

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


Game-specific language constructs

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

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

狀態(tài)并不是非常難加入,盡管它的確需要一些工作;狀態(tài)是一個(gè)額外的類(lèi)成員(不可見(jiàn)),并且每當(dāng)調(diào)用特定的狀態(tài)函數(shù)時(shí)恰當(dāng)?shù)暮瘮?shù)版本將被執(zhí)行.這可以使用一個(gè)使用狀態(tài)號(hào)碼為索引的跳轉(zhuǎn)表來(lái)輕松實(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í)間來(lái)執(zhí)行;換句話說(shuō),這個(gè)過(guò)程可以起動(dòng)一個(gè)函數(shù)等待或者激活那個(gè)等待或者激活一個(gè)人物,當(dāng)這個(gè)動(dòng)畫(huà)完成后代碼繼續(xù)執(zhí)行.這是一個(gè)AI腳本很好的特性.

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

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

That's it for now.. 

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

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

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