Phân tích từ vựng

Trong ngành khoa học máy tính, phân tích từ vựng (Tiếng Anh: lexical analysis, còn được gọi là scanning hoặc lexing) là một quá trình chuyển đổi chuỗi ký tự nguồn thành một chuỗi liên tiếp các đoạn ký tự ngắn hơn đã được phân loại, gọi là từ tố (tokens). Chương trình dùng để phân tích từ vựng được gọi là bộ phân tích từ vựng (tiếng Anh là lexer).

Từ tố
Từ tố (token) là một xâu được gán với một ý nghĩa xác định, có phần giống với loại từ trong ngôn ngữ học. Nó được xây dựng thành cặp gồm mọt tên từ tố và một giá trị từ tố tuỳ chọn. Từ tố là một loại đơn vị từ vựng. Tương tự như danh từ, tính từ và động từ, từ tố cũng có nhiều loại tùy theo đặc điểm của trình biên dịch. Một số tên từ tố phổ biến gồm:

định danh (identifier): những tên do lập trình viên tự đặt;
từ khoá (keyword): những tên đã có trong ngôn ngữ lập trình;
dấu ngăn cách (delimiter): các kí tự dấu câu và các cặp dấu ngăn cách;
toán tử (operator): những biểu tượng thao tác với các đối số để tạo ra kết quả;
nguyên văn (literal): các nguyên văn là số, chữ hoặc tham chiếu;
chú thích: dòng hoặc khối; sẽ bị loại bỏ nếu trình biên dịch không coi chú tính là từ tố.

Ngữ pháp từ vựng
Phần đặc tả của một ngôn ngữ lập trình thường bao gồm một tập hợp các quy tắc, gọi là ngữ pháp từ vựng, định nghĩa các cú pháp từ vựng. Cú pháp từ vựng thường là một ngôn ngữ chính quy, với các quy tắc ngữ pháp gồm các biểu thức chính quy; chúng định nghĩa tập hợp các chuỗi kí tự có thể (vị từ) của một từ tố. Một bộ phân tích từ vựng nhận diện các xâu, và với mỗi loại xâu tìm thấy thì thực hiện một hành động, chủ yếu chỉ đơn giản là tạo ra một dấu hiệu.

Từ tố hoá
Từ tố hoá (tokenization) là quá trình vạch ra ranh giới – và có thể là cả phân loại – giữa các đoạn của một xâu các kí tự đầu vào. Các từ tố này sau đó được chuyển sang các dạng xử lí khác. Quá trình này có thể được coi là một công việc phụ của quá trình phân tích cú pháp.

Thí dụ, trong xâu kí tự sau:

: The quick brown fox jumps over the lazy dog

xâu trên không được phân đoạn một cách ngầm định bằng dấu cách như cách một người nói ngôn ngữ tự nhiên sẽ làm. Xâu đầu vào thô gồm 43 kí tự này phải được ngắt một cách rõ ràng ra thành 9 từ tố với dấu phân cách là dấu cách (v.d. so khớp xâu " " hoặc bằng biểu thức chính quy /\s{1}/).

Quá trình
Các nhiệm vụ của quá trình phân tích từ vựng gồm:
Đọc các ký tự đầu vào
Phát sinh các chuỗi dấu hiệu đầu ra
Bỏ khoảng trắng, cách dòng, tab
Ghi lại vị trí các dấu hiệu được dùng cho bước xử lý tiếp theo.

Các công cụ phát sinh mã phân tích từ vựng
ANTLR - ANTLR phát sinh cú pháp predicated-LL(k).
Flex - Biến thể thay thế của dạng cổ điển "lex" (C/C++).
JFlex - Viết lại của JLex.
Ragel - Bộ quét từ vựng hỗ trợ đầu ra cho mã nguồn C, C++, C, Objective-C, D, Java, Go và Ruby.
Các công cụ phát sinh có thể xử lý Unicode:
JavaCC - JavaCC phát sinh phân tích từ vựng viết trong Java.
JLex - Công cụ phát sinh phân tích từ vựng dành cho Java.
Quex (hoặc "Queχ") - Công cụ phát sinh phân tích từ vựng nhanh cho C và C++.

Xem thêm
Trình biên dịch
Nguyên lý ngôn ngữ lập trình
Phân tích cú pháp
Biểu thức chính quy
Bộ tiền xử lý

Tham khảo

Liên kết ngoài
Compiling with C and Java, Pat Terry, 2005, ISBN 032126360X624
Algorithms + Data Structures = Programs, Niklaus Wirth, 1975, ISBN 0-13-022418-9
Compiler Construction, Niklaus Wirth, 1996, ISBN 0-201-40353-6
Sebesta, R. W. (2006). Concepts of programming languages (Seventh edition) pp.&nbsp;177. Boston: Pearson/Addison-Wesley.
Word Mention Segmentation Task analysis page
On the applicability of the longest-match rule in lexical analysis