由于实现一个完整的引擎相当困难且复杂,所以此项目设立了一些相对容易的目标,不过依然会涵盖大部分关键性的技术。

  • 用rust实现
  • 支持简化版的javascript语法
  • 实现优先

后续会从lexer开始逐渐实现这个目标,代码托管在:项目地址

Lexer

lexer的任务是读取源代码,将字符序列转化为"单词"序列。尽管有词法分析生成器可以自动生成分析器,不过这里选择手写实现。

首先要读取源文件,这里有两个选择,一种是直接读取整个文件,另一种是用BufReader,后者可以在读文件时避免大量的系统调用,在内存有限的情况下很有优势,在机器性能足够的情况下,可以选用直接读取整个文件的方式。 每个字符都有它所属的单词单元,比如关键字(let,var)或者字符串字面量,标识符,因此lexer中会有大量的针对单词单元的分支判断,为了判断该进入哪个分支,有时需要多向前看几个字符,称为peek方法,在处于某分支情况下,字符序列中合法的字符会被消耗,称为next方法。

每个单词单元有着自己的格式,以下是比较重要的几种

标识符

js的标识符规则为:

Identifier :: 
    IdentifierName but not ReservedWord

IdentifierName :: 
    IdentifierStart 
    IdentifierName IdentifierPart 

IdentifierStart :: 
    UnicodeLetter 
    $ 
    _ 
    \ UnicodeEscapeSequence 

IdentifierPart :: 
    IdentifierStart 
    UnicodeCombiningMark 
    UnicodeDigit 
    UnicodeConnectorPunctuation 
    \ UnicodeEscapeSequence 

UnicodeLetter 
    any character in the Unicode categories “Uppercase letter (Lu)”, “Lowercase letter (Ll)”, “Titlecase letter (Lt)”, 
    “Modifier letter (Lm)”, “Other letter (Lo)”, or “Letter number (Nl)”. 

UnicodeCombiningMark 
    any character in the Unicode categories “Non-spacing mark (Mn)” or “Combining spacing mark (Mc)” 

UnicodeDigit 
    any character in the Unicode category “Decimal number (Nd)” 

UnicodeConnectorPunctuation 
    any character in the Unicode category “Connector punctuation (Pc)” 

UnicodeEscapeSequence 
    see 7.8.4. 

HexDigit :: one of 
    0 1 2 3 4 5 6 7 8 9 a b c d e f A B C D E F

识别标识符,首先需要判断是否是合法的标识符开始符号,常规的英文字母,_,以及$可以直接通过字符串比较来判断,比较复杂的是unicode字符和序列。

unicode字符的可使用rust的unicode_xid库来判断,而unicode序列有如下两种种情况:

\u0061   // \u + 四个数字
\u{0061} // \u{ + 任意数量数字 + }

接下来需要读取十六进制数字,并转换为u32十进制,然后转为char

pub fn hex_char_to_digit (s: char) -> Result<u32, String> {
    match s {
        c @ '0'..='9' => Ok(c as u32 - '0' as u32),
        c @ 'a'..='f' => Ok(10 + (c as u32 - 'a' as u32)),
        c @ 'A'..='F' => Ok(10 + (c as u32 - 'A' as u32)),
        _ => Err("parse error".to_string()) // TODO: a custom parse error
    }
}
pub fn four_hex_to_digit() -> u32 {
    let mut v:u32 = 0;
    for i in 0..4 {
        let d = hex_char_to_digit(); // todo
        if let Ok(dv) = d {
            v = (v << 4) | dv;
        }
    }
    v
}

unicode序列的范围是0-0x10FFFF,另外0xD800-0xDFFF属于Surrogate code points被unicode保留,因此需要处理此例外情况:

// TODO: custom error
fn digit_to_char (s: u32) -> Result<char, String> {
    if s > 0x10FFFF {
        return Err("unicode overflow".to_string());
    }
    if s >= 0xd800 && s <= 0xdfff {
        return Err("surrogate code points".to_string());
    }
    return char::try_from(s).map_err(|e| String::from("invalid unicode sequence"));
}

最后通过一个通用的方法判断字符是否合法的标识符起始符


pub fn is_identifier_start (s: char) -> bool {
    if s.is_ascii() {
        return s == '_' || s == '$' || s.is_ascii_alphabetic()
    } else {
        return UnicodeXID::is_xid_start(s);
    }
}

字符串字面量

语法规则参见

分两大类情况来处理,常规字符和特殊转义字符。 常规字符直接接收即可,而转义字符分如下情况

  1. 特殊字符
\0	Null 字节
\b	退格符
\f	换页符
\n	换行符
\r	回车符
\t	Tab (制表符)
\v	垂直制表符
\'	单引号
\"	双引号
\\	反斜杠字符(\)

此类字符需单独判断,然后转成rust中的unicode code point。

  1. 八进制Latin-1 字符 最多三个八进制数字,且不能大于十进制的255。
let mut v: u32 = 0;
let mut tmp: u32 = 0;
tmp = tmp << 3 | (c as u32 - 48);
for _ in 0..2 {
    let pn = self.code.peek();
    if let Some(n) = pn {
        match n {
            '0'..='7' => {
                let to_num = n as u32 - 48;
                tmp = tmp << 3 | to_num;
                if tmp > 255 {
                    self.code.next();
                    break;
                } else {
                    v = tmp;
                }
            },
            _ => {
                break;
            }
        }
    } else {
        break;
    }
}
  1. 两位十六进制Latin-1 字符 读取两个字符,转十进制后,再转字符
let mut v: u32 = 0;
for _ in 0..2 {
    let pn = self.code.peek();
    if let Some(n) = pn {
        let dtr = hex_char_to_digit(n);
        match dtr {
            Ok(d) => {
                v = v << 4 | d;
                self.code.next();
            }
            Err(e) => {
                return Err(e);
            }
        }
    } else {
        return Err(LexerError::InvalidOctalSeq);
    }
}
let t = digit_to_char(v)?;
self.accept(t);
  1. 十六进制unicode字符和unicode code point 处理方式和标识符中的情况相似,不再赘述

parser

语法

expression 与 statement