solution

Một macro object-like có thể tham chiếu đến chính nó hoặc tạo thành vòng lặp tham chiếu lẫn nhau (ví dụ #define X 1 + X). Nếu khai triển "ngây thơ" (cứ thấy tên macro là thay thế) thì quá trình này sẽ lặp vô hạn. Các trình biên dịch C thật sự tránh điều này bằng quy tắc: trong quá trình khai triển một macro, nếu tên của chính nó (hoặc tên của một macro "tổ tiên" đang trong quá trình khai triển dẫn đến vị trí hiện tại) xuất hiện lại, thì không khai triển tiếp occurrence đó nữa — giữ nguyên nó như một token thường (dân trong ngành gọi vui là macro đó đã bị "sơn xanh" tại vị trí đó).

Cho $n$ định nghĩa macro object-like (không tham số) NAME t_1 t_2 \dots t_B, trong đó $NAME$ là tên macro và $t_1,\dots,t_B$ là thân macro — một dãy token ($B \ge 0$), mỗi token có thể là tên của một macro khác (kể cả chính nó) hoặc một token thường. Cho một tên macro truy vấn $Q$ (đảm bảo đã được định nghĩa).

Hãy khai triển $Q$ đầy đủ theo quy tắc đệ quy chính xác sau: gọi $\text{expand}(t, S)$ là kết quả khai triển token $t$ biết tập "đã sơn xanh" hiện tại là $S$ — nếu $t$ là tên một macro và $t \notin S$, kết quả là nối tiếp $\text{expand}(t_i, S \cup \{t\})$ cho từng token $t_i$ trong thân macro $t$ (theo thứ tự); ngược lại (không phải macro, hoặc $t \in S$) kết quả là chính token $t$. Đáp số là $\text{expand}(Q, \emptyset)$.

Ví dụ: X có thân 1 + X. Khai triển X: vì X tham chiếu chính nó, khi gặp lại token X bên trong khai triển của chính nó thì giữ nguyên. Kết quả: 1 + X.