Trong phân tích cú pháp LR, tập FOLLOW(A) của một ký hiệu chưa kết thúc (non-terminal) A là tập các ký hiệu kết thúc (terminal) có thể xuất hiện ngay sau A trong một dạng câu suy dẫn nào đó, kể cả ký hiệu kết thúc xâu "$\$$"" (dùng để đánh dấu cuối chuỗi nhập). Tập FOLLOW là thành phần bắt buộc khi xây dựng bảng phân tích SLR(1).
Cho một văn phạm phi ngữ cảnh (không có ký hiệu chưa kết thúc nào trùng tên ký hiệu kết thúc). Ký hiệu bắt đầu của văn phạm là vế trái (LHS) của luật sinh đầu tiên trong danh sách. Một ký hiệu chưa kết thúc là ký hiệu xuất hiện ở vế trái của ít nhất một luật sinh; mọi ký hiệu khác xuất hiện ở vế phải (RHS) được coi là ký hiệu kết thúc. Luật sinh rỗng (dẫn xuất ε) được ghi bằng ký hiệu đặc biệt # ở vế phải, ví dụ A -> #.
Hãy tính tập FOLLOW của mọi ký hiệu chưa kết thúc theo thuật toán chuẩn (dùng FIRST và lan truyền điểm bất động).
Ví dụ: Với văn phạm
6
E -> E + T
E -> T
T -> T * F
T -> F
F -> ( E )
F -> id
kết quả là:
E: ) + $
T: ) * + $
F: ) * + $
Dòng 1: số nguyên n (1≤n≤15) — số luật sinh.
n dòng tiếp theo: mỗi dòng có dạng LHS -> s1 s2 ... sk, trong đó LHS là một ký hiệu chưa kết thúc, các si là các ký hiệu (chưa kết thúc hoặc kết thúc) cách nhau bởi dấu cách. Nếu vế phải là rỗng (ε), ghi đúng một ký hiệu # sau dấu ->.
In ra đúng m dòng (với m là số ký hiệu chưa kết thúc phân biệt), theo đúng thứ tự xuất hiện lần đầu của các ký hiệu chưa kết thúc đó (là LHS) trong danh sách luật sinh đầu vào. Mỗi dòng có dạng Ten: t1 t2 ... tk, trong đó các terminal thuộc FOLLOW được liệt kê theo thứ tự từ điển tăng dần (so sánh chuỗi), riêng ký hiệu kết thúc chuỗi $ — nếu có trong FOLLOW — luôn được in cuối cùng bất kể thứ tự từ điển. Giữa Ten: và danh sách, cũng như giữa các phần tử, dùng đúng một dấu cách.
Ví dụ:
Đầu vào:
6
E -> E + T
E -> T
T -> T * F
T -> F
F -> ( E )
F -> id
Đầu ra:
E: ) + $
T: ) * + $
F: ) * + $
Đầu vào:
4
S -> A B
A -> a A
A -> #
B -> b
Đầu ra:
S: $
A: b
B: $
Đang tải editor...