solution

Chương trình (một phạm vi duy nhất, không lồng nhau) được biểu diễn bằng dãy $m$ lệnh xử lý tuần tự theo đúng thứ tự dòng, mỗi lệnh thuộc một trong hai dạng:

• DECL type name len: khai báo mảng name gồm len phần tử kiểu type ($type \in$ {char, int, double}, kích thước phần tử tương ứng 1, 4, 8 byte). Bộ cấp phát offset hoạt động tuần tự dùng một con trỏ $off$ dùng chung cho toàn bộ chương trình (bắt đầu $off=0$): gọi $s$ là kích thước phần tử của type; offset gán cho mảng là bội số nhỏ nhất của $s$ không nhỏ hơn $off$ hiện tại (chèn đệm nếu cần); sau đó cập nhật $off \leftarrow \text{offset\_gán} + s \times \text{len}$. Giả thiết tên mảng khi khai báo luôn khác các tên đã khai báo trước đó (không cần xử lý trùng tên).
• INDEX name idx: kiểm tra ngữ nghĩa của việc truy cập phần tử name[idx] tại đúng thời điểm này (dùng trạng thái bảng ký hiệu hiện có, tức chỉ các DECL đã xử lý trước đó theo thứ tự dòng mới có hiệu lực):
  • nếu name chưa từng được DECL tính đến dòng này → báo UNDECLARED;
  • ngược lại, nếu idx (số nguyên, có thể âm) nằm ngoài đoạn $[0, len-1]$ của mảng đó → báo OUT_OF_BOUNDS;
  • ngược lại, hợp lệ: địa chỉ tuyệt đối của phần tử là $\text{offset\_mảng} + idx \times s$ (với $s$ là kích thước phần tử) → báo OK addr.

Ví dụ: DECL int a 3 (offset 0, size $4\times3=12$, $off=12$); INDEX a 0 → hợp lệ, addr $=0+0 \times 4=0$ → a OK 0; INDEX a 5 → $5 \notin [0,2]$ → a OUT_OF_BOUNDS; INDEX b 0 — b chưa được khai báo tại thời điểm này → b UNDECLARED; DECL double b 2 (yêu cầu offset là bội của 8 không nhỏ hơn 12, tức 16; $off$ mới $=16+16=32$).