（只是因为 GFW 导致 Telegram 不能用打个电话）关于某消元法的 issue #1

duangsuse · 2019-03-17T10:34:16Z

某些可能和这个该死的 issue 有关的事情：

为什么说是关于某（高斯-约当）消元法？

因为这次新弄的是从这篇介绍高斯-约当算法的文章上复刻下来的，方便自己下去打印了看。

为什么要开这个 issue？

Telegram 之前上的 MTProto 代理，真舒服，结果最后我从网上随便找的 Proxy 现在全部爆炸了（估计是人太多挤炸了）（现在我越发展系统管理的能力就越差了，呵呵，大概是复杂的东西越找越多然后瞬间信心都没有了，因为实在是 ~~见得多了~~... 🐸 ），我得继续维护我的笔记啊... 🤔 😢 So F@CK YOU 防fāng洪hóng新！

所以你到底要干什么？

我要给 @LEXUGE 发 comment 啊，因为我 Telegram 很难上了嘛。我最后（指上学前）有话要说...

lexuge:

我错了，我不该用 <code> 装这些的

本来这周有很多笔记想发在 dsuse 频道上的，可惜网络不通畅，加上我每周就周日早上到周六中午这点时间还是太少了，别说工程实践理论的笔记想讲都难讲完，当然也有我打字慢的原因。那就只能先说一部分，然后剩下的有时间了再喽。

--

三月十七和之前这七天学了点东西，觉得可能对大佬有帮助，大佬可以收着呗：

ice1000 的 Haskell Monad 解析组合子套餐
送给目前在用 subsequence 解析 String 的你

-- 后来我才知道你新写了个了 Rust 的 pest PEG 解析器...
https://github.com/XCH-CEB/xch-project/blob/master/lib_xch/src/parser/ast/treebuilder.rs#L30
之前发的是我以为没有这个新前端，要不然想来 WebAssembly 的前端也不好做到输入即时检查解析配平啊...
知道你目前应该不会主要学写编译器或者写其他更简单的基于编译原理知识的东西，所以我只想提一点可以帮助扩展 XCH_CEB 前端程序重构的基本思路

== 写程序『认』字符串表达的结构的方法论

duangsuse 目前尝试过的，一共有三种：第一种是针对 String 的子串递归解析法、第二种是针对字符（或者词元）流的递归下降解析法、第三种则是基于各种字符串模式匹配算法的（比如 LL、LR、LALR），而基于 LALR 之类的算法则可能会使用到栈和线性表等数据结构

一般来说直接字符流递归下降法会比拿一串固定长度字符串 subseq、递归下去要好看很多，信息往往可以隐式传递，直接调用 getc() 这种比 index 字符串的往往好一些（虽然基于流也会有 buffer 维护/语法歧义分支解析 lookAhead 的问题（设计不好的解析器子程序或许还要输入流支持反向 seek），但是这些问题其实在 subsequence 里也存在），而且可以用简单的 return 指令允许更灵活地控制解析流程。

基于流的处理方法其实非常 UNIX，但是即便是要处理递归文法，好像初学者都会用拆分子串法（XCH-CEB 目前使用的其实就是拆分 regex 匹配），因为递归总是难理解一些。（虽然递归写解析器很方便）

解析器也是属于编译原理/自然语言处理里面非常基础的内容了，所以它叫前端，稍微有点意思的可能就是二维文法了，反正编译原理的解析器，一般都很 trivial，没啥值得研究的。

稍微进阶一点的基础可能就是解析二元操作优先级了，加入右优先级的话，就可以处理 1^2^3 （应该被解析为 1^(2^3) 而不是 (1^2)^3）这种『右结合性』的表达式了，这又涉及到解析器进行左递归还是右递归（然后回溯出的二元语法树哪个子树离根节点远）（参见 lambda 算子当然是从这里看到的）,,,

这就有点类似于 C++ 的 std::cout << 流式操作和 Java8 的 System.out.println 对比一样，其实曾经写循环调用 println 打印数据或者 String.format，还不如直接 << 操作符写输出呢。

subsequence 解析法的例子：

https://github.com/covscript/covscript/blob/33ead62817b87e049a615b8b68560471bce9ad78/sources/compiler/parser.cpp#L214 （比较不好看，和你之前的 C 暴力搜索版的 parser 有点类似，不过这个更高级而且更难看）

基于字符流的解析器例子（也有些是 Lexer，或者说输出词条的 Parser 层面的东西）

https://github.com/qnnnnez/rs/blob/master/src/sexpr.rs 一个类 Scheme 语法的 parser
https://www.packtpub.com/application-development/llvm-cookbook 里 TOY 语言的前端，就是一个经典的 C++ 递归下降法解析器，支持左递归（传递自己这一层子解析器的归纳结果给下一层，然后回溯回来就是自己这一层先被求值，(1+2)+3. 返回的是第二个 + 解析器的二元运算树
https://github.com/duangsuse/GeekApk/blob/master/src/main/kotlin/lime/text/Parser.kt#L52
+https://github.com/duangsuse/Lite/blob/master/src/lite/lexer/Lexer.java#L150
https://github.com/covscript/covscript/blob/33ead62817b87e049a615b8b68560471bce9ad78/sources/compiler/lexer.cpp#L24

最后推荐文章，建议去体验一下 parser combinator(parserc) 风格的解析器（如果还没有的话）

https://ice1000.org/2017/07/26/HaskellParsers/
https://ice1000.org/2017/07/26/HaskellParsers2/
https://ice1000.org/2018/11/23/MultiDimentionalSyntax/

这个 Functional DFS（Haskell Applicative 函数式思路深度优先搜索）的也很好看
https://ice1000.org/2017/05/26/UseMonadInDfs/
这里有源代码，不过好像是改了一小部分防无脑抄的？
https://ice1000.org/gist/fp-dfs/

-- 后来我才知道你新写了个了 Rust 的 pest PEG 解析器...
https://github.com/XCH-CEB/xch-project/blob/master/lib_xch/src/parser/ast/treebuilder.rs#L30
之前发的是我以为没有这个新前端，要不然想来 WebAssembly 的前端也不好做到输入即时检查解析配平啊...