目录
用 javascript 实现一门编程语言 - 前言
用 javascript 实现一门编程语言 - 语言构想
用 javascript 实现一门编程语言 - 写一个解析器
用 javascript 实现一门编程语言 - 字符输入流
词法分析 (the token input stream)
词法分析是基于字符输入流进行操作的, 但是通过 peek() 或 next() 返回的是一个特殊对象, 即 token. 一个 token 中包含两个属性: type 和 value. 以下是几个例子:
- { type: "punc", value: "(" } // 标点符号 (punctuation): 括号 (parens), 逗号 (comma), 分号 (semicolon) etc.
- { type: "num", value: 5 } // 数字
- { type: "str", value: "Hello World!" } // 字符串
- { type: "kw", value: "lambda" } // 关键字 (keywords)
- { type: "var", value: "a" } // 变量名 (identifiers)
- { type: "op", value: "!=" } // 操作 (operators)
复制代码
空白和注释会被直接跳过, 没有 token 返回.
为了完成词法分析器, 我们需要对语法了解的很详细. 我们需要对 peek() 返回的当前字符进行处理, 返回 token, 有以下几点需要注意:
跳过空格
如果到达末尾, 返回 null
如果遇见 #, 跳过注释, 即本行后面所有内容
如果是引号, 读入字符串
如果是数字, 读入数字
如果是一个单词, 按关键字或者变量处理
如果是标点符号, 返回标点符号的 token
如果是操作符, 返回操作符的 token
如果不匹配上面任何一个, 输出错误 input.croak()
下面是词法分析的核心代码 - 读取下一个:
- function read_next() {
- read_while(is_whitespace);
- if (input.eof()) return null;
- var ch = input.peek();
- if (ch == "#") {
- skip_comment();
- return read_next();
- }
- if (ch == '"') return read_string();
- if (is_digit(ch)) return read_number();
- if (is_id_start(ch)) return read_ident();
- if (is_punc(ch)) return {
- type : "punc",
- value : input.next()
- };
- if (is_op_char(ch)) return {
- type : "op",
- value : read_while(is_op_char)
- };
- input.croak("Can't handle character: " + ch);
- }
复制代码
这是一个分发函数, 他会决定什么时候调用 next() 来获得下一个 token. 这里面用到了很多工具函数, 例如 read_string(), read_number() 等等. 我们没必要在这里就把这些函数写出来增加复杂度.
另一个需要注意的是, 我们不会一下子就去拿到所有的输入流, 每次解析器只会读取下一个 token, 这样便于我们去定位错误 (有时因为语法错误, 解析器不用继续解析).
read_ident() 函数会尽可能多的读取可以作为变量名称的字符作为变量名. 变量名必须以字母,λ或_开头, 可以包含字母, 数字或者?!-<>=. 因此 foo-bar 不会作为 3 个 token 读入, 而是作为一个变量. 定义这个规则的原因是为了让我定义 is-pair 这样的变量.
当然, read_ident() 函数也会去检查读入的名称是不是一个关键字. 如果是关键字将会返回 kw token, 否则返回 var token.
以下是 TokenStream 的所有代码:
- function TokenStream(input) {
- var current = null;
- var keywords = "if then else lambda λ true false";
- return {
- next : next,
- peek : peek,
- eof : eof,
- croak : input.croak
- };
- function is_keyword(x) {
- return keywords.indexOf("" + x +" ")>= 0;
- }
- function is_digit(ch) {
- return /[0-9]/i.test(ch);
- }
- function is_id_start(ch) {
- return /[a-zλ_]/i.test(ch);
- }
- function is_id(ch) {
- return is_id_start(ch) || "?!-<>=0123456789".indexOf(ch)>= 0;
- }
- function is_op_char(ch) {
- return "+-*/%=&|<>!".indexOf(ch)>= 0;
- }
- function is_punc(ch) {
- return ",;(){}[]".indexOf(ch)>= 0;
- }
- function is_whitespace(ch) {
- return "\t\n".indexOf(ch)>= 0;
- }
- function read_while(predicate) {
- var str = "";
- while (!input.eof() && predicate(input.peek()))
- str += input.next();
- return str;
- }
- function read_number() {
- var has_dot = false;
- var number = read_while(function(ch){
- if (ch == ".") {
- if (has_dot) return false;
- has_dot = true;
- return true;
- }
- return is_digit(ch);
- });
- return { type: "num", value: parseFloat(number) };
- }
- function read_ident() {
- var id = read_while(is_id);
- return {
- type : is_keyword(id) ? "kw" : "var",
- value : id
- };
- }
- function read_escaped(end) {
- var escaped = false, str = "";
- input.next();
- while (!input.eof()) {
- var ch = input.next();
- if (escaped) {
- str += ch;
- escaped = false;
- } else if (ch == "\\") {
- escaped = true;
- } else if (ch == end) {
- break;
- } else {
- str += ch;
- }
- }
- return str;
- }
- function read_string() {
- return { type: "str", value: read_escaped('"') };
- }
- function skip_comment() {
- read_while(function(ch){ return ch != "\n" });
- input.next();
- }
- function read_next() {
- read_while(is_whitespace);
- if (input.eof()) return null;
- var ch = input.peek();
- if (ch == "#") {
- skip_comment();
- return read_next();
- }
- if (ch == '"') return read_string();
- if (is_digit(ch)) return read_number();
- if (is_id_start(ch)) return read_ident();
- if (is_punc(ch)) return {
- type : "punc",
- value : input.next()
- };
- if (is_op_char(ch)) return {
- type : "op",
- value : read_while(is_op_char)
- };
- input.croak("Can't handle character: " + ch);
- }
- function peek() {
- return current || (current = read_next());
- }
- function next() {
- var tok = current;
- current = null;
- return tok || read_next();
- }
- function eof() {
- return peek() == null;
- }
- }
复制代码
next() 并不是每次都会调用 read_next(), 因为可能提前调用过 read_next(), 所以, 在 current 存在的时候就直接返回 current 就可以了.
我们只支持十进制数字, 不支持科学计数法, 不支持 16 进制, 8 进制. 如果我们需要这些的话, 就在 read_number() 函数中添加处理方法就可以了
与 javascript 不同的是, 字符串中不能包含引号本身和反斜杠, 但是我们不会影响常用的转义字符 \ n \t.
下面一节会介绍一下 AST.
来源: https://juejin.im/post/5b6e57a0e51d451993590a2e