《两周自制脚本语言》—— 第三天（分割单词）

笔记、源码同步在 github 上，欢迎 Star，蟹蟹～

---

语言处理器的第一个组成部分是词法分析器（lexer）。程序的源代码最初只是一长串字符串，这样的字符串很难处理，语言处理器通常会首先将字符串中的字符以单词为单位分组，切割成多个子字符串。这就是词法分析

Token 对象展开目录

下面是某个程序中的一行代码

while i < 10 {

词法分析会把它拆分为下面这样的字符串

"while" "i" "<" "10" "{"

这句代码被分割为了 5 个字符串。通常把词法分析的结果称为单词（token）

词法分析将筛选出程序的解释与执行必须的成分。单词之间的空白或注释都会在这一阶段被去除，例如

i = i + 1 // increment
i=i+1

这两行代码词法分析的结果相同，都是下面 5 个单词：

"i" "=" "i" "+" "1"

经过词法分析之后，程序员便无需再处理代码的注释，也不用考虑单词之间是否含有空白符。

分割后得到的单词是用代码清单 3.1 中的 Token 对象表示，这种对象除了记录该单词对应的字符串，还会保存单词的类型、单词所处位置的行号等信息

Stone 语言含有标识符、整型字面量和字符串字面量这三种类型的单词，每种单词都定义了对应的 Token 类的子类。每种子类都覆盖了 Token 类的 isIdentifier（如果是标识符则为真）、isNumber（如果是整型字面量则为真）及 isString（如果是字符串字面量则为真）方法，并根据具体类型返回相应的值

此外，Stone 语言还定义了一个特别的单词 Token.EOF（end of file），用于表示程序结束。类似的还有 Token.EOL（end of line），用于表示换行符

代码清单 3.1 Token.java

package Stone;

public abstract class Token { // abstract class
    public static final Token EOF = new Token(-1) {}; // end of file
    public static final String EOL = "\\n";           // end of line
    private int lineNumber;                           // token number

    protected Token(int line) {
        lineNumber = line;
    }

    public int getLineNumber() {
        return lineNumber;
    }

    public boolean isIdentifier() {
        return false;
    }

    public boolean isNumber() {
        return false;
    }

    public boolean isString() {
        return false;
    }

    public int getNumber() {
        throw new StoneException("not number token");
    }

    public String getText() {
        return "";
    }
}

代码清单 3.2 StoneException.java

package Stone;

import Stone.ast.ASTree;

public class StoneException extends RuntimeException {
    public StoneException(String m) {
        super(m);
    }

    public StoneException(String m, ASTree t) { // Overload function
        super(m + " " + t.location);
    }
}

标识符（identifier）展开目录

标识符指的是变量名、函数名或类名等名称。此外，+ 或 - 等运算符及括号也属于标识符。标点符号与保留字也都作为标识符处理。（很重要）

整型字面量（integer literal）展开目录

读者可能会把它与程序执行过程中赋值给变量的整数值混同，因此这里使用整型字面量的名称，用于指代整数值的字符序列。

例如，Java 语言就支持 0x1f 这样的 16 进制数表示。这种 4 个字符组成的字符串也是整型字面量。用一个整数值来表示的话，即 31。

字符串字面量（String literal）展开目录

字符串字面量（string literal) 是一串用于表示字符串的字符序列。与 Java
等语言一样，被双引号（"）括起来的字符序列就是一个字符串字面量。例如，字符串字面量 "Java" 表示的就是字符串值 Java

双引号之间可以使用 \n、\" 与 \\ 这三种类型的转义字符。它们分别表示换行符、双引号符和反斜杠

通过正则表达式定义单词展开目录

借助正则表达式库能简单地实现词法分析器。下表列出的记号在大多数情况下都能使用。例如，.*\.java 指的是以.java 结束的任意长度的字符串模式。.*\. 由两部分组成，.* 表示由任意字符组成的任意长度的字符串模式，\. 表示与句点字符相匹配的字符串模式。(java|javax)\..* 则表示由 java. 或 javax. 起始的任意长度的字符串模式

表 3.1 正则表达式的元字符

首先来定义整型字面量

[0-9]+

然后定义标识符

[A-Z_a-z][A-Z_a-z0-9]*

以字母、下划线开头，之后仅包含有字母、数字、下划线的就是标识符的定义规则

前面我们说 Stone 语言的标识符包括各类符号，因此下面才是真正完整的正则表达式

[A-Z_a-z][A-Z_a-z0-9]*|==|<=|>=|&&|\|\||\p{Punct}

最后的 \p{Punct} 表示与任意一个符号字符匹配。模式 \|\| 将会匹配 ||。由于 | 是正则表达式的元字符，因此在使用时必须添加反斜线转义

最后需要定义的是字符串字面量。由于不得不处理各种转义字符，字符串字面量的定义略微复杂

"(\\"|\\\\|\\n|[^"])*"

首先，从整体上看，这是一个 "(pat)*" 形式的模式，即双引号内是一个与 pat 重复出现至少 0 次的结果匹配的字符串。其中，模式 pat 与 \"、\\、\n 匹配，同时也与除 " 之外任意一个字符匹配

借助 java.util.regex 设计词法分析器展开目录

例如，下面的字符串

https://wmathor.com/

与正则表达式

http://(.+)/

匹配。Java 语言能够获取与括号中的模式匹配的字符串 wmathor.com。如果模式包含多个括号，各个括号内的子字符串都能被分别取得。

每一对左右括号都对应了与其包围的模式相匹配的字符串。要利用这一功能设计词法分析器，首先要准备一个下面这样的正则表达式

\s*((//.*)|(pat1)|(pat2)|pat3)?

其中，pat1 是与整型字面量匹配的正则表达式，pat2 与字符串字面量匹配，pat3 与标识符匹配。起始的 \s 与空字符匹配，\s* 与 0 个或以上的空字符匹配。模式 //.* 匹配由 // 开始的任意长度的字符串，用于匹配注释。于是，上述正则表达式能匹配任意个空白字符及连在其后的注释、整型字面量、字符串字面量或标识符。又因它以 ? 结尾，所以仅由任意多个空白符组成的字符串也能与该模式匹配

执行词法分析时，语言处理器会逐行读取源代码，从各行开头起检查内容是否与该正则表达式匹配，并在检查完后获取与正则表达式括号内的模式相匹配的字符串

如果匹配的字符串是一句注释，则对应于左起第 2 个左括号，从第三个左括号起对应的都是 null。如果匹配的字符串是一个整型字面量，则对应左起第 3 个左括号，第 2 个和第 4 个左括号与 null 对应......

只要像这样检查一下哪一个括号对应的不是 null，就能知道行首出现的是哪种类型的单词。之后再继续用正则表达式匹配剩余部分，就能得到下一个单词。不断重复该过程，词法分析器就能获得由源代码分割而得的所有单词

代码清单 3.3 与代码清单 3.4 是一个实际的词法分析程序。Lexer 类就是一个词法分析器。Lexer 对象的构造函数接受一个 java.io.Reader 对象，它能根据需要逐行读取源代码

Java 语言的字符串字面量中，反斜杠与双引号必须分别以 \\ 与 \" 的形式转义。因此，字符串中将包含大量的反斜杠

read 与 peek 是 Lexer 中主要的两个方法。read 方法可以从源代码头部开始逐一获取单词。read 方法返回的是一个新的单词

peek 方法则用于预读。peek (i) 将返回 read 方法即将返回的单词之后的第 i 个单词。通过 peek 方法，词法分析器就能事先知道在调用 read 方法时将获得什么单词

如果所有单词都已读取，read 方法和 peek 方法都将返回 Token.EOF。这是一个特殊的 Token 对象，用于表示程序结束

在词法分析后需要执行的是语法分析。语法分析将一边获取单词一边构造抽象语法树，在中途发现构造有误时，需要退回若干个单词，重新构造语法树，为了支持这种操作，语言处理器必须要能够取消之前的几次 read 方法调用，并还原先前的结果，不过这样执行效率会受到影响，因此这里准备了 peek 方法

peek 方法可以实现获知之后将会取得的单词，以此避免撤销抽象语法树的构造。当遇到分支路线时，不是先随意选取一条，行不通再原路返回改走另一条，而是险费一番周折，判断前路是否正确，在确信没有问题时才真正继续

要使用 peek 方法，词法分析器需要在读取代码并获取单词后，将这些单词暂时保存在一个名为 queue 的 ArrayList 中。之后 peek 与 read 方法会根据需要从中取值并返回。由 read 方法读取的单词会从 queue 中删除

readLine 方法是实际从每一行中读取单词的方法。由于正则表达式已经实现编译为 Pattern 对象，因此能调用 matcher 方法来获得一个用于实际检查匹配的 Matcher 对象。词法分析器一边通过 region 方法限定该对象检查匹配的范围，以便通过 lookingAt 方法在检查范围内进行正则表达式匹配。之后，词法分析器将使用 group 方法来获取与各个括号对应的子字符串。end 方法用于取得匹配部分的结束位置，词法分析器将从那里开始继续执行下一次 lookingAt 方法调用

代码清单 3.3 最后的 NumToken、IdToken、StrToken 类是 Token 类的子类。他们分别对应不同类型的单词

代码清单 3.3 词法分析器 Lexer.java

package Stone;
import java.io.IOException;
import java.io.LineNumberReader;
import java.io.Reader;
import java.util.ArrayList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Lexer {
    public static String regexPat
    = "\\s*((//.*)|([0-9]+)|(\"(\\\\\"|\\\\\\\\|\\\\n|[^\"])*\")"
      + "|[A-Z_a-z][A-Z_a-z0-9]*|==|<=|>=|&&|\\|\\||\\p{Punct})?";
    private Pattern pattern = Pattern.compile(regexPat);
    private ArrayList<Token> queue = new ArrayList<Token>();
    private boolean hasMore; // Mark if there are still characters
    private LineNumberReader reader; // Tracking character input stream for tracking line numbers

    public Lexer(Reader r) { // Pass in a Reader object
        hasMore = true;
        reader = new LineNumberReader(r);
    }

    public Token read() throws ParseException {
        if (fillQueue(0))
            return queue.remove(0);
        return Token.EOF;
    }

    public Token peek(int i) throws ParseException {
        if (fillQueue(i))
            return queue.get(i);
        else
            return Token.EOF;
    }

    private boolean fillQueue(int i) throws ParseException {
        while (i >= queue.size())
            if (hasMore)
                readLine();
            else
                return false;
        return true;
    }

    protected void readLine() throws ParseException {
        String line;
        try {
            line = reader.readLine();
        } catch (IOException e) {
            throw new ParseException(e);
        }
        if (line == null) {
            hasMore = false;
            return;
        }
        int lineNo = reader.getLineNumber(); // Get the current line number
        Matcher matcher = pattern.matcher(line);
        matcher.useTransparentBounds(true).useAnchoringBounds(false); // About this code you can view the API
        int pos = 0;
        int endPos = line.length();
        while (pos < endPos) {
            matcher.region(pos, endPos); // Sets the limits of this matcher's region
            if (matcher.lookingAt()) { // Attempts to match the input sequence, starting at the beginning of the region, against the pattern
                addToken(lineNo, matcher);
                pos = matcher.end(); // Returns the offset after the last matching character
            } else
                throw new ParseException("bad token at line " + lineNo);
        }
        queue.add(new IdToken(lineNo, Token.EOL));
    }

    protected void addToken(int lineNo, Matcher matcher) {
        String m = matcher.group(1); // Returns the input subsequence captured by the given 1 during the previous match operation
        if (m != null) // if not a space
            if (matcher.group(2) == null) { // if not a comment
                Token token;
                if (matcher.group(3) != null) // is NumToken
                    token = new NumToken(lineNo, Integer.parseInt(m));
                else if (matcher.group(4) != null) // is StrToken
                    token = new StrToken(lineNo, toStringLiteral(m));
                else // is IdToken
                    token = new IdToken(lineNo, m);
                queue.add(token);
            }
    }

    protected String toStringLiteral(String s) {
        StringBuilder sb = new StringBuilder();
        int len = s.length() - 1;
        for (int i = 1; i < len; i++) {
            char c = s.charAt(i);
            if (c == '\\' && i + 1 < len) { // Determine if it is an escape character '\'
                int c2 = s.charAt(i + 1);
                if (c2 == '"' || c2 == '\\') // \" | \\
                    c = s.charAt(++i);
                else if (c2 == 'n') { // \n
                    ++i;
                    c = '\n';
                }
            }
            sb.append(c);
        }
        return sb.toString();
    }

    protected static class NumToken extends Token {
        private int value;

        protected NumToken(int line, int value) {
            super(line);
            this.value = value;
        }

        public boolean isNumber() {
            return true;
        }

        public String getText() {
            return Integer.toString(value);
        }

        public int getNumber() {
            return value;
        }
    }

    protected static class IdToken extends Token {
        private String text;

        protected IdToken(int line, String text) {
            super(line);
            this.text = text;
        }

        public boolean isIdentifier() {
            return true;
        }

        public String getText() {
            return text;
        }
    }

    protected static class StrToken extends Token {
        private String literal;

        StrToken(int line, String literal) {
            super(line);
            this.literal = literal;
        }

        public boolean isString() {
            return true;
        }

        public String getText() {
            return literal;
        }
    }
}

代码清单 3.4 异常 ParseException.java

package Stone;

import java.io.IOException;

public class ParseException extends Exception {
    public ParseException(Token t) {
        this("", t);
    }

    public ParseException(String msg, Token t) {
        super("syntax error around " + location(t) + ". " + msg);
    }

    private static String location(Token t) {
        if (t == Token.EOF)
            return "the last line";
        return "\"" + t.getText() + "\" at line " + t.getLineNumber();
    }

    public ParseException(IOException e) {
        super(e);
    }

    public ParseException(String msg) {
        super(msg);
    }
}

词法分析器试运行展开目录

今天最后我们将尝试运行由代码清单 3.3 的 Lexer 类实现的词法分析器。相应的 main 方法见代码清单 3.5。他将对输入的字符串做词法分析，并逐行显示分析得到的每一个单词

代码清单 3.6 中的 CodeDialog 对象是 Lexer 类构造函数中的参数。CodeDialog 是 java.io.Reader 的子类。Lexer 在调用 read 方法从该对象中读取字符串时，界面上将显示一个对话框，用户输入的文本将成为 read 方法的返回值。其中使用到的 Java Swing 界面并不是重点，读者无需了解，照做就行，

代码清单 3.5 LexerRunner.java

package chap3;

import Stone.*;

public class LexerRunner {
    public static void main(String[] args) throws ParseException {
        Lexer l = new Lexer(new CodeDialog());
        for (Token t; (t = l.read()) != Token.EOF;)
            System.out.println("=> " + t.getText());
    }
}

代码清单 3.6 CodeDialog.java

package Stone;

import java.io.FileReader;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.Reader;
import javax.swing.JFileChooser;
import javax.swing.JOptionPane;
import javax.swing.JScrollPane;
import javax.swing.JTextArea;

public class CodeDialog extends Reader {
    private String buffer = null;
    private int pos = 0;

    public int read(char[] cbuf, int off, int len) throws IOException {
        if (buffer == null) {
            String in = showDialog();
            if (in == null)
                return -1;
            else {
                print(in);
                buffer = in + "\n";
                pos = 0;
            }
        }

        int size = 0;
        int length = buffer.length();
        while (pos < length && size < len)
            cbuf[off + size++] = buffer.charAt(pos++);
        if (pos == length)
            buffer = null;
        return size;
    }

    protected void print(String s) {
        System.out.println(s);
    }

    public void close() throws IOException {
    }

    protected String showDialog() {
        JTextArea area = new JTextArea(20, 40);
        JScrollPane pane = new JScrollPane(area);
        int result = JOptionPane.showOptionDialog(null, pane, "Input", JOptionPane.OK_CANCEL_OPTION,
                JOptionPane.PLAIN_MESSAGE, null, null, null);
        if (result == JOptionPane.OK_OPTION)
            return area.getText();
        return null;
    }

    public static Reader file() throws FileNotFoundException {
        JFileChooser chooser = new JFileChooser();
        if (chooser.showOpenDialog(null) == JFileChooser.APPROVE_OPTION)
            return new BufferedReader(new FileReader(chooser.getSelectedFile()));
        throw new FileNotFoundException("no file specified");
    }
}

第三天的思维导图展开目录