2 本书有关语法解析的一切

语法解析（parsing）是将输入字符流转换成结构化内部表示的过程。常见的内部表示是树，程序可以递归地处理树这种数据结构。例如，给定输入流：

23 + 5 - 6

我们可以将其转换成根节点为加法，左边节点表示数23，右边节点是用树表示5-6的树。语法解析器（parser）是用于实现这种转换的程序。

语法解析本身是个比较复杂，且由于歧义的存在，还远没有被解决的问题。例如上面的例子，你还可以将其转换成根节点为减法，子树为加法的树。我们还需要考虑加法操作符的是否符合交换性（左右参数是否能互换）等问题。要解析功能完整的语言（暂且不提自然语言），要考虑的问题只会更多更复杂。

2.1 轻量级的，内建的语法解析器的前半部分

这些问题使得语法解析本身适合当作单独的主题来讲，也确实有很多书本、课程和工具专注于该方面。从我们的角度来说，语法解析是种令人分心的东西，因为我们想学习的是编程语言的除去语法解析的各个部分。因此，我们使用Racket一个有用的功能来将输入流转换成树：read。read和该语言的括号语法形式紧密关联，它将括号形式的字符流转换成内部树形式。例如，运行(read)然后输入——

(+ 23 (- 5 6))

——会产出一链表，其第一个元素是符号'+，第二个元素是数23，第三个元素是链表；该链表其第一个元素是符号'-，第二个元素是数5，第三个元素是数6。

2.2 快捷方式

你应该知道，程序都会需要详尽的测试，而每次测试都需要手工输入会很麻烦。幸运的是，你可能猜得到，括号表达式可以在Racket中用引号来表达，也就是你刚才看到的'<expr>形式——其效果和运行(read)然后输入<expr>一样。

2.3 语法解析得到的类型

事实上，我刚才的描述并不准确。之前说(read)会返回链表等类型。在Racket中确实如此，但在Typed PLAI中，事情稍有不同，(read)返回值类型为s-expression（符号表达式的简写）。

> (read)
- s-expression
[type in (+ 23 (- 5 6))]
'(+ 23 (- 5 6))

Racket包含了强大的s-expression系统，其语法还甚至可以表达带循环的结构。不过我们只会用到其中的一部分。

在静态类型的语言中，s-expression被认为是和其他类型（例如数、链表）都不同的数据。在计算机内部，s-expression是一种递归数据类型，其基本构造是原子值——例如数、字符串、符号，组合形式可以是表、向量等。因此，原子值（数、字符串、符号等）即是其自由类型，也是一种s-expression。这就造成了输入的歧义，我们后文讨论。

Typed PLAI采取一种简单的方式来处理这种歧义：当直接输入时，原子结构就是它本身的类型；当输入为大结构的一部分时——包括read或者引用——它们就是s-expression类型。你可以通过类型转换将其转换为基本类型。例如：

> '+
- symbol
'+
> (define l '(+ 1 2))
> l
- s-expression
'(+ 1 2)
> (first l)
. typecheck failed: (listof '_a) vs s-expression in:
  first
  (quote (+ 1 2))
  l
  first
> (define f (first (s-exp->list l)))
> f
- s-expression
'+

这方面和Java程序的类型转换类似。我们后文再学习类型转换。

请注意，表结构的第一个元素的类型并不是符号：表形式的s-expression是由s-expressions组成的表。因此，

> (symbol->string f)
. typecheck failed: symbol vs s-expression in:
  symbol->string
  f
  symbol->string
  f
  first
  (first (s-exp->list l))
  s-exp->list

类型转换：

> (symbol->string (s-exp->symbol f))
- string
"+"

必须对s-expressions进行类型转换确实是个麻烦事，但是某种程度的麻烦是不可避免的：因为我们的目的是把没有类型的输入，通过严谨的类型分析，转化为有类型的。所以有些关于输入的假设必须明文给出。

好在我们只在语法解析中使用s-expressions，而我们的目的是尽快处理完语法解析！所以，这一点只会帮助我们尽快摆脱语法解析。

2.4 完整的语法解析器

原则上read就是完整的语法解析器。不过其输出过于一般化：结构体中并不包含其意向的注释信息。所以我们倾向于使用更具体的表达方式，类似于前文中“表达加法”和“表达数”的那种。

首先，我们必须引入一种数据类型来表示这类关系。后文（3.1节）会详细讨论为啥采用这种数据类型，还有我们如何得出该数据类型。现在请先假设它是给定的：

(define-type ArithC
  [numC (n : number)]
  [plusC (l : ArithC) (r : ArithC)]
  [multC (l : ArithC) (r : ArithC)])

现在我们需要能将s-expression解析成该数据类型的函数。这就是语法解析器的另一半：

(define (parse [s : s-expression])
  (cond
    [(s-exp-number? s) (numC (s-exp->number s))]
    [(s-exp-list? s)
     (let ([sl (s-exp->list s)])
       (case (s-exp->symbol (first sl))
         [(+) (plusC (parse (second sl)) (parse (third sl)))]
         [(*) (multC (parse (second sl)) (parse (third sl)))]
         [else (error 'parse "invalid list input")]))]  ;无效的表输入
    [else (error 'parse "invalid input")]))  ;无效的输入

简单运行如下：

> (parse '(+ (* 1 2) (+ 2 3)))
- ArithC
(plusC
 (multC (numC 1) (numC 2))
 (plusC (numC 2) (numC 3)))

恭喜！你完成了首个程序的表示。从今往后我们就只需要处理用递归的树结构表示的程序了，再也不用担心各种不同的语法，还有如何把语法转换为树形结构了。我们终于可以开始学习编程语言了！

练习

如果传给语法解析器的参数忘了加引号，后果是啥？为什么？

2.5 尾声

Racket的语法继承自Scheme和Lisp，不乏争议。不过请观察它给我们带来的深层次好处：对传统语法进行解析会很复杂，而解析这种语法则简单明了，不管是从字符流到s-expressions的解析，还是从s-expressions进一步到语法树的解析。

这种语法的好处就是其多用途性。需要的代码少，而且可以方便的插入各种应用场景。所以很多基于Lisp的语言其语义各不相同，但都保留了历史继承而来的这种语法。

当然，我们也可以采用XML，它更好用；或者JSON，它和s-expression有着本质的不同！

2. 本书有关语法解析的一切