Tập FOLLOW(A) của một non-terminal A là tập các terminal có thể xuất hiện NGAY SAU A trong một dạng câu (sentential form) suy dẫn được từ ký hiệu bắt đầu, cộng thêm ký hiệu kết thúc đầu vào \$$ nếu A$ có thể là ký hiệu cuối cùng của một câu hợp lệ:
FOLLOW(A)={a∣S⇒∗αAaβ} ∪ {$∣S⇒∗αA}
Quy ước văn phạm giống các bài trước (non-terminal 1 chữ in hoa, e đứng riêng biểu diễn ε). Hãy tính FOLLOW(A) cho tất cả non-terminal của văn phạm.
Ví dụ, với văn phạm biểu thức số học kinh điển (ký hiệu bắt đầu E):
E -> T X
X -> + T X
X -> e
T -> F Y
Y -> * F Y
Y -> e
F -> ( E )
F -> id
FOLLOW(E) = \{), \},FOLLOW(F) = {), *, +, $}$, v.v.
A -> X1 X2 ... Xk (hoặc A -> e).Đảm bảo mọi non-terminal xuất hiện ở vế phải đều có ít nhất một luật sinh định nghĩa nó.
In ra đúng một dòng cho MỖI non-terminal của văn phạm (kể cả khi FOLLOW rỗng), theo thứ tự bảng chữ cái tên non-terminal, dạng:
A:t1,t2,...
trong đó A là tên non-terminal, sau dấu : là danh sách terminal thuộc FOLLOW(A) sắp xếp theo thứ tự bảng chữ cái (ASCII) tăng dần, cách nhau bởi dấu phẩy (không khoảng trắng); nếu \ \in FOLLOW(A)thıˋđặt‘ở **cuối** danh sách (sau mọi terminal khác, bất kể thứ tự bảng chữ cái). Nếu $FOLLOW(A)$ rỗng, inA:` (không có gì sau dấu hai chấm).
Ví dụ:
Đầu vào:
S
2
S -> a S
S -> b
Đầu ra:
S:$
Đầu vào:
E
8
E -> T X
X -> + T X
X -> e
T -> F Y
Y -> * F Y
Y -> e
F -> ( E )
F -> id
Đầu ra:
E:),$
F:),*,+,$
T:),+,$
X:),$
Y:),+,$
Đang tải editor...