星期三, 7月 29, 2009

Reverse Regular Expression

我一直都是 Perl 的愛好者,雖然,說實在,我寫perl 的"功力"不怎麼樣,不過 perl 給我寫程式的生涯添了不少色彩,立了不少待征的高山。每次寫perl 都有新的體悟,這也是讓我很喜歡它的原因。

今天因為需要,在找有沒有 regexp 可以從後面開始找第一個 match,換句話說,就是找到最後一個match。於是我 google 到了這篇 Reversing Regular Expressions 剛進去就發現好像是我以前瞄過的文章,今天好好的看一次,發現是很有趣的思維。

所謂的 Reverse Regexp 就是:
1. reverse string input
2. reverse regexp
3. reverse match
reverse 的代價遠比把整個字串都比對完小多了,如此一來對於"找到最後一個xxx" 的問題就有了快速又方便的解法。唯一的缺點就是你要把 regexp 倒過來寫,不過這通常不是什麼難事,或者說.. 對於喜歡寫 perl 的人來說件很有趣的事情。
---------------
下面又提到 variable length 的 zero-width look ahead assertion 實作方法,也是很好玩。

還是要說一句 I love PERL !!


延伸閱讀:
http://japhy.perlmonk.org/sexeger/sexeger.html

Readline & network programming

GNU Readline Library 真的是很不錯的一個東西,對於要做 console interface 的人來說可以說是福音吧!很多shell 也都是用readline 的。
Readline 主要是提供了一些輸入上與使用者的互動,包括一些常用(emacs)的編輯指令,也有我很喜歡的vi mode :p . 想要做到與shell 一樣強大的輸入介面,用readline 就對了!

最近在寫個網路應用程式需要用到 Readline,可是我們寫網路應用程式最討厭的就是會 block,當呼叫 readline 的時候因為他需要分開處理每個 key,並表現在 buffer 中,才能達成一些編輯的功能,當然 readline 也提供在需要 non-blocking IO 的環境使用的方法,配合 select,可以使用它的 Alternate Interface 也就是下面這幾個 function:
void rl_callback_handler_install (const char *prompt, rl_vcpfunc_t *lhandler)
void rl_callback_read_char (void)
void rl_callback_handler_remove (void)
使用方法還蠻簡單的,install 一個在輸入完成(return) 以後會執行的 handler 以後,使用在 select 裡,當 stdin 是active (readline 在 initialize 的時候就已經把stdin 設成 raw 了) 的時候 read_char,結束以後 remove handler 就可以了。

========= update 3 Aug ========
值得注意的是,bind key 似乎要在 rl_callback_handler_install 之前先做,或是bind 完要重新remove&install 一次,不然有些key binding 的時候一些Meta key 會讀不到.