Phân tích từ vựng

Quá trình phân tích từ vựng trong các giai đoạn xử lý.

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.^[1] 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ố.

Tên từ tố	Ví dụ
định danh	x, color, UP
từ khoá	if, while, return
dấu ngăn cách	}, (, ;
toán tử	+, <, =
nguyên văn	true, 6.02e23, "âm nhạc"
chú thích	/* Lấy dữ liệu người dùng */, // phải là số nguyên âm

Ngữ pháp từ vựng

Xem thêm thông tin: 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

Quá trình phân tích từ vựng tạo ra các dấu hiệu (token) cho bước phân tích cú pháp tiếp theo.

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

1. page 111, "Compilers Principles, Techniques, & Tools, 2nd Ed." (WorldCat) by Aho, Lam, Sethi and Ullman, as quoted in https://stackoverflow.com/questions/14954721/what-is-the-difference-between-token-and-lexeme

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. 177. Boston: Pearson/Addison-Wesley.
• Word Mention Segmentation Task analysis page
• On the applicability of the longest-match rule in lexical analysis Lưu trữ 2012-02-25 tại Wayback Machine