很好很強大的矬人，哇咔咔  回復  更多評論
  

果然經典哈 最后對學習方法的見解對我很有幫助  回復  更多評論
  

向您學習嘍  回復  更多評論
  

詞法分析部分寫好了，不過擴展正則表達式部分懶的寫，想先寫語法分析器了。
用正則表達式的引擎提供了一套接口給詞法分析器。測試了下
測試的內容如下，然后自己把一份代碼粘帖了10幾次，擴充到3MB，然后分析了下。大約44W標記每秒

AddMoreType( scanner, L"ID", L"[_a-zA-Z][a-zA-Z0-9_]*" );
AddMoreType( scanner, L"ID.IF", L"if" );
AddMoreType( scanner, L"ID.BOOL", L"true|false" );
AddMoreType( scanner, L"ID.ELSE", L"else" );
AddMoreType( scanner, L"ID.WHILE", L"while" );
AddMoreType( scanner, L"ID.DO", L"do" );
AddMoreType( scanner, L"ID.BREAK", L"break" );
AddMoreType( scanner, L"ID.CONTINUE", L"continue" );
AddMoreType( scanner, L"ID.FOR", L"for" );
AddMoreType( scanner, L"OPERATOR", L"\\+|\\-|\\*|/|%|<|>|=|<=|>=|==|!=|!|&&|\\|\\||\\^|;|\\(|\\)|\\{|\\}|,|\\[|\\]" );
AddMoreType( scanner, L"OPERATOR.NOT", L"!" );
AddMoreType( scanner, L"OPERATOR.ADDMINUS", L"\\+|\\-" );
AddMoreType( scanner, L"OPERATOR.MULDIVMOD", L"\\*|/|%" );
AddMoreType( scanner, L"OPERATOR.COMPARE", L"<|>|<=|>=|==|!=" );
AddMoreType( scanner, L"OPERATOR.ASSIGN", L"=" );
AddMoreType( scanner, L"OPERATOR.AND", L"&&" );
AddMoreType( scanner, L"OPERATOR.OR", L"\\|\\|" );
AddMoreType( scanner, L"OPERATOR.XOR", L"\\^" );
AddMoreType( scanner, L"OPERATOR.LEFT", L"\\(" );
AddMoreType( scanner, L"OPERATOR.RIGHT", L"\\)" );
AddMoreType( scanner, L"OPERATOR.BEGIN", L"\\{" );
AddMoreType( scanner, L"OPERATOR.END", L"\\}" );
AddMoreType( scanner, L"OPERATOR.SPLITER", L"," );
AddMoreType( scanner, L"OPERATOR.ARRBEGIN", L"\\[" );
AddMoreType( scanner, L"OPERATOR.ARREND", L"\\]" );
AddMoreType( scanner, L"OPERATOR.FINISH", L";" );
AddMoreType( scanner, L"NUM", L"[0-9]+" );
AddMoreType( scanner, L"REAL", L"([0-9]+\\.[0-9]*)|([0-9]*\\.[0-9]+)" );
AddMoreType( scanner, L"STRING", L"\"([^\\\\\"]|\\\\\\.)*\"" );
AddMoreType( scanner, L"COMMENT.discard", L"#[^\\n]*" );
  回復  更多評論
  

日哦，我寫了N多的評論，一下就沒了。
正則表達式的引擎的擴展部分，我還是沒寫```，人懶沒辦法。過幾天最后幾門考試考完了后開始看看語法分析部分了。

寫這份代碼總出過一個大BUG，一個小BUG，大BUG是自己一邊調試一邊想別的，結果一開始調試了6個小時，后來又調試3個小時總算搞定``，出錯的地方很簡單就是使用iterator的時候，next到下一個元素的時候，數組變長用了realloc后，指針變了```。哎，我郁悶到了。后來看設計模式的書，發現就講了這點，刪除和重新分配必須得保證那iterator一直正確才行```，羨慕用c++的，我用C，發現設計模式有些地方看不懂，特別是代碼部分。

小BUG是昨天晚上出的，結果雖然都出來了，突然發現標記都錯了。```，花了兩個小時左右搞定。

算了不寫了```，小v的文章簡單易懂，大家該多看看。
  回復  更多評論
  

設計模式里面的類和接口都是C語言里面沒有的概念，模擬起來也比直接支持類的語言麻煩。  回復  更多評論
  

仔細拜讀，簡單易懂。多謝  回復  更多評論
  

<b>sad</b>  回復  更多評論
  

不錯，建議跟libpcre對測一下~  回復  更多評論
  

謝謝樓主這樣的精品文章。  回復  更多評論
  

跟大俠請教一個問題：如果讓引擎支持unicode的話，只能用分類壓縮法。
例如如果只有一個字符單元為：a-z,
那么，內部字符集將被分割為：
編號1、0-96,
編號2、97-122,
編號3、123-65535,
但是有一個問題是在搜索的時候，如何才能快速的得到字符到字符集編號的轉換呢？如果用您提到的一張65535個字符的大表來映射的話，也太粗魯，太耗內存了吧?有沒有什么更好的算法呢？那些有名的引擎是怎么做的呢，翻遍了internet沒有這方面的任何資料。不知道大俠有什么好的建議？  回復  更多評論
  

@林林
65535*2不就128k，哪里粗魯，哪里太耗內存了？其實一個程序同時存在的正則表達式是不多的。當然這是O(1)，如果你實在想減少內存，那就沒有這么快了，傳說中有一種數據結構叫線段樹。  回復  更多評論
  

線段樹! 謝謝大俠的指點！
之所以覺得耗內存是因為，我認為自己做正則引擎主要并不是用來做單純的詞法搜索的。因為現在正則引擎這么多，自己去做吃力又不討好。自己做的主要目的在于做詞法分析?，F在的詞法分析引擎還非常難用的，象flex等，生成出來的代碼，看了想吐！完全不能接受這種風格的代碼入侵到我的工程中。而詞法分析是難于避免一個程序有多個分析引擎的。所以才會覺得耗費內存。  回復  更多評論
  

@ooseven
如果是自己的腳本引擎，完全可以手寫一個此法分析，簡單明了。
  回復  更多評論
  

樓主，我悲劇啊，我畢業兩年了還要參考你在大學時期的文檔來進行正則引擎的實現。。  回復  更多評論
  

@aho
你這個名字……  回復  更多評論
  

@陳梓瀚(vczh)
寫得真好，讓師兄很汗顏啊~~不太敢相信你是大三時候寫的，特別是貪婪匹配算法那部分，補充了龍書的不足，正為怎么較優雅地設計正則的擴展功能而發愁呢.

話說你推薦的那本《Parsing Techniques》真的這么好嗎~~？  回復  更多評論
  

@aho
嗯，真的那么好。  回復  更多評論
  

<<構造可配置詞法分析器>>(詞法分析.doc)
"在處理這種有沖突的規則的時候，既可以報錯，也可以根據指定的優先級進行挑選。"
能否解釋下"根據指定的優先級進行挑選"?
在這例子里,
狀態AB讀入[^a-z]則識別出if,
讀入[a-z]則繼續識別標識符.
難道這就是"根據指定的優先級進行挑選"?

還有, 字符轉字符類,有個問題.
舉一簡單例子, 就識別標識符和十六進制數的狀態圖.
識別標識符用到的字符集: [a-z]、[A-Z]、_、[0-9]
識別十六進制數(0x????)用到的字符集: [0-9]、[a-f]、[A-F]、x
當字符轉字符類的時候, 若當前字符為a, 那么該判定它屬于字符集[a-f],
還是判定它屬于字符集[a-z]?
請問怎么處理?

讓"神"費心了, 謝謝.
  回復  更多評論
  

詞法分析.doc 中的圖用什么畫啊?

"按照規則構造出四個DFA并將它們組合起來："
按那圖, 標識符的長度豈不是只能為2?
1不行, 3 也不行?

  回復  更多評論
  

"這個其實跟正則表達式本身有關。至于什么正則表達式可以達到這個效果這里就不深究了。"
能否說下"什么正則表達式可以達到這個效果"?
不想深究, 只想知道什么樣正則表達式, 就可以了.
  回復  更多評論
  

"123.ABC"
識別到"A"那里, 已經說明輸入的字符串不合法, 直接報錯說"expected digit but alpha encountered."就得, 為何還要繼續分析"BC"?  回復  更多評論
  

"我們都要做一些額外的工作"
與
"我們將無從知道一個記號被識別出來的確切時間"
有何矛盾?
能否詳細說明下?
  回復  更多評論
  

"行代表字符，列代表DFA的狀態"

c代字
s代當前態
t代目標態
下述的,哪個對?
s1 s2
c1 t1 t2
c2 t3 t4
----------
c1 c2
s1 t1 t2
s2 t3 t4  回復  更多評論
  

"吞吐速度高達46萬記號/秒","只有10%的時間花在了DFA上，90%的時間花在了處理結果的工作上"
統計本身沒有代價(因統計而增加的開銷)?
不統計的話, 程序應該跑得更快吧?

另:
請問用什么工具或代碼來統計一個程序或代碼段的各種開銷(時、空)?
  回復  更多評論
  

正則 ==> ε-NFA ==> NFA ==> DFA
貌似文章沒有講如何"(E)BNF ==> 正則"?

(E)BNF ==> 正則 ==> ε-NFA ==> NFA ==> DFA
步驟太多!
能不能少點?比如
(E)BNF ==> DFA
  回復  更多評論
  

有些圖的結束狀態是粗邊
有些圖的結束狀態是雙邊
一樣嗎?  回復  更多評論
  

@thircese
1：如果您仔細看文章就會發現，如果[a-f]存在，那么[a-z]是不存在的，存在
的只有[g-z]。
2：ENFA到DFA的步驟只能這么多，減少的話會讓一個算法變得非常復雜。
3：只要記錄一下開始跟結束的時間就可以記錄時間了，自己寫代碼做。
4：詞法分析那一節說的是一個中介狀態可以包含舊的若干個DFA的若干個終結狀態，因此會有那些結論。
5：其他問題，請自行閱讀文章。所有與開發無關的問題我一概不解釋，請利用您的智商和您的數學水平自行推導，譬如說哪個正則表達式可以用來深究的問題。BTW，我畫圖用的是微軟公司偉大的照耀我們前進方向的全銀河系唯一一個不需要看幫助就可以繪制專業圖形的visio軟件。還有，如何從狀態機反著做出正則表達式不在這篇文章的討論范圍內。  回復  更多評論
  

謝謝您為我的"弱智"問題費神.
不過,
"貌似文章沒有講如何"(E)BNF ==> 正則"?"
中的"(E)BNF"是指"(擴展)巴斯克范式"
而不是指狀態機ENFA哦!  回復  更多評論
  

@thircese
有一些EBNF無法被轉換為正則，所以當然不存在EBNF到正則的轉換了。倘若這是一個可以被轉換為正則的EBNF，那那些非終結符肯定沒有遞歸引用，那么你可以逐個消除他們。譬如說a=b "."; b = "+"消除b的結果就是a="+" "."。最后剩下一條，就是正則表達式了。  回復  更多評論
  

有幸拜讀閣下兩篇文章，受益匪淺，謝過！  回復  更多評論
  

兩個鏈接都失效了，可以重新鏈接下？  回復  更多評論
  

@steven
估計是bug，我發郵件給cppblog了  回復  更多評論
  

下不了  回復  更多評論
  

師兄啊  回復  更多評論
  

最近一直在學習python，剛好做爬蟲的時候涉及到了正則表達式這一塊？。想弱弱的問一句有沒有可能用python來實現這個正則表達式引擎呢？ 非常謝謝你。（不是不想用c++，而是想暫時先專注于python。）  回復  更多評論