Thiết kế trình biên dịch - Dữ liệu tự động hữu hạn
Automata hữu hạn 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. Dữ liệu 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 ô tự động hữu hạn, nó sẽ thay đổi trạng thái của nó cho mỗi chữ. 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ữ trong tay.
Mô hình toán học của ô tô 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 dữ liệu tự động hữu hạn
Cho L (r) là một ngôn ngữ thông thường được một số tự động hữu hạn (FA) công nhận.
States: Các quốc gia của CHNC được biểu diễn bằng các vòng tròn. Tên tiểu bang được viết bên trong vòng tròn.
Start state: Trạng thái từ nơi tự động 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ó.
Intermediate states: 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.
Final state: Nếu chuỗi đầu vào được phân tích cú pháp thành công, dữ liệu tự động 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ố lượng mũi tên lẻ lớn hơn một mũi tên chẵn, tức làodd = even+1.
Transition: Sự chuyển đổi từ trạng thái này sang trạng thái khác xảy ra khi tìm thấy một ký hiệu mong muốn trong đầu vào. Khi chuyển đổi, dữ liệu tự động có thể chuyển sang trạng thái tiếp theo hoặc giữ nguyên trạng thái đó. Chuyển động 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 dữ liệu tự động 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ẽ.
Example: Chúng tôi giả sử 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 (q 0 , q f ), Σ (0,1), q 0 , q f , δ}
