用PHP实现一门新语言-HW语言（一）

简介：从今天开始，我们用PHP实现一门新的语言，HW（hello world）语言，目的就是更好的理解一门脚本语言的运行机制。本篇内容就是介绍一下这门语言的四个部分，词法分析、语法分析、生成语法树、语法树解释器，并实现这门语言的最基本的两个功能，定义变量、输出变量。下面直接开始...

一、准备工作

  1. 首先我们准备如下目录结构：
├── app/            ----- 存放HW语言文件目录
│   └── hellow.hw    ----- HW语言文件
├── index.php         ----- 入口文件
├── lexer.php        ----- 词法分析文件
├── parser.php    ----- 语法分析文件
├── eval.php    ----- 语法树解析器文件
└── test.php  ----- 测试文件
  1. 我们在hello.hw文件中写入待执行的代码
let aa = "hello world"  
echo aa

其中，第一行就是定义一个变量aa并赋值为hello world，第二行为变量的输出。

二、测试

  1. 说明：测试这一部分本可以归为准备工作，但是这种 “先写测试，再写代码” 的思想不仅可以用于本次新语言的开发，在平时的工作中也可以这样。
  2. 测试文件的写法和思想其实很简单：“列出我们期望得到的结果和实际代码返回的结果，并比较两种结果是否相等即可”。
  3. 下面开始编写测试代码：
    3-1. lexer词法分析测试：
    词法分析就是把要执行的HW的代码分割成一个个“词”，又或者叫“token”，本来hello.hw文件中的代码应该分割成：
$exp_lexer = [ 'let', 'aa', '=', 'hello world', 'echo',  'aa'];

但是经过试验证明，这样不太好做，这里我们就绕过验证过程，有兴趣你可以自己去试试。我们的解决办法就是给每一个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代表关键字（key word），var代表变量，str代表字符串，符号的类型就是它本身。目前只关心这四种，再有再加就可以了。那么词法分析期望返回的结果定义好了，再定义一个用于比较期望结果和实际结果的方法就可以了。

//$input代表待分析的源代码，$expect代表期望返回的结果
function testLexer($input, $expect) {
    //此处为伪代码，代表调用词法分析方法，tokens存放实际返回结果
    $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这两部分是紧密联系在一起的，虽然代码分别在一个class中，但是使用的时候却是parser不停的从lexer中取值，即parser从lexer中获取一个个token，然后根据token的一个或者几个组合，分析语法，并生成相应的语法树，eval再解析语法树。（如果代码先经过lexer分析生成一个个token，然后再把所有的token在parser中进行分析。。。这无论从时间还是空间上都是一个巨大的开销，这样是不对的）

三、lexer词法分析器

  1. lexer 类的原理: 输入源码，解析成一个个token。根据整体思路来说，我们只需要对外提供一个公共方法nextToken()即可，用来返回一个token给parser。
  2. 开始编码：首先，定义几个类属性和常量，用于存储特殊值，具体含义见注释
class Lexer
{
    private $input; // 输入的字符串

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

    private $char; // 当前的字符

    //关键字集合
    private $KeyWords = array(
        'let',
        'echo'
    );

    //文件结尾
    const EOF = -1;
}

同时，还需要一个构造方法，用于输入源码的存储，以及第一个字符的赋值

public function __construct(string $input)
{
    $this->input = $input;
    $this->char = $this->input[$this->pos];
}
  1. 然后，定义公共方法nextToken()，目前来说方法的具体实现我们还没有思路，但是我们知道肯定是返回一个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];
}
  1. 继续思考，我们先不考虑复杂的源码匹配，就现在的源码而言，每一行的第一个单词，（也是我们要匹配的第一个token）都为关键字，所以我们先写出匹配关键字的方法：
//匹配关键字
private function matchKw()
{
    return $KeyWord;
}

想要匹配关键字，首先需要对关键字进行分析，得出关键字的两个条件：

一、由英文字母组成；
二、在我们前面定义的关键字数组中；

条件二好判断，PHP的in_array()方法即可。
条件一需要当某个位置的字符为英文字母，并且后面连接几个字符都为英文字符时才满足。判断一个字符是否为英文字母，可以用==判断，但是这种需要用到循环判断，很明显不是一个好办法，这里我们用的是判断字符的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;
}

判断是否为关键字：

//判断是否为关键字
private function isKw($str)
{
    return in_array($str, $this->KeyWords);
}

好了，现在我们可以匹配关键字了，但是我们什么时候去匹配关键字呢，条件和时机是什么？答案是在获取token时，也就是在nextToken()方法中，当我们遇到一个字符为英文字母时：

public function nextToken(): array
{
    if ($this->isLetter()) //是否为英文字符
    {
        $word = $this->matchWord();
        if ($this->isKw($word))  //是否为关键字
        {
            return $this->makeToken('kw', $word);
        }
        else 
        {   //否则直接返回匹配内容
            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文件，开始调试我们写好的代码，看能否匹配到关键字

$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"}...

由以上输出可以看到，关键字let成功匹配并返回，但是接下来的字符空格还未做处理，这里我们可以在主方法nextToken()中添加else分支，但是细想，如果有多个空格连续呢，并且还有其他特殊字符，比如回车。。。所以，我们抽象出一个方法，用于跳过这些对我们无意义的字符

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

方法有了，但是我们把它加到哪里呢？第一个地方，每次匹配完成，返回token之前；如果这样，就会发现每个匹配的判断里都要加上这个方法；第二，放到nextToken()的最开始，这样，每次匹配只关注对应的匹配内容，其他无意义的字符，下次匹配之前就自动略过了。对比发现，还是第二种是最合适的。
于是，就有了下面的代码：

//主方法，获取下一个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"},  ......

以上内容我们可以看出，第一，变量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;
}

回到第一个问题，首先我们要明确变量的命名规则，由 _、0~9、a~z、A~Z 组成，这其中包含了关键字的组成部分 a~z ，于是我们可以把两部分合并，并抽象一个方法，匹配相应的内容，然后再判断是否为关键字，不是关键字的都归为变量：

//判断是否为变量字符
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))  //是否为关键字
    {
        return $this->makeToken('kw', $word);
    }
    else
    {   //否则直接返回匹配内容
        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：""
......

没问题，前面的部分都已经完美匹配。

下一个未匹配的字符为 " 引号，这里我们不把它跟 = 归为符号类，而是当我们遇到引号时，接下来的一系列字符为一个字符串整体，直到遇到另一个引号结束，于是我们就跟签名一样，抽象出匹配字符串方法，并且添加 nextToken() 的匹配字符串分支：

......
elseif ($this->char == '"') //""中的内容视为一个整体，字符串
{
    $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 发现 lexer test pass ，说明我们的词法分析器已经能正常工作，并且成功解析HW源码为我们想要的格式。虽然这部分代码还不完善，但是我们已经学到了词法分析的一种新思路，后面我们要做的就是不断的完善它就可以了。

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,324评论 5赞 476
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,303评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,192评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,555评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,569评论 5赞 365
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,566评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,927评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,583评论 0赞 257
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,827评论 1赞 297
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,590评论 2赞 320
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,669评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,365评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,941评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,928评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,159评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,880评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,399评论 2赞 342