會寫 Parser、Tokenizer 是什麼水平？

01-12

聽說會寫Parser、Tokenizer，就可以達到和王垠不相伯仲的水平，是真的么？上次林建入也是靠Parser、Tokenizer將C語言一代宗師薛非一舉擊潰的，Parser、Tokenizer到底有多麼高端？

謝邀。

我不僅會手寫 Tokenizer、Parser，還把AST解釋器、堆棧管理、垃圾回收一塊兒都寫了，擼了個五臟俱全的編程語言（Def 編程語言官方網站）。

什麼？你問我是什麼水平？然而並沒有什麼卵水平。我仍然在一家不知名的小公司，用著天底下最好的語言(PHP)，開發買菜的網站。

╮(╯_╰)╭

想當年C語言一代宗師 @薛非大戰水貨程序員@林建入時，正殺的天昏地暗，不想@林建入忽使出絕招Tokenizer！ @薛非中計落荒而逃。

不好啦！鬧大啦！程序員約架啦！！場面太血腥了！！！

從此見人殺人見佛見佛的Tokenizer大法開始在江湖暗中流傳。

幾載之後，歷史終於重現， @winter 大戰PLT界巨擘 @王垠，正殺的你死我活，忽然一道金光！一聲驚雷

—— 別廢話了咱倆比賽寫tokenizer！
@王垠就這樣倒在了血泊之中。

可見Tokenizer就是程序員界的降龍十八掌

........

@王垠：喂導演這劇情怎麼設定的，我壓根沒跟他開打呢啊，難道剛才一陣風就是他的Tokenizer大法嗎？

前幾年我上了一個為時兩個月的 compiler and execution environment 課

做一個 LR(1) parser builder 是這個課的課程設計

我覺得我的水平很渣但是也只做了一個星期所以應該沒啥難度吧。。。

不過也許因為我只測試過 parse parser builder 自己的 syntax 定義文件

也沒實現正則表達式匹配

樓主，我來答你這個模糊的問題。

Parser 和 Tokenizer 其實只是把無意義的字元流變得有某種意義而已。Parse 這個詞其實可以用在很多的地方，比如說只要你能在一個字元流中標識出所有的字元 a，你就在做 Tokenize 和 Parse。你可以看得出，Parse 和 Tokenize 有多難實際是針對編程的人的目的來說的。

如果目的簡單，Tokenizer 和 Parser 非常簡單，比如大學課堂上一個 toy language 的 Parser，或者你面試的時候考官出一道題讓你寫 atoi 函數，都是在寫一個簡單的 Parser。更何況現在編程語言的 Tokenizer 和 Parser 都是通過 lexer 和 yacc 這些程序來自動生成，是個了解過正則表達式的人照貓畫虎都會寫 Tokenizer 和 Parser。對於其他比較複雜的 Parser，比如針對一些 Markup 語（Markdown，RST，Org-mode，Asciidoc 等等）情況就很複雜了，專門做 Parser 也是可以去做 PhD 的。你可以在這裡找到相關的書：Parsing Techniques: A Practical Guide。

最後，我想說的是關於「高端」，知識沒有高低，只有你喜歡不喜歡而已。你自己買幾台機器用 GPU 編程就能開始自己的 Deep Learning 的研究；你自己買些設備來就能自己開始研究四軸直升機；你自己買個 Raspberry pi 就能開始自己編操作系統；你自己在你的電腦上什麼庫都不用就可以做一個和 OpenGL 一樣的 Graphics Rendering Engine；你同樣可以在你的電腦上花上幾個星期把 TCP/IP 協議完全實現一遍……例子不多舉了，這些東西在國內的學校大概不常見，但是在國外的學校做的都是這些實打實的東西。哪裡有做 Graphics 的人看不起做 ML 的人？哪裡又會有一個用 Haskell 的人看不起用 C 的人？我今天第一次聽說什麼一代宗師比賽寫 Parser 的事情。如果要比賽，根本不要比什麼寫某編程語言的 Parser，因為它只是一個熟練度的問題。我們做一件事情時間長了（或者受環境的影響），都會慢慢變得熟練。所謂的「寺廟旁邊的豬都會念經」就是這個道理（這個道理也見於 Surely You"re Joking, Mr. Feynman的 Latin or Italian 一章）。

到處有書教你做，到處有代碼給你抄，掌握一些別人早就搞出來的東西有啥好沾沾自喜的呢？這個充滿資訊的年代裡，學習大家都掌握的東西只是一個基本過程，沒什麼值得稱道的，當你baidu上找不到方案，google里沒有參考，國內外沒有任何人能給你啟示的時候，任然能夠充滿創造的分析問題，抽象問題，並解決問題。找到別人完全沒走過的路，創造別人從來沒有創造過的東西，並給予他人啟示與幫助，這才是有價值的事情。

------------

能在自己的領域探索出到新方法的人，能在關鍵問題上把市面上現有方案哪怕提高 5%的人，都是很了不起的，這都叫：「有所貢獻」。比成天賣弄自己會個什麼，掌握個什麼的人，更值得我們尊敬。

就是學完編譯原理課程做個課程設計的水平。

我們學校要求是

詞法分析:正規文法的,要求使用NFA或DFA
語法分析:LL(1)或LR(1),當然我猜你寫LALR肯定也是可以的.

然而

根據我前兩天答辯時的觀察,整個年級是自己寫不會超過20個人，不少10個人（一共是300人）。

基本上過來答辯的同學會直接承認不是自己寫的，能把程序講清楚就是優秀，講不大清楚就是良好，沒來答辯的只提交程序的就是及格。當然，自己寫的程序，符合上述兩點要求一定是優秀。

我寫了個左線性文法，被老師說這幾天第一次見。

答辯老師曾經說過一句話

這兩天我一共就見過三個版本的程序

——————————————————————

學編譯原理之前當然還是覺得這個兩個東西還是蠻高端的，不過自己寫一下，其實搞出來了感覺也沒啥。寫個Tokenizer把上的NFA-&> DFA ，DFA最小化之類的都實現一遍，肯定能加深你對書本的理解（主要是踩坑）。把LR(1)的符號棧變化過程輸出來，看到分析過程還是蠻爽的。

寫個Tokenizer 和 Parser能收穫的喜悅感，就像第一次自己手寫Hello World並成功運行一樣，以前覺得很高端，在這麼短的時間內搞出來了，真的可以用，是會比較爽的。

計算機科班出來還不會寫個玩具級別的，只能說現在計算機教育的實踐要求太低。

Tokenizer 和 Parser 本身並不難，為了那份喜悅，我覺得每一個計算機專業的學生都應該試一試。

Tokenizer很簡單，Parser的話不同語言難度不同，簡單語言的Parser沒什麼難的，但如果沒用yacc等工具純手擼的話說明底子也蠻厚了。

比較考驗一個人的功力的是一個語言的其他配套設施，其他答主提到的CodeGen，Optimizer都屬於巨坑，還有其他的比如標準庫，Native Interface等等。做出來一個功能完全的實用編程語言非常考驗一個程序員的綜合素質。

just code, that"s all.

o_O.

為什麼網上各種教程都是教人寫tokenize和parser，說明這部分太容易學了。

不吹不黑，一個數據結構及格的程序員，即使完全不懂編譯原理，看一下nfa和遞歸下降的原理再寫一個簡單的tokenize和parser解析一個簡單的語言兩天應該能搞定。不過要是吃透編譯器前端的那麼多知識，比如nfa-&>dfa到最小dfa，LL/LR/SLR/LALR，能做到手寫標準的正則引擎，山寨yacc的水平的話，不潛下心來鑽研個一年半載估計是沒戲。能做到這個水平，全國任何公司的offer肯定都是任意挑選的。反正我比較笨學了好多年都還沒吃透

編譯器前端的到目前為止確實像是到頭了，像lex、yacc、antlr這麼多工具你看看手冊就能寫個parser出來。而編譯器後端的代碼生成、數據流分析、寄存器分配這些怎麼就沒見多少人談論？還不是因為這部分跟前端相比難得多，高手都直接發論文了，普通人接觸過這些東西就會發現自己知識的淺薄不敢亂吹牛了。

這是我們計算機專業本科大二上學期的必修專業課，想接著往下學的話必須有獨立寫出這個的能力

這算是基礎吧

大概編程入門了

能寫出某個 CF 語言的 Parser 不難；

寫出 Parser Generator，很難； // ← 推薦從 PEG 跳坑，因為 PEG 真的很好寫

寫出高效的 Parser Generator，更難。

說實話沒啥水平，因為詞法和語法分析無非就是自動機而已（一個正則，一個帶棧的下推），都是計算機專業基礎課，學校的大作業都有，就看學校教不教，自己學不學了，會者不難

若不考慮性能和很多工業上的細節，做個語言真心沒啥難度

大概是國內大學編譯原理課程設計能過的水品

我上個月剛花一周時間把一個 Lisp 的 tokenizer，parser，包括解釋器一起擼掉了。解釋器上花的時間長一些，主要是因為要實現各種函數和宏 ShisoftResearch/Dovahkiin

那得看寫什麼語言的了。EDG靠賣C++前端養活了一整個公司，然而你要是只會寫JavaScript的parser和tokenizer的話並沒有什麼卵用。

明明是找不到工作的水平 ...

----------------------------------------------------------

看看Diagram of π-Calculus，不僅有Tokenizer, Parser，還額外贈送pi-calculus解釋器，以及對運行過程逐步畫圖 ... 你覺得這水平能高到哪裡去

-----------------------------------------------------------

Update:

反對

比如nfa-&>dfa到最小dfa，LL/LR/SLR/LALR，能做到手寫標準的正則引擎，山寨yacc的水平的話，不潛下心來鑽研個一年半載估計是沒戲。能做到這個水平，全國任何公司的offer肯定都是任意挑選的。

這個並不難。要花多少時間取決於你想做個湊合能用的，還是Bug-to-Bug Compatible的。前者並不要多久，後者真的需要很長時間。

你看上面那個鏈接里的例子，就是自己山寨了個湊合能用的 lex/yacc 。顯然我還沒找到工作。

而編譯器後端的代碼生成、數據流分析、寄存器分配這些怎麼就沒見多少人談論？還不是因為這部分跟前端相比難得多

數據流分析，實際上和前端是一樣的。參考: 編譯原理不就是Datalog嘛 - impress your cat - 知乎專欄。大部分內容都可以直接從Datalog derive出來。

至於寄存器分配，已經有人證明了，SSA下的寄存器分配，用graph coloring的話，實際上是在對一個chordal graph著色，也就是比graph coloring問題要簡單。

為什麼沒人提起dragon book呢：

Compilers: Principles, Techniques, and Tools

讀懂這本書應該可以入門了，真正能用到生產中還需要親自寫一些不太簡單的lexer和parser。

有一個C++大師課程（C++ Grandmaster Certification [CPPGM]），12次作業從零開始寫一個C++編譯器。粗略地說，完成第一個作業算是通lexer，完成前五次作業算是通lexer和parser。

編譯器方面最先進的技術和工程都基於美國：GCC和LLVM Clang。推薦還是看這些實際中使用的工程學習吧，看書只能幫你入門，真正要懂要精通需要在這些大項目上學。

下限來說，也就我這水平，或者稍高點，並沒有什麼卵用……

這要看語言，不同的語言的詞法分析器，語法分析器的難度可以相差很大。如果是簡單的語言，很容易寫出來，而且可以很輕易的直接到CodeGen，Optimization等階段，然後一條龍直接到生成可執行文件的階段。但是如果是C++這樣的語言的話......

證明大學編譯器課程剛剛及格。。。

補充下，王垠的水平，不是我們隨意評價的，人家水平確實牛，雖然逗比點。。。但個人還是覺得像V神這種天才的才有資格。。