Thiết kế trình biên dịch: Phân tích từ vựng

Trong hướng dẫn trước bạn đã tìm hiểu trình biên dịch là gì? Giới thiệu tổng quan về thiết kế trình biên dịch, các giai đoạn trong trình biên dịch. Nếu bỏ lỡ hướng dẫn này thì bạn có thể xem ở đây:

Thiết kế trình biên dịch: Tổng quan

Trong hướng dẫn này, bạn sẽ tìm hiểu tổng quan trình biên dịch là gì? Vì sao nên học thiết kế trình biên dịch? Các thành phần của trình biên dịch.

Trung NguyenComdy

Trong hướng dẫn này bạn sẽ tìm hiểu về các giai đoạn phân tích từ vựng (Lexical Analysis) trong thiết kế trình biên dịch.

Phân tích từ vựng là giai đoạn đầu tiên của trình biên dịch. Nó lấy mã nguồn đã sửa đổi từ các bộ tiền xử lý ngôn ngữ được viết dưới dạng các câu lệnh.

Trình phân tích từ vựng chia các cú pháp này thành một loạt các mã thông báo (token), bằng cách loại bỏ bất kỳ khoảng trắng hoặc chú thích nào trong mã nguồn.

Nếu trình phân tích từ vựng tìm thấy mã thông báo không hợp lệ, nó sẽ tạo ra lỗi. Bộ phân tích từ vựng hoạt động chặt chẽ với bộ phân tích cú pháp.

Nó đọc các luồng ký tự từ mã nguồn, kiểm tra các mã thông báo hợp lệ và chuyển dữ liệu đến trình phân tích cú pháp khi nó yêu cầu.

Mã thông báo (token)

Lexeme được cho là một chuỗi các ký tự (chữ và số) trong một mã thông báo. Có một số quy tắc được xác định trước để mọi lexeme được xác định là mã thông báo hợp lệ.

Các quy tắc này được xác định bởi các quy tắc ngữ pháp, bằng một khuôn mẫu. Một mẫu giải thích những gì có thể là một mã thông báo và những mẫu này được xác định bằng các biểu thức chính quy (regular expression).

Trong ngôn ngữ lập trình, các từ khóa, hằng số, định danh, chuỗi, số, toán tử và ký hiệu dấu chấm câu có thể được coi là mã thông báo.

Ví dụ, câu lệnh khai báo biến trong ngôn ngữ C sau:

int temp = 100;

Chứa các mã thông báo:

int (keyword)
temp (identifier)
= (operator)
100 (constant)
; (symbol).

Thông số kỹ thuật của Token

Chúng ta hãy hiểu làm thế nào lý thuyết ngôn ngữ thực hiện các thuật ngữ sau:

Bảng chữ cái

Bất kỳ bộ ký hiệu hữu hạn nào {0,1} là một bộ bảng chữ cái nhị phân, {0,1,2,3,4,5,6,7,8,9, A, B, C, D, E, F} là một tập hợp các bảng chữ cái hệ thập lục phân, {az, AZ} là một tập hợp các bảng chữ cái tiếng Anh.

Chuỗi

Bất kỳ chuỗi hữu hạn của bảng chữ cái được gọi là một chuỗi. Độ dài của chuỗi là tổng số lần xuất hiện của các chữ cái, ví dụ: độ dài của chuỗi comdy là 5 và được ký hiệu là | comdy | = 5.

Một chuỗi không có chữ cái, tức là một chuỗi có độ dài bằng 0 được gọi là chuỗi rỗng và được ký hiệu là ε (epsilon).

Ký tự đặc biệt

Một ngôn ngữ cấp cao điển hình chứa các ký hiệu sau: –

Ký hiệu toán học	Phép cộng (+), Phép trừ (-), Phép chia lấy phần dư (%), Phép nhân (*), Phép chia(/)
Chấm câu	Dấu phẩy (,), Dấu chấm phẩy (;), Dấu chấm (.), Dấu mũi tên (->)
Phép gán	=
Phép gán đặc biệt	+=, /=, *=, -=
So sánh	==, !=, <, <=, >, >=
Bộ tiền xử lý	#
Bộ định danh vị trí	&
Logic	&, &&, |, ||, !
Toán tử dịch bit	>>, >>>, <<, <<<

Ngôn ngữ

Một ngôn ngữ được coi là một tập hợp các chuỗi hữu hạn trên một số tập hợp các bảng chữ cái hữu hạn.

Các ngôn ngữ máy tính được coi là tập hợp hữu hạn và tập hợp các tính toán toán học có thể được thực hiện trên chúng. Các ngôn ngữ hữu hạn có thể được mô tả bằng các biểu thức chính quy.

Quy tắc đối sánh dài nhất

Khi bộ phân tích từ vựng đọc mã nguồn, nó sẽ quét từng ký tự mã; và khi nó gặp phải khoảng trắng, ký hiệu toán tử hoặc các ký hiệu đặc biệt, nó sẽ quyết định rằng một từ đã được hoàn thành.

Ví dụ:

int intTemp;

Trong khi quét cả hai từ vựng cho đến khi gặp ‘int’ thứ 2, bộ phân tích từ vựng không thể xác định liệu đó là từ khóa int hay các chữ cái đầu của biến intTemp của mã định danh.

Quy tắc đối sánh dài nhất quy định rằng lexeme được quét phải được xác định dựa trên đối sánh dài nhất trong số tất cả các mã thông báo có sẵn.

Bộ phân tích từ vựng cũng tuân theo quy tắcmức độ ưu tiên trong đó một từ dành riêng, ví dụ, một từ khóa của một ngôn ngữ được ưu tiên hơn so với đầu vào của người dùng. Nghĩa là, nếu trình phân tích từ vựng tìm thấy một lexeme khớp với bất kỳ từ dành riêng nào hiện có, nó sẽ tạo ra lỗi.

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 chuỗi / mã thông báo / lexeme hợp lệ thuộc về ngôn ngữ. 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 thể hiện 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à ngữ pháp thông thường (regular grammar).

Ngôn ngữ được xác định bởi ngữ pháp thông thường được gọi là ngôn ngữ thông thường (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, do đó, 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. Các ngôn ngữ thông thường dễ hiểu và có khả năng triển khai hiệu quả.

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.

Toán tử

Các toán tử khác nhau trên các ngôn ngữ là:

• Phép 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 nối của hai ngôn ngữ L và M được viết là: LM = {st | s ở L và t ở M}
• Bao đóng Kleene của một ngôn ngữ L được viết là: L * = không hoặc nhiều 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ì:

• Phép hợp: (r) | (s) là một biểu thức chính quy biểu thị L(r) U L(s).
• Phép nối: (r) (s) là một biểu thức chính quy biểu thị L(r) L(s).
• Bao đóng Kleene: (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

• *, phép nối (.) và dấu xuyệt đứng (|) được kết hợp trái
• * có mức độ ưu tiên cao nhất
• Phép nối (.) có mức độ ưu tiên cao thứ hai.
• dấu xuyệt đứng (|) có mức độ ưu tiên thấp nhất.

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 chữ cái viết thường của ngôn ngữ tiếng Anh.

[AZ] là tất cả các 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

• Chữ cái = [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 để 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 là sử dụng máy tự động hữu hạn để xác minh.

Máy tự động hữu hạn

Máy tự động hữu hạn (Finite automata) là một máy trạng thái lấy một chuỗi ký hiệu làm đầu vào và thay đổi trạng thái của nó tương ứng.

Máy tự động hữu hạn là một trình nhận dạng cho các biểu thức chính quy. Khi một chuỗi biểu thức chính quy được đưa vào máy tự động hữu hạn, nó sẽ thay đổi trạng thái của nó cho mỗi chữ cái.

Nếu chuỗi đầu vào được xử lý thành công và dữ liệu tự động đạt đến trạng thái cuối cùng, nó được chấp nhận, tức là chuỗi vừa được nạp được cho là mã thông báo hợp lệ của ngôn ngữ.

Mô hình toán học của máy tự động hữu hạn bao gồm:

• Tập hợp hữu hạn các trạng thái (Q).
• Tập hợp hữu hạn các ký hiệu đầu vào (Σ).
• Một trạng thái bắt đầu (q0).
• Tập hợp các trạng thái cuối cùng (qf).
• Hàm chuyển tiếp (δ).

Hàm chuyển tiếp (δ) ánh xạ tập hữu hạn trạng thái (Q) thành một tập hữu hạn các ký hiệu đầu vào (Σ), Q × Σ ➔ Q

Xây dựng máy tự động hữu hạn

Cho L(r) là một ngôn ngữ thông thường được công nhận bởi một số máy tự động hữu hạn (FA).

• Trạng thái: Các trạng thái của máy tự động hữu hạn được đại diện bởi các vòng tròn. Tên trạng thái được viết bên trong vòng tròn.
• Trạng thái bắt đầu: Trạng thái từ nơi máy tự động hữu hạn bắt đầu, được gọi là trạng thái bắt đầu. Trạng thái bắt đầu có một mũi tên chỉ về phía nó.
• Các trạng thái trung gian: Tất cả các trạng thái trung gian đều có ít nhất hai mũi tên; một trỏ đến và một trỏ ra khỏi chúng.
• Trạng thái cuối cùng: Nếu chuỗi đầu vào được phân tích cú pháp thành công, máy tự động hữu hạn sẽ ở trạng thái này. Trạng thái cuối cùng được biểu diễn bằng các vòng tròn đôi. Nó có thể có bất kỳ số lượng mũi tên lẻ nào trỏ đến nó và số lượng mũi tên chẵn hướng ra từ nó. Số mũi tên lẻ lớn hơn số chẵn, tức là số lẻ = chẵn + 1.
• Chuyển đổi: Sự chuyển đổi từ trạng thái này sang trạng thái khác xảy ra khi một ký tự mong muốn trong đầu vào được tìm thấy. Khi chuyển đổi, máy tự động hữu hạn có thể chuyển sang trạng thái tiếp theo hoặc giữ nguyên trạng thái đó. Chuyển đổi từ trạng thái này sang trạng thái khác được thể hiện dưới dạng một mũi tên có hướng, trong đó các mũi tên chỉ đến trạng thái đích. Nếu máy tự động hữu hạn vẫn ở cùng một trạng thái, một mũi tên chỉ từ một trạng thái đến chính nó sẽ được vẽ.

Ví dụ: Chúng tôi giả sử máy tự động hữu hạn (FA) chấp nhận bất kỳ giá trị nhị phân có ba chữ số nào kết thúc bằng chữ số 1.

FA = {Q(q0, qf), Σ(0,1), q0, qf, δ}

Ở hướng dẫn tiếp theo, bạn sẽ tìm hiểu chi tiết về phân tích cu pháp và trình phân tích cú pháp trong thiết kế trình biên dịch.

Thiết kế trình biên dịch: Phân tích cụ pháp

Trong hướng dẫn này, bạn sẽ tìm hiểu chi tiết về phân tích cu pháp và trình phân tích cú pháp trong thiết kế trình biên dịch.

Trung NguyenComdy