Một lexer tổng quát được xây dựng từ một DFA (đơn định) cho trước dưới dạng bảng chuyển trạng thái, thay vì các luật viết tay. DFA có Q trạng thái đánh số 0,…,Q−1 (trạng thái bắt đầu luôn là 0), bộ chữ cái Σ gồm σ ký tự cho trước, và một tập trạng thái kết thúc, mỗi trạng thái kết thúc gắn với tên một loại token.
Việc token hóa dùng đúng kỹ thuật so khớp dài nhất có quay lui (maximal munch with backtracking) vẫn dùng trong Lex/Flex: tại một vị trí bắt đầu (bỏ qua các ký tự khoảng trắng \ \t\n\r — các ký tự này chỉ phân tách token, không thuộc Σ), mô phỏng DFA đi xa nhất có thể miễn là ký tự tiếp theo thuộc Σ và có bước chuyển được định nghĩa; trong quá trình đó ghi nhớ vị trí xa nhất mà DFA từng ở một trạng thái kết thúc. Khi không thể đi tiếp (ký tự không thuộc Σ, không có bước chuyển, hoặc hết mã nguồn), quay lui về vị trí kết thúc xa nhất đã ghi nhớ đó, cắt lấy token tương ứng và tiếp tục từ vị trí sau nó.
Nếu tại một vị trí bắt đầu token mới, DFA chưa từng đạt trạng thái kết thúc nào (kể cả sau khi đọc 0 ký tự) trước khi buộc phải dừng, đó là một lỗi từ vựng: cần báo vị trí (dòng, cột — đánh số từ 1) của ký tự bắt đầu token lỗi đó, và dừng xử lý ngay (không xét phần còn lại).
Cho định nghĩa DFA và mã nguồn, hãy token hóa toàn bộ mã nguồn hoặc báo lỗi từ vựng đầu tiên gặp phải.
Dòng 1: số nguyên Q (1≤Q≤50) — số trạng thái. Dòng 2: số nguyên σ rồi σ ký tự của bộ chữ cái Σ (các ký tự phân biệt, cách nhau dấu cách; các ký tự này khác với khoảng trắng, tab, xuống dòng). Q dòng tiếp theo, dòng thứ i (ứng với trạng thái i−1, từ dòng thứ 3) gồm σ số nguyên: số thứ j là trạng thái đến khi ở trạng thái i−1 đọc ký tự thứ j của Σ, hoặc −1 nếu không có bước chuyển. Dòng tiếp theo: số nguyên A — số trạng thái kết thúc. A dòng tiếp theo, mỗi dòng gồm một trạng thái kết thúc và tên loại token tương ứng (một từ không chứa khoảng trắng). Các dòng còn lại (đến hết input): mã nguồn cần token hóa (có thể nhiều dòng, có thể chứa các ký tự không thuộc Σ và không phải khoảng trắng).
Nếu token hóa thành công toàn bộ mã nguồn: in ra một dòng gồm các token theo thứ tự tìm được, mỗi token ở dạng TenLoai:xau_token, cách nhau một dấu cách (nếu không có token nào thì in dòng rỗng).
Nếu gặp lỗi từ vựng: in ra ERROR line col với line, col là vị trí 1-based của ký tự đầu tiên gây lỗi, rồi dừng.
Ví dụ:
Đầu vào:
5
5 a b 0 1 =
1 1 2 2 3
1 1 -1 -1 -1
-1 -1 2 2 -1
-1 -1 -1 -1 4
-1 -1 -1 -1 -1
4
1 ID
2 NUM
3 ASSIGN
4 EQ
ab+cd
Đầu ra:
ERROR 1 3
Đầu vào:
5
5 a b 0 1 =
1 1 2 2 3
1 1 -1 -1 -1
-1 -1 2 2 -1
-1 -1 -1 -1 4
-1 -1 -1 -1 -1
4
1 ID
2 NUM
3 ASSIGN
4 EQ
ab01==a
Đầu ra:
ID:ab NUM:01 EQ:== ID:a
Đang tải editor...