相：

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);

我发现这个 ws0P 实现的果然还是不仅仅不对，而且还不能忽视它的不对...

它在有且只有一个空格的时候，直接把下一项目跳过了 然后继续扫描空格...

你说我这是设计个啥劲.... 放着好的 next 不用，反而舍近求远去用 duplast.... 根本没有组合的概念

真的是被自己蠢到了，为什么不懂得去复制自己的代码.... 非得再写第二遍

世界上不存在莫名其妙的问题，只存在会把简单问题弄复杂的傻人。（注意空格解析的结果是正确的）

又抓出一条虫子。刚才是不懂得『简单的』抄代码导致白白浪费时间，现在这个又是反面 — 过分依赖抄代码，改都不改想都不想导致的逻辑缺失

最终的解决方案呢？

const p = require('./fp').parserc;
let __ = p.wsP(), _ = p.ws0P();

let numP = p.someFold(p.elemP('0123456789'.split(''), 'digit'), [0, (a,x) => a*10+(x-'0')], f => 'number value expected');
let pa = p.seq([p.charP(','), _, numP, _], xs => xs[2]);
let List_ItemsP = p.manyFold(pa, [[], (v,x)=>v.concat(x)]);
let ListP = p.seq([ p.charP('['), _, p.possible([ p.charP(']'), p.skip(']'), p.seq([numP, _, List_ItemsP, p.charP(']')]) ]) ]);
pp = p.run(ListP);
不过得同步我最新的修复版本 FP.js...

... 我受不了目前这个辣鸡反向思维架构了，重构算了
为什么 seq 要多管闲事，不消耗字符还得手动弄个 keepLast，还能够多次 keepLast... 只是因为支持内嵌在 seq 里面， 我...

现在所有哥哥就是哥哥、弟弟就是弟弟，哥哥不再强迫弟弟 next 了

『当一个称职的哥哥、不再区分 possible 和 seq/some/many』
组合 不分家

从此 FP.js 的解析组合子无需再考虑『哥哥』是一个有强迫症的哥哥还是一个正常的哥哥了。
尤其是在组合的时候，绝对不需要了、不再需要了
不会再有莫名其妙多跳一两个字符的问题了，子解析器解析的了就跳、解析不了就不跳。解析不了 seq 直接失败、possible 尝试下一个解析器。
再也不会 seq 里嵌套 seq/many，还需要 duplast N （视嵌套情况而定，呵呵）次呦....

『以为是各种问题很奇怪，其实是因为思路不清晰，把简单的问题弄复杂了』