Thiết kế trình biên dịch - Biểu thức chính quy

Trình phân tích từ vựng chỉ cần quét và xác định một tập hợp hữu hạn các chuỗi / mã thông báo / lexeme hợp lệ thuộc về ngôn ngữ trong tay. Nó tìm kiếm mẫu được xác định bởi các quy tắc ngôn ngữ.

Biểu thức chính quy có khả năng diễn đạt các ngôn ngữ hữu hạn bằng cách xác định một mẫu cho các chuỗi ký hiệu hữu hạn. Ngữ pháp được xác định bởi biểu thức chính quy được gọi làregular grammar. Ngôn ngữ được xác định bởi ngữ pháp thông thường được gọi làregular language.

Biểu thức chính quy là một ký hiệu quan trọng để chỉ định các mẫu. Mỗi mẫu khớp với một tập hợp các chuỗi, vì vậy các biểu thức chính quy đóng vai trò là tên cho một tập hợp các chuỗi. Mã thông báo ngôn ngữ lập trình có thể được mô tả bằng ngôn ngữ thông thường. Đặc tả của biểu thức chính quy là một ví dụ về định nghĩa đệ quy. Ngôn ngữ thông thường dễ hiểu và có hiệu quả triển khai.

Có một số luật đại số được tuân theo bởi các biểu thức chính quy, có thể được sử dụng để điều chỉnh các biểu thức chính quy thành các dạng tương đương.

Hoạt động

Các hoạt động khác nhau trên các ngôn ngữ là:

Liên hợp của hai ngôn ngữ L và M được viết là

LUM = {s | s ở L hoặc s ở M}
Phép ghép của hai ngôn ngữ L và M được viết là

LM = {st | s ở L và t ở M}
Câu kết Kleene của một ngôn ngữ L được viết là

L * = Số lần xuất hiện của ngôn ngữ L.

Ký hiệu

Nếu r và s là các biểu thức chính quy biểu thị các ngôn ngữ L (r) và L (s), thì

Union : (r) | (s) là một biểu thức chính quy biểu thị L (r) UL (s)
Concatenation : (r) (s) là một biểu thức chính quy biểu thị L (r) L (s)
Kleene closure : (r) * là một biểu thức chính quy biểu thị (L (r)) *
(r) là một biểu thức chính quy biểu thị L (r)

Tính ưu tiên và tính liên kết

*, nối (.), và | (dấu ống) được kết hợp trái
* có mức độ ưu tiên cao nhất
Liên kết (.) Có mức độ ưu tiên cao thứ hai.
| (dấu ống) có mức độ ưu tiên thấp nhất trong tất cả.

Biểu diễn mã thông báo hợp lệ của một ngôn ngữ trong biểu thức chính quy

Nếu x là một biểu thức chính quy, thì:

x * có nghĩa là không hoặc nhiều lần xuất hiện x.

tức là, nó có thể tạo ra {e, x, xx, xxx, xxxx,…}
x + có nghĩa là một hoặc nhiều lần xuất hiện của x.

tức là, nó có thể tạo ra {x, xx, xxx, xxxx…} hoặc xx *
x? có nghĩa là nhiều nhất một lần xuất hiện của x

tức là, nó có thể tạo ra {x} hoặc {e}.

[az] là tất cả các bảng chữ cái viết thường của ngôn ngữ tiếng Anh.

[AZ] là tất cả các bảng chữ cái viết hoa của ngôn ngữ tiếng Anh.

[0-9] là tất cả các chữ số tự nhiên được sử dụng trong toán học.

Biểu diễn sự xuất hiện của các ký hiệu bằng cách sử dụng biểu thức chính quy

letter = [a - z] hoặc [A - Z]

chữ số = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 hoặc [0-9]

dấu = [+ | -]

Biểu diễn mã thông báo ngôn ngữ bằng cách sử dụng cụm từ thông dụng

Số thập phân = (dấu) ^?(chữ số) ⁺

Định danh = (chữ cái) (chữ cái | chữ số) *

Vấn đề duy nhất còn lại với trình phân tích từ vựng là làm thế nào để xác minh tính hợp lệ của một biểu thức chính quy được sử dụng trong việc chỉ định các mẫu từ khóa của một ngôn ngữ. Một giải pháp được chấp nhận tốt là sử dụng dữ liệu tự động hữu hạn để xác minh.