#GitHub https://github.com/BaseMax/PHPBeautifier/blob/master/Parser.php

#Parser 别人怎么写 Parser：这一会我居然还没有看懂... 🌚

https://epsil.github.io/gll/#continuation-passing-style-section

#FP #scheme #parser 想了解 continuation-passing-style （没有 return 如何编程？）的大佬们可以看看这人的文章，我觉得相当好。实用性，王垠那几十行代码不就是 CPS 优化吗。

照例个人观点：
0. 上文定义了 success/failure 的 union ，以及 (successed val rest) failure ，还有添加回调的 (bind p f)，基本是 (match (p s) [(success v rest) (+ v 1)] [failure failure]) 这么用的。
实现的解析器不支持流，支持 substring 。传递方式是 backtrace (比如 (string "abc") 在 (seq) 里成功则 (cons "abc" (cont "")) 失败就只是 failure 单值，所以要利用 memo 函数)

1. PKT 是不需要这种“优化”的（顶多比过程式慢 50倍的纯函数式框架要用），因为我们的 Seq 明白一解析器失败不考虑后面就 return notParsed ，不需要玩 p1(p2(p3 { })) 这种耗栈的游戏。Kotlin 不支持 CPS 优化，编程也不是智商测试。

2. CPS 也是有一定价值的，虽然它会损失一定性能，但能够拿到调用者的句柄（比如在有 Decide 的模式里，就可以后继操作遍历所有分支了，或者进行异步回调"thunk"函数）。和非 CPS 一样可作为 suspend fun 协程

3. 即便这篇文章相对易懂 #Lisp #Racket ，我不建议大家认真用 Racket ，原因是括号的表现力不够

比如文中 (let (result (apply op args)) (entry (mcons args result)) (set! alist (mcons entry alist)) (m=map)一大堆括号，有没有注意到 (let (a v) expr) 只是为可读性而加的，量定义可以内联…… 只是表达 alist = args to op(args) : alist 甚至 alist[args] = result 的意思呢（这例还是SICP里的呢，多余命名量本身就可能意味着语言性能缺失😢，比如『文言文』里甲乙丙丁一大堆OK么）…… 函数式那么多年修成正果了，开始从“无副作用”往“看起来像过程式”靠，草生(*￣m￣)

4. 从解决实际问题而言我觉得 ParserKt 更贴近，但这个文章所创建的解析组合子用更少的代码定义了更广义的实现方法，非常有意思（最后也用左递归和 regex 创建了计算器，缓存和穷举最长匹配问题如此有意思以至于我开始可惜PKT不用处理它了😳），而且也易懂的讲解了 CPS/trampoline 以及“穷举所有可能结果”的正统函数式思路 #Learn

#Python #dev 🤔 半解析器 。

在设计 fill_template 脚本的过程中，我发现其宏展开语法不能直接用 \((.*?)\) 匹配，也不可用非 greedy match （容易引起问题）

我写了个基于列表副作用的递归下降法 #parser ，它求值的方法大概是：

iBeg=len(sb)
readMacroTo(sb, s,i)
iStop=len(sb)
for idx in range(iBeg,iStop): buf.push(sb.pop(i))
sb.insert(iBeg, call(name,buf))

这里没有问题（大不了就是多 remove 几个值，改写成一个展开结果嘛）

但是函数的定义是 readMacroTo(sb:list, s:str, i0:int) -> int

我用了 s/i0 的配对而不是一个 stream 对象，返回值是解析末尾的 i 值（所以与其对应的 s 在哪？）

这个问题以 class 封装改好后，还可以实现宏展开调用栈的功能（准确的说是可以看到化简步骤，不然只能看到 caller/callee ）

#TypeScript #parser 🤔lex-yacc 式框架... 但是感觉代码质量不过关啊，文档也没写

刚才说完这个我突然想到关于这个 CPS(continuation-passing-style) 的一点不对…… #functional
看起来要么然之前在那篇文章上看的说法是错的，要么然 CPS 是一个类 longjmp() 的控制流概念，不是函数式概念

刚才说的 listE("item", ) = <items>$=<item> op($)</items> 是这样定义的(#Python 的压行技巧，不过之前说的 walrud operator 发现根本不能用)：

def listE(tag, op, xs): e = E(tag+"s" if tag[-1]!='y' else tag[:-1]+"ies"); [lets(E(tag), lambda ee: op(ee,x), e.append) for x in xs]; return e

如果

lets(E(tag), lambda ee: op(ee,x), e.append)

是 cps call-site ，那交给 callee 调用前的 continuation 应该是从 lets() 的头部(？)
程序可组合性的关键点在于，op “返回”后要能覆盖 x 才能算够用，但此例 op 也得能覆盖（而且要实现仅改 gavTo(e,coord) 的“单至多项展开”，这还远远不够吧）
如果不知道 return-side 的 type (接收什么变量)，就是说这种 cps 式编程，必须显式定义回转方类型，或类型不安全(形式参数列表意义--)
看来只有 yield/resume continuation 是好的（

不对啊， CPS 哪里来的 forEach 😂？看来我还不够了解真正纯的函数式……

#Kotlin #parser #ce https://t.me/dsuses/4519 🤔看来想做 REPL ，对字符终端模型没有坚实的理解是不可以的
写完贪吃蛇和烂苹果，就有经验了，不要老侥幸，下次就不会出了事，倒大霉。

吃饭的路上（最近有点劳累过度了，思量着 ANSI BadApple 赶紧结束休息几天吧），谈到所谓“优雅性”，想了一下 ParserKt 新 LexerFeed 的问题，感觉很 complicated ，流对象的各种属性真的不好办

首先是说这个给冰封提到底有没有意义的问题（毕竟 PM 冰封是一个比较要心理准备的事情，心理难度比与 Python 红姐、九月姐 谈笑风生不低多少），最后结论是有。

虽然 jimgui 的本意未必是做“定义式”的 GUI 框架，更像是学习 JNI 设计，而且 Kotlin wrapper 很可能会有好的接口，技术交流也是不应有太多压力的。
TkGUI 的代码生成方法利用了 Python 无编译期/运行期，虚拟机相关组件基本可用的动态性，以及动态类型；很难(或者说意义不大)移植到 Java ，但我的本意是 GUI 可以这么写， ImGui 的做法可以说是业界惯例(就我的观察, GTK, Wx 的大部分封装不需要为子控件选择 parent, 但没有一个支持树形代码定义一个视图，即便其语言有足够表现力)，Java 的 Swing Frame,Panel 和 Fx Stage,Scene,Group 都必须用 mutate 对象的方法「创建」模板化的视图树(当然这是过程式的自然映照,无可厚非)， Qt 和 C#, VB 有 uic 这样的 code generator ；而 TkGUI 的 way 更像是 parser combinator 那样，尽可能少用外部工具，直接在语言里组合。

这个 way 就是一句话，“优美的代码能直观地反映它所处理数据的结构”，程序结构和数据结构相互照应、谐调统一，虽然会有额外开销，但一件事情只有你重视了才能找到各方面的最优解决办法，否则就永远只是传说。

再谈 ParserKt 的问题，其实最初版本相较于一些同类已经可以算是优雅了（当然离我想的还更远）
几个月前的重计划里包含了“削除 Parser 里 Lexer 相关代码”的改动，可以说是解决了我心头一厌(很多 PEG 生成器都逃不开跳空格注释的问题，要么然写文法里，要么然走 lexer/parser 的老路，要么然可配置性不够好，这是比较草的，因为我觉得在 a b c “按顺序”模式里默认插跳空格的逻辑是接近正解的)

具体实现还算好， Lexer/Parser 的区分、 Token 而非 Char 流的存在，核心原因是空格和注释对语法结构是无效的——最好能无视，免得解析器混杂
scannerless parser 很好，但跳空格其实有更容易的解决方法——为 Input stream 添加 filter ，到底还是 java 那一套自由组合的 stream 最好，连 skipped whitespaces 以及 AST element spans 它都可以往 Map<K,V> 存储好了，这就同时解决了 AST data class 不好写的问题，在不必使用这些信息时，也提升了性能，就从根源上解决了许多联带(代码复用、类型冗余和构造器隐式参数、分词解析器如何相互协调的)问题。

核心思想容易，实现上也有些问题—— Lexer 和 parser 在最近的语言里越来越模糊了，你可以看到 KotlinLexer 里会处理一些嵌套问题(就需要 push/pop state number 了)，而且 >= 与 fun():P<T>= 的区分也使得它必须识别一些本该由文法处理的模式——在过去这是不可想象的，C 的词法规则相当简单

这么做势必造成计算力的浪费(分词器和解析器对同一份数据做了类似的动作——检查它的嵌套结构)，以及编程的冗余、重复代码，是应该努力避免的。

解析器与“分词器”之间的交流，显然是 parser combinator 的优势——它们的结构对程序员是完全透明的，可以自由定义、随意组合，让 Parser 去驱动其输入流上的 Lexer ，告诉分词器现在是什么状态，需不需要跳空格(例如 "" 里就不能跳)；分词器是一个针对 Feed 流的状态机，本身也是一个 Feed ，而 onChar 的时候被动进行状态转移，就可以 filter 掉那些解析器不想看的字符，同时也能选择性地保留(如语法高亮) 的数据，一举多得。

有的观众就会问了：这么好的方法，比你高到不知哪里去的聪明人可多了，怎么就你想出来？
首先，不能说是没人想，要看编程实践怎么用、怎么组合这些技巧，不是说你去做了，效果就真的能像想象的那样好
其次，如果你没把代码重写 9遍，也容易被 Lexer/parser 和 scannerless 的那群既有实践误导，以为必须有 tokenizer ，或者流只能是一层，不能有“滤过”操作的
如果 LexerFeed 的被动性[2](非阻塞,要不然无法共享 string 等词法的定义)以及 Parser 对其的主动性(传递在解析词条类型号)不能被保证， 许多人对输入字符序列的抽象不够灵活(万恶之源)，使得他们不能够发现这一点。 （所以你在编程的时候，记得重复的少写一点、稀奇的功能特性多写一点，说不定还能帮助你对程序模型整体的理解）
(这种设计也很好的发扬了 ParserKt 的 one-pass 设计，而 C 系语言 // /* 注释与除号的区分早有给 InfixPattern 扫描操作符的 TriePattern 专定子类可轻易完成，PKT 的组合性不加盖的)

但这个封装有很大问题—— ParserKt 最初只有 Feed { val peek; fun consume() } ，不像一些 nextChar() 或 curChar() 数据视口不一致、命名迷惑的框架，它的流模型只允许程序员着眼一项（最本质的问题），结束时抛 Feed.End 异常
尽管这是根基(SliceFeed, Iterator/ReaderFeed 子类)，它也是不切实际的，所以很快有了 Input(s: Feed): Feed, SourceLocated, ErrorHandler [1]，以及一大堆 Feed 上试着 (this as Input) 的扩展函数，允许解析器带行号，尽量减小开销(统计行号信息是要在 Char 输入上，而一些输入根本无需 Input 的一些成员)
而那些接收 Input 的 Input ，就只能用一个代理(delegate)类 Input.By 去 proxy 这 underlying stream 实现的一些特性，这种问题严重后有点像“责任链”的字面含义——不断尝试 unwrap 一个 (可能是Input的)Feed ，寻找某个 trait 的实现者。

如果说你组织流嵌套的方法是手工的，应该不需要滥用多态去做“动态类型”，又或者是自动的——真的到那种“可组合”的地步吗？

最后我觉得，还是做 LexerInput(s:Input): Input.By 比较好，这样 LexerInput(Input(s=SliceFeed(Slice("wtf") ))) 这样的二层就会成为必要的组合法，如果需要其他层，则不能打破 Lexer 需求 Input (SourceLocated) 的类型， 还是取消这样的限制吧…… 真不知该怎样解决这问题 #parser #parsing #learn #Kotlin #project #suggest

[^1] 现在我更倾向 Input: Feed, FeedControl, SourceLocated { val states:Map<String,Any>; val onError; val isCompleteRead:Boolean }
isCompleteRead 是重新建模的(结果存逆波兰栈的)算符链解析器需要的，在非 complete read 时，可以像 Lua 一样直接进行简单的常量折叠，否则不仅不能折叠，还要存语法元素行号、前部空格等(重现原文所需的)信息
[^2] 其实我理解错了，这也是因为 LexerFeed 最开始是能自动识别底层输入的状态机，上级请求字符时肯定是要 blocking consume 直到非空格字符的，所谓非阻塞是因为对非空格单个字符它照样要处理状态转移；现在我倾向把它做成“能暂时屏蔽的自动 ws skip”一些，因为这才能真正统一复用文法/词法规则 ，虽然那样就没有花里胡哨的 List<Triple<Char,Int,Int>> 了(毕竟有效性在那)

#pr #GitHub 收到几个回复，还有个作者说只有我贡献代码才会加特性，太草了
https://github.com/fork-handles/forkhandles/issues/6 #parser #Kotlin
https://github.com/jindrapetrik/jpexs-decompiler/pull/86 这个感觉是不是代码质量有点低吧，虽然只是小功能… 但也是因为原版质量没有太高，入乡随俗的原因
https://github.com/kelseyhightower/nocode/pull/2230/files #China #meme nocode 🌚
—
https://github.com/jindrapetrik/jpexs-decompiler/pull/86/files#diff-e22b65fd014072fcf1d474f1c7c47361a46747939f5187ac4ef46c264e35c870

parser-combinator-koans #parser #cs #functional 🤔就是难以理解传来传去的 pure parser(CP -S style)...

interface Parser<out T> { fun parse(input: Input): Output<T>? }
data class Output<out T>(val payload: T, val nextInput: Input)

data class Input(val value: String, val offset: Int = 0) {
val unprocessed = value.substring(offset)
fun consumed() = copy(offset = value.length) // 改 offset 处理完了调用下
}

https://ace.c9.io/index.html#higlighter=&nav=higlighter
#parser 都是只支持内部状态机分词吗... Kate KSyntaxHighlight 也是
看来不能靠解析器导出 span 区间，还得想办法导出 tmlanguage，然后让它去支持新语言 tokenize rules...
也的确是…… 编辑器用状态机维持高亮的话就能避免完整解析了，如果算法写得好而词法规则又允许的情况下