https://github.com/icsharpcode/ILSpy/issues/1591

总有国人用中文开 issue...

#paper #article #doc #Haskell #Math 讨论了几个数学问题，引用已经得到原作者的许可

目前写了这些 #CXX 将会继续讨论关于 #PLT 二元流解析器相关的话题 #Parsing

#PLT #Parsing 下面我会告诉大家一些关于编写二元操作解析器的事情

calc.c++ 是我练习写 parser 的一个小程序，它的打算是成为一个二元运算计算器（也没有必要成为更多了）

二元计算是什么呢？上过小学的人知道有四则运算（加减乘除）

并且，当加法和乘法同时出现的时候先算乘法，比如

1 + 2 * 3
= 1 + (2 * 3)
= 1 + 6 = 7

然后要『按顺序执行计算』（当然也有交换律(commutative law)什么的）。

3 + 2 + 1
= (3 + 2) + 1
= 5 + 1 = 6

恰巧，我的计算器就是模拟了这种模式，不过这涉及到解析器（准确的来说只是一种用于提取句子结构的流处理程序，状态机）编写的一个问题，就是『运算符的结合顺序』


首先我在睡觉（没错，你没有听错，是睡觉... 不过没有睡着）的时候想了一会写不出来的二元运算链解析的问题，
首先我修复了自己之前的一个误解：

我的解析器使用的字符流是这样的

static char vLastChar;
char next_char() { return (vLastChar = getchar()); }
bool has_next();

过去我对这个 LastChar 全局静态变量的含义一直有误解，我以为它等价 peek() 操作（不移动流指针，只是拿到当前流出口处的数据）
然后 next() 还是返回数据同时移动指针。

至少我以为 LastChar 它 hold 住了一个长度为 1 * char 的 buffer，然后我可以随便看『上一个字符』，同时也可以访问到下一个字符（使用上可以通过复制做到，但是这根本不是 peek 操作，只是为了方便解耦合抽提子解析器程序而出现的）

可是之前我没有考虑到一个问题：就是它的定义并不是任何 buffer... 实际上，它应该被理解成对『当前流出口处』上一次结果的缓冲，用途就是在不同的函数中传递上一次的结果，等待有心的函数去消耗(consume)掉它（next() 移动指针到下一项）

实际上，它本身对流并没有什么帮助，只是在抽提逻辑的过程中，为了解决生存周期不够的问题，做的一个 hack。
把原来最多是函数作用域的东西提升到了全局（也可以认为是一个软件模块，虽然 C 里好像还是蛮不同的...）
然后可以让这个模块里的函数都能访问到它们可能感兴趣的这个字符

实际上，只是放在函数作用域，也是完全可能的，只不过这样就要到处传来传去，不能 implicit 传递了

—
说回本来要谈的问题... 就是那个二元运算链
其实我之前（4 天前）也说过，不过就是思路不够清晰，而且有点错误
果然纸上谈兵还是不行的！Naive！ 🐸

我提到了两个解析子程序的类型签名：

Expr scanChain(Item left);
Expr scanChain(Item left, int precedence_l);

它们怎么样？都正确！而且没有我开始说的那么复杂。
递归，是表达式链解析器构造语法树的方式、流，是解析器解决数据上下文耦合性问题的方式。（这种基于程序计数器，就是程序当前控制流状态的解析器本身只依赖一个『对象流』进行操作，『流』本身是一种状态机，线性的流比如基于数组、序列的流可以认为是一种计数器，也是状态机）

chainl1 = item | chainl1 sep item
chainr1 = item sep chainr1 | item

（上面给你们不存在单个 item 分支的模式是无法被构造出来的，因为存在无尽递归）
这些模式都没有错，但对它们的理解要从『使用』而非『定义』上来看，比如

1 + 2 + 3 匹配到 chainr1，首先是 (item)1, (sep)+，然后再扫描 chainr (item)2

然后你会发现，解析器要问『这是 item 还是 chain？』
一般用 lookahead（流预取判断）即可实现（判断下下个项目是不是 sep 即可，是则代表是 chain）

2 的下一项 skip 掉 spaces 是 +，于是知道这是 chain，再次递归解析下去

1 + (2 + ?...) 然后前面判断并且拿到一个 item: 3

最终回溯得出语法树 1 + (2 + 3), 这是『右递归』，根(root) 项目是 (1 + ...), 第一个被求值的是 (2+3)
（语法树求值的后序遍历）

二元表达式，从字符流来看，『从左向右扫描』，我们应该怎么想？
二元表达式的问题在于它不是可以『不依赖被解析项目』地被提取的，相邻两个操作符的优先级会影响到解析输出语法树的构造。
chainl, chainr 则是两个比较简单的二元链构造方法，它们在解析上下文（代表一层递归子程序）里决定两种情况。

如果要利用递归程序的方式构造这种二叉树，基本单元显然要『能拿到』(b · a ·) （b 是第 n 项、a 是 n+1 项、第一个 · 是 b a 的二元操作符、下一个 · 是第一个 · 后的二元操作符）

[b (·1) a (·2)]
然后，按照两个中缀(infix)操作符 ·1 ·2 的优先级决定递归的流程：

1. (·1) > (·2): 显然 (·1) 的“力气”比较大，它把 b a 拉到一起了（先结合）（而不是 a 被 ·2 『拉』走了），选择 infixl 的递归模式 （自己这层递归先结合了 a b，然后让下一层递归继续在这个基础上进行解析）

chainl1 = item | chainl1 sep item

第一层构造的，就是这个 "chainl1"，余下的层都在这上面再组合
（允许我这么描述，虽然显得有点幼稚）
（自己直接构造了这一层的值 (a + b) + c...）『返回下一层』
2. (·1) < (·2): 看起来 ·1 争夺不过 ·2，它也只好等待 ·2 先结合了自己那一层递归，再来结合 ·2 递归的结果了，选择 infixr.

chainr1 = item sep chainr1 | item

下一层构造的，就是这个"chainr1"的递归，而在那之前可能还有很多层等待这自己的这个返回值。
（等待下一层递归组织好自己的 a + (b + c)）『返回这一层』

递归是解析器针对二元表达式链构造数据的方式、流是解析器解决编程可读性问题、提升解耦能力的方式。

#CXX #share #snippet 我调试了好久，才发现是因为（有时候自己不用心写漏了字符流移动）（有时候是因为自己思路不清晰，没搞清楚设计 计算结果输出时机、执行换行和空格的区分）

但总而言之，已经完成了这个（基本可用）的二元操作解析器
也意味着我可以开始学习编译原理了

虽然花了很多时间（大概两三个小时...），但考试最终还是（勉强...）通过了

下一步是 继续下去...

#CXX #PLT

... 总而言之，理论就是这样，大家去实践吧，也没啥好讲的了...
就是字符流字符流字符流... 啊，一般都是用解析组合子好了

解析子程序的话怎么组织，一般都是传 lhs 和 lhs_precednece，当然只传 lhs 也是可以
我这个性能痴每次看到一个 char 一个 char 的处理甚至判断都想死... 感觉要慢炸了，其实那些自动生成的还应该反而慢一些呢...（何况那题解根本不可接受）

其实写代码调试的时候 大概也是可以看的出具体情况的，重要的是要写出来...

虽然可能没啥意思了... 也不是很成功

这个抄 Lua 的问题在于没有做到判断左右是否一致，Lua 给两边的都一个 (n, n-1) 实现了『同优先级』左右递归，这里的是错的... 我开始也给 rhsprec 加上了 !leftrec 的赠优先级，然后默认是左递归(+1) 开始没有写上，害得我以为我的思路是错了又瞎改...

关于计算表达式终止的问题，我就的确没有考虑到，也导致了这次我没有完全成功...

实际上，我不知道 infix chain 表达式应该何时终止，我以为其中也可以包含换行的，但那样就和 REPL 的『执行』键冲突了，其他语言语法上可能支持的原因是他们有对应的终结符（比如，Java 里二元表达式链肯定是在诸如函数调用参数的地方，而那些地方有对应终结符(Terminator)）

然后我写的语法树推导，就没有终结符... 我开始没有考虑到这个问题，之前的 BinOps 是正确处理了冲突的（表达式只能写在一行内）

有时候单单考虑一个知识点不难，难在 all together 而且还不能错...

正确的优先级和 infixl/r 处理

比如：lhs / rhs
infixl + = (2-1)-1 = 1 / infixr ^ = (1-1) = 0
最终右结合

infixl - = (1-1)-1 = 0 / infixl - = (1-1) = 1
最终左结合

infixr ^ = (1-0)-1 = -1 / infixr ^ = 1-1 = -1
最终右结合

关键在对 infixr 右边赠优先级的添加上，等号右边最终比左边高一个等级（把默认的 -1 infixl 赠优先级抵消了）
然后会进到下面 if (lhsprec < rhsprec) ... else 的 else branch 里

最终 不负泽抛弃的版本（

#acg #life 今天突然想到两首歌：《中华美食颂》和《投食歌》 🤔

噢 不 是 千年食谱颂

... 第一件对于这周的我有点硬核了，从 1 开始吧（

#sysadmin #linux #Haskell 灵魂 Shell 迫真堆砌... 这都能编程...
虽然最终的代码根本不能看，但这居然可以编程...

for i in `ldd /bin/pandoc |grep not|awk '{print $1}'`; do name=`echo $i | awk -F- '{print $1}'`; echo -e "Mapping $i (\e[35m$name\e[0m) to \\n \\e[34m" found=`find /usr/lib64/$name*`; printf "\e[0m"; [ "$found" == "" ] || sudo ln -s $found $i; done

for i in `ldd /bin/pandoc |grep not|awk '{print $1}'`; do name=`echo $i | awk -F- '{print $1}'`; found=`find /usr/lib64/$name* | head -n1`; echo -e "Mapping $i (\e[35m$name\e[0m) to \\n \\e[34m$found\\e[0m"; [ "$found" == "" ] || echo sudo ln -s $found /usr/lib64/$i; done

目前准确度很辣鸡，在修改

for i in `ldd /bin/pandoc |grep not|awk '{print $1}'`; do name=`echo $i | awk '{ gsub("-", "\n", $1); print $1 }' | grep -E '^[A-Za-z]*$' | xargs | sed 's/ /-/'`; found=`find /usr/lib64/$name* | head -n1`; echo -e "Mapping $i (\e[35m$name\e[0m) to \\n \\e[34m$found\\e[0m"; [ "$found" == "" ] || echo sudo ln -s $found /usr/lib64/$i; done

这个方法实在是太危险了...