加快我的lexing算法

我將一個潛在的大字符串（讓我們說20MB，儘管這完全是任意的）分解成由正則表達式列表定義的標記。加快我的lexing算法

我現在的算法採用以下方法：

所有的正則表達式進行了優化，具有零寬度斷言^他們開始
對於列表中的每個正則表達式，我試圖#slice!的輸入字符串
如果我們#slice!什麼，我們得到了一個匹配，並且輸入字符串已提前準備尋找下一個標記（因爲#slice!修改字符串）

不幸的是，這是緩慢的，這是由於長字符串上重複的#slice! ...它似乎像在紅寶石中修改大字符串並不快。

所以我想知道是否有一種方法來匹配我的正則表達式與新的子字符串（即字符串的其餘部分）而不修改它？

在（測試，可運行）的僞代碼當前算法：

rules = { 
    :foo => /^foo/, 
    :bar => /^bar/, 
    :int => /^[0-9]+/ 
    } 

    input = "1foofoo23456bar1foo" 
    # or if you want your computer to cry 
    # input = "1foofoo23456bar1foo" * 1_000_000 

    tokens = [] 

    until input.length == 0 
    matched = rules.detect do |(name, re)| 
     if match = input.slice!(re) 
     tokens << { :rule => name, :value => match } 
     end 
    end 

    raise "Uncomsumed input: #{input}" unless matched 
    end 

    pp tokens 
    # => 
    [{:rule=>:int, :value=>"1"}, 
    {:rule=>:foo, :value=>"foo"}, 
    {:rule=>:foo, :value=>"foo"}, 
    {:rule=>:int, :value=>"23456"}, 
    {:rule=>:bar, :value=>"bar"}, 
    {:rule=>:int, :value=>"1"}, 
    {:rule=>:foo, :value=>"foo"}]

注意，儘管非常簡單地對字符串匹配正則表達式的次數相等數目並不快通過任何手段，它不是那麼慢慢地，你在等待的時候會有時間做一個披薩（幾秒鐘，比很多分鐘）。

來源

2011-11-20 d11wtq

String#match()方法有一個雙參數版本，它將匹配從字符串中特定字符位置開始的正則表達式。你只需要得到one-past-the-last-matching-character from the previous match作爲新比賽的開始位置。

在未經檢驗的，不運行的僞代碼：

input = "foo" 
input_pos = 0 
input_end = input.length 

until input_pos == input_end do 
    matched = rules.detect do |(name, re)| 
    if match = input.match(re, input_pos) 
     tokens << { :rule => name, :value => match } 
     input_pos = match.post_match 
    end 
    end 
end

來源

2011-11-20 08:40:58 sarnold

謝謝，我希望這將是解決方案，但正則表達式不符合那個'^'在sta處rt如果將'pos'傳遞給'＃match'並且沒有這個約束，正則表達式會浪費很多時間來掃描整個循環的20MB字符串。我看不出一種簡單的方法讓正則表達式看起來像是在查看字符串的開始。我想我可以在某種標記的前面加上前綴，但是我們又回到了重複創建/修改字符串的領域:) – d11wtq

也許如果用'\ G'替換'^'以匹配從前一次匹配的結尾，它會工作？ ...雖然第一場比賽可能需要更多的工作。我希望[pguardiario的答案]（http://stackoverflow.com/questions/8200195/speed-up-my-lexing-algorithm/8200774#8200774）解決。 :) – sarnold

聖潔的廢話。這比我的代碼至少快30倍，可能更多（由於我們正在查看的巨大時間，我沒有以亞秒級精度進行基準測試）。謝謝！我從來不知道'\ G'。我現在在一秒鐘內（而不是30秒）匹配70,000個令牌。 – d11wtq

也許我過於簡單化，但串＃掃描將最有可能超越其他任何東西：

tokens = input.scan(/foo|bar|\d+/).map{|m| {:value => m, :rule => rules.find{|name,re| m =~ re}[0]}}

或者更一般地說：

rules = { 
    :foo => /foo/, 
    :bar => /bar/, 
    :int => /[0-9]+/ 
} 
tokens = input.scan(Regexp.union(rules.values)).map{|m| {:value => m, :rule => rules.find{|name,re| m =~ re}[0]}}

來源

2011-11-20 10:00:57 pguardiario

是的，過度簡化;）我需要能夠報告什麼時候匹配失敗，但是，我也有一些規則可以做一些狀態切換（例如，在內插字符串內部）。 – d11wtq

在這種情況下，請在該問題中添加該規則的示例。 – pguardiario

加快我的lexing算法

回答

相關問題