solution

Một kỹ thuật phục hồi lỗi ngữ nghĩa phổ biến khi trình biên dịch gặp một định danh chưa khai báo là gợi ý định danh gần đúng nhất có trong bảng ký hiệu (giống thông báo "did you mean ...?" của nhiều trình biên dịch hiện đại), dựa trên khoảng cách chỉnh sửa Levenshtein: số phép chèn, xóa, thay thế ký tự tối thiểu để biến chuỗi này thành chuỗi kia.

Cho bảng ký hiệu gồm $n$ định danh hợp lệ, và $m$ định danh bị báo lỗi "chưa khai báo". Với mỗi định danh lỗi $x$, xét tất cả định danh $y$ trong bảng ký hiệu, tính khoảng cách Levenshtein $d(x,y)$. Gọi $t = \lfloor |x| / 2 \rfloor$ (với $|x|$ là độ dài $x$) là ngưỡng chấp nhận.

• Nếu tồn tại ít nhất một $y$ với $d(x,y) \le t$: chọn $y$ có $d(x,y)$ nhỏ nhất; nếu có nhiều $y$ cùng đạt khoảng cách nhỏ nhất, chọn $y$ nhỏ nhất theo thứ tự từ điển (so sánh chuỗi thông thường).
• Nếu không có $y$ nào thỏa: không có gợi ý.

Ví dụ: bảng ký hiệu $\{$counter, total, result$\}$, định danh lỗi countr (độ dài 6, ngưỡng $t=3$). Khoảng cách đến counter là 1 (thiếu một ký tự e) — nhỏ nhất và $\le 3$ → gợi ý counter.