來自正則表達式的虛擬機

Question

我讀Regular Expression Matching: the Virtual Machine Approach現在我嘗試解析一個正則表達式並從中創建一個虛擬機。 標記器工作並創建其標記。這一步之後，我創建令牌流的逆轉波蘭記號所以在最後我從正則表達式a|(b|c)得到

a b c | | 

。 好了，現在我在那裏停留了一步：我想獲得一個數組

0: split 1, 3 
1: match 'a' 
2: jump 7 
3: split 4, 6 
4: match 'b' 
5: jump 7 
6: match 'c' 
7: noop 

從上面的數據流。而且我沒有把它做對......我使用輸出數組和堆棧作爲每個令牌的開始位置。首先，將3個值添加到輸出中（並且它是堆棧的起始位置）。

output    stack 
------------------- ------ 
0: match 'a'  0: 0 
1: match 'b'  1: 1 
2: match 'c'  2: 2 

隨着|，我從棧中彈出最後的2個位置，插入在特定位置split和jump。這些值是根據當前堆棧長度和我添加的元素數量計算得出的。 最後，我將最後一個元素的新開始位置添加到堆棧中（在這種情況下保持不變）。

output    stack 
------------------- ------ 
0: match 'a'  0: 0 
1: split 2, 4  1: 1 
2: match 'b' 
3: jump 5 
4: match 'c' 

這似乎沒問題。現在，下一個|被彈出...

output    stack 
------------------- ------ 
0: split 1, 3  0: 0 
1: match 'a' 
2: jump 7 
3: split 2, 4 
4: match 'b' 
5: jump 5 
6: match 'c' 

這就是問題所在。我必須更新我之前計算的所有地址（第3行和第5行）。這不是我想要的。 我猜，相對地址有相同的問題（至少如果值是負值）。

所以我的問題是，如何從正則表達式創建一個虛擬機。 我是在正確的軌道上（與rpn形式）還是有另一種（和/或更容易）的方式？輸入數組存儲爲整數數組。該split其實3項-command需要，jump需要兩個，...

Answer 1

我認爲與其在處理過程中設置的地址，你可以存儲參考對要跳命令，在輸出數組中，還可以存儲引用（或指針）。在所有處理完成後，您沿着生成的輸出並根據所得到的命令在結果數組中的實際位置分配索引。

Answer 2

RPN並不是構建所需輸出的最佳方式。如果你建立了一個AST，那麼使用遞歸遍歷來生成代碼將很容易。

假設你有一個OR節點，例如，有兩個孩子「左」和「右」。每個節點實現的方法generate(OutputBuffer)，以及一個或節點的實現應該是這樣的：

void generate(OutputBuffer out) 
{ 
int splitpos = out.length(); 
out.append(SPLIT); 
out.append(splitpos+3); //L1 
out.append(0); //reservation 1 
//L1 
left.generate(out); 
int jumppos = out.length(); 
out.append("JUMP"); 
out.append(0); //reservation 2 
//L2 
out.set(splitpos+2, out.length()); //reservation 1 = L2 
right.generate(out); 
//L3 
out.set(jumppos+1, out.length()); //reservation 2 = L3 
}