1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
use crate::syntax::ast::{Pattern, Regex};
use crate::vm::instr::Instr;
pub fn compile(re: &Regex) -> Vec<Instr> {
let compiler = Compiler::default();
compiler.compile(&re.root)
}
#[derive(Default)]
struct Compiler {
instrs: Vec<Instr>,
labels: Vec<usize>,
}
impl Compiler {
fn compile(mut self, pat: &Pattern) -> Vec<Instr> {
self.compile_pattern(pat);
self.resolve_labels();
self.instrs.push(Instr::Match);
self.instrs
}
fn compile_pattern(&mut self, pat: &Pattern) {
match pat {
Pattern::Empty => todo!(),
Pattern::Literal(c) => self.instrs.push(Instr::Char(*c)),
Pattern::Concat(a, b) => {
self.compile_pattern(&a);
self.compile_pattern(&b);
}
Pattern::Alt(a, b) => {
// split l1 l2
// l1: compile(a)
// jmp l3
// l2: compile(b)
// l3:
let label_1_index = self.create_new_label();
let label_2_index = self.create_new_label();
let label_3_index = self.create_new_label();
self.instrs.push(Instr::Split(label_1_index, label_2_index));
self.fix_label_address(label_1_index);
self.compile_pattern(&a);
self.instrs.push(Instr::Jmp(label_3_index));
self.fix_label_address(label_2_index);
self.compile_pattern(&b);
self.fix_label_address(label_3_index);
}
Pattern::Star(a) => {
// l1: split l2 l3
// l2: compile(a)
// jmp l1
// l3:
let label_1_index = self.create_new_label();
let label_2_index = self.create_new_label();
let label_3_index = self.create_new_label();
self.fix_label_address(label_1_index);
self.instrs.push(Instr::Split(label_2_index, label_3_index));
self.fix_label_address(label_2_index);
self.compile_pattern(&a);
self.instrs.push(Instr::Jmp(label_1_index));
self.fix_label_address(label_3_index);
}
}
}
fn resolve_labels(&mut self) {
for instr in self.instrs.iter_mut() {
match instr {
&mut Instr::Jmp(ref mut a) => {
*a = self.labels[*a];
}
&mut Instr::Split(ref mut a, ref mut b) => {
*a = self.labels[*a];
*b = self.labels[*b];
}
_ => (),
}
}
}
fn create_new_label(&mut self) -> usize {
self.labels.push(0);
self.labels.len() - 1
}
fn fix_label_address(&mut self, label_index: usize) {
let address = self.instrs.len();
self.labels[label_index] = address;
}
}
|
