Common Lisp/外部库/CL-YACC
CL-YACC 是一个用可移植 ANSI Common Lisp 编写的 LALR(1) 解析器生成器。
在深入研究 CL-YACC 的用法之前，让我们先对解析进行一个简单的回顾，特别是解析器生成器的使用。
解析器生成器是最早被大众（程序员）使用的元编程形式之一。YACC，或称 Yet Another Compiler Compiler，是一个 C 程序，它接收一个语法描述作为输入（以产生式规则的形式），并输出一个可以解析该语法输入的 C 程序。虽然 YACC 不是第一个做这个的，但它变得非常流行。
YACC 的意图是将其用作开发工具，即开发人员通过让这个解析器生成器完成她的工作而省去了很多麻烦。对于许多开发人员来说，这是一个很棒的想法，因为编写解析器（通常是手工完成的）不像它那么令人厌烦，至少当你掌握了它之后。然而，在很多情况下，词语 “令人厌烦” 并不能完全描述编写解析器的过程，更确切地说，更像是 “不可能”。例如，C 编程语言的 CL-YACC 输入大约有 280 行，但 CL-YACC 语法的宏扩展大约有 13,000 行高度冗余的意大利面条代码。这让你了解了它为你做了多少。
所以 YACC 是一个程序，它从为指定语法专门设计的语言中接收输入，然后用更低级的语言编写一个程序。听起来 YACC 就像一个宏扩展函数。YACC 正是人们通过 Common Lisp 宏完成的那种事情。
通常，解析被分成两个部分，词法分析和解析。词法分析是一个非常基本的步骤，它检查输入，将输入分解成标记，或解析器可以处理的片段。词法分析通常处理识别输入的哪些部分是什么，例如符号或标识符、常量（如数字、字符串文字或字符）以及运算符（如加、减或乘）。
另一方面，解析则拥有更多知识和智慧。例如，实际的解析器知道括号在程序中必须匹配。它还需要知道转义的括号（在 CL 中是可能的）和字符串中的括号不需要匹配。简而言之，解析器知道你的语言中某些语法实际上意味着什么。
由于能够使用解析器生成器的一个主要好处是你不需要知道它的工作原理，所以我们不会讨论解析或生成解析器的实际机制。相反，我们将注意到 CL-YACC 可以生成的 LALR(1) 解析器能够解析大多数上下文无关语法，包括大多数（所有？）编程语言和配置/数据文件的语法。事实上，大多数编程语言定义它们的语法，以便它可以由 LALR(1) 解析器解析，因为 LALR(1) 解析器提供了它提供的功能（一个高效且小巧的解析器，可以通过现有且常见的解析器生成器自动生成）。
产生式规则是表示语法的另一种方式。它们声明特定语言元素如何映射到其他语言元素。为了说明这一点，让我们看看你可能在 Lisp 解析器中期待的一些产生式规则。
form : atom
| list</lisp>
This states that in Lisp, a form is either an atom or a list. We go on to declare what an atom and a list is.
<syntaxhighlight lang="lisp">
atom : constant
| symbol
list : ( symbol forms )
forms : form
| form forms</lisp>
Here we stated that an atom is either a constant (number, string, etc.), or a symbol. We also specify that a list is a function followed by some number of forms, and that forms is one or more form. We left out quoted lists for now. Notice how one uses recursive definitions like in forms.
What about definitions for <code>constant</code> and <code>symbol</code>? These are what is known as terminals which relate to actual tokens in the input. These are not composite objects like <code>list</code>.
We can translate this into CL-YACC syntax like so.
<syntaxhighlight lang="lisp">
(yacc:define-parser lisp-parser
(:start-symbol form)
(:terminals (\( \) symbol constant))
(form atom
list )
(atom constant
symbol )
(list (\( symbol forms \)))
(forms form
(form forms) ))
这种新形式的大部分都是不言自明的。一个新的部分是开始符号的规范。这是解析器最高级别或入口点。现在让我们对一些输入运行这个解析器。
(yacc:parse-with-lexer
(let ((list '((\( \()
(symbol +)
(constant 1)
(constant 2)
(\) \)) )))
(lambda () (values-list (pop list))) )
lisp-parser )
==> (|(| + (1 2) |)|)
输出有点不起眼，但让我们回顾一下发生了什么。parse-with-lexer 的第一个参数是一个词法分析器函数，它在每次调用时返回两个值，标记类型和值。我们正在使用一个简单的列表词法分析器，我在其中提前指定了词法标记，它只是将它们从列表中弹出。我们的词法标记是左括号，以及加号 symbol、两个 constant（1 和 2）和一个右括号。括号被赋予它们自己的标记类型，并且是语法中的终结符。如果这令人困惑，不要纠结它。词法分析器的目的是表示词法标记流，这些标记表示语法中的终结符。这个词法分析器返回的可能是来自 "(+ 1 2)" 输入的内容。
现在让我们看看解析器。它从 form 状态开始。它查看传入的标记，并意识到它正在查看一个 list（它肯定不是正在查看一个 atom，atom 被定义为一个 constant 或一个 symbol）。然后，它查看列表中的第一个元素，以确保它是 symbol 类型，然后它查看构成参数的形式。默认情况下，CL-YACC 基本上返回它在产生式规则中出现的方式。因此，我们看到一个标记列表，只要产生式规则需要一个列表来定义它，这些标记列表就会被分组在一个列表中。需要注意的是，所描述的解析过程与解析器在内部工作的方式完全不同，但它可以很好地作为思考这个过程的一种方式。
如果你已经玩过一段时间 Lisp，你可能会问为什么要这样做。如果你只是在 REPL 中键入 '(+ 1 2)，它会给你一个非常类似的东西。好吧，重要的是要注意，Lisp 读取器在某种程度上使用了类似的东西。有些东西需要理解你输入的内容。但更重要的是，返回的值是一个默认值，我们得到它是因为我们没有告诉解析器在解析时做任何事情。在任何 Lisp 中，这个默认解析都将非常接近输入，因为 Lisp 是通过直接指定解析树来编写的。在任何其他语言中，解析代码的第一步通常是将语言语法转换为更接近 Lisp 的东西。
话虽如此，让我们看看我们到底完成了什么。有一点需要注意：这个解析器非常灵活。有了合适的词法分析器，它可以处理 "hello"、(my-function 1 2 3) 和 (/ 1 (+ 3 7) (- x y (a-function z))) 这样的表达式。此外，解析器知道一些关于语言的信息，它知道括号需要匹配，并且知道像 ((+ 1 2) 3) 这样的东西是非法的，因为第一个元素必须是一个符号。所有这些都在几行代码中完成。
词法分析器就像是一毛钱一打，但很难找到一个好的。在这里，我们将使用 DSO-LEX，一个使用 CL-PPCRE 定义词法标记的词法分析器。
在这里，我们将做一个非常简单的计算器函数。人们说计算器是解析器中的 hello world 程序。
有一些库被设置为为 Common Lisp 用户提供中缀语法，用于数学表达式等等。我们将自己做一个。
由于解析器生成的元编程性质，Lisp 有大量的解析器生成器。其他值得注意的是 FUCC，一个可以解析比 LALR 语法更多内容的生成器，以及 META，一个（较老的）非常轻量级的生成器，注重速度。