solution

Trình biên dịch cấp phát bộ nhớ cho một bản ghi (struct) bằng một SDD (syntax-directed definition) trong đó mỗi trường có một thuộc tính tổng hợp (synthesized) width (kích thước) và nhận một thuộc tính kế thừa (inherited) offset (vị trí bắt đầu của trường, tính từ đầu bản ghi), được cập nhật tuần tự: offset của trường sau bằng offset của trường trước cộng width của nó, có làm tròn lên theo yêu cầu căn lề (alignment).

Cho $n$ trường theo đúng thứ tự khai báo, mỗi trường có kiểu cơ sở thuộc $\{\text{char}, \text{short}, \text{int}, \text{long}\}$ với (kích thước, căn lề) tương ứng là $(1,1), (2,2), (4,4), (8,8)$ byte, hoặc là một mảng của kiểu cơ sở gồm $k$ phần tử liên tiếp (kích thước $= k \times$ kích thước phần tử, căn lề $=$ căn lề phần tử, không đổi).

Quy tắc cấp phát: gọi $p$ là con trỏ cấp phát hiện tại (khởi đầu $p=0$). Trường có yêu cầu căn lề $a$ được đặt tại offset $= \lceil p / a \rceil \times a$ (chèn padding nếu cần), sau đó $p \leftarrow \text{offset} + \text{width}$. Sau khi cấp phát hết $n$ trường, tổng kích thước bản ghi (bao gồm tail padding) được làm tròn lên theo bội số của căn lề lớn nhất trong toàn bộ bản ghi: $\text{SIZE} = \lceil p / a_{\max} \rceil \times a_{\max}$.

Ví dụ với 4 trường a:char, b:int, c:char[3], d:long: a tại offset 0 (p=1); b cần căn lề 4 nên offset 4 (p=8); c (kích thước 3, căn lề 1) tại offset 8 (p=11); d cần căn lề 8 nên offset 16 (p=24); căn lề lớn nhất là 8 nên SIZE $=24$.