🙈 那么... 还真是不能强行上递归呢。

其实左递归是真的... 难受了，所以还是算了

左递归，比如说

cidentifier
  = nondigit
  | identifier digit
  | identifier nondigit

匹配的时候就需要检查匹配栈了呢。

而这里的左递归

addSub
  = addSub "+" addSub — add
  | addSub "-" addSub — sum
  | mulDiv
mulDiv
  = mulDiv "*" mulDiv — mul
  | mulDiv "/" mulDiv  — div
  | number
ws = [ \t\n\r]
number = ws \d+ ws

比如说有个输入 1 + 1 + 1，解析 addSub
首先 匹配 addSub

addSub "1 + 2 + 3"

addSub
mulDiv
number "1"
"+" — add
addSub
mulDiv
number "2"
"+" — add
addSub
mulDiv
number "3"

总之，每次去检查递归栈，如果的确符合左递归的模式就成功匹配了
最后归纳出这个树

(add (add 1 2) 3)

#blog https://www.cnblogs.com/nano94/p/4020775.html #recommended

https://www.zhihu.com/question/266250146 #zhihu

左结合：

总不可能这样来『兼容』嵌套的二元运算

add$2
  = num "+" num

add$3
  = num "+" num "+" num

add = add$2 | add$3

也不可能来这样

op = "+" | "-" | "*" | "/"
bin = num { op num }

为啥解析的时就能创建好的结构，非得解析完了再去创建？

当然可以这样

bin = (num|bin) op num

就是左递归，可是就不方便

然后介绍了一个 chainr1 和 chainr1，用来进行表达式树的左结合和右结合

+ 结合性、优先级

* 的优先级比 + 高，就是说 a + b * c 解析后乘法离根节点最远
(add a (mul b c))

+ 的优先级和 + 自己一样高，但是 a + b + c 是
(add (add a b) c)
或者说
(a + b) + c
而不是
(add (add a b) c)

就好像 Lambda calculus 里，默认也是左结合的

f g x 的意思是 ((f g) x) 而不是 (f (g x))
haskell 里也是一个样子，所以要 f $ g x，要不然会炸

+ 所以有啥关系

adds = chainl1 numberP addOp

其中 addOp 是一个 Parser，解析 "+" 返回 (+)
chainl1 会继续解析构造直到无法成功解析

然后就可以组织出这种东西：

1 + 2 + 3

(1 + 2) + 3

或者说，它先解析一个 num addOp num, 用存下来的 lhs (number) 构造出一个 Op 作为 lhs
然后继续往下解析 addOp num, 继续用存下来的东西构造 Op，结果就成了

o' = Add 1 2
o'' = Add o' 3

chainl1 p op = do
a <- p
rest a
where
rest a = (do
f <- op
b <- p
rest $ f a b) <|> return a — rest unmatched

3 + 2 + 1

a = 3
op = (+)
b = 2
a = (3 + 2)
op = (+)
b = 1
a = (3 + 2) + 1
return a

这样，看来我还不是特别理解递归..

最后附赠给大家一点小玩意，从 Ruby 那学的，Ruby 果然是比 Perl 强，后者真的是不规范绝了

dig :: [a] -> [Int] -> b
dig x [] = x 
dig xs (i : is) = dig (xs !! i) is

emmm... 我描述不出这个类型... 不会 Haskell。没想到是这样 😐
算了...

{-# LANGUAGE RankNTypes #-}

printStringOrInt :: forall a. Show a => a -> IO ()
printStringOrInt x = putStrLn . show $ x

main = do
  printStringOrInt 1
  printStringOrInt "Hello"

直接写明 forall
可是不知道为什么，据说是因为有些平常的情况下可能需要 RankNTypes

https://en.wikibooks.org/wiki/Haskell/Polymorphism

foo :: (forall a. a -> a) -> (Char,Bool)
foo f = (f 'c', f True)

好像是可以这样

{-# LANGUAGE RankNTypes #-}

foo :: (forall a. Show a => a -> IO ()) -> IO ()
foo f = (f True) >> (f "String")

main = do
  foo $ putStrLn . show

就是说通过手动指定 Type variable 的 forall 可以使用 N 阶多态，而不是第一次 (f True) 确定了 f 是 Boolean -> IO () 就不允许再次判断了

https://en.wikibooks.org/wiki/Haskell/GADT #Haskell 啊...

辣鸡 Haskell，我还是回去用我的幼儿园 Java 好了

在提到如何解析有优先级和结合性处理的二元操作时，冰封哥也提到了左递归

首先，chainl1 的定义

chainl1 p o = do
  a <- p
  rest a
  where
    rest l = (do
      f <- o
      r <- p
      rest $ f l r) <|> return l

然后，chainr1 的定义，有点像 foldl 和 foldr 啊...
chainr1 就不能尾递归了

要构造 1 + (2 + 3) 这种程序结构，显然不能再『构造这一层，传给下一层组合之用』了，必须得『等待下一层解析完成』再规约到自己身上

chainr1 p o = scan
where
scan = do
l <- p
return $ f l (rest)
rest = (do
f <- o
r <- p
s <- scan
return s) <|> return f


... 好像是我自己写的时候理解不深刻弄错了？
这个是冰封贴的... 我方才才发现其实不必弄那么特殊，不就是保留个调用栈吗？

chainr1 p o = scan
  where
    scan = do
      l <- p
      rest l
    rest l = (do
      f <- o
      -- r <- p —开始我默写的时候多加了个这个... 居然也没觉出什么异常
      s <- scan
      return $ f l s) <|> return l

1+2+3 其实是要组成 1 + (2 + (3)) 的啊！

LLVM Cookbook 里面的递归下降解析器稍微搞基一点，支持自定义优先级，不过要支持的话理解了 chainl1 chainr1 的实现也不难操作，也就是个比大小而已

不过很幸运，要解析现在绝大部分编程语言都是不需要处理自定义优先级问题的，稍微难一点的也就是二维文法和 string interpolation，都不太需要递归

addP = chainl1 mulP $ binOp "+" $ \x y -> Op x "+" y
mulP = chainl1 oneP $ binOp "*" $ \x y -> Op x "*" y
oneP = numberP

对于右结合的例子：

pwrP = chainr1 numberP $ binOp "^" $ \x y -> Op x "^" y

像这样，就可以解析二元表达式了（包括类似 Java 里的 . 操作符）

以上是对使用 Haskell 编写灵活的 Parser （下）文章的简单解说。
感谢相关人员的学习和付出


至于为何左递归就能实现优先级了，我们来考虑一下：

1 + 2 * 3

如果我们完全用 chainl1 的话会被解析成 (1 + 2) * 3
但是我们这么解析

addP = chainr1 mulP $ binP "+" (+)
mulP = chainr1 numP $ binP "*" (*)
numP = satisfy isDigit

题外话，我连 compose 都差点不熟悉了...

(.) :: (b -> c) -> (a -> b) -> (a -> c)
(f . g) x = f (g x)

isDigit :: Char -> Bool
satisfy :: (Char -> Bool) -> ReadP Char

不能是 satisfy . isDigit... 至少，就
b@satisfy = (Char -> Bool)
b@isDigit = Bool
是不匹配的...

回到无聊的正题...

正是因为 addP 的元素是 mulP，所以 + 的优先级就比 * 小（结合 *，但是求值的时候是后序遍历）
或者，如果不是也没有关系，反正可以堆砌很远（直到栈溢出，因为一般来说栈比较小容易溢出）

比如 1 + 2 * 3

先假设没有考虑优先级，仅仅左结合是什么样，方便参考
l = 1
P 1
o = (+)
r = 2
= P (1 + 2)
o = (*)
r = 3
= P (1 + 2) * 3

如果有呢？
l = mulP = numP
P 1
o = (+)
r = mulP
l = 2
o = (*)
r = 3
= P return
1 + (2 * 3)

如果有，而且没解析到 * 号呢？

l = 1
P 1
o = (+)
r = mulP = numP
P (1 + 2)
o = (+)
r = mulP = numP
return (1 + 2) + 3

就得到了正确的结果，因为 chainl1 chainr1 都会在解析不出来的时候（一个 atom，没有 operation）直接返回 atom
这也就是 chainl1 这个 1 的来历

所以 r 在不是 operation 的时候可以直接是 atom （Haskell 里 GADT 树的 Tip）
也就直接导致了合适情况下 mulP 等于 numP 等于正确的结果

data BinTree a = Node (BinTree a) a (BinTree a) | Tip a

Oh 开销...

岂止是『有点』.... emm

祝大家新年快乐（呃...）好吧（）晚安，希望我能恢复快点，不要长痘... 😕

#Haskell #code

这玩意的使用方法：

首先这玩意是个计算器，可以这么玩
Sigma 本来是想当 prompt 的，可惜好像缓冲区刷新有问题

[DuangSUSE@duangsuse]~/Projects% ./BinOps
1+1
Σ:: We got: 1+1
= Just (1.0 + 1.0)
= 2.0

这种。
下面的都是示例算式
Σ:: We got: 1+1*2
= Just (1.0 + (1.0 * 2.0))
= 3.0
Σ:: We got: (1+1)*2
= Just ((1.0 + 1.0) * 2.0)
= 4.0
Σ:: We got: 0xFF_FF_FF_FF
= Just 4.294967295e9
= 4.294967295e9
Σ:: We got: 0xFF
= Just 255.0
= 255.0
0.5*10
Σ:: We got: 0.5*10
= Just (0.5 * 10.0)
= 5.0
3 mod 10
Σ:: We got: 3 mod 10
= Just (3.0 mod 10.0)
= 3.0
2**8
Σ:: We got: 2**8
= Just (2.0 ** 8.0)
= 256.0
log2 16
Σ:: We got: log2 16
= Just log2 16.0
= 4.0
sin 3 + cos 3
Σ:: We got: sin 3 + cos 3
= Just (sin 3.0 + cos 3.0)
= -0.8488724885405782
Σ:: We got: (1+2) * 3 + 3 * log2 8
= Just (((1.0 + 2.0) * 3.0) + (3.0 * log2 8.0))
= 18.0
1/0
Σ:: We got: 1/0
= Just (1.0 / 0.0)
= Infinity

- 一元求逆运算解析我写错了，没法用（一元求逆和 Rat 的 -xxx 字面量语法混淆了，我不该这样的...），暂时算了
有好玩的玩法跟我说，原理上面也写了。

还蛮好玩的，可惜不完整

#thinking #life #China 🤔

我觉得我之前有一次关于『儿童编程』提的建议不好。

虽然就儿童编程来说，我也算是老人了，我小学六年级在一位朋友的带动下认识了 Scratch、并且之前一段时间还去听过网课，但其实之前我的人际交流能力有很大的改善空间。

公交车上，一个带小孩的妈妈看到我拿着 Kotlin 极简教程这本书后，问我『这门语言是有界面的吗？』

我只后的回答果然还是极简... 说了一大堆，就是坦明有没有界面和是什么语言没有关系而已，这丝毫没有参考价值。

这种交流... 势必没有什么效果。

其实考虑到这位母亲的需求，应该是想给小孩找一个编程培训班，我本来应该给她提点相关的建议的，可是我却只是考虑到了技术上的问题，这就叫浅薄。

因为技术本来就是为生活而生的，不应该去抛开别的单单当一个疯子（排除合作的情况下）


其实，这么答或许才是真正好的：

呃，如果你说的界面，是指平常用的电脑上那些窗口、界面的话，其实和什么编程语言没有太大关系。

不管是新语言、老语言现在基本都可以做上面所说的那种界面，对于普通人来说能接触到的语言都可以写界面。

不过如果一定要给个建议的话，如果以后想让孩子能写『界面』，我建议不要学 C 语言，C 语言比较繁琐，编程效率很低，而且新手不容易写好，不适合用于入门选择。

现在有很多编程培训班，不管是网上的还是传单上的，基本都会提供很多课程选择，他们几乎都会提供能做出好看东西的课
不过和上面说的界面有点区别，更类似能交互的动画一些、编程的时候也可能是有界面像堆积木一样编程的，我觉得这个选择可能比较好，
如果要这么选，最好是选有创新、有资质、有自主研发产品的公司，不要相信说自己使用『外国技术』的，这种往往比其他的课好。

刚才阅读代码加强理解的时候忽然发现不对，这个 chianr1 怎么和 chainl1 是一样的，对着冰封的博客，发现我写错了...

r 要改成 scan

改了一下还是错的，然后我就上 Haskell 的 Text.Combinators 源代码抄了... 觉得没区别啊..