启动方案语言的解析器
Starting a parser for scheme language
我正在为 Scheme 解释器编写一个基本的解析器，这里是我为定义各种类型的标记而设置的定义：
# 1. Parens
Type:
PAREN
Subtype:
LEFT_PAREN
Value:
'('
# 2. Operators (<=, =, +, ...)
Type:
OPERATOR
Subtype:
EQUALS
Value:
'='
Arity:
2
# 3. Types (2.5, "Hello", #f, etc.)
Type:
DATA
Subtype:
NUMBER
Value:
2.4
# 4. Procedures, builtins, and such
Type:
KEYWORD
Subtype:
BUILTIN
Value:
"set"
Arity:
2
PROCEDURE:
... // probably need a new class for this
以上看起来是个不错的起点吗？我是否遗漏了一些明显的东西，或者这是否为我提供了一个“足够好”的基础？
您的方法做出了语言语法中实际上不存在的区别，并且还过早地做出了决定。例如考虑这个程序：
(let ((x 1))
(with-assignment-notes
(set! x 2)
(set! x 3)
x))
当我运行这个：
> (let ((x 1))
(with-assignment-notes
(set! x 2)
(set! x 3)
x))
setting x to 2
setting x to 3
3
为了使其工作 with-assignment-notes 必须以某种方式重新定义 (set! ...) 在其正文中的含义。这是一个 hacky 和可能不正确的 (Racket) 实现：
(define-syntax with-assignment-notes
(syntax-rules (set!)
[(_ form ...)
(let-syntax ([rewrite/maybe
(syntax-rules (set!)
[(_ (set! var val))
(let ([r val])
(printf "setting ~A to ~A~%" 'var r)
(set! var r))]
[(_ thing)
thing])])
(rewrite/maybe form) ...)]))
所以 Lisp 家族语言的任何解析器的关键特性是：
- 它不应该对它可以避免做出的语言语义做出任何决定；
- 它构造的结构必须作为第一个class对象对语言本身可用；
- （可选）解析器应该可以从语言本身进行修改。
例如：
- 解析器需要决定什么是数字，什么不是数字，以及它是什么类型的数字，这可能是不可避免的table；
- 如果它有默认的字符串处理就好了，但这最好由用户控制；
- 它根本不应该决定什么，比如
(< x y) 意思，而是应该 return 表示它的结构以供语言解释。
最后一个可选要求的原因是 Lisp 家族语言被有兴趣使用它们来实现语言的人使用。允许从语言中更改 reader 使这变得非常容易，因为您不必每次都从头开始创建一种有点像您开始使用但不完全相同的语言.
解析 Lisp
解析 Lisp 家族语言的常用方法是使用机器将字符序列转换为由语言本身定义的对象组成的 s 表达式序列，特别是符号和条件（但也数字、字符串等）。一旦你有了这个结构，你就可以遍历它来将它解释为一个程序：要么动态地评估它，要么编译它。重要的是，您还可以编写程序来操纵此结构本身：宏。
在 'traditional' Lisps 中，例如 CL，这个过程是显式的：有一个 'reader' 将字符序列转换为 s 表达式序列，宏显式地操作列表结构这些 s 表达式，然后 evaluator/compiler 处理它们。因此，在传统的 Lisp 中，(< x y) 将被解析为（符号 < 的缺点和（符号 x 的缺点和（符号 y 的缺点和空列表对象)), 或 (< . (x . (y . ()))), 这个结构被传递给宏扩展器，因此传递给计算器或编译器。
在 Scheme 中它有点微妙：宏是根据将一种语法转换为另一种语法的规则指定的（无论如何可移植），而且（我认为）这些对象是否是明确的是否由 conses & symbols 组成。但是语法规则可用的结构需要像由 conses 和符号组成的东西一样丰富，因为语法规则会在其中四处游荡。如果你想写类似下面的宏：
(define-syntax with-silly-escape
(syntax-rules ()
[(_ (escape) form ...)
(call/cc (λ (c)
(define (escape) (c 'escaped))
form ...))]
[(_ (escape val ...) form ...)
(call/cc (λ (c)
(define (escape) (c val ...))
form ...))]))
然后您需要能够查看来自 reader 的结构，并且该结构需要像由列表和条件构成的东西一样丰富。
一个玩具reader：reeder
Reeder 是一个用 Common Lisp 编写的小 Lisp reader，我不久前写的，原因我忘记了（但也许是为了帮助我学习它使用的 CL-PPCRE）。它着重是一个玩具，但它也足够小且足够简单易懂：当然它比标准 CL reader 更小更简单，并且它演示了解决此问题的一种方法。它由称为簧片 table 的 table 驱动，它定义了解析的进行方式。
因此，例如：
> (with-input-from-string (in "(defun foo (x) x)")
(reed :from in))
(defun foo (x) x)
芦苇
用芦苇阅读（芦苇）东西table:
- 寻找下一个有趣的字符，即 table 中未定义为空白的下一个字符（reedtable 有一个可配置的空白字符列表）；
- 如果那个字符在table中被定义为宏字符，调用它的函数来读一些东西；
- 否则调用 table 的令牌 reader 来读取和解释令牌。
芦苇令牌
令牌reader住在芦苇table中，负责积累和解释一个令牌：
- 它以自己已知的方式累积一个令牌（但默认的方式是 t运行dling 沿着字符串处理单个（
\）和多个（| ) 在 reedtable 中定义的转义，直到它到达 table 中的空白）；
- 此时它有一个字符串，它要求簧片table将这个字符串转换成某种东西，它通过令牌解析器来完成。
第二步有一个小问题：当令牌 reader 累积一个令牌时，它会跟踪它是否是 'denatured'，这意味着其中有转义字符。它将此信息传递给令牌解析器，这允许它们，例如，解释变性的 |1| 与未变性的 1 不同。
令牌解析器也在 reedtable 中定义：有一个 define-token-parser 形式来定义它们。他们有优先级，因此优先级最高的优先级首先被尝试，然后他们可以决定是否应该对变性令牌进行尝试。某些令牌解析器应该始终适用：如果 none 这样做是错误的。
默认的 reedtable 具有可以解析整数和有理数的标记解析器，以及一个解析符号的后备解析器。下面是一个示例，说明如何替换此后备解析器，以便 return 不再使用符号 return 对象 'cymbals'，这可能是某些嵌入式语言中符号的表示形式：
首先我们想要一个芦苇的副本table，我们需要从该副本中删除符号解析器（之前使用 reedtable-token-parser-names 检查了它的名称）。
(defvar *cymbal-reedtable* (copy-reedtable nil))
(remove-token-parser 'symbol *cymbal-reedtable*)
下面是一个铙钹的实现：
(defvar *namespace* (make-hash-table :test #'equal))
(defstruct cymbal
name)
(defgeneric ensure-cymbal (thing))
(defmethod ensure-cymbal ((thing string))
(or (gethash thing *namespace*)
(setf (gethash thing *namespace*)
(make-cymbal :name thing))))
(defmethod ensure-cymbal ((thing cymbal))
thing)
最后是 cymbal 令牌解析器：
(define-token-parser (cymbal 0 :denatured t :reedtable *cymbal-reedtable*)
((:sequence
:start-anchor
(:register (:greedy-repetition 0 nil :everything))
:end-anchor)
name)
(ensure-cymbal name))
这方面的一个例子。修改簧片前table:
> (with-input-from-string (in "(x y . z)")
(reed :from in :reedtable *cymbal-reedtable*))
(x y . z)
之后：
> (with-input-from-string (in "(x y . z)")
(reed :from in :reedtable *cymbal-reedtable*))
(#S(cymbal :name "x") #S(cymbal :name "y") . #S(cymbal :name "z"))
宏字符
如果某些东西不是标记的开头，那么它就是一个宏字符。宏字符有关联的函数，这些函数被调用来读取一个对象，但是他们选择这样做。默认簧片table有两个半宏字符：
"读取一个字符串，使用reedtable的单个&多个转义字符；( 读取列表或缺点。) 被定义为引发异常，因为它只有在括号不平衡时才会发生。
字符串 reader 非常简单（它与标记 reader 有很多共同点，尽管它们不是相同的代码）。
list/cons reader 有点繁琐：大部分繁琐是处理 consing 点，它通过一个有点恶心的技巧来处理：它安装了一个秘密令牌解析器，它将解析一个 consing 点如果动态变量为真，则作为特殊对象，否则将引发异常。 cons reader 然后适当地绑定这个变量以确保仅在允许的地方解析 cons 点。显然 list/cons reader 在许多地方递归地调用了整个 reader。
这就是所有宏字符。因此，例如在默认设置中，' 将读作一个符号（或铙钹）。但是你可以只安装一个宏字符：
(defvar *qr-reedtable* (copy-reedtable nil))
(setf (reedtable-macro-character #\' *qr-reedtable*)
(lambda (from quote table)
(declare (ignore quote))
(values `(quote ,(reed :from from :reedtable table))
(inch from nil))))
现在 'x 在 *qr-reedtable* 中读作 (quote x)。
同样，您可以在 # 上添加一个更复杂的宏字符，以按照 CL 的方式根据下一个字符读取对象。
引用 reader 的示例。之前：
> (with-input-from-string (in "'(x y . z)")
(reed :from in :reedtable *qr-reedtable*))
\'
它returned 的对象是一个名称为"'" 的符号，当然它不会读取更多。之后：
> (with-input-from-string (in "'(x y . z)")
(reed :from in :reedtable *qr-reedtable*))
`(x y . z)
其他注意事项
一切都提前一个字符工作，所以所有不同的函数都读取流，他们应该感兴趣的第一个字符和簧片table，return他们的值和下一个字符。这避免了无休止的未读字符（并且可能会告诉您它可以本机处理什么语法 class（显然，宏字符解析器可以做任何他们喜欢的事情，只要它们 return 是理智的）。
它可能不会使用任何在非 Lisp 语言中不是适度实现的东西table。一些
- 宏会以通常的方式引起疼痛，但唯一的一种是
define-token-parser。我认为解决这个问题的方法是通常的手动扩展宏并编写代码，但你可能会通过使用 install-or-replace-token-parser 函数来帮助一点，该函数处理保持的簿记列表排序等
- 你需要一种带有动态变量的语言来实现像 cons reeder 这样的东西。
- 它使用 CL-PPCRE 的正则表达式的 s 表达式表示。我敢肯定其他语言也有类似的东西（Perl 有），因为没有人愿意编写字符串正则表达式：它们一定在几十年前就消失了。
这是一个玩具：读起来可能很有趣，但不适合table任何严肃用途。我在写这篇文章时至少发现了一个错误：还会有更多。
我正在为 Scheme 解释器编写一个基本的解析器，这里是我为定义各种类型的标记而设置的定义：
# 1. Parens
Type:
PAREN
Subtype:
LEFT_PAREN
Value:
'('
# 2. Operators (<=, =, +, ...)
Type:
OPERATOR
Subtype:
EQUALS
Value:
'='
Arity:
2
# 3. Types (2.5, "Hello", #f, etc.)
Type:
DATA
Subtype:
NUMBER
Value:
2.4
# 4. Procedures, builtins, and such
Type:
KEYWORD
Subtype:
BUILTIN
Value:
"set"
Arity:
2
PROCEDURE:
... // probably need a new class for this
以上看起来是个不错的起点吗？我是否遗漏了一些明显的东西，或者这是否为我提供了一个“足够好”的基础？
您的方法做出了语言语法中实际上不存在的区别，并且还过早地做出了决定。例如考虑这个程序：
(let ((x 1))
(with-assignment-notes
(set! x 2)
(set! x 3)
x))
当我运行这个：
> (let ((x 1))
(with-assignment-notes
(set! x 2)
(set! x 3)
x))
setting x to 2
setting x to 3
3
为了使其工作 with-assignment-notes 必须以某种方式重新定义 (set! ...) 在其正文中的含义。这是一个 hacky 和可能不正确的 (Racket) 实现：
(define-syntax with-assignment-notes
(syntax-rules (set!)
[(_ form ...)
(let-syntax ([rewrite/maybe
(syntax-rules (set!)
[(_ (set! var val))
(let ([r val])
(printf "setting ~A to ~A~%" 'var r)
(set! var r))]
[(_ thing)
thing])])
(rewrite/maybe form) ...)]))
所以 Lisp 家族语言的任何解析器的关键特性是：
- 它不应该对它可以避免做出的语言语义做出任何决定；
- 它构造的结构必须作为第一个class对象对语言本身可用；
- （可选）解析器应该可以从语言本身进行修改。
例如：
- 解析器需要决定什么是数字，什么不是数字，以及它是什么类型的数字，这可能是不可避免的table；
- 如果它有默认的字符串处理就好了，但这最好由用户控制；
- 它根本不应该决定什么，比如
(< x y)意思，而是应该 return 表示它的结构以供语言解释。
最后一个可选要求的原因是 Lisp 家族语言被有兴趣使用它们来实现语言的人使用。允许从语言中更改 reader 使这变得非常容易，因为您不必每次都从头开始创建一种有点像您开始使用但不完全相同的语言.
解析 Lisp
解析 Lisp 家族语言的常用方法是使用机器将字符序列转换为由语言本身定义的对象组成的 s 表达式序列，特别是符号和条件（但也数字、字符串等）。一旦你有了这个结构，你就可以遍历它来将它解释为一个程序：要么动态地评估它，要么编译它。重要的是，您还可以编写程序来操纵此结构本身：宏。
在 'traditional' Lisps 中，例如 CL，这个过程是显式的：有一个 'reader' 将字符序列转换为 s 表达式序列，宏显式地操作列表结构这些 s 表达式，然后 evaluator/compiler 处理它们。因此，在传统的 Lisp 中，(< x y) 将被解析为（符号 < 的缺点和（符号 x 的缺点和（符号 y 的缺点和空列表对象)), 或 (< . (x . (y . ()))), 这个结构被传递给宏扩展器，因此传递给计算器或编译器。
在 Scheme 中它有点微妙：宏是根据将一种语法转换为另一种语法的规则指定的（无论如何可移植），而且（我认为）这些对象是否是明确的是否由 conses & symbols 组成。但是语法规则可用的结构需要像由 conses 和符号组成的东西一样丰富，因为语法规则会在其中四处游荡。如果你想写类似下面的宏：
(define-syntax with-silly-escape
(syntax-rules ()
[(_ (escape) form ...)
(call/cc (λ (c)
(define (escape) (c 'escaped))
form ...))]
[(_ (escape val ...) form ...)
(call/cc (λ (c)
(define (escape) (c val ...))
form ...))]))
然后您需要能够查看来自 reader 的结构，并且该结构需要像由列表和条件构成的东西一样丰富。
一个玩具reader：reeder
Reeder 是一个用 Common Lisp 编写的小 Lisp reader，我不久前写的，原因我忘记了（但也许是为了帮助我学习它使用的 CL-PPCRE）。它着重是一个玩具，但它也足够小且足够简单易懂：当然它比标准 CL reader 更小更简单，并且它演示了解决此问题的一种方法。它由称为簧片 table 的 table 驱动，它定义了解析的进行方式。
因此，例如：
> (with-input-from-string (in "(defun foo (x) x)")
(reed :from in))
(defun foo (x) x)
芦苇
用芦苇阅读（芦苇）东西table:
- 寻找下一个有趣的字符，即 table 中未定义为空白的下一个字符（reedtable 有一个可配置的空白字符列表）；
- 如果那个字符在table中被定义为宏字符，调用它的函数来读一些东西；
- 否则调用 table 的令牌 reader 来读取和解释令牌。
芦苇令牌
令牌reader住在芦苇table中，负责积累和解释一个令牌：
- 它以自己已知的方式累积一个令牌（但默认的方式是 t运行dling 沿着字符串处理单个（
\）和多个（|) 在 reedtable 中定义的转义，直到它到达 table 中的空白）； - 此时它有一个字符串，它要求簧片table将这个字符串转换成某种东西，它通过令牌解析器来完成。
第二步有一个小问题：当令牌 reader 累积一个令牌时，它会跟踪它是否是 'denatured'，这意味着其中有转义字符。它将此信息传递给令牌解析器，这允许它们，例如，解释变性的 |1| 与未变性的 1 不同。
令牌解析器也在 reedtable 中定义：有一个 define-token-parser 形式来定义它们。他们有优先级，因此优先级最高的优先级首先被尝试，然后他们可以决定是否应该对变性令牌进行尝试。某些令牌解析器应该始终适用：如果 none 这样做是错误的。
默认的 reedtable 具有可以解析整数和有理数的标记解析器，以及一个解析符号的后备解析器。下面是一个示例，说明如何替换此后备解析器，以便 return 不再使用符号 return 对象 'cymbals'，这可能是某些嵌入式语言中符号的表示形式：
首先我们想要一个芦苇的副本table，我们需要从该副本中删除符号解析器（之前使用 reedtable-token-parser-names 检查了它的名称）。
(defvar *cymbal-reedtable* (copy-reedtable nil))
(remove-token-parser 'symbol *cymbal-reedtable*)
下面是一个铙钹的实现：
(defvar *namespace* (make-hash-table :test #'equal))
(defstruct cymbal
name)
(defgeneric ensure-cymbal (thing))
(defmethod ensure-cymbal ((thing string))
(or (gethash thing *namespace*)
(setf (gethash thing *namespace*)
(make-cymbal :name thing))))
(defmethod ensure-cymbal ((thing cymbal))
thing)
最后是 cymbal 令牌解析器：
(define-token-parser (cymbal 0 :denatured t :reedtable *cymbal-reedtable*)
((:sequence
:start-anchor
(:register (:greedy-repetition 0 nil :everything))
:end-anchor)
name)
(ensure-cymbal name))
这方面的一个例子。修改簧片前table:
> (with-input-from-string (in "(x y . z)")
(reed :from in :reedtable *cymbal-reedtable*))
(x y . z)
之后：
> (with-input-from-string (in "(x y . z)")
(reed :from in :reedtable *cymbal-reedtable*))
(#S(cymbal :name "x") #S(cymbal :name "y") . #S(cymbal :name "z"))
宏字符
如果某些东西不是标记的开头，那么它就是一个宏字符。宏字符有关联的函数，这些函数被调用来读取一个对象，但是他们选择这样做。默认簧片table有两个半宏字符：
"读取一个字符串，使用reedtable的单个&多个转义字符；(读取列表或缺点。)被定义为引发异常，因为它只有在括号不平衡时才会发生。
字符串 reader 非常简单（它与标记 reader 有很多共同点，尽管它们不是相同的代码）。
list/cons reader 有点繁琐：大部分繁琐是处理 consing 点，它通过一个有点恶心的技巧来处理：它安装了一个秘密令牌解析器，它将解析一个 consing 点如果动态变量为真，则作为特殊对象，否则将引发异常。 cons reader 然后适当地绑定这个变量以确保仅在允许的地方解析 cons 点。显然 list/cons reader 在许多地方递归地调用了整个 reader。
这就是所有宏字符。因此，例如在默认设置中，' 将读作一个符号（或铙钹）。但是你可以只安装一个宏字符：
(defvar *qr-reedtable* (copy-reedtable nil))
(setf (reedtable-macro-character #\' *qr-reedtable*)
(lambda (from quote table)
(declare (ignore quote))
(values `(quote ,(reed :from from :reedtable table))
(inch from nil))))
现在 'x 在 *qr-reedtable* 中读作 (quote x)。
同样，您可以在 # 上添加一个更复杂的宏字符，以按照 CL 的方式根据下一个字符读取对象。
引用 reader 的示例。之前：
> (with-input-from-string (in "'(x y . z)")
(reed :from in :reedtable *qr-reedtable*))
\'
它returned 的对象是一个名称为"'" 的符号，当然它不会读取更多。之后：
> (with-input-from-string (in "'(x y . z)")
(reed :from in :reedtable *qr-reedtable*))
`(x y . z)
其他注意事项
一切都提前一个字符工作，所以所有不同的函数都读取流，他们应该感兴趣的第一个字符和簧片table，return他们的值和下一个字符。这避免了无休止的未读字符（并且可能会告诉您它可以本机处理什么语法 class（显然，宏字符解析器可以做任何他们喜欢的事情，只要它们 return 是理智的）。
它可能不会使用任何在非 Lisp 语言中不是适度实现的东西table。一些
- 宏会以通常的方式引起疼痛，但唯一的一种是
define-token-parser。我认为解决这个问题的方法是通常的手动扩展宏并编写代码，但你可能会通过使用install-or-replace-token-parser函数来帮助一点，该函数处理保持的簿记列表排序等 - 你需要一种带有动态变量的语言来实现像 cons reeder 这样的东西。
- 它使用 CL-PPCRE 的正则表达式的 s 表达式表示。我敢肯定其他语言也有类似的东西（Perl 有），因为没有人愿意编写字符串正则表达式：它们一定在几十年前就消失了。
这是一个玩具：读起来可能很有趣，但不适合table任何严肃用途。我在写这篇文章时至少发现了一个错误：还会有更多。