很好很強(qiáng)大的矬人，哇咔咔  回復(fù)  更多評(píng)論
  

果然經(jīng)典哈 最后對(duì)學(xué)習(xí)方法的見解對(duì)我很有幫助  回復(fù)  更多評(píng)論
  

向您學(xué)習(xí)嘍  回復(fù)  更多評(píng)論
  

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

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]*" );
  回復(fù)  更多評(píng)論
  

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

寫這份代碼總出過(guò)一個(gè)大BUG，一個(gè)小BUG，大BUG是自己一邊調(diào)試一邊想別的，結(jié)果一開始調(diào)試了6個(gè)小時(shí)，后來(lái)又調(diào)試3個(gè)小時(shí)總算搞定``，出錯(cuò)的地方很簡(jiǎn)單就是使用iterator的時(shí)候，next到下一個(gè)元素的時(shí)候，數(shù)組變長(zhǎng)用了realloc后，指針變了```。哎，我郁悶到了。后來(lái)看設(shè)計(jì)模式的書，發(fā)現(xiàn)就講了這點(diǎn)，刪除和重新分配必須得保證那iterator一直正確才行```，羨慕用c++的，我用C，發(fā)現(xiàn)設(shè)計(jì)模式有些地方看不懂，特別是代碼部分。

小BUG是昨天晚上出的，結(jié)果雖然都出來(lái)了，突然發(fā)現(xiàn)標(biāo)記都錯(cuò)了。```，花了兩個(gè)小時(shí)左右搞定。

算了不寫了```，小v的文章簡(jiǎn)單易懂，大家該多看看。
  回復(fù)  更多評(píng)論
  

設(shè)計(jì)模式里面的類和接口都是C語(yǔ)言里面沒有的概念，模擬起來(lái)也比直接支持類的語(yǔ)言麻煩。  回復(fù)  更多評(píng)論
  

仔細(xì)拜讀，簡(jiǎn)單易懂。多謝  回復(fù)  更多評(píng)論
  

<b>sad</b>  回復(fù)  更多評(píng)論
  

不錯(cuò)，建議跟libpcre對(duì)測(cè)一下~  回復(fù)  更多評(píng)論
  

謝謝樓主這樣的精品文章。  回復(fù)  更多評(píng)論
  

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

@林林
65535*2不就128k，哪里粗魯，哪里太耗內(nèi)存了？其實(shí)一個(gè)程序同時(shí)存在的正則表達(dá)式是不多的。當(dāng)然這是O(1)，如果你實(shí)在想減少內(nèi)存，那就沒有這么快了，傳說(shuō)中有一種數(shù)據(jù)結(jié)構(gòu)叫線段樹。  回復(fù)  更多評(píng)論
  

線段樹! 謝謝大俠的指點(diǎn)！
之所以覺得耗內(nèi)存是因?yàn)椋艺J(rèn)為自己做正則引擎主要并不是用來(lái)做單純的詞法搜索的。因?yàn)楝F(xiàn)在正則引擎這么多，自己去做吃力又不討好。自己做的主要目的在于做詞法分析?，F(xiàn)在的詞法分析引擎還非常難用的，象flex等，生成出來(lái)的代碼，看了想吐！完全不能接受這種風(fēng)格的代碼入侵到我的工程中。而詞法分析是難于避免一個(gè)程序有多個(gè)分析引擎的。所以才會(huì)覺得耗費(fèi)內(nèi)存。  回復(fù)  更多評(píng)論
  

@ooseven
如果是自己的腳本引擎，完全可以手寫一個(gè)此法分析，簡(jiǎn)單明了。
  回復(fù)  更多評(píng)論
  

樓主，我悲劇啊，我畢業(yè)兩年了還要參考你在大學(xué)時(shí)期的文檔來(lái)進(jìn)行正則引擎的實(shí)現(xiàn)。。  回復(fù)  更多評(píng)論
  

@aho
你這個(gè)名字……  回復(fù)  更多評(píng)論
  

@陳梓瀚(vczh)
寫得真好，讓師兄很汗顏啊~~不太敢相信你是大三時(shí)候?qū)懙?，特別是貪婪匹配算法那部分，補(bǔ)充了龍書的不足，正為怎么較優(yōu)雅地設(shè)計(jì)正則的擴(kuò)展功能而發(fā)愁呢.

話說(shuō)你推薦的那本《Parsing Techniques》真的這么好嗎~~？  回復(fù)  更多評(píng)論
  

@aho
嗯，真的那么好。  回復(fù)  更多評(píng)論
  

<<構(gòu)造可配置詞法分析器>>(詞法分析.doc)
"在處理這種有沖突的規(guī)則的時(shí)候，既可以報(bào)錯(cuò)，也可以根據(jù)指定的優(yōu)先級(jí)進(jìn)行挑選。"
能否解釋下"根據(jù)指定的優(yōu)先級(jí)進(jìn)行挑選"?
在這例子里,
狀態(tài)AB讀入[^a-z]則識(shí)別出if,
讀入[a-z]則繼續(xù)識(shí)別標(biāo)識(shí)符.
難道這就是"根據(jù)指定的優(yōu)先級(jí)進(jìn)行挑選"?

還有, 字符轉(zhuǎn)字符類,有個(gè)問題.
舉一簡(jiǎn)單例子, 就識(shí)別標(biāo)識(shí)符和十六進(jìn)制數(shù)的狀態(tài)圖.
識(shí)別標(biāo)識(shí)符用到的字符集: [a-z]、[A-Z]、_、[0-9]
識(shí)別十六進(jìn)制數(shù)(0x????)用到的字符集: [0-9]、[a-f]、[A-F]、x
當(dāng)字符轉(zhuǎn)字符類的時(shí)候, 若當(dāng)前字符為a, 那么該判定它屬于字符集[a-f],
還是判定它屬于字符集[a-z]?
請(qǐng)問怎么處理?

讓"神"費(fèi)心了, 謝謝.
  回復(fù)  更多評(píng)論
  

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

"按照規(guī)則構(gòu)造出四個(gè)DFA并將它們組合起來(lái)："
按那圖, 標(biāo)識(shí)符的長(zhǎng)度豈不是只能為2?
1不行, 3 也不行?

  回復(fù)  更多評(píng)論
  

"這個(gè)其實(shí)跟正則表達(dá)式本身有關(guān)。至于什么正則表達(dá)式可以達(dá)到這個(gè)效果這里就不深究了。"
能否說(shuō)下"什么正則表達(dá)式可以達(dá)到這個(gè)效果"?
不想深究, 只想知道什么樣正則表達(dá)式, 就可以了.
  回復(fù)  更多評(píng)論
  

"123.ABC"
識(shí)別到"A"那里, 已經(jīng)說(shuō)明輸入的字符串不合法, 直接報(bào)錯(cuò)說(shuō)"expected digit but alpha encountered."就得, 為何還要繼續(xù)分析"BC"?  回復(fù)  更多評(píng)論
  

"我們都要做一些額外的工作"
與
"我們將無(wú)從知道一個(gè)記號(hào)被識(shí)別出來(lái)的確切時(shí)間"
有何矛盾?
能否詳細(xì)說(shuō)明下?
  回復(fù)  更多評(píng)論
  

"行代表字符，列代表DFA的狀態(tài)"

c代字
s代當(dāng)前態(tài)
t代目標(biāo)態(tài)
下述的,哪個(gè)對(duì)?
s1 s2
c1 t1 t2
c2 t3 t4
----------
c1 c2
s1 t1 t2
s2 t3 t4  回復(fù)  更多評(píng)論
  

"吞吐速度高達(dá)46萬(wàn)記號(hào)/秒","只有10%的時(shí)間花在了DFA上，90%的時(shí)間花在了處理結(jié)果的工作上"
統(tǒng)計(jì)本身沒有代價(jià)(因統(tǒng)計(jì)而增加的開銷)?
不統(tǒng)計(jì)的話, 程序應(yīng)該跑得更快吧?

另:
請(qǐng)問用什么工具或代碼來(lái)統(tǒng)計(jì)一個(gè)程序或代碼段的各種開銷(時(shí)、空)?
  回復(fù)  更多評(píng)論
  

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

(E)BNF ==> 正則 ==> ε-NFA ==> NFA ==> DFA
步驟太多!
能不能少點(diǎn)?比如
(E)BNF ==> DFA
  回復(fù)  更多評(píng)論
  

有些圖的結(jié)束狀態(tài)是粗邊
有些圖的結(jié)束狀態(tài)是雙邊
一樣嗎?  回復(fù)  更多評(píng)論
  

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

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

@thircese
有一些EBNF無(wú)法被轉(zhuǎn)換為正則，所以當(dāng)然不存在EBNF到正則的轉(zhuǎn)換了。倘若這是一個(gè)可以被轉(zhuǎn)換為正則的EBNF，那那些非終結(jié)符肯定沒有遞歸引用，那么你可以逐個(gè)消除他們。譬如說(shuō)a=b "."; b = "+"消除b的結(jié)果就是a="+" "."。最后剩下一條，就是正則表達(dá)式了。  回復(fù)  更多評(píng)論
  

有幸拜讀閣下兩篇文章，受益匪淺，謝過(guò)！  回復(fù)  更多評(píng)論
  

兩個(gè)鏈接都失效了，可以重新鏈接下？  回復(fù)  更多評(píng)論
  

@steven
估計(jì)是bug，我發(fā)郵件給cppblog了  回復(fù)  更多評(píng)論
  

下不了  回復(fù)  更多評(píng)論
  

師兄啊  回復(fù)  更多評(píng)論
  

最近一直在學(xué)習(xí)python，剛好做爬蟲的時(shí)候涉及到了正則表達(dá)式這一塊？。想弱弱的問一句有沒有可能用python來(lái)實(shí)現(xiàn)這個(gè)正則表達(dá)式引擎呢？ 非常謝謝你。（不是不想用c++，而是想暫時(shí)先專注于python。）  回復(fù)  更多評(píng)論