一个parserc的教程


#1

上篇主要讲token和parserc constructs

http://www.bilibili.com/video/av43674707?share_medium=android&share_source=copy_link&bbid=blpvX2tdOFw4DDpbJ1sninfoc&ts=1550320939363

中篇很短, 讲automatic lexer

http://www.bilibili.com/video/av43767045?share_medium=android&share_source=copy_link&bbid=blpvX2tdOFw4DDpbJ1sninfoc&ts=1550321098785

下篇是lisp解释器实现,30分钟,后半段基本靠jit overhead拖时间了。现在还在审核。


#2

小 bug?

function seq
function seq(p :: Parser{A}, atleast :: Number, atmost :: Number) :: Parser{Vector{A}} where A
    Parser{Vector{A}}(
    atmost === ∞ ?
        function (stream :: Stream{Token})
            res :: Vector{A} = []
            remained = stream
            while true
                (elt, remained) = p(remained)
                if elt === nothing
                    break
                end
                push!(res, elt.value)
            end
            length(res) < atleast ?  #= (I) =#
                (nothing, stream) :
                (Some(res), remained)
        end :
        function (stream :: Stream{Token})
            res :: Vector{A} = []
            remained = stream
            while true
                (elt, remained) = p(remained)
                if elt === nothing || length(res) > atmost  #= (II) =#
                    break
                end
                push!(res, elt.value)
            end
            length(res) < atleast ?  #= (I) =#
                (nothing, stream) :
                (Some(res), remained)
        end
    )
end
getindex(p :: Parser{A}, atleast :: Int) where A =
    seq(p, atleast, ∞)
getindex(p :: Parser{A}, atleast :: Int, atmost :: T) where {A, T <: Number} =
    seq(p, atleast, atmost)

其中的判断条件 (I): if elt === nothing || length(res) > atmost(II): length(res) < atleast 都应该带等号吧。
即改为

  • (I): if elt === nothing || length(res) >= atmost
  • (II): length(res) <= atleast

视频中拿 match 举例

julia> match(r"\d{2,3}", "123456")
RegexMatch("123")

julia> match(r"\d{2,3}", "123")
RegexMatch("123")

julia> match(r"\d{2,3}", "12")
RegexMatch("12")

julia> match(r"\d{2,3}", "1")

julia> 

也能看出 match [2,3] 时,捕获 3 个就停止了,不带等号就要捕获到 4 个才会停止。

F# 那边也带了等号


#3

对的,谢谢指出错误!
我有点纠结怎么修改错误,因为视频有点长,录起来麻烦。。


#4

我又试了下,第二种情况的条件还得小改一下。

需要先判断 length(res) >= atmost,再去尝试 parse。
如果先 parse 一下,又刚好满足返回的条件(length(res) == atmost
remained 就会少一个 elt

function (stream :: Stream{Token})
    res :: Vector{A} = []
    remained = stream
    while true
        if length(res) >= atmost  
            break # 如果已经满足条件则 break 返回
        end
        (elt, remained) = p(remained)
        if elt === nothing
            break
        end
        push!(res, elt.value)
    end
    length(res) <= atleast ?
        (nothing, stream) :
        (Some(res), remained)
end

测试样例

mock_stream6 = [
    Token(:identifier, "a", 1, 2, 1, "..."),
    Token(:identifier, "a", 1, 2, 1, "..."),
    Token(:identifier, "a", 1, 3, 1, "..."),
    Token(:identifier, "a", 1, 4, 1, "..."),
]
@info parse(parse_id[1,2], mock_stream6) # should be len(result) = len(remain) = 2

#5

是的。你已经全懂了~( ̄▽ ̄~)~
我看了我python的代码,确实是两个判断中间夹parse.

但fsharp那边这个问题解决得很自然,大概这是一个fp比过程式优越的实例吧。。


#6

@woclass 感谢弹幕纠正! 比心心~


#7

话说在 Parserc(中) 里面最后调用 lex 时,最后怎么么跟了个 collect?

lex(text, convert(LexerTable, lexer_table), Reserved(), "a.txt") |> 
    ( x -> foreach(println, x) ) = collect
                               # ^ 视频中那是个啥符号?

collect 和那个奇怪的符号删了也没什么问题。


#8

是函数compose, \circ。
啊好烦,感觉我讲的时候还是很难发现听众不知道什么。。。


#9

你直接collect就好了, 不用foreach print


#10

想给听众讲懂一个东西感觉够呛,特别是在它们没多少主观能动性时。

  1. 讲的细了要不是自己鸽了,要不就是听众坚持不下去。
    典型例子:各种 MOOC 讲的够细了,坚持跟完的也不多;再就是鸽子们,b 站上Qemu + 汇编从头写操作系统的好像全都鸽了?(至少我关注的都鸽了)

上面是对观众水平没要求/要求很低的。好处就是看着门槛低,能骗来观众,我看这话题门槛也不低了,给观众提点要求也合适。

  1. 可以自己定一个 baseline,不一定要明确的写出来,心里有个数就行。
    讲还是按你自己的逻辑讲,超过 baseline 水平的就补充一下,或者给个链接/paper/MOOC/… 之类能补齐这部分知识的东西。

  2. 再就是默认观众是同行/知识渊博/主观能动性强…,可能和出去开会比较像(x并不)。
    github repo 一丢,只讲自己觉得有趣的、想要分享的部分,其余的都是细节,看代码嘛。
    又想了一下,好像这个程度代码也不是必须的…

1 -> 3 对观众要求越来越高,(理论上)自己讲的时候也越来越爽。
我感觉介于 2~3 之间可能比较合适,毕竟做这个事首先得自己快乐嘛,这样才有动力。(做人嘛最重要的是开心


还有你做这件事的目的也十分重要,展示一下 MLStyle.jl 是真好用、ParserC in julia(自从有了新锤子,钉过的钉子都要再钉一边…)、Lisp 解释器 in julia (证明新锤子>=旧锤子,和前一条可以并列/互换/…)…
目的多种多样:展示一下 julia/MLStyle.jl 能做什么、写起来很方便;跟教你怎么写;教你一个新的套路 等等。做视频的难度、关注的方向都有所不同。

如果我想讲 “写 ParserC”,可能的目的是:展示一下 MLStyle.jl 写起来很方便 + 教你怎么写 ParserC。
前者是我的主要目的,后者顺带。完成后者其实挺简单,我对自己要求低,给了 repo 就算 ok 了。
视频中就讲用了 MLStyle.jl 会变得简介/用起来方便/写起来爽的地方 <=> 我觉得爽的地方/我觉得你用也会爽的地方。
我可能还是会从头到尾手敲一边代码/过一遍全部的代码,就是给你串一串逻辑,知道楼是怎么一步步盖的。哪些些地方是核心,改了后面都得改;哪些是可选的/可以继续完善的。

当然现写有一个好处:能让大家看到你的思维过程,有可能还带 debug 的过程,怎样犯错误,然后修正。(zhihu 上有人就是这么夸 The litter xxxx 系列书的)

一些坑/预估超出 baseline 的地方就直接说:就这样写,想学见 ref[x],不深入讲/不讲。
大概就是类似 parser 里面用的正则这种。

想稍微讲一下这些坑也可以:拿b站上手写操作系统的那波人来说,一些坑很深的东西,汇编/中断/一些奇奇怪怪的硬件接口/也包括 makefile 这种,都是这一次要用啥,现给你讲一讲:让我们打开 Intel x86 巨著第三卷,先看目录再翻到 xxx 页,基本也就仅限涉及到的这一部分。
他们这种大概算是上述分类 1~2 之间的样子,想向 1 靠近(至少标题是这样)。
个人觉得这个有点鸡肋,你也没给讲懂,又多说了一堆零碎的知识点,让人不容易抓住重点,还浪费自己时间。

说了一堆,给强行下个结论:还是得看观众的积极性/主观能动性。所以说开心就好啦
积极性高,主动来找你讨论,视频之外 3 都能给讲成 1;积极性不高去看 1 都不会有然后。


#11

可能这种事线下确实会好一点,虽然各种不便。线下+直播或许能解决一部分问题。

讲一个小故事:
去过一次 tuna 的 金枪鱼之夜 就(目前)最新的那次。@dramforever 讲 Nix/NixOS。

我和我基友去的,严格算我基友日常参加此活动,我是准备去角里落暗中观察。
像我这样的好听众当然看了标题就把 NixOS 装上了,大概了解了一下;基友则是空手去的。待我们赶着晚高峰赶到了指定的小教室,发现就 dram 一个人,场面一度十分尴尬。幸好基友经常水群,看起来和他挺熟。
dram 说今天来的估计不多,所以活动估计要取消了,顺延至下周,不过既然有人来了,三个人凑一起就对着电脑讲,效率还高。不过过了一会 tuna 的部分其他成员也来了,大概又来了 4~5 个人。

然后就讲呗,我大概前面还能听个大概,跟着操作一番。后面就就各种知识盲区了,默默合上电脑。
基友则不一样还能时不时提问/吐槽一下。讲完之后,大家还让 dram 现场拿 NixOS 编译一次看看,并深究了一下 依赖是怎么管理的、到底 link 到了哪里。我大概能知道他们在讲什么,该补点啥,但做不到加入他们愉快的吐槽/玩梗。基友好像交流起来毫无障碍(是该多水水群了)。

听完一次金枪鱼之夜,我的最大收获应该是知道了 cat 的替代物 bat 自带高亮。
另外知道了 NixOS 是基于 Nix 包管理脚本语言构建的系统;构建过程可复现,函数式的优点;系统中相同的(有一些约束条件,可以理解为版本/hash)依赖就独一份;拿截断的 sha256 当路径/文件名;NixOS 啥都能更新,现换内核/libc 无压力;并可以多版本共存;换内核还是得重启;貌似还巧妙地绕过了 PE 头中某些字段的长度限制。

这是活动简介

介绍 Nix 包管理器和与之配套的 Nixpkgs 软件发行版,了解基于 Nix 的软件包使用、构建、定制、开发环境方面的内容,以及背后 Nix 的基本设计和简单原理。

这次活动,对我大概算上一楼的分类 2;对我基友算第 3 类吧。全程听下来 dram 是按第 3 类讲的,默认你有足够的基础知识,他只讲 Nix 的特点、有趣的地方、以及一些基础操作。
貌似 tuna 上可以下讲稿,也可以参考一下。虽然这个方向稍有不同
全程 2h 越往后,大家越兴奋、交流也越多。我觉得这种也十分不错,虽然说不出具体哪里好。
他讲的挺开心,听众听+交流也挺开心,我自己也有点收获,这也就足够了。

以上是小故事,感叹一下:还是跟观众的素质高,讲的爽啊。


#12

你们这个才是真正的社团啊。我个人对这种讨论是羡慕得要死。
而且你认识dram,好奇你是谁。。。


#13

不算认识吧,只是在 zhihu 以及其他地方看过他的文章。

没有机会线下去,也可以线上看看直播,tuna 上有录像下载的都是直播过的,直播的时候可以水群参与讨论。


#14

我看 “ Parserc(下)” 照着敲了一边代码,不过好像少点东西,报错 ERROR: LoadError: MethodError: no method matching >> 后面一串贼长,就不贴了。

(<<), (>>) 的定义都没给吧,目测放在 Combinator.jl 里,用的肯定是重载过的,不是 base 里原装的位运算。

“ Parserc(上)” 我看的挺认真的,应该不至于漏了两个函数。


#15

哇,我居然漏了这俩,抱歉。我把代码发你吧。。


#16

哈,有人愿意实现 PEG 吗?


#17

做。我现在是用haskell分析生成parser图,拿给julia再做代码生成。