/tmp/duangsuse.sock
关于某『双重标准』排序方法，我有一点新的想法， 下面我来举出一个真正不可能实现（逻辑相悖）的例子： 对于程序设计入门来说，很多人都会喜欢用一些简单的交互式“游戏”做例子， 比如一个支持对初始为 0 的『计数器』进行『+1; -1; *2; /2』操作的计算器，比如猜数游戏 『剪刀石头布』这个游戏也是一个例子。 给定双方的游戏『出拳』，关于判定游戏的输赢，本来是这样的： {-# LANGUAGE UnicodeSyntax #-} data G出拳 = C剪刀 | S石头 | F布 deriving…
This media is not supported in your browser
VIEW IN TELEGRAM
/tmp/duangsuse.sock
内容是这样，原文不再修改，开源后会加附注
🤔 啊 100 mod 10 是 0、(10 mod 10)*10 也是 0... 明明是相等的，我会加注，而且这里应用 Sum 求和公式
/tmp/duangsuse.sock
calc.c++
#PLT #Parsing 下面我会告诉大家一些关于编写二元操作解析器的事情
二元计算是什么呢？上过小学的人知道有四则运算（加减乘除）
并且，当加法和乘法同时出现的时候先算乘法，比如
首先我在睡觉（没错，你没有听错，是睡觉... 不过没有睡着）的时候想了一会写不出来的二元运算链解析的问题，
首先我修复了自己之前的一个误解：
我的解析器使用的字符流是这样的
然后
至少我以为 LastChar 它 hold 住了一个长度为 1 * char 的 buffer，然后我可以随便看『上一个字符』，同时也可以访问到下一个字符（使用上可以通过复制做到，但是这根本不是 peek 操作，只是为了方便解耦合抽提子解析器程序而出现的）
可是之前我没有考虑到一个问题：就是它的定义并不是任何 buffer... 实际上，它应该被理解成对『当前流出口处』上一次结果的缓冲，用途就是在不同的函数中传递上一次的结果，等待有心的函数去消耗(consume)掉它（
实际上，它本身对流并没有什么帮助，只是在抽提逻辑的过程中，为了解决生存周期不够的问题，做的一个 hack。
把原来最多是函数作用域的东西提升到了全局（也可以认为是一个软件模块，虽然 C 里好像还是蛮不同的...）
然后可以让这个模块里的函数都能访问到它们可能感兴趣的这个字符
实际上，只是放在函数作用域，也是完全可能的，只不过这样就要到处传来传去，不能 implicit 传递了
—
说回本来要谈的问题... 就是那个二元运算链
其实我之前（4 天前）也说过，不过就是思路不够清晰，而且有点错误
果然纸上谈兵还是不行的！Naive！ 🐸
我提到了两个解析子程序的类型签名：
递归，是表达式链解析器构造语法树的方式、流，是解析器解决数据上下文耦合性问题的方式。（这种基于程序计数器，就是程序当前控制流状态的解析器本身只依赖一个『对象流』进行操作，『流』本身是一种状态机，线性的流比如基于数组、序列的流可以认为是一种计数器，也是状态机）
这些模式都没有错，但对它们的理解要从『使用』而非『定义』上来看，比如
1 + 2 + 3 匹配到 chainr1，首先是 (item)1, (sep)+，然后再扫描 chainr (item)2
然后你会发现，解析器要问『这是 item 还是 chain？』
一般用 lookahead（流预取判断）即可实现（判断下下个项目是不是 sep 即可，是则代表是 chain）
2 的下一项 skip 掉 spaces 是 +，于是知道这是 chain，再次递归解析下去
二元表达式，从字符流来看，『从左向右扫描』，我们应该怎么想？
二元表达式的问题在于它不是可以『不依赖被解析项目』地被提取的，相邻两个操作符的优先级会影响到解析输出语法树的构造。
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 『拉』走了），选择
（允许我这么描述，虽然显得有点幼稚）
（自己直接构造了这一层的值 (a + b) + c...）『返回下一层』
2. (·1) < (·2): 看起来 ·1 争夺不过 ·2，它也只好等待 ·2 先结合了自己那一层递归，再来结合 ·2 递归的结果了，选择
（等待下一层递归组织好自己的 a + (b + c)）『返回这一层』
递归是解析器针对二元表达式链构造数据的方式、流是解析器解决编程可读性问题、提升解耦能力的方式。
calc.c++ 是我练习写 parser 的一个小程序，它的打算是成为一个二元运算计算器（也没有必要成为更多了）二元计算是什么呢？上过小学的人知道有四则运算（加减乘除）
并且，当加法和乘法同时出现的时候先算乘法，比如
1 + 2 * 3然后要『按顺序执行计算』（当然也有交换律(commutative law)什么的）。
= 1 + (2 * 3)
= 1 + 6 = 7
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（上面给你们不存在单个 item 分支的模式是无法被构造出来的，因为存在无尽递归）
chainr1 = item sep chainr1 | 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)）『返回这一层』
递归是解析器针对二元表达式链构造数据的方式、流是解析器解决编程可读性问题、提升解耦能力的方式。
Telegram
/tmp/duangsuse.sock
这里先提一下 infix operator 扫描的一些事情：
1. Infix chain 是什么？
1 + 1 * 9 这种代码写多了
可是不知道怎么解析
a.toString().hashCode() 也写过
可是也不知道怎么解析
Int -> String -> Int 实际上是 Int -> (String -> Int)
不知道如何解析成 data Type = ... | Fn Type Type 的形式
(Fn Type "Int" (Fn (Type "String") (Type…
1. Infix chain 是什么？
1 + 1 * 9 这种代码写多了
可是不知道怎么解析
a.toString().hashCode() 也写过
可是也不知道怎么解析
Int -> String -> Int 实际上是 Int -> (String -> Int)
不知道如何解析成 data Type = ... | Fn Type Type 的形式
(Fn Type "Int" (Fn (Type "String") (Type…
这还把一个 leftright recursive 给弄错了，是我的问题，抄了 Lua 的解决思路却没有做好逻辑上的理解工作，生搬硬套
/tmp/duangsuse.sock
#PLT #Parsing 下面我会告诉大家一些关于编写二元操作解析器的事情 calc.c++ 是我练习写 parser 的一个小程序，它的打算是成为一个二元运算计算器（也没有必要成为更多了） 二元计算是什么呢？上过小学的人知道有四则运算（加减乘除） 并且，当加法和乘法同时出现的时候先算乘法，比如 1 + 2 * 3 = 1 + (2 * 3) = 1 + 6 = 7 然后要『按顺序执行计算』（当然也有交换律(commutative law)什么的）。 3 + 2 + 1 = (3 + 2) +…
... 总而言之，理论就是这样，大家去实践吧，也没啥好讲的了...
就是字符流字符流字符流... 啊，一般都是用解析组合子好了
解析子程序的话怎么组织，一般都是传 lhs 和 lhs_precednece，当然只传 lhs 也是可以
我这个性能痴每次看到一个 char 一个 char 的处理甚至判断都想死... 感觉要慢炸了，其实那些自动生成的还应该反而慢一些呢...（何况那题解根本不可接受）
其实写代码调试的时候 大概也是可以看的出具体情况的，重要的是要写出来...
虽然可能没啥意思了... 也不是很成功
就是字符流字符流字符流... 啊，一般都是用解析组合子好了
解析子程序的话怎么组织，一般都是传 lhs 和 lhs_precednece，当然只传 lhs 也是可以
我这个性能痴每次看到一个 char 一个 char 的处理甚至判断都想死... 感觉要慢炸了，其实那些自动生成的还应该反而慢一些呢...（何况那题解根本不可接受）
其实写代码调试的时候 大概也是可以看的出具体情况的，重要的是要写出来...
虽然可能没啥意思了... 也不是很成功
关于计算表达式终止的问题，我就的确没有考虑到，也导致了这次我没有完全成功...
实际上，我不知道 infix chain 表达式应该何时终止，我以为其中也可以包含换行的，但那样就和 REPL 的『执行』键冲突了，其他语言语法上可能支持的原因是他们有对应的终结符（比如，Java 里二元表达式链肯定是在诸如函数调用参数的地方，而那些地方有对应终结符(Terminator)）
然后我写的语法树推导，就没有终结符... 我开始没有考虑到这个问题，之前的 BinOps 是正确处理了冲突的（表达式只能写在一行内）
有时候单单考虑一个知识点不难，难在 all together 而且还不能错...
实际上，我不知道 infix chain 表达式应该何时终止，我以为其中也可以包含换行的，但那样就和 REPL 的『执行』键冲突了，其他语言语法上可能支持的原因是他们有对应的终结符（比如，Java 里二元表达式链肯定是在诸如函数调用参数的地方，而那些地方有对应终结符(Terminator)）
然后我写的语法树推导，就没有终结符... 我开始没有考虑到这个问题，之前的 BinOps 是正确处理了冲突的（表达式只能写在一行内）
有时候单单考虑一个知识点不难，难在 all together 而且还不能错...
/tmp/duangsuse.sock
正确的优先级和 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 赠优先级抵消了）
然后会进到下面
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 里