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，一個（較老的）非常輕量級的生成器，注重速度。