solution

Xét văn phạm phi ngữ cảnh sinh ra các chuỗi ngoặc tròn cân bằng:

$S \to (\,S\,)\,S \;\mid\; \varepsilon$

Cho một chuỗi $s$ chỉ gồm các ký tự ( và ) (có thể rỗng, độ dài tới $10^4$). Hãy dùng bộ phân tích cú pháp đệ quy đi từ trái sang phải theo đúng văn phạm trên để xác định chuỗi có thuộc ngôn ngữ $L(S)$ hay không.

Nếu chuỗi hợp lệ, hãy tính thêm độ sâu lồng ngoặc lớn nhất (số cặp ngoặc mở chưa đóng tại thời điểm sâu nhất). Nếu chuỗi không hợp lệ, hãy xác định vị trí (0-indexed) đầu tiên mà bộ phân tích không thể tiếp tục khớp theo văn phạm: đó là vị trí một ký tự ) dư thừa không có ( tương ứng đứng trước nó, hoặc bằng độ dài chuỗi nếu thiếu ) ở cuối để đóng một ( đã mở.

Ví dụ: chuỗi (() thiếu một dấu ) ở cuối, bộ phân tích báo lỗi tại vị trí $3$ (bằng độ dài chuỗi), in ra INVALID 3.