regex - 来自正则表达式的虚拟机

Question

我读了 Regular Expression Matching: the Virtual Machine Approach现在我尝试解析一个正则表达式并从中创建一个虚拟机。
分词器工作并创建其标记。在这一步之后，我从 token 流中创建了反向波兰符号，所以最后我得到

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

从上面的溪流。我没有做对......我使用一个输出数组和一个堆栈作为每个 token 的起始位置。首先，将 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 行)。那不是我想要的。
我猜，相对地址有同样的问题(至少如果值为负)。

所以我的问题是，如何从正则表达式创建一个 vm。
我是在正确的轨道上(使用 rpn-form)还是有另一种(和/或更简单的)方法？

输出数组存储为整数数组。 split -command 实际上需要 3 个条目， jump需要两个，...

Answer 1

使用相对跳转和拆分会更容易。

a — 推送 match到堆栈

0: match 'a'

b — 推送 match到堆栈

0: match 'a'
--
0: match 'b'

c — 推送 match到堆栈

0: match 'a'
--
0: match 'b'
--
0: match 'c'

| — 从堆栈中弹出两帧，然后推送 split <frame1> jump <frame2>

0: match 'a'
--
0: split +1, +3
1: match 'b'
2: jump +2
3: match 'c'

| — 从堆栈中弹出两帧，然后推送 split <frame1> jump <frame2>

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

如果您确实需要绝对跳转，则可以轻松地迭代并调整所有偏移量。