Cho một văn phạm phi ngữ cảnh gồm các ký hiệu chưa kết thúc là chữ cái in hoa (A-Z, mỗi ký hiệu 1 ký tự) và các ký hiệu kết thúc là các token khác. Luật sinh rỗng (sinh ra ε) được ghi là A -> eps.
Với một tập mục hạt nhân (kernel items) ban đầu, hãy tính bao đóng (closure) của tập mục đó theo đúng thuật toán chuẩn: lặp lại — với mỗi mục A→α.Bβ trong tập hiện tại mà B là ký hiệu chưa kết thúc, với mọi luật sinh B→γ của văn phạm, thêm mục B→.γ vào tập (nếu chưa có) — cho đến khi tập không đổi (điểm bất động). Với luật sinh rỗng B→ε, mục được thêm là B -> . (dấu chấm đứng một mình).
Ví dụ: văn phạm gồm E -> E + T, E -> T, T -> T * F, T -> F, F -> ( E ), F -> id; với hạt nhân {E -> . E + T}, bao đóng thu được gồm 6 mục (đã sắp xếp theo thứ tự từ điển của chuỗi biểu diễn mục): E -> . E + T, E -> . T, F -> . ( E ), F -> . id, T -> . F, T -> . T * F.
Dòng đầu là P (1≤P≤30) — số luật sinh của văn phạm. P dòng tiếp theo, mỗi dòng dạng A -> X1 X2 ... Xk (nếu k=0, ghi A -> eps). Dòng tiếp theo là K (1≤K≤10) — số mục hạt nhân. K dòng tiếp theo là các mục hạt nhân dạng A -> ... . ... (đúng một dấu chấm trong vế phải, có thể ở đầu, giữa, hoặc cuối; một mục ứng với luật sinh rỗng trong hạt nhân được ghi trực tiếp là A -> .).
In ra dòng đầu là M — tổng số mục trong bao đóng. M dòng tiếp theo là các mục, mỗi mục theo định dạng A -> t1 t2 . t3 ... (nếu vế phải rỗng thì in A -> .), được sắp xếp tăng dần theo thứ tự từ điển (so sánh chuỗi ký tự) của toàn bộ chuỗi biểu diễn mục.
Ví dụ:
Đầu vào:
6
E -> E + T
E -> T
T -> T * F
T -> F
F -> ( E )
F -> id
1
E -> . E + T
Đầu ra:
6
E -> . E + T
E -> . T
F -> . ( E )
F -> . id
T -> . F
T -> . T * F
Đầu vào:
4
S -> A B
A -> a A
A -> eps
B -> b
1
S -> . A B
Đầu ra:
3
A -> .
A -> . a A
S -> . A B
Đang tải editor...