Parcom: CL Parser Combinators

Source | HN Comments

`Parcom` 是一个简洁的 Common Lisp 解析器组合库，类似于 Haskell 的 `parsec` 和 Rust 的 `nom`。它主要针对字符串进行操作，并提供“零拷贝”特性。库本身无依赖，提供了丰富的 API，包括字符、字符串、数字、空白字符、批量获取、组合子等多种解析器。此外，它还支持 JSON 解析。用户可以利用库提供的组合子编写自定义解析器，并支持参数化。当解析失败时，可以使用 `fail` 函数提供自定义诊断信息。

Parcom：CL Parser Combinators 解析器组合库

简单 Common Lisp 解析器组合库

fosskers/parcom

Simple parser combinators for Common Lisp. parcom 是一个简洁的解析器组合库，风格类似于 Haskell 的 parsec 和 Rust 的 nom。

(in-package :parcom)
(parse (*> (string "Tempus") #'space (string "fugit")) "Tempus fugit.")

fugit

parcom 严格操作字符串，而不是流式字节数据，但在其他方面是“零拷贝”的，即原始输入的提取子字符串不会被重新分配。 parcom 没有依赖项。

Compatibility
API
- Types and Running Parsers
- Parsers
  - Characters and Strings
    - char
    - string
    - any
    - anybut
    - hex
    - eof
  - Numbers
    - unsigned
    - integer
    - float
  - Whitespace
  - Taking in Bulk
- Combinators
  - *>, right
  - <*, left
  - <*>, all
  - <$, instead
  - alt
  - opt
  - between
  - many, many1
  - sep, sep1
  - sep-end, sep-end1
  - skip
  - peek
  - count
  - recognize
- Utilities
  - empty?
  - digit?
  - fmap
  - const
- JSON
  - parse
  - json
Writing your own Parsers

Compatibility

Compiler| Status ---|--- SBCL| ✅ ECL| ✅ Clasp| ❓ ABCL| ✅ CCL| ✅ Clisp| ✅ Allegro| ✅ LispWorks| ❓

API

以下示例为了简洁起见使用了 (in-package :parcom)，但假定您将在实际代码中使用局部别名，如 pc。此外，大多数示例都使用 parse 运行解析器，但偶尔会使用 funcall 来演示解析成功后剩余的输入是什么。您通常会在自己的代码中使用 parse。

Types and Running Parsers 类型和运行解析器

所有解析器都具有函数签名 string -> parser，其中 parser 是一个结构，其中包含解析成功的 value 以及剩余的输入字符串。

(in-package :parcom)
(funcall (string "Hello") "Hello there")

#S(PARSER :INPUT " there" :VALUE "Hello")

当然，解析器可能会失败，在这种情况下，将返回一个 failure 结构：

(in-package :parcom)
(funcall (string "Hello") "Bye!")

#S(FAILURE :EXPECTED "string: Hello" :ACTUAL "string: Bye!")

通常，我们调用 parse 来完全运行一些组合的解析器，并产生最终输出：

(in-package :parcom)
(apply #'+ (parse (sep (char #\.) #'unsigned) "123.456.789!"))

否则，parse 将忽略任何最终的、未使用的输入。如果解析失败，它还会引发 Condition 错误。

Parsers 解析器

“解析器”是一个消耗某些特定输入并产生单个结果的函数。

Characters and Strings 字符和字符串

char

解析给定的字符。

(in-package :parcom)
(parse (char #\a) "apple")

#\a

string

解析给定的字符串。

(in-package :parcom)
(parse (string "Hello") "Hello there!")

Hello

any

解析任何字符。

(in-package :parcom)
(parse #'any "Hello there!")

#\H

anybut

解析除了你不想解析的字符之外的任何字符。

(in-package :parcom)
(parse (anybut #\!) "Hello there!")

#\H

(in-package :parcom)
(funcall (anybut #\H) "Hello there!")

#S(FAILURE :EXPECTED "anybut: not H" :ACTUAL "Hello there!")

hex

解析任何大小写的十六进制字符。

(in-package :parcom)
(funcall (many #'hex) "abcd0efgh")

#S(PARSER :INPUT "gh" :VALUE (#\a #\b #\c #\d #\0 #\e #\f))

eof

识别输入的结束。

(in-package :parcom)
(parse #'eof "")

(in-package :parcom)
(parse (*> (string "Mālum") #'eof) "Mālum")

(in-package :parcom)
(funcall (*> (string "Mālum") #'eof) "Mālum rubrum")

#S(FAILURE :EXPECTED "the end of the input" :ACTUAL " rubrum")

Numbers 数字

unsigned

将正整数解析为 fixnum。

(in-package :parcom)
(parse #'unsigned "44")

integer

将正整数或负整数解析为 fixnum。

(in-package :parcom)
(parse #'integer "-44")

-44

float

将正浮点数或负浮点数解析为 float。

(in-package :parcom)
(parse #'float "123.0456")

123.0456

Whitespace 空白字符

newline

匹配单个换行符。

(in-package :parcom)
(let ((s (concatenate 'cl:string '(#\newline #\a #\b #\c)))) ; "\nabc"
 (parse #'newline s))

#\Newline

space, space1

解析 0 个或多个 ASCII 空格和制表符。

(in-package :parcom)
(length (parse #'space "  Salvē!"))

解析 1 个或多个 ASCII 空格和制表符。

(in-package :parcom)
(length (parse #'space1 "  Salvē!"))

(in-package :parcom)
(funcall #'space1 "Salvē!")

#S(FAILURE :EXPECTED "space1: at least one whitespace" :ACTUAL "Salvē!")

multispace, multispace1

解析 0 个或多个 ASCII 空格、制表符、换行符和回车符。

(in-package :parcom)
(length (parse #'multispace (concatenate 'cl:string '(#\tab #\newline #\tab))))

解析 1 个或多个 ASCII 空格、制表符、换行符和回车符。

(in-package :parcom)
(length (parse #'multispace1 (concatenate 'cl:string '(#\tab #\newline #\tab))))

(in-package :parcom)
(funcall #'multispace1 "Ārcus")

#S(FAILURE
  :EXPECTED "multispace1: at least one space-like character"
  :ACTUAL "Ārcus")

Taking in Bulk 批量获取

这些始终产生直接从原始输入借用的子字符串。

take

从输入中提取 n 个字符。

(in-package :parcom)
(parse (take 3) "Arbor")

Arb

take-while, take-while1

当某个谓词成立时，提取字符。

(in-package :parcom)
(parse (take-while (lambda (c) (equal #\a c))) "aaabbb")

aaa

take-while1 类似于 take-while，但必须至少产生一个字符。

(in-package :parcom)
(funcall (take-while1 (lambda (c) (equal #\a c))) "bbb")

#S(FAILURE :EXPECTED "take-while1: at least one success" :ACTUAL "bbb")

rest

消耗剩余的输入。总是成功。

(in-package :parcom)
(parse (<*> (string "Salvē") (*> #'space #'rest)) "Salvē domine!")

("Salvē" "domine!")

Combinators 组合子

“组合子”将子解析器组合在一起以形成复合结果。它们使我们能够表达诸如“解析这个然后解析那个”和“解析这个，然后可能解析那个，但前提是……”等意图。

*>, right

依次运行多个解析器，但产生最右边的解析器的值。 right 是别名。

(in-package :parcom)
(funcall (*> (char #\!) #'unsigned) "!123?")

#S(PARSER :INPUT "?" :VALUE 123)

<*, left

依次运行多个解析器，但产生最左边的解析器的值。 left 是别名。

(in-package :parcom)
(funcall (<* (char #\!) #'unsigned) "!123?")

#S(PARSER :INPUT "?" :VALUE #\!)

<*>, all

解析器组合，将所有结果作为列表产生。 all 是别名。

(in-package :parcom)
(parse (<*> #'unsigned (char #\!) #'unsigned) "123!456")

(123 #\! 456)

此库不提供柯里化机制，因此通常在 Haskell 中可用的技术，即将函数 fmap 到 <*> 链上，必须改为使用 apply 来完成：

(in-package :parcom)
(apply #'+ (parse (<*> #'unsigned (*> (char #\!) #'unsigned)) "123!456"))

<$, instead

运行某个解析器，但如果解析成功，则将其内部值替换为其他值。 instead 是别名。

(in-package :parcom)
(parse (<$ :roma (string "Roma")) "Roma!")

:ROMA

alt

接受一组解析器中第一个成功的解析器的结果。可以组合任意数量的解析器。

(in-package :parcom)
(parse (alt (string "dog") (string "cat")) "cat")

cat

opt

如果解析器失败，则产生 nil，但不会使整个过程失败，也不会消耗任何输入。

(in-package :parcom)
(parse (opt (string "Ex")) "Exercitus")

Ex

(in-package :parcom)
(parse (opt (string "Ex")) "Facēre")

NIL

between

一个由另外两个解析器夹在中间的主解析器。仅保留主解析器的值。适用于解析括号等。

(in-package :parcom)
(parse (between (char #\!) (string "Salvē") (char #\!)) "!Salvē!")

Salvē

many, many1

many 解析 0 个或多个解析器的出现。 many1 要求至少一个解析成功，否则将引发 Condition 错误。

(in-package :parcom)
(parse (many (alt (string "ovēs") (string "avis"))) "ovēsovēsavis!")

("ovēs" "ovēs" "avis")

sep, sep1

sep 解析 0 个或多个由某个 sep 解析器分隔的解析器实例。 sep1 要求至少一个解析成功，否则将引发 Condition 错误。

(in-package :parcom)
(parse (sep (char #\!) (string "pilum")) "pilum!pilum!pilum.")

("pilum" "pilum" "pilum")

至关重要的是，如果检测到分隔符，则父解析器也必须成功，否则整个组合将失败。例如，由于末尾的 !，这将不会解析：

(in-package :parcom)
(parse (sep (char #\!) (string "pilum")) "pilum!pilum!pilum!")

有关分隔符的更宽松行为，请参见 sep-end。

sep-end, sep-end1

与 sep 相同，但分隔符 may 可能出现在最终“父级”的末尾。同样，sep-end1 要求至少一个父级解析成功。

(in-package :parcom)
(funcall (sep-end (char #\!) (string "pilum")) "pilum!pilum!pilum!scūtum")

#S(PARSER :INPUT "scūtum" :VALUE ("pilum" "pilum" "pilum"))

skip

解析某个解析器 0 次或多次，但丢弃所有结果。

(in-package :parcom)
(parse (*> (skip (char #\!)) #'unsigned) "!!!123")

peek

产生解析器的值，但不消耗输入。

(in-package :parcom)
(funcall (peek (string "he")) "hello")

#S(PARSER :INPUT "hello" :VALUE "he")

count

将解析器应用给定的次数，并将结果收集为列表。

(in-package :parcom)
(funcall (count 3 (char #\a)) "aaaaaa")

#S(PARSER :INPUT "aaa" :VALUE (#\a #\a #\a))

recognize

如果给定的解析器成功，则返回消耗的输入作为字符串。

(in-package :parcom)
(funcall (recognize (<*> (string "hi") #'unsigned)) "hi123there")

#S(PARSER :INPUT "there" :VALUE "hi123")

Utilities 实用工具

empty?

给定的字符串是否为空？

(in-package :parcom)
(empty? "")

digit?

给定的字符是否为 0 到 9 之间的数字？

(in-package :parcom)
(digit? #\7)

fmap

将纯函数应用于解析器的内部内容。

(in-package :parcom)
(fmap #'1+ (funcall #'unsigned "1"))

#S(PARSER :INPUT "" :VALUE 2)

const

产生一个忽略其输入并返回某个原始种子的函数。

(in-package :parcom)
(funcall (const 1) 5)

JSON

通过依赖于可选的 parcom/json 系统，您可以解析简单的 JSON 或将 parcom 兼容的 JSON 解析器包含到您自己的自定义解析代码中。 (in-package :parcom/json) 在下面为了简洁起见而使用，但假定您将在自己的代码中使用一个昵称，可能为 pj。如果您不关心每个 JSON 解析器的具体内容，而只想简单地解析一些 JSON，请使用 parse。

转换：

JSON| Lisp ---|--- true| T false| NIL Array| Vector Object| Hash Table Number| double-float String| String null| :NULL

与父级 parcom 库一样，parcom/json 严格地处理字符串，并且不会尝试变得聪明或高性能。有关更“工业强度”的 JSON 解析库，请参见 jzon。 parcom/json 的优势在于其简单性和轻量级。

parse

尝试解析任何 JSON 值。类似于主库中的 parse。

(in-package :parcom/json)
(parse "{\"x\": 1, \"y\": 2, \"z\": [1, {\"a\":true}]}")

#<HASH-TABLE :TEST EQUAL :COUNT 3 {100985EBF3}>

(in-package :parcom/json)
(parse "[1.9,true,3e+7,\"hi\",[4],null]")

#(1.9d0 T 3.0d7 "hi" #(4) :NULL)

支持非 ASCII 和 Unicode 字符：

(in-package :parcom/json)
(parse "\"hēllお🐂\\u03B1\"")

hēllお🐂α

json

解析任何类型的 JSON（实际解析器）。

(in-package :parcom/json)
(json "{\"x\": 1, \"y\": 2, \"z\": [1, {\"a\":true}]} ")

#S(P:PARSER :INPUT " " :VALUE #<HASH-TABLE :TEST EQUAL :COUNT 3 {1009D16A63}>)

还有其他子解析器公开，但为了简洁起见，此处将其省略。如果您需要它们，请查阅源代码。

Writing your own Parsers 编写您自己的解析器

Basics 基础知识

解析器组合子的全部意义在于，编写您自己的解析函数变得很简单。回想一下，“完全实现的”解析器具有签名 string -> parser。在最简单的情况下，您的解析器可能如下所示：

(in-package :parcom)
(defun excited-apple (input)
 (funcall (<* (string "Mālum") (char #\!)) input))
(funcall #'excited-apple "Mālum! Ō!")

#S(PARSER :INPUT " Ō!" :VALUE "Mālum")

您可以在其中利用此库提供的组合子来构建对您有用的复合解析器。

Parameterized Parsers 参数化解析器

您还可以参数化您的解析器，类似于 take 之类的解析器或 count 之类的组合子：

(in-package :parcom)
(defun excited-apple (input)
 (funcall (<* (string "Mālum") (char #\!)) input))
(defun excited-apples (n)
 "Parse a certain number of excited apples."
 (lambda (input)
  (funcall (count #'excited-apple n) input)))
(funcall (excited-apples 3) "Mālum!Mālum!Mālum!Mālum!")

#S(PARSER :INPUT "Mālum!" :VALUE ("Mālum" "Mālum" "Mālum"))

因此，如果您的解析器由某个初始参数参数化，则它必须返回一个接受 input 字符串的 lambda。

Failure 失败

您可以在更复杂的手写解析器中使用 fail 来显式地使用您自己的诊断信息进行失败：

(in-package :parcom)
(defun three-sad-pears (input)
 (let ((res (funcall (many (string "Pirum trīste")) input)))
  (cond ((failure-p res)
      (fail "Three sad pears" "No pears at all!"))
     ((< (length (parser-value res)) 3)
      (fail "Three sad pears" "Not enough pears"))
     ((> (length (parser-value res)) 3)
      (fail "Three sad pears" "Way too many pears"))
     (t res))))
(three-sad-pears "Pirum trīste")

#S(FAILURE :EXPECTED "Three sad pears" :ACTUAL "Not enough pears")

请注意使用 parser-value 来访问 parser 结果的当前内部成功值。同样，parser-input 用于访问剩余的输入。