Tag

2016年4月1日 星期五

使用Rust 實作regular expression tester

其實這個功能很早以前就已經完成了,將正規表示式對轉換成Non-Deterministic Automata(NFA) ,來match字串,
先前的實作有一些問題,因為再建 NFA的時候,狀態是使用整數來表示,在轉換成NFA時,正規表示式的Concatenate, Choose, Repeat 需要將兩個NFA 結合成一個,因為由Empty 或Literal 直接建NFA時,編號一定是從0開始,兩個都包含狀態0的狀態機,直接結合起來絕對不會是對的,需要讓兩邊的狀態都不一樣才行。
當然也不可能用亂數來作為狀態,畢竟以亂數作為狀態,連一個NFA裡面有哪些狀態都不知道,結合時根本就無法檢查是否有衝突。

這是之前版本的 toNFA:
toNFA with u32

可以看到因為使用整數來表示狀態,為了避免第二個NFA 接到第一個上面時,第二個NFA 的狀態和第一個的重複,必須實作一些必要的函式,例如FARule 的shift 將規則中的狀態都偏移一個數值;如果像Choose 或Repeat ,需要建一個新的start state,則兩個 NFA的 rule都要shift;另外像accept state也要用iterator的方式 shift,總之就是各種麻煩。

相對的在書中的例子,使用Ruby實作的關係,他直接使用Ruby Object來當作他的狀態,絕對不會有重複的問題,就像這裡的start_state:
class Choose
  def to_nfa_design
    first_nfa_design = first.to_nfa_design
    second_nfa_design = second.to_nfa_design
    start_state = Object.new
    accept_states = first_nfa_design.accept_states + second_nfa_design.accept_states
    rules = first_nfa_design.rulebook.rules + second_nfa_design.rulebook.rules
    extra_rules = [first_nfa_design, second_nfa_design].map { |nfa_design|
      FARule.new(start_state, nil, nfa_design.start_state)
    }
    rulebook = NFARulebook.new(rules + extra_rules)
    NFADesign.new(start_state, accept_states, rulebook)
  end
end
當然Rust 也是可以這樣做,只是麻煩些,畢竟Ruby 是動態語言,要用什麼東西當狀態都可以直接使用,Rust 需要明確的指定型別,某種程度它用Ruby 實作也是一種語言的霸凌Orz。

相對應的修改如下:
首先我們先建一個空的state,裡面不用內容,功用就跟Ruby 的Object 差不多:
Struct State;
這樣就可以建state了:
let start_state = State{};
let next_state = State{};
let rule = FARule(start_state, c, next_state);
NFA(start_state, next_state, rule);

因為Rust 在struct 的比較的時候,會直接把struct 拆開比較裡面的值,所以上面 start_state == next_state 會是true,解決方法在於自己實做比較的方法,改成比較struct 的位址即可避免不同struct 被認定成相同:
impl PartialEq for State {
  fn eq(&self, rhs: &Self) -> bool {
    self as *const _ == rhs as *const _
  }
}

另外 Rust 會避免同個struct 被兩個不同的地方擁有,當我們使用了某個State當作start_state,我的rule 就沒辦法再用這個State 了,上面的code 在建nfa 的時候會報錯,因為start_state 跟next_state 已經move 到FARule 中了。 因此我們狀態不能直接使用state 而必須用rust 的 Reference Count: Rc。
https://doc.rust-lang.org/std/rc/struct.Rc.html
用Rc<State> 當作state,這樣
let start_state = Rc::new(State{});
let next_state = Rc::new(State{});
let rule = FARule(start_state.clone(), c, next_state.clone());
就可以避免重複使用start_state 的問題,同時 start_state == start_state.clone() 也會是true。

以下是修改後的toNFA:
toNFA with struct state
相較起來簡單的多,也跟Ruby code 相似得多。
Related Posts Plugin for WordPress, Blogger...