Trong một trình biên dịch, sau khi từ vựng hoá, các định danh (identifier) do người dùng đặt tên được đưa vào bảng ký hiệu (symbol table), còn các từ khoá (keyword) của ngôn ngữ thì không.
Cho danh sách k từ khoá của ngôn ngữ và một đoạn mã nguồn nhiều dòng. Quét đoạn mã theo lexer đơn giản sau: bỏ qua khoảng trắng và ký tự xuống dòng; một định danh khớp mẫu [a-zA-Z_][a-zA-Z0-9_]∗; một số khớp mẫu digit+; mọi ký tự khác (dấu ngoặc, toán tử, ...) được xem là một token riêng lẻ độc lập (không cần phân loại thêm). Việc so khớp luôn theo maximal munch.
Duyệt các token theo đúng thứ tự xuất hiện (từ trên xuống dưới, trái sang phải). Với mỗi token là định danh và không trùng khớp chính xác với bất kỳ từ khoá nào, nếu đây là lần đầu tiên định danh đó xuất hiện, hãy gán cho nó một chỉ số ID bắt đầu từ 0, tăng dần theo thứ tự xuất hiện lần đầu.
Dòng 1: số nguyên k (k≥0) — số lượng từ khoá. Dòng 2: k từ khoá cách nhau bởi khoảng trắng (dòng này vẫn tồn tại kể cả khi k=0, khi đó có thể là dòng rỗng). Các dòng tiếp theo (đến hết input): mã nguồn cần phân tích, có thể rỗng (không có dòng nào).
Nếu bảng ký hiệu có ít nhất một định danh, in mỗi dòng theo định dạng ID TEN, theo thứ tự ID tăng dần. Nếu không có định danh nào (ngoài từ khoá), in ra đúng một dòng EMPTY.
Ví dụ:
Đầu vào:
0
a b a c b d
Đầu ra:
0 a
1 b
2 c
3 d
Đầu vào:
3
if else while
if (x > 0) { y = x + 1; } else { y = while_val; }
Đầu ra:
0 x
1 y
2 while_val
Đang tải editor...