用PHP實現(xiàn)一門新語言-HW語言（一）

簡介：從今天開始，我們用PHP實現(xiàn)一門新的語言抵碟，HW（hello world）語言虫埂，目的就是更好的理解一門腳本語言的運行機制。本篇內(nèi)容就是介紹一下這門語言的四個部分葱蝗，詞法分析穴张、語法分析、生成語法樹垒玲、語法樹解釋器陆馁，并實現(xiàn)這門語言的最基本的兩個功能，定義變量合愈、輸出變量叮贩。下面直接開始...

一、準備工作

首先我們準備如下目錄結(jié)構(gòu)：

├── app/            ----- 存放HW語言文件目錄
│   └── hellow.hw    ----- HW語言文件
├── index.php         ----- 入口文件
├── lexer.php        ----- 詞法分析文件
├── parser.php    ----- 語法分析文件
├── eval.php    ----- 語法樹解析器文件
└── test.php  ----- 測試文件

我們在hello.hw文件中寫入待執(zhí)行的代碼

let aa = "hello world"  
echo aa

其中佛析，第一行就是定義一個變量aa并賦值為hello world益老，第二行為變量的輸出。

二寸莫、測試

說明：測試這一部分本可以歸為準備工作捺萌，但是這種 “先寫測試，再寫代碼” 的思想不僅可以用于本次新語言的開發(fā)膘茎，在平時的工作中也可以這樣桃纯。
測試文件的寫法和思想其實很簡單：“列出我們期望得到的結(jié)果和實際代碼返回的結(jié)果，并比較兩種結(jié)果是否相等即可”披坏。
下面開始編寫測試代碼：
3-1. lexer詞法分析測試：
詞法分析就是把要執(zhí)行的HW的代碼分割成一個個“詞”态坦，又或者叫“token”，本來hello.hw文件中的代碼應該分割成：

$exp_lexer = [ 'let', 'aa', '=', 'hello world', 'echo',  'aa'];

但是經(jīng)過試驗證明棒拂，這樣不太好做伞梯，這里我們就繞過驗證過程，有興趣你可以自己去試試帚屉。我們的解決辦法就是給每一個token加上類型谜诫，這樣操作起來就容易的多了，就像下面這樣:

$exp_lexer = [
    ['type' => 'kw', 'literal' => 'let'],
    ['type' => 'var', 'literal' => 'aa'],
    ['type' => '=', 'literal' => '='],
    ['type' => 'str', 'literal' => 'hello world'],
    ['type' => 'kw', 'literal' => 'echo'],
    ['type' => 'var', 'literal' => 'aa']
];

其中攻旦，kw代表關(guān)鍵字（key word）喻旷，var代表變量，str代表字符串牢屋，符號的類型就是它本身且预。目前只關(guān)心這四種牺陶，再有再加就可以了。那么詞法分析期望返回的結(jié)果定義好了辣之，再定義一個用于比較期望結(jié)果和實際結(jié)果的方法就可以了掰伸。

//$input代表待分析的源代碼，$expect代表期望返回的結(jié)果
function testLexer($input, $expect) {
    //此處為偽代碼怀估，代表調(diào)用詞法分析方法狮鸭，tokens存放實際返回結(jié)果
    $tokens = lexer($input);
    if ($tokens != $expect) {
        echo "expect token is:";
        echo json_encode($expect);
        echo "<br>";
        echo "givens token is:";
        echo json_encode($tokens);
        exit();
    }

    print "lexer test pass \n";
}

整體思路：

下面是最主要的三部分，分別為一個類class多搀，這樣使得代碼比較清晰歧蕉，而且減少代碼的冗余。但是要注意的是lexer和parser這兩部分是緊密聯(lián)系在一起的康铭，雖然代碼分別在一個class中惯退，但是使用的時候卻是parser不停的從lexer中取值，即parser從lexer中獲取一個個token从藤，然后根據(jù)token的一個或者幾個組合催跪，分析語法，并生成相應的語法樹夷野，eval再解析語法樹懊蒸。（如果代碼先經(jīng)過lexer分析生成一個個token，然后再把所有的token在parser中進行分析悯搔。骑丸。。這無論從時間還是空間上都是一個巨大的開銷妒貌，這樣是不對的）

三通危、lexer詞法分析器

lexer 類的原理: 輸入源碼，解析成一個個token灌曙。根據(jù)整體思路來說菊碟，我們只需要對外提供一個公共方法nextToken()即可，用來返回一個token給parser平匈。
開始編碼：首先框沟，定義幾個類屬性和常量藏古，用于存儲特殊值增炭，具體含義見注釋

class Lexer
{
    private $input; // 輸入的字符串

    private $pos = 0;  // 當前字符的位置

    private $char; // 當前的字符

    //關(guān)鍵字集合
    private $KeyWords = array(
        'let',
        'echo'
    );

    //文件結(jié)尾
    const EOF = -1;
}

同時，還需要一個構(gòu)造方法拧晕，用于輸入源碼的存儲隙姿，以及第一個字符的賦值

public function __construct(string $input)
{
    $this->input = $input;
    $this->char = $this->input[$this->pos];
}

然后，定義公共方法nextToken()厂捞，目前來說方法的具體實現(xiàn)我們還沒有思路输玷，但是我們知道肯定是返回一個token队丝，而且token有類型，有具體的值欲鹏，那么我們就先寫個最簡單的出來：

//主方法机久，獲取下一個token的值
public function nextToken(): array
{
    return $this->makeToken($this->char, $this->char);
}

//生成token
private function makeToken($type, $literal): array
{
    //其中type為token的類型，literal為token的值
    return ['type' => $type, 'literal' => $literal];
}

繼續(xù)思考赔嚎，我們先不考慮復雜的源碼匹配膘盖，就現(xiàn)在的源碼而言，每一行的第一個單詞尤误，（也是我們要匹配的第一個token）都為關(guān)鍵字侠畔，所以我們先寫出匹配關(guān)鍵字的方法：

//匹配關(guān)鍵字
private function matchKw()
{
    return $KeyWord;
}

想要匹配關(guān)鍵字，首先需要對關(guān)鍵字進行分析损晤，得出關(guān)鍵字的兩個條件：

一软棺、由英文字母組成；
二尤勋、在我們前面定義的關(guān)鍵字數(shù)組中喘落；

條件二好判斷，PHP的in_array()方法即可最冰。
條件一需要當某個位置的字符為英文字母揖盘，并且后面連接幾個字符都為英文字符時才滿足。判斷一個字符是否為英文字母锌奴，可以用==判斷兽狭，但是這種需要用到循環(huán)判斷，很明顯不是一個好辦法鹿蜀，這里我們用的是判斷字符的ASCII碼值的方法箕慧，看該字符的ASCII碼值是否大于等于字符a的ASCII碼值，并且小于等于z的ASCII碼值：

//判斷字符是否為英文字母a~z
private function isLetter()
{
    $ord = ord($this->char);

    if ($ord >= 97 && $ord <= 122)//a~z
    {
        return true;
    }

    return false;
}

以上是判斷單個字符是否為英文字符茴恰，但是匹配英文字符串還需要不停的讀取并判斷下一個字符颠焦，直到遇到不是英文字母的字符為止，于是：

//匹配單詞
private function matchWord(): string
{
    $word = '';

    while ($this->isLetter())
    {
        $word .= $this->char;
        $this->readChar();
    }

    return $word;
}

//因為讀取下一個字符會有很多地方用到往枣，所以抽象為一個方法

//讀取下一個字符
private function readChar()
{
    $this->char = $this->input[$this->pos++] ?? self::EOF;
}

判斷是否為關(guān)鍵字：

//判斷是否為關(guān)鍵字
private function isKw($str)
{
    return in_array($str, $this->KeyWords);
}

好了伐庭，現(xiàn)在我們可以匹配關(guān)鍵字了，但是我們什么時候去匹配關(guān)鍵字呢分冈，條件和時機是什么圾另？答案是在獲取token時，也就是在nextToken()方法中雕沉，當我們遇到一個字符為英文字母時：

public function nextToken(): array
{
    if ($this->isLetter()) //是否為英文字符
    {
        $word = $this->matchWord();
        if ($this->isKw($word))  //是否為關(guān)鍵字
        {
            return $this->makeToken('kw', $word);
        }
        else 
        {   //否則直接返回匹配內(nèi)容
            return $this->makeToken($word, $word);
        }
    }
    elseif ($this->char == self::EOF)
    {
        return $this->makeToken('eof', 'EOF');
    }

    var_dump('unknown char：' . $this->char);
    return $this->makeToken('eof', 'EOF');
}

此時集乔，我們修改test.php文件，開始調(diào)試我們寫好的代碼坡椒，看能否匹配到關(guān)鍵字

$json = file_get_contents("hw/hello.hw");
testLexer($json, $exp_lexer);
function testLexer($input, $expect) {
    $lexer = new Lexer($input);
    $tokens = [];

    while (($tok = $lexer->nextToken())['type'] != 'eof') {
        $tokens[] = $tok;
    }
    ...
}

切換到test.php文件所在目錄扰路，命令行運行 php test.php

array(2) {
  ["type"]=>
  string(2) "kw"
  ["literal"]=>
  string(3) "let"
}
string(16) "unknown char： "
expect token is:[{"type":"kw","literal":"let"},{"type":"var","literal":"aa"}...

由以上輸出可以看到尤溜，關(guān)鍵字let成功匹配并返回，但是接下來的字符空格還未做處理汗唱，這里我們可以在主方法nextToken()中添加else分支宫莱，但是細想，如果有多個空格連續(xù)呢哩罪，并且還有其他特殊字符梢睛，比如回車。识椰。绝葡。所以，我們抽象出一個方法腹鹉，用于跳過這些對我們無意義的字符

//跳過空白符
private function skipBlank()
{
    while ( ord($this->char) == 10 || //換行
            ord($this->char) == 13 || //回車
            ord($this->char) == 32 )  //空格
    {
        $this->readChar();
    }
}

方法有了藏畅，但是我們把它加到哪里呢？第一個地方功咒，每次匹配完成愉阎，返回token之前；如果這樣力奋，就會發(fā)現(xiàn)每個匹配的判斷里都要加上這個方法榜旦；第二，放到nextToken()的最開始景殷，這樣溅呢，每次匹配只關(guān)注對應的匹配內(nèi)容，其他無意義的字符猿挚，下次匹配之前就自動略過了咐旧。對比發(fā)現(xiàn)，還是第二種是最合適的绩蜻。
于是铣墨，就有了下面的代碼：

//主方法，獲取下一個token的值
public function nextToken(): array
{
    //跳過空白符
    $this->skipBlank();
    ......
}

再次運行test.php

array(2) {
  ["type"]=>
  string(2) "kw"
  ["literal"]=>
  string(3) "let"
}
array(2) {
  ["type"]=>
  string(2) "aa"
  ["literal"]=>
  string(2) "aa"
}
string(16) "unknown char：="
expect token is:[{"type":"kw","literal":"let"},  ......

以上內(nèi)容我們可以看出办绝，第一伊约，變量aa沒有還有處理為對應的token類型；第二孕蝉，=等號沒有做相應的匹配屡律。第二個問題相對容易解決，因為符號種類有限昔驱，而且我們不需要對符號加特殊的token類型疹尾，所以上忍，直接抽象出一個匹配符號的方法即可：

private function isSymbol($c='')
{
    $c = $c?:$this->c;
    if ($c == '=' ||
        $c == '+' ||
        $c == '-' ||
        $c == '*' ||
        $c == '/' ||
        $c == '>' ||
        $c == '<' ||
        $c == '!' ||
        $c == '(' ||
        $c == ')' ||
        $c == ',' ||
        $c == '{' ||
        $c == '}' 
    )
    {
        return true;
    }

    return false;
}

//然后完善nextToken()骤肛，加上對應的分支
elseif ($this->isSymbol()) {
    $symbol = $this->char;
    $token = $this->makeToken($symbol, $symbol);
    $this->readChar();
    return $token;
}

回到第一個問題纳本，首先我們要明確變量的命名規(guī)則，由 _腋颠、0~9繁成、a~z、A~Z 組成淑玫，這其中包含了關(guān)鍵字的組成部分 a~z 巾腕，于是我們可以把兩部分合并，并抽象一個方法絮蒿，匹配相應的內(nèi)容尊搬，然后再判斷是否為關(guān)鍵字，不是關(guān)鍵字的都歸為變量：

//判斷是否為變量字符
private function isVarChar($c='')
{
    $c = $c?:$this->char;
    $ord = ord($c);
    if ( $ord == 95 || //_
        ($ord >= 48 && $ord <=57) || //0~9
        ($ord >= 65 && $ord <= 90) || //A~Z
        ($ord >= 97 && $ord <= 122) )  //a~z
    {
        return true;
    }

    return false;
}

//nextToken()分支
if ($this->isVarChar()) //是否為變量字符
{
    $word = $this->matchVariable();
    if ($this->isKw($word))  //是否為關(guān)鍵字
    {
        return $this->makeToken('kw', $word);
    }
    else
    {   //否則直接返回匹配內(nèi)容
        return $this->makeToken('var', $word);
    }
}

//匹配變量名
private function matchVariable($str=''): string
{
    $str = $str?:'';
    while ($this->isVarChar())
    {
        $str .= $this->char;
        $this->readChar();
    }

    return $str;
}

再次運行 test.php

array(2) {
  ["type"]=>
  string(2) "kw"
  ["literal"]=>
  string(3) "let"
}
array(2) {
  ["type"]=>
  string(3) "var"
  ["literal"]=>
  string(2) "aa"
}
array(2) {
  ["type"]=>
  string(1) "="
  ["literal"]=>
  string(1) "="
}

string(16) "unknown char：""
......

沒問題土涝，前面的部分都已經(jīng)完美匹配佛寿。

下一個未匹配的字符為 " 引號，這里我們不把它跟 = 歸為符號類但壮，而是當我們遇到引號時冀泻，接下來的一系列字符為一個字符串整體，直到遇到另一個引號結(jié)束蜡饵，于是我們就跟簽名一樣弹渔，抽象出匹配字符串方法，并且添加 nextToken() 的匹配字符串分支：

......
elseif ($this->char == '"') //""中的內(nèi)容視為一個整體溯祸，字符串
{
    $this->readChar();
    $str = $this->matchStr();
    $token = $this->makeToken('str', $str);
    $this->readChar();
    return $token;
}
......

//匹配字符串
private function matchStr(): string
{
    $str = '';
    while ($this->char != '"' && $this->char != self::EOF) {
        $str .= $this->char;
        $this->readChar();
    }
    return $str;
}

再次運行 test.php 發(fā)現(xiàn) lexer test pass 肢专，說明我們的詞法分析器已經(jīng)能正常工作，并且成功解析HW源碼為我們想要的格式焦辅。雖然這部分代碼還不完善鸟召，但是我們已經(jīng)學到了詞法分析的一種新思路，后面我們要做的就是不斷的完善它就可以了氨鹏。