手把手教你寫腳本引擎（三）——簡單的高級語言（1,基本原理）

 

陳梓瀚

華南理工大學軟件本科05級

vczh@163.com

http://m.shnenglu.com/vczh/

 

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

 

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

 

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

 

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

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

 

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

unit 單元名;

 

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

 

type

  新類型名稱=類型聲明;

  ……

 

var

  變量名組:類型;

  ……

 

interface

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

 

implementation

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

end.

 

對于語言本身來說，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ù)名。譬如我們需要一個輸入兩個整數(shù)輸出一個整數(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ù)名組可以為多個用逗號隔開的參數(shù)名，也可以僅為一個參數(shù)名。其中var代表引用參數(shù)。

 

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

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

 

語句：

一般語句：表達式、new 類型[長度]

賦值語句：變量名:=表達式

分支語句：if 布爾表達式 then 語句 [else 語句]

循環(huán)語句：

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

  while 布爾表達式 do 語句

  repeat 語句塊 while 布爾表達式

復合語句：begin 語句塊 end

命令語句：continue、break、exit

語句塊為多個“語句;”連接而成。

 

表達式：

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

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

 

既然有了這個簡單的語法規(guī)定，我們可以試著來寫一個程序。跟上一篇文章相同，我們寫一個判斷一個數(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變量僅僅用于設(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++很強大，但是其語法卻是很不利于分析的。舉個例子：

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

a<b,c>d;知道是什么嗎？逗號表達式？一個類型為某模板類的變量？

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

 

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

 

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

 

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

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

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

 

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

a="vczh";

b=a;

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

 

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

 

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

 

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

function A(x:integer):integer;

begin

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

end;

 

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

begin

  result:=x*y;

end;

 

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

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;

 

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

 

地址  內(nèi)容

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

100   5{x}

104   0{result變量}

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

112   ×××{FUNCTION_A返回的時候的地址}

 

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

 

地址  內(nèi)容

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

100   5{x}

104   0{result變量}

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

112   ×××{FUNCTION_A返回的時候的地址}

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返回的時候的地址}

116   6

120   4

124   0{新的result 變量}

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

132   07{FUNCTION_B返回的時候的地址，指向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返回的時候的地址}

116   6

120   4

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

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

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

 

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

 

地址  內(nèi)容

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

100   5{x}

104   0{result變量}

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

112   ×××{FUNCTION_A返回的時候的地址}

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

 

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

 

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