推荐一个博客 #recomended #blog
@yifenshijie （已经废弃，请转到博客）
我很喜欢它的内容，观点很有意思、面向用户方面的技术讲的也很新颖贴近生活

#China #life

Exactly correct. This is why they have nice things in Hong Kong.

我们忘记无关内容，开始讲这个很辣鸡但是依然可以用的解析组合子。

昨天我们说了，如何去解析 satisfy, charP, elemP, kwP, wsP, ws0P 并且提供好看的错误标识
现在是组合解析器的时候了：以上解析器皆可被用于哥哥（貌似）解析器，来实现顺序解析和循环解析（递归不支持，如果需要的话解析程序得自己写）
由于是基于无法重置字符流、简单函数闭包组合的方式，视窗有限并且无法做到在任何解析器失败时都可以重置（消耗的字符已经也只能消耗了，无法回到从前出现第二次）
所以所有这些哥哥 都很废（因为 FP.js 也只是个弟弟...），哥哥不能再组合自己的兄弟、只能组合不消耗字符 / 最多 lookahead 一个字符的弟弟 也是没有办法的事情呢（要不然就要使用 workaround）

seq, possible, lookahead1, someFold, manyFold

+ seq(ps, folder, msgr)
这个哥哥是顺序解析弟弟的。

ps = p.seq([p.satisfy(x => x.startsWith('--')), p.elemP(['mode', 'quiet', 'version']), p.kwP('ok')]); pp = p.run(ps);

> pp(['--version', 'mode', 'o', 'k'])


Either { inner: [ '--version', 'mode', 'ok' ], left: false }

这里我们组合了 satisfy 和 elemP、kwP
注意 kwP 的行为是正常的，它本来就是字符流的解析器（它不叫 listP）
它的行为就是阅读每个项目的第一个字符（在字符流里，这肯定是一个字符而已）、和需要的 keyword 比较，如果成功则判断下一项，失败就完了

如果你使用 possible 和 kwP 的组合，务必注意：kwP 实际上只能区别开头的一个字符，如果有成功的情况，万事大吉
如果失败，请 务必 让 possible 和嵌套它的组合也一起失败，不然就是未定义行为（可能发生莫名其妙的解析错误，因为 kwP 做不出能够在失败时重置输入流的担保）。
比如 cat 和 cab 就分不清了（都是 c 开头）但是能够分出 cat 和 dog（一个 c 一个 d）
（题外话，kwP 这个名字应该改成 stringP 的，此外，它的功能也应该被泛化成列表解析，而非字符串解析....

> ps = p.seq([p.kwP('你好', '我不好？'), p.kwP('世界', '404 Not Found')]); pp = p.run(ps);

> pp('你')

Left('Parser failed @<feed>:1:1 (pos=1@<eof>), sequence item 0: Unexpected EOF. Expecting keyword <你好>@1 我不好？')

> pp('你好')

Left('Parser failed @<feed>:1:2 (pos=2@<eof>), sequence item 1: Unexpected EOF. Expecting keyword <世界>@0 404 Not Found')

> pp('你好世界')

Right([ '你好', '世界' ])
> 

pp('你好世界哈').toString()

'R(你好,世界)'

seq 使用的 match folder(这个名字有点莫名其妙) 真正的魅力在于可以快速创建 AST
比如我们有一门叫做 def 的语言，它的 Item 规则是这样的：
<def> ws name ws0 <=> ws0 value
假设 value 肯定是 "abc" 这种的，则实际上可以这样：

function DefItem(_d, w0, name, w1, _eq, w2, val) {
  this.wss = [w0, w1, w2];
  this.name = name;
  this.value = val;
}

> ps = p.seq([p.kwP('def'), p.wsP(), p.someFold(p.elemP(['a','b','c','d'])), p.ws0P(), p.kwP('='), p.ws0P(), p.someFold(p.elemP(['1','2','3'])) ], p.makeNew(DefItem))
> pp = p.run(ps);

我们试一下

演示方便就不写复杂了

+ possible(ps, msgr)
这个哥哥可以组合很多弟弟的可能性

+ someFold(p, folder, msgr)
这个哥哥顺序解析弟弟、直到解析不了 return f(f(f...(v, x), y), z)

+ manyFold(p, folder)
这个哥哥首先看弟弟能不能被解析，如果不能直接成功 return v，重复解析弟弟、直到解析不了

+ lookahead1(pmap, flmap, msgr)
这个哥哥首先判断 pmap 是个 array 还是个 object
如果是 object，pmap 的 key 是下一个字符的可能性，value 是处理这个可能性的函数
如果是 array，pmap 的 key 是一个谓词函数，lookahead1 以下一个字符尝试找到满足的函数，并且在 flmap 里找到这个函数名字的键，就是它的处理器。
任何不匹配都会导致解析失败

啊... 这个『无论怎么样都要加花括号』『不要使用 i++』原则还真是蛮重要的，我都没有想到可能会被解析成不知道什么样子....

开始我利用了 i++，可是没有想到：

1. 如果某次判定失败，则 for update 块的 i++ 一般来说会运作（但不可能大于 str.length+1，因为那时已经 break (&&短路)）
2. 如果第一次判定失败，则 i 为 undefined，失败
如果成功，则 for 后 i 是 str.length+1，问题是，在 for.predicate 里更新变量... 本身就是很差的编程风格
这样就出现了一个问题：
1. 如果最后的条件不符合，i 会被更新，但是条件实际上不符合，导致了
"你_世_" 这样的也能 match....
人间之鉴...

这类模板化的循环，应该以可读性为主... 这点很多嵌入式软件设计的例子很好，都是模板化的判断
我看不起模板化（实际上我在 JavaScript 这样的层次也使用 C/C++ 的模板逻辑风格），可是这却导致了难以察觉和修复的错误的产生...

另外的一个 #人间之鉴 ：一定要理清思路再下手，尤其是隐式上下文的问题，如果各种加 Workaround，你就会进入无限 REPL 和修代码加 case 狂猜的状态无法自拔，最终会浪费掉大量的时间。 如果成功则最终代码会令人莫名其妙而且往往有比它好十倍的解决方案；如果失败，则你就白白浪费了几个小时的时间...

什么人间之鉴，但的确是有点莫名其妙。这个问题我最终没有解决，
'2' 和 '=' 看起来是一模一样，可我不知道为什么差一个空格两个空格就会有问题

我已经没法去想了，对我来说这真的就是莫名其妙，很对不起，也很对不起我自己... 坐了这么久、盯着屏幕，但是没有任何进展并且模拟的都成功、REPL 全不符合预期，我根本搞不懂，为什么『两边』还不一样，而其他结果全都正确。

对不起，真的没办法了，我真的两面 方法都试过了，可是用了很长时间，依然没有办法，而且，我不知道为什么 两个完全相同的解析器还『不一样』，为什么 '=' 和 '2' 还不一样、为什么同样的循环，一会对一会错... 但我真的没法想办法弄正确了，我已经尝试了很久，没办法再继续这样可能没有希望的事情... 或许未来再写就会明白吧...

（给自己）提示一下：其实这个问题的『疑点』都是编程错误和 L-R 扫描的结果而已，是对称的，但是循环和空格跳过/非空格保留上存在控制流的问题；本身也和组合子使用的流架构不好有关

以后如果再写，我不会再写错了.... 真的对不起自己啊

目前，使用 workaround.

#China #HK #Low

这全 TM 要怪中国大陆政府，为什么要说一套做一套、为什么有潜规则还一定要推行到香港去、干涉香港的自由环境，简直莫名其妙，怪不得现在一片反对声，全 TMD 怪自己瞎搞，控制欲太强

一面说避免被利用，一面加紧钳制，这倒车吃枣要 💊

中央这个样子是不行的！ 🐸👎

相：

https://lih.kg/1397150

辣鸡处理方式 #Zhihu

知乎读到这篇回答的时候觉得终于有一个脑子正常的人说暂停台湾自由行这事儿了，结果读完之后想点赞才发现已经因为“政治敏感”被建议修改了，之前他们说知乎已完的时候我还觉得至少可以当做一个渠道兼听一下，现在才发现已经只准赞美，完全没有信息量了 pic.twitter.com/9I02QyU9sP
— lobatt (@lobatt) August 1, 2019

言行不一致，不知道中央里哪位脑子进水了，怎么能这个样子呢？

今天咱来讲一个控制流分析的问题, 可能有助于大家提升自己阅读代码的效率和 Get 编程者 point 的能力.

原图片正在请求转发中... 下面是代码

private static boolean isPasswordAcceptabel(final String passwd) {
  if (passwd.length() == 0) return false;
  for (int i=0; i<passwd.length(); ++i) {
    if (Character.isDigit(passwd.charAt(i)) return true;
  }
  return false;
}

(刻意使用了规范的循环 init next update 和缩进)

然后大家看到了,就很迷,首先是没看懂的人觉得莫名其妙
然后大部分人看到这个 if 会觉得欸,为什么是这个样子,然后琢磨一会发现,噢,为什么要这么写呢? (校验字符串, 本来应该确保只包含字符, 却变成存在符合条件的字符就可以...)

这个程序呢，是 pass.isNotEmpty() && exists c in pass: isDigit(c)

可是读的都不快,我读了一下,虽然速度可以但我存在误解(以为是上面说的那种正规思路,就是 forall x in xs. predicate(x)),而且,现在这是从程序分析直觉的角度看一下:

首先这个程序本来可以用 kotlin 写

fun isValidPass(pass: String): Boolean {
  if (pass.length == 0 ) return false
  pass.forEach { if (Character.isDigit(it) return@isValidPass true }
  return false
}

程序的目的明确了一些.

然后还可以用 Haskell 写,你会发现 Haskell 的表示最明确，虽然咱没有使用副作用，一切可能有变化的东西都是参数传递

isValidPass :: String -> Bool
isValidPass "" = False
isValidPass (c:cs) = (Char.isDigit c) || isValidPass cs

那么为什么这个程序能这样转换成这种 “等价” 的 Haskell 声明呢？其实这是一个 immediate 的问题

大家看到这个程序呢

fun isValidPass(pass: String): Boolean {
  if (pass.length == 0 ) return false
  pass.forEach { if (Character.isDigit(it) return@isValidPass true }
  return false
}

这是一个比较普通的遍历判断算法，先找有几个出口：三个

+ ("") = false
+ str.each { it isDigit } = true
+ || false

非常模板的程序
那看不出来是因为不明显（跑
来回到 old-school 的 Java

private static
boolean isPasswordAcceptabel(final String passwd) {
  if (passwd.length() == 0) return false;
  for (int i=0; i<passwd.length(); ++i) {
    if (Character.isDigit(passwd.charAt(i))
      { return true; }
    else { continue; }
  } // broken
  return false;
}

这就很明显了，

+ 首先，如果 passwd 是 ""（length=0 只有这一种 case），则 false
+ i=0，如果 str[i] || (i < str.length && str[i++]) （表达式折叠）则 true
- 上面的就是 forall i. str[i] || str[i+1]，显然 i 的 bound 是 (0..str.length-1]
+ 否则 false

那考虑一下 for, if ... break 控制流的后件，就知道了，这是一个表达式链条

+ 如果 i 超出索引则 false（break 后到 func scope 的 return false）；如果 str[i] 是 true，则 true (1)
+ 否则进行下一项，如果 i+1 超出索引则... (1) （利用赋值副作用）

那么就是这些了，大家记得控制流分析的入门思考 方式哦（跑
编程的时候，为什么不面向 contract 编程呢？（跑
自己试着断言/收束 一下某个变量 和一些参数的关系

这里更迷

那咱来看一下这个 继续 🐱

我们刚才说道了第一个组合解析器 — seq 函数，现在测试一下
首先，你需要同步 FP.js 库的版本，以引入新的一些抽象操作

const p = require('./fp').parserc;

function DefItem(_d, w0, name, w1, _eq, w2, val) {
  this.wss = [w0, w1, w2];
  this.name = name;
  this.value = val; }
ps = p.seq([p.kwP('def'), p.wsP(), p.someFold(p.elemP(['a','b','c','d'])), p.ws0P(), p.kwP('='), p.ws0P(), p.someFold(p.elemP(['1','2','3'])) ], p.makeNew(DefItem)); pp = p.run(ps)

由于 FP.js parser combinator 本身的不完善和 buggy，空格数据不对 很抱歉 没法修复

咱有了这个 pp 解析函数就可以开工了，测试解析器！

> pp('').toString()

'L(Parser failed @<feed>:1:1 (pos=1@<eof>), sequence item 0: Unexpected EOF. Expecting keyword <def>@0 )'

> pp('def').toString()

'L(Parser failed @<feed>:1:3 (pos=3@<eof>), sequence item 1: at least one whitespace)'

> pp('def a').toString()

'L(Parser failed @<feed>:1:5 (pos=5@<eof>), sequence item 4: Unexpected EOF. Expecting keyword <=>@0 )'

> pp('def a = 2')

Either {
  inner: DefItem { wss: [ 1, 3, 1 ], name: 'a', value: '2' },
  left: false }

> pp('def abcdd = 2')

Either {
  inner: DefItem { wss: [ 1, 3, 1 ], name: 'abcdd', value: '2' },
  left: false }

> pp('def abcdd = 22')

Either {
  inner: DefItem { wss: [ 1, 3, 2 ], name: 'abcdd', value: '22' },
  left: false }

> pp('def abcdd =122')

Either {
  inner: DefItem { wss: [ 1, 3, 0 ], name: 'abcdd', value: '122' },
  left: false }

> pp('def abcdd=122')

Either {
  inner: DefItem { wss: [ 1, 0, 0 ], name: 'abcdd', value: '122' },
  left: false }

好耶！它可以正常工作！It works！

— 包装你的解析器

如果只能这样的话，是不可以的呢（不是特别友好）
我们来写一点 错误提示 和更多的 seq 规则 吧！

let numP = p.someFold(p.elemP('0123456789'.split(''), 'digit'), [0, (a,x) => a*10+(x-'0')], f => 'number value expected');

这里提到的是一种解析手段，FP.js 的组合子解析器就是这样 — pmatch/pfail，并且存在返回值随便

let idents = 'abcdefghijklmnopqrstuvwxyz'.split('');
let nameP = p.someFold(p.elemP(idents, 'ascii letter char'), ['', (s,x)=>s+x], f => 'identifier expected');
let kw_DEF = p.kwP('def', 'definition item');
let sym_EQ = p.charP('=', 'equals infix');
let __ = p.wsP(), _ = p.ws0P();
ps = p.seq([kw_DEF, __, nameP, _, sym_EQ, _, numP], p.makeNew(DefItem)); pp = p.run(ps)

好耶！

> pp('def a=a')

Either {
  inner:
   "Parser failed @<feed>:1:7 (pos=7@`a'), sequence item 6: number value expected",

> pp('def 123=1z23')

Either {
  inner:
   "Parser failed @<feed>:1:5 (pos=5@`1', next=`2'), sequence item 2: identifier expected",

> pp('def abc=123')

Either {
  inner: DefItem { wss: [ 1, 0, 0 ], name: 'abc', value: 123 },

— 语法的规范

FP.js parserc 支持类似 LL(1) （但归纳和实现方式不同）的文法
并且可以随便插入扩展解析器（这是当然的！）

我们的 『def』语言，需要先指定一个规范：它的具体语法是怎么样的
然后，因为 FP.js 的废柴，我们要将这个语法 LL(1) 合法化，使得它可以被用于解析组合子。

DEF 语言是一门简单的 DSL，让我们自由地使用 FP.js 的『解析组合子』来实现它的解析器！
这个语言的用途，是描述一个 HashMap（JavaScript 的 Object）

TheDefLang = {{ Def }}
Def = <def> Name <=> Value NL
NL = '\n'|'\r'
Name = ('a'~'z'|'A'~'Z')+
Value = Bool | Num | Str | Name | Array

Bool = <true> | <false>
Num = ('0'~'9')+
Str = <"> char* <">
Array = <[> (Value <,>)* Value? <]>

我来解释一下：

a b 表示项目按顺序出现，比如 <hello> <world> 只是匹配 helloworld 关键字
(a)+ (a)* 表示 a 重复，至少一遍 / a 重复，可以 0 次
'0'~'9' 就是 0123456789 字符
<> 里包裹的是关键字
a | b 代表可能是 a，也可能是 b
a? 代表 a 可能没有也可能有

FP.js 的 parser combinator 虽然废，但是兼容这种文法。怎么样呢？

这个语言可以举出的例子：

def a = 1
def b = "string"
def boo = true
def ary = [a, b, false, "string"]

如何来解析它呢？

大佬们 已经见识了 seq, someFold, manyFold 并且开始了解它们
已经认识了解析器的顺序和循环

接下来让我们认识解析器的分支 — lookahead1 和 possible 构造
首先，请从 GitHub 拖下最新的 FP.js，里面加入了一个 notElemP...

const p = require('./fp').parserc;

— 解析组合子是代码复用的高境界产物

所以，请我们复制一些个还能用的定义：

let numP = p.someFold(p.elemP('0123456789'.split(''), 'digit'), [0, (a,x) => a*10+(x-'0')], f => 'number value expected');
let kw_DEF = p.kwP('def', 'definition item');
let sym_EQ = p.charP('=', 'equals infix');
let __ = p.wsP(), _ = p.ws0P();

我们的 name 语法得重置了（一般都是 letter letterOrDigit*），不过这里我们不重置

那么要实现这么一个了不起的语法（迫真，不过其实你实现了这个之后，类似 JSON、TOML 这样的语法的解析器也不难做了，YAML 这种你需要加一个手写子解析器）

首先咱得做好理论准备，是吧？ 所以感兴趣的朋友请耐心地接着看，你马上就要自创一门配置文件语法了呢~ 而且，这个语言的代码还可以在 JavaScript 里被求值为标准的 object，是不是很 Happy 呢~

要解析 [1, 2, 3] 这种列表，我们就得先重视 FP.js parserc 的一个缺陷 -- seq/manyFold/someFold 里不能内嵌 seq
这是为什么呢？因为你输入的字符串不是魔法的就被一大堆松耦合的解析器抽提了句子结构，而是通过一个 Lookahead1 『流』(stream) 输入的：比如你有两个 charP

pp = p.run( p.seq([p.charP('H'), p.charP('i')]) );

这样我们就得到了一个解析 'Hi' 的解析器，不过这是个简单的例子，如果我们从输入数据（就是字符）流的角度看：

输入流是 tryLookAhead1Iter`Hi`：
如果 'H' 解析失败，则 seq 也会 pfail(parser fail)，并且下一个字符是 'H'
如果这个 seq 上面是还有一个 seq/some/many 呢，则上面的 seq 也会解析失败
如果这个 seq 上面是有一个 possible/lookahead1，则会就这这个 'H' 进行下一次解析（工作符合预期）

这是因为 seq 成功在『pmatch』解析成（所有子解析器都匹配）功和『pfail』解析失败，所有解析器都回滚的情况下保证了输入流符合预期（成功则矣、不成回滚输入流到进入时的状态，这是因为第一个字符 pfail 的时候保留了当前字符 'H'，而 seq 本身的 next 不会执行）

瞎猫撞着死耗子 -- 碰巧成功符合预期。

那咱知道了这一点 -- 就是 seq 里可以随便嵌套 seq、需要的时候（保证只有 match 的可能，最多只能有一个 seq 会被安排解析输入流，或者 seq 失败的的一定只可能是第一个解析器）可以在 possible/lookahead1 里嵌套 --- 不过有个问题，如果第一个解析器 charP`H` 成功并且第二个失败会怎么样？ 这就爆炸了，因为 seq 失败的时候，不能把流回滚...

如果父层是 possible，则下一个尝试就是在流的不同位置 'i' 进行了，你们这个样子不行的！
所以就不能用来解析 Value (',' ws0P ValueP ws0P | ']'); 可能，我们需要类似这种解析器啊！

不要忘了类 LL(1) 的限制 — 每个子解析器，最多只向前看一个字符就决定是 match 还是 unmatch，所以利用 Feeder 架构 charP, elemP, notElemP, kwP 什么的都可以正常工作，可是 seq([charP, charP]) 就不可以

所以我们来看看到底，这个列表的语法是什么：

List = '[' ws0P ']' | '[' ws0P ValueP { ws0P Value COMMA ws0P} ']'
COMMA = ','

我们这么说：

match("[ ]")
match("[ 1, 2 , 3 ]")
unmatch("[,]")
unmatch("[1,]")

有时候你会发现循环的东西还是比较有意思的，好像总是要弄个特例 -- 1/0 这两个特例
它等价：

List = '[' (ws0 Value ws0 { Value ws0 ',' ws0 })? ']'

那就有一个问题 -- 废 的 FP.js 解析组合子，无法弄那么多分支（不能在 possible 里使用 sequence 解析器），如何去解析这种语法？
答案已经给出来了 -- 等价代换！

-- 奇妙的等价代换

List = '[' ws0 ']' | '[' (ws0 Value ws0 { Num ws0 ',' ws0 }) ']'

符合 LL(1) 的预期吗？
我们先展开 ? (optional) 解析器，把 (|) possible 解析器左边两边都有的操作忽略掉进行合并。
为了等价，右边也一样

List
= '[' ws0 ']' | '[' (ws0 Num ws0 { Num ws0 ',' ws0 }) ']'
= '[' ws0 (1 vs. 2) Num ws0 { Num ws0 ',' ws0 } ']'
= '[' ws0 (Num ws0 { Num ws0 ',' ws0 } | ']'
{- Reorder branch priority -}
= '[' ws0 (']' | (Num ws0 { Num ws0 ',' ws0 } ']') (1)

我们看文法 (1)，它服不符合 LL(1) 的文法呢？符合！
因为解析完 ws0 后，我们 possible([charP, seq]) 就可以了，如果 charP 成功，则列表已经结束、如果失败，则解析 (Value ws0 {Num ws0 ',' ws0} {- 直到 -} ']')

这个语法也是符合 LL(1) 的 -- 不过还需转化一下
因为 seq/fold {Num ws0 ',' ws0} 在失败时是无法完全重置的，虽然或许能（在 Value 不能识别 ']' 时）瞎猫再次撞上死耗子，但是我们不能指望次次走运。
(Num ws0 {Num ws0 ',' ws0} ']')
= Num ws0 {']' | Num ws0 ',' ws0}
只需把 ']' 放在前面就可以正确处理这种情况（很难看，而且不能区分错误的方法... 迫真 所以还是用上面的手段吧）。
因为后面的 Num ws0 ',' ws0 的第一项的确可以区分列表是否已经结束，而如果第一项可以解析后面却解析不了，说明用户输入是错的。

-- 编程实现

既然咱理论做足了，为什么不写码实际去尝试一下呢？
说的天花乱坠，不如实际下地干活。不能饿肚子。

> const p = require('./fp').parserc;
先引入我们优秀的 FP.js 先生（迫真）

> let numP = p.someFold(p.elemP('0123456789'.split(''), 'digit'), [0, (a,x) => a*10+(x-'0')], f => 'number value expected');
定义一个 number parser
> let __ = p.wsP(), _ = p.ws0P();
方便空格。

//'[' ws0 (']' | (Num ws0 { ',' ws0 Num ws0 } ']')
> let List_ItemsP = p.manyFold(p.seq([p.charP(','), _, numP, _], xs => xs[0]));
> let ListP = p.seq([ p.charP('['), _, p.possible([ p.charP(']'), p.skip(']'), p.seq([numP, _, List_ItemsP, p.charP(']')]) ]) ]);

possible 里引入的 charP(']') 不得不加上 p.skip，因为如果没有 match，则 charP 会自动 dup 一次 LastItem 使得后面的流上下文不正确（因为这个功能本来是为了自动 revert 父 seq 解析器的 next 操作的... 可是实际上，自己失败了 seq 不会 next... 全怪 some/many 实现不对，没有帮弟弟解决这个问题 设计有问题）

好了，测试一下

let pp = p.run(ListP);