解析

程序设计语言中最直观的部分就是语法（syntax）或符号。解析器是一种程序，负责读入文本片段（包含程序的文本），并产生一系列与程序结构对应的数据结构。若文本不是一个合法程序，解析器应该指出错误。

我们的语言语法简单，而且具有一致性。Egg 中一切都是表达式。表达式可以是绑定名称、数字，或应用（application）。不仅函数调用属于应用，而且if和while之类的语言构造也属于应用。

为了确保解析器的简单性，Egg 中的字符串不支持反斜杠转义符之类的元素。字符串只是简单的字符序列（不包括双引号），并使用双引号包围起来。数值是数字序列。绑定名由任何非空白字符组成，并且在语法中不具有特殊含义。

应用的书写方式与 JavaScript 中一样，也是在一个表达式后添加一对括号，括号中可以包含任意数量的参数，参数之间使用逗号分隔。

  1. do(define(x, 10),
  2.    if(>(x, 5),
  3.       print("large"),
  4.       print("small")))

Egg 语言的一致性体现在：JavaScript 中的所有运算符（比如>）在 Egg 中都是绑定，但是可以像其他函数一样调用。由于语法中没有语句块的概念，因此我们需要使用do结构来表示多个表达式的序列。

解析器的数据结构用于描述由表达式对象组成的程序，每个对象都包含一个表示表达式类型的type属性，除此以外还有其他描述对象内容的属性。

类型为"value"的表达式表示字符串和数字。它们的value属性包含对应的字符串和数字值。类型为"word"的表达式用于标识符（名称）。这类对象以字符串形式将标识符名称保存在name属性中。最后，类型为"apply"的表达式表示应用。该类型的对象有一个operator属性，指向其操作的表达式，还有一个args属性，持有参数表达式的数组。

上面代码中> (x, 5)这部分可以表达成如下形式：

  1. {
  2.   type: "apply",
  3.   operator: {type: "word", name: ">"},
  4.   args: [
  5.     {type: "word", name: "x"},
  6.     {type: "value", value: 5}
  7.   ]
  8. }

我们将这样一个数据结构称为表达式树。如果你将对象想象成点，将对象之间的连接想象成点之间的线，这个数据结构将会变成树形。表达式中还会包含其他表达式，被包含的表达式接着又会包含更多表达式，这类似于树的分支重复分裂的方式。

解析 - 图1

我们将这个解析器与我们第 9 章中编写的配置文件格式解析器进行对比，第 9 章中的解析器结构很简单：将输入文件划分成行，并逐行处理。而且每一行只有几种简单的语法形式。

我们必须使用不同方法来解决这里的问题。Egg 中并没有表达式按行分隔，而且表达式之间还有递归结构。应用表达式包含其他表达式。

所幸我们可以使用递归的方式编写一个解析器函数，并优雅地解决该问题，这反映了语言自身就是递归的。

我们定义了一个函数parseExpression，该函数接受一个字符串，并返回一个对象，包含了字符串起始位置处的表达式与解析表达式后剩余的字符串。当解析子表达式时（比如应用的参数），可以再次调用该函数，返回参数表达式和剩余字符串。剩余的字符串可以包含更多参数，也有可以是一个表示参数列表结束的右括号。

这里给出部分解析器代码。

  1. function parseExpression(program) {
  2.   program = skipSpace(program);
  3.   let match, expr;
  4.   if (match = /^"([^"]*)"/.exec(program)) {
  5.     expr = {type: "value", value: match[1]};
  6.   } else if (match = /^\d+\b/.exec(program)) {
  7.     expr = {type: "value", value: Number(match[0])};
  8.   } else if (match = /^[^\s(),"]+/.exec(program)) {
  9.     expr = {type: "word", name: match[0]};
  10.   } else {
  11.     throw new SyntaxError("Unexpected syntax: " + program);
  12.   }
  14.   return parseApply(expr, program.slice(match[0].length));
  15. }
  17. function skipSpace(string) {
  18.   let first = string.search(/\S/);
  19.   if (first == -1) return "";
  20.   return string.slice(first);
  21. }

由于 Egg 和 JavaScript 一样，允许其元素之间有任意数量的空白，所以我们必须在程序字符串的开始处重复删除空白。 这就是skipSpace函数能提供的帮助。

跳过开头的所有空格后，parseExpression使用三个正则表达式来检测 Egg 支持的三种原子的元素：字符串、数值和单词。解析器根据不同的匹配结果构造不同的数据类型。如果这三种形式都无法与输入匹配，那么输入就是一个非法表达式，解析器就会抛出异常。我们使用SyntaxError而不是Error作为异常构造器，这是另一种标准错误类型，因为它更具体 - 它也是在尝试运行无效的 JavaScript 程序时，抛出的错误类型。

接下来，我们从程序字符串中删去匹配的部分，将剩余的字符串和表达式对象一起传递给parseApply函数。该函数检查表达式是否是一个应用，如果是应用则解析带括号的参数列表。

  1. function parseApply(expr, program) {
  2.   program = skipSpace(program);
  3.   if (program[0] != "(") {
  4.     return {expr: expr, rest: program};
  5.   }
  7.   program = skipSpace(program.slice(1));
  8.   expr = {type: "apply", operator: expr, args: []};
  9.   while (program[0] != ")") {
  10.     let arg = parseExpression(program);
  11.     expr.args.push(arg.expr);
  12.     program = skipSpace(arg.rest);
  13.     if (program[0] == ",") {
  14.       program = skipSpace(program.slice(1));
  15.     } else if (program[0] != ")") {
  16.       throw new SyntaxError("Expected ',' or ')'");
  17.     }
  18.   }
  19.   return parseApply(expr, program.slice(1));
  20. }

如果程序中的下一个字符不是左圆括号，说明当前表达式不是一个应用，parseApply会返回该表达式。

否则，该函数跳过左圆括号，为应用表达式创建语法树。接着递归调用parseExpression解析每个参数，直到遇到右圆括号为止。此处通过parseApply和parseExpression互相调用，实现函数间接递归调用。

因为我们可以使用一个应用来操作另一个应用表达式（比如multiplier(2)(1)），所以parseApply解析完一个应用后必须再次调用自身检查是否还有另一对圆括号。

这就是我们解析 Egg 所需的全部代码。我们使用parse函数来包装parseExpression，在解析完表达式之后验证输入是否到达结尾（一个 Egg 程序是一个表达式），遇到输入结尾后会返回整个程序对应的数据结构。

  1. function parse(program) {
  2.   let {expr, rest} = parseExpression(program);
  3.   if (skipSpace(result.rest).length > 0) {
  4.     throw new SyntaxError("Unexpected text after program");
  5.   }
  6.   return expr;
  7. }
  9. console.log(parse("+(a, 10)"));
  10. // → {type: "apply",
  11. //    operator: {type: "word", name: "+"},
  12. //    args: [{type: "word", name: "a"},
  13. //           {type: "value", value: 10}]}

程序可以正常工作了！当表达式解析失败时，解析函数不会输出任何有用的信息，也不会存储出错的行号与列号，而这些信息都有助于之后的错误报告。但考虑到我们的目的，这门语言目前已经足够优秀了。