Máy ảo từ biểu thức chính quy

Question

Tôi đọc Regular Expression Matching: the Virtual Machine Approach và bây giờ tôi cố gắng phân tích biểu thức chính quy và tạo một máy ảo từ đó. Trình mã thông báo hoạt động và tạo mã thông báo. Sau bước đó, tôi tạo ra các ký hiệu đánh bóng đảo ngược từ dòng mã thông báo như vậy tại cuối cùng tôi nhận được

a b c | | 

từ biểu thức chính quy a|(b|c). Vâng, bây giờ bước nơi tôi bị mắc kẹt: Tôi muốn để có được một mảng

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 

từ dòng trên. Và tôi đã không làm cho nó đúng ... Tôi sử dụng một mảng đầu ra và một ngăn xếp cho các vị trí bắt đầu của mỗi mã thông báo. Đầu tiên, 3 giá trị được thêm vào đầu ra (và nó là vị trí bắt đầu cho ngăn xếp).

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

Với |, tôi bật 2 vị trí cuối cùng từ ngăn xếp và chèn split và jump tại các vị trí cụ thể. Các giá trị được tính toán dựa trên chiều dài ngăn xếp hiện tại và số lượng phần tử tôi thêm vào. Cuối cùng, tôi thêm vị trí bắt đầu mới của phần tử cuối cùng vào ngăn xếp (vẫn giữ nguyên trong trường hợp này).

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

Điều đó có vẻ ổn. Hiện tại, | tiếp theo được mở ...

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' 

Và đây là vấn đề. Tôi phải cập nhật tất cả các địa chỉ mà tôi đã tính toán trước đó (dòng 3 và 5). Đó không phải là điều tôi muốn. Tôi đoán, các địa chỉ tương đối có cùng một vấn đề (ít nhất là nếu các giá trị là số âm).

Vì vậy, câu hỏi của tôi là, cách tạo vm từ regex. Tôi đang đi đúng hướng (với mẫu rpn) hay có cách nào khác (và/hoặc dễ dàng hơn) không?

Mảng đầu ra được lưu trữ dưới dạng mảng số nguyên. Các split -Command cần trên thực tế 3 mục, jump cần hai, ...

Answer 1

Tôi nghĩ rằng thay vì thiết lập địa chỉ trong chế biến, bạn có thể lưu một tài liệu tham khảo để lệnh mà bạn muốn nhảy, và trong mảng đầu ra, bạn cũng lưu trữ các tham chiếu (hoặc con trỏ). Sau khi tất cả quá trình xử lý hoàn tất, bạn đi theo đầu ra được tạo ra và gán các chỉ số dựa trên vị trí thực tế của lệnh được tham chiếu trong mảng kết quả.

Answer 2

RPN không phải là cách tốt nhất để xây dựng đầu ra bạn cần. Nếu bạn xây dựng một AST thay vào đó, sau đó nó sẽ được dễ dàng để tạo ra các mã với một traversal đệ quy.

Giả sử bạn có nút OR, ví dụ: với hai con "trái" và "phải". Mỗi nút thực hiện một phương pháp generate(OutputBuffer), và việc thực hiện cho một nút OR sẽ trông như thế này:

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 
}