手把手教你寫腳本引擎（三）——簡(jiǎn)單的高級(jí)語言（1,基本原理）

陳梓瀚

華南理工大學(xué)軟件本科05級(jí)

vczh@163.com

http://www.shnenglu.com/vczh/

這一篇文章開始講述如何實(shí)現(xiàn)一個(gè)高級(jí)語言的腳本引擎了。由于工程量較為龐大，因此將分開幾篇文章講。學(xué)習(xí)做腳本還是要從簡(jiǎn)單的東西做起的。上一篇文章介紹的命令腳本為實(shí)現(xiàn)高級(jí)語言的原理做了鋪墊。首先，高級(jí)語言和低級(jí)語言腳本的架構(gòu)是一致的。其次，為了具有較大的優(yōu)化的空間，我們將把高級(jí)語言轉(zhuǎn)換成低級(jí)語言，并配合一個(gè)低級(jí)語言的腳本引擎來實(shí)現(xiàn)高級(jí)語言的腳本引擎。當(dāng)然，習(xí)慣上，在這種情況下我們把低級(jí)語言叫『指令』。

在這個(gè)階段，我們實(shí)現(xiàn)的這門語言是非惰性計(jì)算的、弱類型的、僅支持基本類型、數(shù)組和函數(shù)指針的語言。作為擴(kuò)展，隱式類型轉(zhuǎn)換和函數(shù)重載也將包含在這幾篇文章的主題中。好了，開始介紹語法吧。

為了免去分析C語言函數(shù)指針聲明的一堆麻煩問題，在這里我借用了pascal的語法。我們將構(gòu)造出一門非常類似pascal的語言出來。

文件結(jié)構(gòu)：

我們將實(shí)現(xiàn)的高級(jí)語言腳本是支持多文件的。腳本引擎總是需要外部函數(shù)的。為了方便的讓宿主程序提供外部函數(shù)的聲明，因此我們做成了多文件的腳本引擎。也就可以有類似C語言#include那樣子的東西了。pascal有一個(gè)奇怪的注釋規(guī)則：使用大括號(hào)注釋。

結(jié)構(gòu)如下：

unit 單元名;

uses 單元名1,單元名2,……;

type

  新類型名稱=類型聲明;

  ……

var

  變量名組:類型;

  ……

interface

  公開的函數(shù)聲明;

implementation

  公開和非公開的函數(shù)實(shí)現(xiàn)（非公開函數(shù)不需要聲明）

end.

對(duì)于語言本身來說，type和uses最好應(yīng)該屬于interface和implementation的。不過我們?yōu)榱朔奖悖们揖瓦@么做吧。不然的話，既不能揭示更多的原理，又給自己添麻煩。

類型聲明：

類型聲明有普通類型、數(shù)組類型和函數(shù)指針。

普通類型有boolean、integer、real、char和string。

數(shù)組類型的聲明方法是array of 類型。

函數(shù)指針的聲明方法跟函數(shù)聲明一致，唯一的區(qū)別是函數(shù)指針不可出現(xiàn)函數(shù)名。譬如我們需要一個(gè)輸入兩個(gè)整數(shù)輸出一個(gè)整數(shù)的函數(shù)指針，我們寫：

type MyPointer=function(a,b:integer):integer;

函數(shù)聲明：

pascal的函數(shù)根據(jù)有沒有返回值的區(qū)別使用不同的語法。基本語法如下：

procedure 函數(shù)名(參數(shù)表)和function 函數(shù)名(參數(shù)表):返回類型

參數(shù)表的語法：[var]參數(shù)名組1:類型; [var]參數(shù)名組2:類型;……[var]參數(shù)名組n:類型。其中參數(shù)名組可以為多個(gè)用逗號(hào)隔開的參數(shù)名，也可以僅為一個(gè)參數(shù)名。其中var代表引用參數(shù)。

函數(shù)實(shí)現(xiàn)：

函數(shù)實(shí)現(xiàn)的語法由函數(shù)聲明、分號(hào)、可選的變量聲明、語句、分號(hào)構(gòu)成。其中變量聲明由var開頭，后面街上多個(gè)“變量名組:類型;”構(gòu)成。

語句：

一般語句：表達(dá)式、new 類型[長(zhǎng)度]

賦值語句：變量名:=表達(dá)式

分支語句：if 布爾表達(dá)式 then 語句 [else 語句]

循環(huán)語句：

  for 變量:=值 to|downto 值 do 語句

  while 布爾表達(dá)式 do 語句

  repeat 語句塊 while 布爾表達(dá)式

復(fù)合語句：begin 語句塊 end

命令語句：continue、break、exit

語句塊為多個(gè)“語句;”連接而成。

表達(dá)式：

表達(dá)式由變量、操作符、常數(shù)以及函數(shù)調(diào)用構(gòu)成。支持的操作符有+、-、*、div、mod、/、and、or、xor、not。其中/的返回值一定是real，div用于兩個(gè)整數(shù)的整除，mod用于求余數(shù)。在這里我們修改一下pascal的語法，我們默認(rèn)字符串的下標(biāo)從0開始，而不是1。

數(shù)組和字符串可以用“表達(dá)式[下標(biāo)]”來獲得指向元素的引用。數(shù)組賦值的時(shí)候使用引用復(fù)制，字符串也使用引用復(fù)制。不過字符串修改的時(shí)候保證不影響到其他的副本，這個(gè)工作由虛擬機(jī)完成。

既然有了這個(gè)簡(jiǎn)單的語法規(guī)定，我們可以試著來寫一個(gè)程序。跟上一篇文章相同，我們寫一個(gè)判斷一個(gè)數(shù)字是否質(zhì)數(shù)的函數(shù)：

unit PrimeTest;

uses IO;{writeln和read}

interface

  function IsPrime(Num:integer):boolean;

implementation

function IsPrime(Num:integer):boolean;

var i:integer;

begin

  result:=true; {這是delphi設(shè)置返回值的方法，此處借用。exit用于退出函數(shù)，result變量?jī)H僅用于設(shè)置返回值}

  if Num<2 then

    result:=false;

  else if Num>2 then

    for i:=2 to Num-1 do

      if Num mod i=0 then

        result:=false;

end;

end.

語法的介紹就到此結(jié)束了。在這里發(fā)一下牢騷。雖然我們知道C++很強(qiáng)大，但是其語法卻是很不利于分析的。舉個(gè)例子：

A*B;知道是什么嗎？乘法？指針聲明？

a<b,c>d;知道是什么嗎？逗號(hào)表達(dá)式？一個(gè)類型為某模板類的變量？

因此，各位有志于分析C++語法的大大們注意了，傳統(tǒng)的先語法分析后語義分析的方法在C++面前基本上是一點(diǎn)用都沒有。如果你不知道上述代碼中兩個(gè)A代表著什么（類型還是對(duì)象），你就無法正確得到你想要的語法樹，那么你就慘了。所以，要分析C++，想個(gè)辦法吧語法分析和語義分析揉在一起吧。在這里我很想知道早期的gcc為什么能用yacc來搞，用yacc寫出來的C/C++編譯器的代碼肯定很難看的，雖然寫得出來。

回到我們的主題中。這個(gè)語言擁有可以遞歸調(diào)用的函數(shù)以及全局變量，我們需要準(zhǔn)備一個(gè)堆棧和一個(gè)堆才可以支撐所有的內(nèi)存操作。堆棧有很多種實(shí)現(xiàn)的方法，可以放在堆里也可以不放在堆里。這個(gè)決策將對(duì)接下去的指令集將會(huì)有一點(diǎn)小影響。

現(xiàn)在讓我們考慮一下各種類型的結(jié)構(gòu)。首先，boolean、integer、char和real都是實(shí)體類型，只需要那么一段數(shù)據(jù)就行了。在32位的機(jī)器上分別是1、4、1、8個(gè)字節(jié)。其次是函數(shù)指針。我們可以使用一個(gè)全局的ID指向一個(gè)函數(shù)，就跟我們拿函數(shù)去編號(hào)一樣，一個(gè)函數(shù)一個(gè)編號(hào)。那么，函數(shù)指針跟integer就一致了，區(qū)別在于函數(shù)指針不能計(jì)算也不能轉(zhuǎn)換類型。

接下來是字符串和數(shù)組，字符串和數(shù)組的結(jié)構(gòu)都是一致的，我們可以使用引用計(jì)數(shù)來達(dá)到垃圾收集的功能。根據(jù)類型理論我們可以知道我們剛剛設(shè)計(jì)的語言是不可能存在內(nèi)存泄漏的（如果所有的數(shù)據(jù)都只讓腳本修改）。于是，我們可以讓數(shù)組和字符串的結(jié)構(gòu)如下：

[引用計(jì)數(shù):int][數(shù)據(jù)]

當(dāng)創(chuàng)建一個(gè)數(shù)組變量的時(shí)候，我們讓數(shù)組的值為nil，讓其為空，需要使用new創(chuàng)建一個(gè)數(shù)組。new創(chuàng)建的數(shù)組的引用計(jì)數(shù)是1。如果這個(gè)數(shù)組被復(fù)制的話，那么引用計(jì)數(shù)也會(huì)隨之增大。當(dāng)引用計(jì)數(shù)為0，也就是所有的變量都不指向這個(gè)數(shù)組的時(shí)候，數(shù)組就該釋放了。而且剛剛設(shè)計(jì)的這門語言是保險(xiǎn)的，也就是說，只要我們無法訪問到這個(gè)數(shù)組，那么這個(gè)數(shù)組就一定會(huì)被釋放。至于原因就留給大家思考了。

字符串的結(jié)構(gòu)跟array of char是一致的，但是字符串有一個(gè)特殊的地方。我們將一個(gè)字符串賦值給另一個(gè)字符串的時(shí)候，兩個(gè)字符串變量其實(shí)指向相同的空間。但是我們對(duì)其中一個(gè)字符串進(jìn)行修改的時(shí)候，是不影響到另一個(gè)字符串的。我們可以在修改之前將被修改的字符串進(jìn)行復(fù)制。舉個(gè)例子：

a="vczh";

b=a;

這個(gè)時(shí)候字符串的引用計(jì)數(shù)是2。當(dāng)我們修改b（而不是對(duì)b賦值），譬如說b[0]= 'V'的時(shí)候，我們對(duì)b進(jìn)行復(fù)制。這個(gè)時(shí)候內(nèi)存中就有兩個(gè)引用計(jì)數(shù)為1而且內(nèi)容都是vczh，但是指向的空間不同的字符串了。這個(gè)時(shí)候我們對(duì)b指向的空間進(jìn)行修改的時(shí)候，a指向的空間是不變的。這種方法是經(jīng)常被使用的。

接下來我們考慮堆棧的構(gòu)造。堆棧是用來存放不支持閉包的語言的函數(shù)中的參數(shù)和變量的。對(duì)于我們剛剛說的這門語言來說，堆棧是相當(dāng)合適的數(shù)據(jù)結(jié)構(gòu)。堆棧是分段的，一個(gè)段記錄的內(nèi)容有參數(shù)、變量、臨時(shí)信息、函數(shù)參數(shù)起始位置以及函數(shù)的執(zhí)行位置。函數(shù)的執(zhí)行位置用于記錄當(dāng)前函數(shù)在調(diào)用新函數(shù)之前所執(zhí)行的指令。有了這個(gè)信息之后，我們就可以在函數(shù)返回的時(shí)候找到合適的指令繼續(xù)執(zhí)行了。

如果堆棧中存放字符串或者數(shù)組的話，在堆棧的一個(gè)段被銷毀的同時(shí)，我們需要減少相應(yīng)的字符串或數(shù)組的引用計(jì)數(shù)，并在適當(dāng)?shù)臅r(shí)候釋放他們。那么，我們?nèi)绾沃蓝褩５氖裁吹胤接涗浿裁搭愋偷淖兞磕兀恳驗(yàn)楸磉_(dá)式也會(huì)頻繁地使用堆棧的臨時(shí)空間進(jìn)行計(jì)算，因此類型信息有必要放在堆棧里面。如果不這樣做的話，我們就要在指令集里面加入各種不同的pop指令，并在函數(shù)的很多地方使用。這兩種做法各有利弊，在實(shí)現(xiàn)的時(shí)候需要衡量一下。

函數(shù)調(diào)用的時(shí)候需要大量更改堆棧的內(nèi)容。在這里我舉一個(gè)例子。已知如下代碼：

function A(x:integer):integer;

begin

  result:=B(x+1,x-1);

end;

function B(x,y:integer):integer;

begin

  result:=x*y;

end;

我們可以假想出一個(gè)編譯后的指令：

FUNCTION_A:

00  push x;

01  push 1;

02  add;

03  push x;

04  push 1;

05  sub;

06  call FUNCTION_B;

07  pushref result;

08  assign;

09  ret 1;

FUNCTION_B:

10  push x;

11  push y;

12  mul;

13  pushref result;

14  assign;

15  ret 2;

當(dāng)我們執(zhí)行A(5)的時(shí)候，堆棧如下：

地址  內(nèi)容

<以前的內(nèi)容>

100   5{x}

104   0{result變量}

108   100{FUNCTION_A參數(shù)起始地址}

112   ×××{FUNCTION_A返回的時(shí)候的地址}

好了，我們一直執(zhí)行指令，直到05（sub;）。這個(gè)時(shí)候堆棧上有了x+1和x-1兩個(gè)數(shù)：

地址  內(nèi)容

<以前的內(nèi)容>

100   5{x}

104   0{result變量}

108   100{FUNCTION_A參數(shù)起始地址}

112   ×××{FUNCTION_A返回的時(shí)候的地址}

116   6

120   4

現(xiàn)在執(zhí)行06（call FUNCTION_B;），堆棧變成這樣：

地址  內(nèi)容

<以前的內(nèi)容>

100   5{x}

104   0{result變量}

108   100{FUNCTION_A參數(shù)起始地址}

112   ×××{FUNCTION_A返回的時(shí)候的地址}

116   6

120   4

124   0{新的result 變量}

128   116{FUNCTION_B參數(shù)起始地址}

132   07{FUNCTION_B返回的時(shí)候的地址，指向pushref result;指令}

然后一直執(zhí)行，終于FUNCTION_B執(zhí)行完了，到了15（ret 2）。

地址  內(nèi)容

<以前的內(nèi)容>

100   5{x}

104   0{result變量}

108   100{FUNCTION_A參數(shù)起始地址}

112   ×××{FUNCTION_A返回的時(shí)候的地址}

116   6

120   4

124   24{新的result 變量，被更改}

128   116{FUNCTION_B參數(shù)起始地址}

132   07{FUNCTION_B返回的時(shí)候的地址，指向pushref result;指令}

于是執(zhí)行15（ret 2）。ret 2的意思是屬于FUNCTION_B的參數(shù)和變量一共有2個(gè)。虛擬機(jī)尋找有沒有字符串和數(shù)組，發(fā)現(xiàn)沒有。這時(shí)，虛擬機(jī)將132處的返回地址07拿出來，并將124處的函數(shù)返回值24保存好，最后將堆棧頂部重新指向116，并push函數(shù)返回值。這個(gè)時(shí)候堆棧如下：

地址  內(nèi)容

<以前的內(nèi)容>

100   5{x}

104   0{result變量}

108   100{FUNCTION_A參數(shù)起始地址}

112   ×××{FUNCTION_A返回的時(shí)候的地址}

116   24{函數(shù)執(zhí)行結(jié)果}

這就是一次函數(shù)調(diào)用和函數(shù)返回之后堆棧中數(shù)據(jù)的變動(dòng)了。當(dāng)然，我們可以加入新的指令以調(diào)整result變量、函數(shù)參數(shù)、起始地址以及返回地址的位置，讓call和ret指令輕松一些，效率也提高一些。不過這是后話了。事實(shí)上上述指令中ret指令的參數(shù)是需要一個(gè)函數(shù)的參數(shù)表和變量表才能正確工作的。不同的解決方案中的ret有不同的意義。

這篇文章就到此為止了。剛剛開始實(shí)習(xí)，雜七雜八的事情比較多，因此寫文章的速度會(huì)慢一些。下一批文章將講述如何對(duì)我們構(gòu)造的一門腳本語言進(jìn)行語法分析以及語義分析。語法分析和語義分析主要還是用來分析代碼并檢查語法錯(cuò)誤的，并附帶給出一個(gè)描述語言的數(shù)據(jù)結(jié)構(gòu)，用于接下來的代碼生成等問題。