原生Python寫parser

如果不是我經過一天的瞎搞搞出來的這個新辦法的話，我已經不喜歡寫parser了。。。(由於這個方法是我自己瞎搞出來的，雖然和大佬們說的parser組合子有點像，但估摸著還是naive... 所以有大佬看的話，笑笑就好...

四個月前的我非常鬼畜，腦袋裡只知道狀態機大概是什麼樣的（通過字面意思試圖理解含義，同理，遺傳演算法，機器學習這些都可以通過字面意思來研究...），這樣來寫parser(雖然當時我不知道這個叫parser), 腦袋裡時常裝著十幾二十幾個狀態，互相跳轉，一團亂碼。于是之後我就不想寫了。

昨天我想刷題，然後去codewars上寫了兩道看起來對自己比較簡單的紫題後，發現My Language(我當時還沒用Js寫過題，只有Python、Java寫過)里剩的題基本都是解釋器，我看著就難受...

演算法題呢，冰封那個扔雞蛋昨天沒讀懂，那個高樓大廈的演算法又寫不來，然後我就找啊找。

最後折中找到了一個解析Ascii85編碼的題(如果我哪一天開始做不到3kyu的題，就說明我開始養老了。...

一開始我要知道它是Parser我肯定不會去做。

然而寫到中途，關鍵步驟都弄出來了，但是一些邊角情況感覺有點亂。因為昨晚還寫了一個church number的水題，覺得很漂亮，於是心底不願意用OO來處理這些邊角情況。

所以花了一個下午研究如何漂亮地解決問題。

然後我舉幾個例子，表達一下我今天下午的所感所悟。

Parser

parser = lambda f: lambda string, parsed, ok=None : f(string, parsed, ok)nparser_continue = lambda string, parsed, ok=None : (string, parsed, True)n

parser是一個抽象解析器，你需要給它定義一個解析方法才能以解析。

parser_continue這個是一個跳過步驟的parser。

一個具體的Parser對象是callable的，有三個參數接受。第一個參數是未parsed的字元串，第二個參數是一個parse的結果，初始其實是一個空列表， 第三個參數，表示一次parse流程中，一組有優先順序的parser是否已經處理結束。

從Ascii256到Ascii85的轉化，一般情況對原始字元串以4個為一組進行切分，一般處理為長度為5的Ascii85字元串。我們假設已經寫出了一般情況的解析方法，名為_to85。

那麼對一般情況的Parser，先定義一個抽象方法chunk。

(因為各個語言里，chunk函數的意思和這裡分批次做解析看起來很相似，而我時而不太會命名，這裡就用chunk

chunk = lambda n : lambda f: parser(lambda string, parsed, ok: (string[n:], append(parsed,f(string[:n])), True) if not ok else parser_continue(string, parsed))n

chunk接受第一個參數n後，表示該parser按照最大n個為一組進行解析。

接受第二個參數f後，表示解析方法為f。

則一般情況下，從Ascii256到Ascii85的parser是

chunk_encode = chunk(4)(_to85 )n

還是很清晰的。

同理，當我告訴你從Ascii85到Ascii256的轉化，是以5個字元為一組進行，且一般情況的函數為_from85後，你是否可以寫出對應的parser呢？

嗯...是這樣。

chunk_decode = chunk(5)(_to64)n

然後有一些特殊情況，例如從256到85時，如果一組字元全為0，則解析為z

zcompress = parser(lambda string, parsed, ok: parser_continue(string, parsed) if ok else zcompress_ok(string ,parsed ))nzcompress_ok = parser(lambda string, parsed, ok=Nonestring[4:], append(parsed, "z" ), True) if string.startswith("0"*4) else (string, parsed, False))n

這東西，我叫它z壓縮，名字我隨便取的...

zcompress這個parser的優先順序要在chunk_encode的前面。

先寫一個按照優先順序組合parser的抽象方法

parser_combine = lambda *f : lambda string, parsed, okstring,parsed, False) if not len(f) or ok else parser_combine(*f[1:])(*f[0](string,parsed, False)) n

然後我們把兩個parser按照正確的優先順序組合起來。

encode = parser_combine(zcompress , chunk_encode)n

而對於85到256，也有一些特殊情況，比如z解壓縮(當然這也是我取的名字

zdecompress = parser(lambda string, parsed, ok: parser_continue(string, parsed) if ok else zdecompress_ok(string, parsed)) nzdecompress_ok = parser(lambda string, parsed, ok=Nonestring[1:], append(parsed, "0"*4), True) if string.startswith(z) else (string, parsed, False)) n

它把字母z解壓為4個0

組合一下

decode = parser_combine(zdecompress, chunk_decode)n

然後parser是怎麼執行的？

抽象方法如下，接受一個parser組合列。

parsing = lambda f : lambda string, parsed, ok =None : .join(parsed) if not string else parsing(f)(*f(string, parsed, False))n

然後從256轉化為85的方法和逆方法就是

_toAscii85 = parsing(encode)n_fromAscii85 = parsing(decode)nfromAscii85 = lambda string : print([ord(i) for i in string]) or andThen( unbox, lambda str:_fromAscii85(str, []))(re_clean.sub(,string))ntoAscii85 = lambda string : print([ord(i) for i in string]) or andThen(lambda str:_toAscii85(str, []), box)(string)n

（涉及到的一些方法，比如andThen就是Scala那個andThen， unbox表示把"<~xxx~>"轉成"xxx", box是它的逆。

舉一個使用例子

>> fromAscii85(<~GA(]4ATMg !@q?d)ATMq~>)n>> whitespace testn>> toAscii85(fromAscii85(<~GA(]4ATMg !@q?d)ATMq~>)) == <~GA(]4ATMg !@q?d)ATMq~>n>> Truen

額，很簡單...

因為難的地方稍微沒那麼好看，因為出現了不只是lambda的東西。要是能用flowpython該多好（逃

這幾天做的題=>

thautwarm/My-Blog

（當然這些方面只是業餘興趣。