crafting-interpreters2——scanning

interpreter

关于编译器学习的第二课，这次介绍了一个和C语言风格极其类似的LOX语言。后面我们要实现的编译器就和这个语言相关。

此外本篇还介绍了关于tree-walk interpreter中，scanner的代码原理部分。

首先文章介绍了lox语言，但是显然我们没有他的编译器。可以在线下载。我们要实现的语言是弱类型的，也就是一个变量可以存放很多种类的数据，此外，关于运行时变量处理，通常有两种方法，一个是引用计数(存在的问题是对于循环，将会很难处理变量计数问题)，另一个是GC。我们将要实现的是一个自己的GC。

变量类型

LOX语言有很简单的几种变量类型，看起来有点类似python。

  1. booleans
  2. numbers(十进制，八进制等等)
  3. strings
  4. nil (等同于null)

expression

表达式分为几种，算术表达式、比较表达式，逻辑表达式

lox语言支持加减乘除的双目算术表达式。单目以及三目表达式。

比较表达式也是支持正常的大于小于等于，不等这些。在这些比较部分中，一般不涉及隐式转换。

逻辑表达式包含and 和or，这部分和python的类似，不在说明了。

Lox语言表达式中和C不同得地方在于没有位操作。比方说bitwise move, xor等等。

闭包(closure)

这里提到了LOX语言的一个神奇的特性。热河函数可以被当作变量传递。这就会导致以下问题。

image-20220801163746371

比如上面的例子，返回的fn将会是inner()但是他要输出outside这个变量，但是它是在函数外部定义的。此时inner确实还可以访问得到这个数据。这种技术就是closure()

For that to work, inner() has to “hold on” to references to any surrounding variables that it uses so that they stay around even after the outer function has returned. We call functions that do this closures.

tree walk interpreter

前面的lox语言由于和C相关性太强，其他和C相同的地方我就没有详细写。这里直接开始写tree-walk机制。

我们首先将会用少于2000行代码的量构建一个完整的LOX编译器。首先将会介绍的是scanning，parsing和evaluating code。

框架

首先编写一个编译器框架，如下所示。简单来说就是一个runFile(通过文件输入)，另一个runPrompt(通过命令行交互输入)。另外还有一个报错退出的标志。

1
2
3
4
5
6
7
8
9
10
11
12
public class jlox {
	  public static void main(String[] args) throws IOException {
		    if (args.length > 1) {
		      System.out.println("Usage: jlox [script]");
		      System.exit(64); 
		    } else if (args.length == 1) {
		      runFile(args[0]);
		    } else {
		      runPrompt();
		    }
		  }
}

接下来编写runFiel和runPrompt，对于runFile，主要的功能就是通过字节读取的方式阅读文件，之后调用run()。对于run()我们目前没有添加新的内容，仅仅是打印出字节码。(当然还要使用到后面的scanner库和token库)。对于runPrompt，主要功能是接受从命令行输入的每一行的内容，并调用run()。

错误处理

错误处理的原则是：产生错误的地方和汇报错误的地方要尽量分开。因此lox语言在run()中放置了错误处理函数。如下

1
2
3
4
5
6
7
8
private static void runFile(String path) throws IOException {

    byte[] bytes = Files.readAllBytes(Paths.get(path));
    run(new String(bytes, Charset.defaultCharset()));
	// Indicate an error in the exit code.
    if (hadError) System.exit(65);
  }

词法分析\定位

词法分析就是把当前的语句拆分成

1
var language = "lox";

image-20220804111114669

拆分得到的一个一个小小块，称作token。token服务于parser，一般来说token中需要规定一些限定词，比如说class，public等。由此我们定义了一个常量表。

关于定位，就是当我们做词法分析时，将一行字拆分开来，分成type，lexeme，literal等部分。之后最有用的地方是报错分析时可以使用。

token的结构体为

1
2
3
4
5
6
Token(TokenType type, String lexeme, Object literal, int line) {
    this.type = type; //比方说string，变量类型
    this.lexeme = lexeme; // 直接substr()下的数值
    this.literal = literal; // 字面数值,对于字符串，就是去掉引号的部分
    this.line = line;
}

处理语言和表达式

scanner负责处理我们输入的字符串。他从我们输入的第一个byte开始处理，分析每一个字符隶属于哪一个lexeme，并一直处理到文件末尾。

比方说对于变量名称，我们是通过一种lexical grammar进行分析的，这种语言很像正则表达式。

我们首先构建scanner，其源代码如下。我们建立一个list用来存放所有的token，并且后续scanner的工作就是把输入的字符串语句解析成token放在这个list中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Scanner {
	  private final String source;
	  private final List<Token> tokens = new ArrayList<>();

	  Scanner(String source) {
	    this.source = source;
	  }
    
    // 不停进行扫描
    List<Token> scanTokens() {
    while (!isAtEnd()) {
      // We are at the beginning of the next lexeme.
      start = current;
      scanToken();
    }

    tokens.add(new Token(EOF, "", null, line));
    return tokens;
  }
}

接下来我们开始识别词法。首先对于加减乘除等表达式，我们可以直接用seitch:case的方法匹配。首先取出下一个字符，之后与后面的字符匹配，并向token列表中加入对应的内容(token名称，行数)即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private void scanToken() {
  char c = advance();
  switch (c) {
    case '(': addToken(LEFT_PAREN); break;
    case ')': addToken(RIGHT_PAREN); break;
    case '{': addToken(LEFT_BRACE); break;
    case '}': addToken(RIGHT_BRACE); break;
    case ',': addToken(COMMA); break;
    case '.': addToken(DOT); break;
    case '-': addToken(MINUS); break;
    case '+': addToken(PLUS); break;
    case ';': addToken(SEMICOLON); break;
    case '*': addToken(STAR); break; 
  }
}

接下来我们还要处理由两个符号构成的运算符，例如==，!=之类的。我们只需要在扫描到对应符号之后再扫描一位就能确定了。

1
2
3
4
5
6
7
8
9
10
11
12
case '!':
addToken(match('=') ? BANG_EQUAL : BANG);
break;
case '=':
addToken(match('=') ? EQUAL_EQUAL : EQUAL);
break;
case '<':
addToken(match('=') ? LESS_EQUAL : LESS);
break;
case '>':
addToken(match('=') ? GREATER_EQUAL : GREATER);
break;

接下来还要处理一个特殊的符号，也就是除号。因为lox中，注释也是两条斜线构成的。基本思路很简单，如果找到两条斜线，就从这里到一行的结尾，我们都不需要管理，跳过即可。但是如果斜杠后面没有斜杠，就说明是除法。

1
2
3
4
5
6
7
8
case '/':
if (match('/')) {
    // A comment goes until the end of the line.
    while (peek() != '\n' && !isAtEnd()) advance();
} else {
    addToken(SLASH);
}
break;

除此以外，我们还可能碰到空格，换行符等等。这些我们直接简单跳过，或者跳过之后，对于line变量进行增加即可。

处理数字和字符串

处理字符串

通过识别双引号，可以提取字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private void string() {
    while (peek() != '"' && !isAtEnd()) {
        if (peek() == '\n') line++;
        advance();
    }

    if (isAtEnd()) {
        jlox.error(line, "Unterminated string.");
        return;
    }

    // The closing ".
    advance();

    // Trim the surrounding quotes.
    String value = source.substring(start + 1, current - 1);
    addToken(STRING, value);
}

同理，在switch case中加上双引号的判断，并指向这里的string()函数，就能提取出一个string，并将其作为token加到token列表中。

处理数字

对于数字而言，我们只是识别是不是数字开头，一直到最后一个数字结尾。中间包含的小数点当然也会被提取。但是注意我们这种方法对于负数而言无能为力。我们只能把负数识别为一个表达式，并且把数字单独提取出来。

首先是识别数字

1
2
3
4
5
6
if (isDigit(c)) {
    number();
} else {
    jlox.error(line, "Unexpected character.");
}
break;

其中isDigit()具体内容为

1
2
3
private boolean isDigit(char c) {
    return c >= '0' && c <= '9';
}

而number()主要目的就是提取出来数字，并把他放到token list中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private void number() {
    while (isDigit(peek())) advance();

    // Look for a fractional part.
    if (peek() == '.' && isDigit(peekNext())) {
        // Consume the "."
        advance();

        while (isDigit(peek())) advance();
    }

    addToken(NUMBER,
             Double.parseDouble(source.substring(start, current)));
}

其实这里可以看到还是用到了java中对于数字进制转换的库。

保留字符

对于保留字符，我们肯定要用完全匹配的方法来确定(或者说是最长匹配)。一个例子就是对于—a的解释。如果采用较长匹配，得到的结果是– (-a)。

我们首先在switch case部分做以下判断

1
2
else if (isAlpha(c)) {
          identifier();

也就是如果识别到一个字符，就调用identifier()。

实现如下，也就是一直获取字符直到字符的结尾。并添加一个token，类别是identidier。

1
2
3
4
5
6
7
8
private void identifier() {
    while (isAlphaNumeric(peek())) advance();

    String text = source.substring(start, current);
    TokenType type = keywords.get(text);
    if (type == null) type = IDENTIFIER;
    addToken(type);
}

其中isAlphaNumeric就是判断下一个字符是不是数字或者大小写字母。之后我们去逐个匹配这个字符单词是不是我们的保留字符。如果不是九将其type设置为IDENTIFIER，否则添加相应的type即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private static final Map<String, TokenType> keywords;

static {
  keywords = new HashMap<>();
  keywords.put("and",    AND);
  keywords.put("class",  CLASS);
  keywords.put("else",   ELSE);
  keywords.put("false",  FALSE);
  keywords.put("for",    FOR);
  keywords.put("fun",    FUN);
  keywords.put("if",     IF);
  keywords.put("nil",    NIL);
  keywords.put("or",     OR);
  keywords.put("print",  PRINT);
  keywords.put("return", RETURN);
  keywords.put("super",  SUPER);
  keywords.put("this",   THIS);
  keywords.put("true",   TRUE);
  keywords.put("var",    VAR);
  keywords.put("while",  WHILE);
}

这样就基本完成了我们对输入一行内容的词法分析，分类。

image-20220804145726428

总结

总结一下这一部分内容：我们把得到的输入按照每行进行处理，分为几种类别

  1. 运算符，特征为直接switch case识别
  2. 字符串，特征为” “
  3. 数字，特征为数字开头，数字结尾
  4. 保留字符，特征为直接使用hashmap匹配

每一种识别到的内容，都将他们放入一个向量中，向量里面有四种数据类型

1
2
3
4
5
6
Token(TokenType type, String lexeme, Object literal, int line) {
    this.type = type; //比方说string，变量类型
    this.lexeme = lexeme; // 直接substr()下的数值
    this.literal = literal; // 字面数值,对于字符串，就是去掉引号的部分
    this.line = line;
}

到此完成了scanning和lox基本语法的介绍

本文标题:crafting-interpreters2——scanning

文章作者:

发布时间:2022-08-04, 15:59:21

最后更新:2022-08-04, 15:03:24

原始链接:https://nicholas-wei.github.io/2022/08/04/crafting-interpreters2/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 变量类型
  2. 2. expression
  3. 3. 闭包(closure)
  4. 4. tree walk interpreter
    1. 4.1. 框架
    2. 4.2. 错误处理
    3. 4.3. 词法分析\定位
    4. 4.4. 处理语言和表达式
    5. 4.5. 处理数字和字符串
      1. 4.5.1. 处理字符串
      2. 4.5.2. 处理数字
    6. 4.6. 保留字符
  5. 5. 总结
|