#Hardware https://github.com/itsFrank/MinecraftHDL

Verilog for MCHDL redstone 🙊 Wow...

原来 verilog 是这样的！

module bit2adder (
input x0, y0, x1, y1,
output o2, o0, o1
);

assign {o2, o0, o1} = {x0, y0} + {x1, y1}

endmodule

🤔 比 perl 简单一些？可是既然要给电路编程，就要写很多吧...

不会玩... #hardware

绝望，看来写不了了，就学点 Haskell 吧。

选择一下
写个 JSON Parser，不过必须得把某 Monad 组合子 Parserc 框架抄写下来，这个是没有技术难度的...
扩展这个计算器，支持 ** 和 mod 运算，支持十六进制和运算符结合算了... 🙈

https://ice1000.org/2017/07/27/HaskellParsers2/

要是我就选择第二种。我才不去做没有提升空间的事情...

我们先左递归描述一下我们要解析的语法

input = binOp

binOp = addOp

opP x = do
ws charP(x) ws

addOp = numP opP('+') numP | numP opP('-') numP | mulOp

ws = whiteSpace

numP
= "0x" hexDigit
| digit+

hexDigit = satisfy (`elem` "0123456789abcdefABCDEF_")
digit = satisfy (`elem` "0123456789_")

... 好难看算了

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

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

左递归，比如说

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