solution

Xét văn phạm mô tả một "chương trình" là danh sách các câu lệnh, mỗi câu lệnh chỉ là token id, các câu lệnh cách nhau bởi token ;: $\text{Program} \to \text{id} \; (; \; \text{id})^*$

Một bộ phân tích đệ quy xuống (recursive-descent) xử lý luồng token lần lượt, luôn ở một trong hai trạng thái kỳ vọng: kỳ vọng id hoặc kỳ vọng ;, bắt đầu ở trạng thái kỳ vọng id.

• Nếu token hiện tại khớp với kỳ vọng: tiêu thụ token đó, chuyển sang kỳ vọng còn lại (id $\leftrightarrow$ ;), tiếp tục.
• Nếu không khớp: tăng biến đếm lỗi, rồi áp dụng panic mode với token đồng bộ hoá là ;: bỏ qua liên tiếp các token cho đến khi gặp token ; (token này được tiêu thụ luôn, coi là điểm đồng bộ) hoặc hết luồng token. Sau khi tiêu thụ token ; đồng bộ, bộ phân tích quay về trạng thái kỳ vọng id (bắt đầu câu lệnh tiếp theo). Nếu luồng token kết thúc trước khi tìm được ; để đồng bộ, quá trình phân tích dừng lại.

Cho luồng gồm $n$ token (mỗi token là id, ;, hoặc một chuỗi "rác" bất kỳ khác), hãy tính tổng số lỗi cú pháp được phát hiện.

Ví dụ: luồng gồm 5 token id ; id id ;. Xử lý: id khớp (kỳ vọng id) → kỳ vọng ;; ; khớp → kỳ vọng id; id khớp → kỳ vọng ;; token thứ 4 là id nhưng đang kỳ vọng ; → không khớp, 1 lỗi, bỏ qua đến khi gặp ; (token thứ 4 bị bỏ qua, token thứ 5 là ; được tiêu thụ để đồng bộ) → kỳ vọng id; hết luồng. Tổng số lỗi: 1.