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

 

陳梓瀚

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

vczh@163.com

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

 

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

 

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

 

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

 

文件結構：

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

 

結構如下：

unit 單元名;

 

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

 

type

  新類型名稱=類型聲明;

  ……

 

var

  變量名組:類型;

  ……

 

interface

  公開的函數聲明;

 

implementation

  公開和非公開的函數實現（非公開函數不需要聲明）

end.

 

對于語言本身來說，type和uses最好應該屬于interface和implementation的。不過我們為了方便，姑且就這么做吧。不然的話，既不能揭示更多的原理，又給自己添麻煩。

 

類型聲明：

類型聲明有普通類型、數組類型和函數指針。

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

數組類型的聲明方法是array of 類型。

函數指針的聲明方法跟函數聲明一致，唯一的區別是函數指針不可出現函數名。譬如我們需要一個輸入兩個整數輸出一個整數的函數指針，我們寫：

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

 

函數聲明：

pascal的函數根據有沒有返回值的區別使用不同的語法。基本語法如下：

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

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

 

函數實現：

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

 

語句：

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

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

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

循環語句：

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

  while 布爾表達式 do 語句

  repeat 語句塊 while 布爾表達式

復合語句：begin 語句塊 end

命令語句：continue、break、exit

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

 

表達式：

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

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

 

既然有了這個簡單的語法規定，我們可以試著來寫一個程序。跟上一篇文章相同，我們寫一個判斷一個數字是否質數的函數：

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設置返回值的方法，此處借用。exit用于退出函數，result變量僅僅用于設置返回值}

  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.

 

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

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

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

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

 

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

 

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

 

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

[引用計數:int][數據]

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

 

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

a="vczh";

b=a;

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

 

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

 

如果堆棧中存放字符串或者數組的話，在堆棧的一個段被銷毀的同時，我們需要減少相應的字符串或數組的引用計數，并在適當的時候釋放他們。那么，我們如何知道堆棧的什么地方記錄著什么類型的變量呢？因為表達式也會頻繁地使用堆棧的臨時空間進行計算，因此類型信息有必要放在堆棧里面。如果不這樣做的話，我們就要在指令集里面加入各種不同的pop指令，并在函數的很多地方使用。這兩種做法各有利弊，在實現的時候需要衡量一下。

 

函數調用的時候需要大量更改堆棧的內容。在這里我舉一個例子。已知如下代碼：

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;

 

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

 

地址  內容

<以前的內容>

100   5{x}

104   0{result變量}

108   100{FUNCTION_A參數起始地址}

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

 

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

 

地址  內容

<以前的內容>

100   5{x}

104   0{result變量}

108   100{FUNCTION_A參數起始地址}

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

116   6

120   4

 

現在執行06（call FUNCTION_B;），堆棧變成這樣：

 

地址  內容

<以前的內容>

100   5{x}

104   0{result變量}

108   100{FUNCTION_A參數起始地址}

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

116   6

120   4

124   0{新的result 變量}

128   116{FUNCTION_B參數起始地址}

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

 

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

 

地址  內容

<以前的內容>

100   5{x}

104   0{result變量}

108   100{FUNCTION_A參數起始地址}

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

116   6

120   4

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

128   116{FUNCTION_B參數起始地址}

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

 

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

 

地址  內容

<以前的內容>

100   5{x}

104   0{result變量}

108   100{FUNCTION_A參數起始地址}

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

116   24{函數執行結果}

 

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

 

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