peg, ometa 解決什麼問題,ometa-js怎麼入門/正確理解和認知?

01-13

我自己想實現語言內部的dsl
於是找到了以下項目
但是很久都弄不明白他們到底是怎麼做到詞法/語法分析的?

參考:
pypeg http://fdik.org/pyPEG/
pegjs http://pegjs.majda.cz/
ometa http://www.tinlizzie.org/ometa/
ometa-js OMeta/JS 2.0 Workspace
很奇怪為啥我啃了很久文檔還是看不懂

為什麼中文資料非常少,貌似國內很少有人關心這塊?
同時我也發到了 segmentfault 上: peg, ometa 解決什麼問題,ometa-js怎麼(入門||正確理解和認知)

實際上PEG的定義本身就已經是一個可用的parsing演算法了，只不過直接按照定義寫的話，回溯可能造成指數級的時間複雜度。

入門的方法就是看Bryan Ford的Parsing Expression Grammars: A Recognition-Based Syntactic Foundation，這篇文章後面那些證明PEG性質的部分都可以略過不看，就看前面PEG的描述就行，然後就會寫一個遞歸下降的PEG parser了。還可以仿照http://www.cs.nott.ac.uk/~gmh/Parsing.lhs，用Monad來組織這些parser組合子，以免case語句滿天飛。到這一步你的parser已經可堪一用了。

如果要繼續優化的話，看Packrat Parsing: Simple, Powerful, Lazy, Linear Time，這篇文章中心思想就一句話：記憶化搜索。PEG是無狀態的parsing，存表格做記憶化搜索的話，時間和空間複雜度都是O(k*N)，k是你的文法里非終結符數目，N是輸入的字元串長度。而且這個不用原始文章里那樣折騰一個奇怪的鏈表，直接用C++存全局數組也能做記憶化。

實際上PEG跟LL(k)之類的文法共享了一個缺點就是本身是不支持左遞歸的，而很多時候你的文法不用左遞歸不好表達（比如中綴的算術表達式），那就看龍書的4.3.3，按照上面的方法把文法改寫成沒有左遞歸的版本。至於自動改寫，或者嘗試拓展PEG/Packrat使之支持左遞歸之類的工作，我沒有看過，題主可以自己看下。

我理解的PEG是針對於為語法分析器生成器提供一個容易消除二義性的描述文法。

常見的語法分析器生成器yacc/bison/ANTLR的描述文法，需要手動的消除二義性，PEG提供了一個更加簡便的消除二義性的描述文法，可利用如下PEG的文法規則：

Ordered choice: e1 / e2
And-predicate: e
Not-predicate: !e

對於手寫的語法分析器，不管使用CFG或者PEG描述都需要自己做到lookahead才能繼續往下parse。

參考資料：Parsing expression grammar

PEG 的思路和傳統的，從文法生成 Parser 的思路不同。

傳統上文法描述語言，Parser 是從文法生成的——不論 yacc 或者 ANTLR 都是這個思路。

PEG 則是描述 Parser 的行為，它的「文法」並不是傳統意義里的產生式文法，而是 Parser 的抽象表示。從 PEG 文法生成 Parser 的代碼只有幾十行。

搜索的時候發現譯言有人翻譯了維基百科英文的一部分，解析表達文法-維基百科，自由的百科全書。

我把這個譯言網上的文章轉載回了中文維基，還有很多工作沒做，不過格式應該看起來舒服一點，推薦看這裡：解析表達文法

並且感謝翻譯者。

http://arxiv.org/abs/1207.0443

這個演算法可以讓PEG支持直接和間接的左遞歸文法，不需要做左遞歸消除。

這裡面也提到Warth et al.的基於packrat的支持左遞歸的演算法是有缺陷的。

今天在pegjs的issue里看到的。pegjs的作者似乎不打算實現這個…… Add support for left recursion · Issue #231 · pegjs/pegjs · GitHub。

=== update ===

用golang實現了這個演算法，代碼不複雜，論文那些natural semantics如果看不懂可以參考下：reusee/paza · GitHub

不過實現了才發現從來沒有提過時間複雜度，這個演算法只是理論上正確而已。

路過,說點我知道的,幾個月前,我也有過寫解析器的想法,也搜索過這方面的資料,拿過裡面的example:javascript做練習,peg.js的語法文件相比於在網上能找到的比較少,能有的相關資料在這個網址都有了Home · pegjs/pegjs Wiki · GitHub,裡面的Projects Using PEG.js · pegjs/pegjs Wiki · GitHub你可以看看.我是有一點BNF/EBNF基礎的,當時自己的練習就是把BNF往PEG里寫,後來發現 ANTLR的功能更強大,支持的平台多,,就去用ANTLR了.如果你只是想寫DSL,不用想它的實現細節吧,知道怎樣用文法描述你的語言就可以了.如果你想吃透,那就去看編譯原理.希望能幫到你.

題外話,你可以看一下chaosim/peasy · GitHub和編程語言實現模式 (豆瓣)