solution

Chuẩn C quy định cơ chế quét lại (rescanning): sau khi một macro được thay bằng thân của nó, dãy token mới sinh ra tiếp tục được quét để tìm macro cần khai triển thêm. Vì thân của một macro có thể chứa (trực tiếp hoặc gián tiếp) chính tên của nó, để thuật toán luôn dừng, chuẩn C áp dụng luật "tô xanh" (blue paint / self-referential macro protection):

Mỗi token trong quá trình khai triển được gắn một tập nhãn — tập tên các macro đã được dùng để sinh ra token đó trên đường từ token gốc. Tại một bước, một token là tên macro $X$ chỉ được khai triển nếu $X$ không có mặt trong tập nhãn của chính token đó. Khi khai triển token này (thay bằng thân của $X$), mọi token mới sinh ra được kế thừa tập nhãn của token cũ cộng thêm $X$.

Cho $m$ macro đối tượng (object-like, không tham số), mỗi macro có tên và thân là một dãy token. Cho một dãy token ban đầu (tập nhãn rỗng cho mỗi token gốc). Hãy khai triển lặp đi lặp lại theo đúng luật trên (mỗi bước, quét từ trái sang phải, khai triển token đầu tiên thoả điều kiện có thể khai triển, rồi quét lại từ đầu) cho đến khi không còn token nào khai triển được nữa.

Ví dụ: với A có thân a SELF b... — nói cách khác, nếu thân của SELF là a SELF b thì khai triển SELF một lần cho ra a SELF b, và token SELF mới này đã mang nhãn {SELF} nên không được khai triển tiếp — kết quả cuối cùng là a SELF b.

In ra dãy token cuối cùng, cách nhau bởi đúng một dấu cách (in dòng trống nếu kết quả không còn token nào).