转载

用 Parser Combinator 解析 Cirru 的缩进语法

在 Parsec 当中是存在解析缩进语法的方案的, 然而我没深入了解过等了解以后, 也许会有其他的想法, 到时候再考虑不迟

概览

这篇文章主要是整理一下我用"解析器组合子"解析缩进的知识

解析器组合子大概是 Parser Combinator 中文翻译, 应该还是准确吧

Cirru 语法解析器前面用的是 Tricky 的函数式编程做的, 有点像 State Monad

不过我当时搞不清楚 LL 和 LR 的区别, 现在看其实两个都不符合

关于编译器的知识我一直在积累, 但没有学成体系, 只是零星的

上周我写 WebAssembly 的 S-expression 解析器 , 解析成 JSON

突然想明白了 Parser Combinator, 就尝试写了下, 结果真的有用

但是用的是 CirruScript 加 immutable-js, 觉得有点吃力

于是想到尝试一下用解析器组合子解析 Cirru 的缩进

这次用的是 Clojure, 断断续续花了一个星期, 终于跑通了测试

LL, LR, Parser Combinator 资源

这是我期间和昨天整理的资源, 大概梳理了一下语法解析是怎么回事

Parser Combinator 在语法解析的当中处于怎样的位置?

为什么所有的教科书中都不赞成手写自底向上的语法分析器？

shift reduce，预测分析，递归下降和LL(K) LR(K) SLR 以 LALR 的关系？

LL and LR Parsing Demystified

LL and LR in Context: Why Parsing Tools Are Hard

[The difference between top-down parsing and bottom-up parsing

]( http://qntm.org/top)

Parser combinators explained

Parsing CSS with Parsec

[Simple Monadic Parser in Haskell

]( http://michal.muskala.eu/2015/09/23/simple-monadic-parser-in-haskell.html)

概括说, 语法解析要有一套语法规则, 一个结果, 还有每个字符串

解析的过程就是通过三个信息推导出中间组合的过程, 也就是 parse tree

LL 是先从 Parse Tree 根节点开始, 预测程序所有的可能结构, 排除错误的预测

LR 是先从每个字符开始组合, 逐步组合更多, 看最后是否得到单个程序

而 Parser Combinator 是用高阶函数递归构造 LL 解析, 充分利用递归的优势

实际当中的 Parser 经常因为太复杂, 而不是依据单纯 LL 和 LR 理论

Parser Combinator 基础

具体的原理这里解释不了, 建议看上边的文章, 虽然是英文, 还好懂我只是大概解释一下, 方便后面解释我是怎么解析缩进的

在解析器组合子当中, 比如要解析字母 a , 要先定一个对应的解析器

比如用 Clojure 表示一下大概的意思:

(def read-a [code]   (if (= (subs code 0 1) "a")     (subs code 1) nil))

对于字符串 code , 取第一个字符, 判断是否是 a
如果是 a , 就返回后面的内容, 如果不是 a , 就返回错误, 比如 nil

思路是这样, 但 Haskell 用 State Monad, 就是内部隐藏一个 State

而我在 Clojure 实际上定义了一整个 Map 存储我需要的数据:

(def initial-state {   :code "code"   :failed false   :value nil   :indentation 0   :msg "initial" })

其中 :failed 存储解析成功失败的状态, :value 存储当前局部解析的结果

:code 就是存储还没解析的字符串, :msg 是错误消息, 调试用的

上边的 read-a 改成 parse-a 的话, 参数也就改成用对象来写

解析正确的时候 :code 和 :value 更新成解析 a 以后的值

解析失败的时候把 :failed 设置为 true , 加上对应的 :msg

单个字符的解析就是这样, 其他的字符类似, 就是每次取一个字符判断

然后是组合的问题, 比如 aa , 就是两个 parse-a 的组合

常见的名字是 many , 就是到第一个 parse-a 的结果继续尝试解析

因为每个 parser 的输入输出都是 State, 所以前一个结果后一个 Parser 直接用

而 many 也可以把两个 parser 的 :value 处理成列表, 作为结果

类似也有 option 或者 choice , 比如 parse-a-or-b
解析的原理就是对字符串先用 parse-a , 不匹配就尝试 parse-b
然后得到结果, 或者是 a 或者是 b , 或者是 :failed true

此外还可以构造比如取反, 零个或多个, 可选, 间隔, 等等不同的匹配方式

发挥想象力, 尝试组合 parse, 根据返回的 :failed 值决定后续操作

我的语言描述不清楚, 最好加一些图, 这里我先贴代码, 可以尝试看下

大概的意思是连续解析几个内容, 以此作为新的解析器

(注意代码中 "log" "just" "wrap" 是生成调试消息用的, 可以先忽略)

(defn helper-chain [state parsers]   (log-nothing "helper-chain" state)   (if (> (count parsers) 0)     (let       [parser (first parsers)         result (parser state)]       (if (:failed result)         (fail state "failed apply chaining")         (recur           (assoc result :value             (conj (into [] (:value state)) (:value result)))           (rest parsers))))     state))  (defn combine-chain [& parsers]   (just "combine-chain"     (fn [state]       (helper-chain (assoc state :value []) parsers))))  (defn combine-times [parser n]   (just "combine-times"     (fn [state]       (let         [method (apply combine-chain (repeat n parser))]         (method state)))))

总之按照这样的思路, 就能把解析器越写越大, 做更复杂的解析

另外要注意的是递归生成的预测会非常复杂, 调试很难

我实际上是写了比较复杂的 log 系统用于调试的, 看一下简单的例子:

https://gist.github.com/jiyinyiyong/0568487a4ab31716186f

这只是解析表达式的, 而且是简单的 Cirru 语法

对于缩进, 而且如果加上更复杂的语法, 这个 log 会非常非常长

另外有个后面用到的 parser 要先解释一下, 就是 peek

peek 意思是预览后续的内容, 但不是真的把 :value 作为解析的一部分

也就是说, 尝试解析一次, 把 :failed 结果拷贝过来, 而 :code 不影响

(defn combine-peek [parser] (just "combine-peek"   (fn [state]     (let       [result (parser state)]       (if (:failed result)         (fail state "peek failed")         state)))))

以及 combine-value 函数, 专门处理处理 :value

用来讲每个单独 Parser 解析的结果处理成整个 Parser 想要得到的值

由于每个组合得到的 Parser 逻辑可能不同, 这里传入函数去处理的

(defn combine-value [parser handler] (just "combine-value"   (fn [state]     (let       [result (parser state)]       (assoc result :value         (handler (:value result) (:failed result)))))))

关于缩进

最初解析缩进的思路是, 模拟括号的解析, 每次解析 eat 掉对应缩进的字符串

然而这个方案并不靠谱, 有两个无法解决的问题

一个是如果出现一次多层缩进, 可能有换行, 但多个缩进是共用换行的

另一个是缩进结束位置, 经常会出现同时多层缩进, 也是共用缩进

这样的情况就需要用 peek , 也就是查看后续内容而不解析具体结果

最终我想到了一个方案, 可能也有一些 tricky, 但按照原理能运行了

如果对于缩进有更深入的理解的话, 也许有更好的方案

这个方案有几个要准备的点, 我分开来介绍一遍

首先准备工作是前面 initial-state 当中的 :indentation

这个值表示的是当前解析状态所处的缩进层级

后面具体的解析过程拿到代码行的缩进层级, 和这个值对比

那么就能缩进和反缩进就有一个办法可以识别出来了

缩进的空格, Cirru 限制了使用两个空格, 因而我直接定义好

(defn parse-two-blanks [state]   ((just "parse-two-blanks"     (combine-value       (combine-times parse-whitespace 2)       (fn [value is-failed] 1))) state))

换行本来就是 /n 字符, 不过为了兼容中间的空行, 做了一些处理

star 是参考正则里的习惯, 表示零个或者多个, 这里是零个或多个空行

(defn parse-line-breaks [state]   ((just "parse-line-breaks"     (combine-value       (combine-chain         (combine-star parse-empty-line)         parse-newline)       (fn [value is-failed] nil))) state))

然后是重要的函数 parse-indentation 匹配换行加缩进

其中缩进的具体的值, 通过 combine-value 进行一次处理

所以这个函数主要做的事情, 就是在发现缩进时把具体的缩进读出来

这个值就可以和上边 State 的 Map 里的缩进数据做对比了

(defn parse-indentation [state] ((just "parse-indentation"   (combine-value     (combine-chain       (combine-value parse-line-breaks (fn [value is-failed] nil))       (combine-value (combine-star parse-two-blanks)         (fn [value is-failed] (count value))))     (fn [value is-failed]       (if is-failed 0 (last value))))) state))

当解析出来的行缩进值大于 State 中保存的缩进时, 表示存在缩进

这里做的就是生成一个成功的状态, 并且 :indentation 的值加一

也就是说这后面的解析, 以新的一个缩进值作为基准了

同时 :code 内容在执行一次缩进解析时并不改变, 也就不影响多层缩进解析

所以解析缩进实际上是在 State 上操作, 而不是跟字符串一样 eat 字符

(def parse-indent (just "parse-indent"   (fn [state]     (let       [result (parse-indentation state)]       (if         (> (:value result) (:indentation result))         (assoc state           :indentation (+ (:indentation result) 1)           :value nil)         (fail result "no indent"))))))

反缩进的解析参考上边的原理, 只是在大小的对比上取反就可以了

(def parse-unindent (just "parse-unindent"   (fn [state]     (let       [result (parse-indentation state)]       (if         (< (:value result) (:indentation result))         (assoc state           :indentation (- (:indentation result) 1)           :value nil)         (fail result "no unindent"))))))

最后, 在行缩进层级和 State 中的缩进值相等时, 说明只是单纯的换行这时, 就可以 eat 掉换行和空格相关的字符串了, 从而进行后续的解析

(def parse-align (just "parse-align"   (fn [state]     (let       [result (parse-indentation state)]       (if         (= (:value result) (:indentation state))         (assoc result :value nil)         (fail result "not aligned"))))))

解析缩进的关键代码就是按照上边所说了, 已经满足 Cirru 的需要

此外做的就是 block-line 和 inner-block 相关的抽象

我把一个行(以及紧跟的因为缩进而包含进来的行)称为 block-line

整个程序代码实际上就是一组 block-line 为内容的列表

block-line 内部的缩进的很多行, 称为 inner-block

然后 inner-block 实际上也就是基于不同缩进的 block-line 组合而成

(defn parse-inner-block [state]   ((just "parse-inner-block"     (combine-value       (combine-chain parse-indent         (combine-value           (combine-optional parse-indentation)           (fn [value is-failed] nil))         (combine-alternate parse-block-line parse-align)         parse-unindent)       (fn [value is-failed]         (if is-failed nil           (filter some? (nth value 2)))))) state))  (defn parse-block-line [state]   ((just "parse-block-line"     (combine-value       (combine-chain         (combine-alternate parse-item parse-whitespace)         (combine-optional parse-inner-block))       (fn [value is-failed]         (let           [main (into [] (filter some? (first value)))             nested (into [] (last value))]           (if (some? nested)             (concat main nested)             main))))) state))

整理这样的思路, 整个按照缩进组织的程序代码就组合出来了

注意 block-line 之间需要有 indent-align 作为换行分割的

我专门写了 combine-alternate 表示间隔替代的两个 Parser

总体就这样, 得到的一个 parser-program 的 Parser

(defn parse-program [state] ((just "parse-program"   (combine-value     (combine-chain       (combine-optional parse-line-breaks)       (combine-alternate parse-block-line parse-align)       parse-line-eof)     (fn [value is-failed]       (if is-failed nil         (filter some? (nth value 1)))))) state))

大致解释完了, 应该还是很难懂的. 我也不打算写到非常清楚了对这个解析的方案有兴趣的话, 可以在微博或者微信上找我私聊