solution

Một văn phạm phi ngữ cảnh được gọi là LL(1) nếu với mọi non-terminal $A$ có từ hai luật sinh trở lên $A \to \alpha_1 \mid \alpha_2 \mid \ldots$, các tập SELECT tương ứng đôi một rời nhau:

$SELECT(A \to \alpha_i) \cap SELECT(A \to \alpha_j) = \emptyset \quad \forall i \ne j$

(định nghĩa $SELECT$ như bài "Tính tập SELECT của một luật sinh"). Nếu tồn tại một cặp luật sinh vi phạm điều kiện trên, bộ phân tích dự đoán (predictive parser) không thể quyết định chọn luật sinh nào chỉ dựa vào 1 ký hiệu lookahead — đó là một XUNG ĐỘT.

Các luật sinh được đánh số $1, 2, \ldots, n$ theo thứ tự trong input. Hãy kiểm tra văn phạm có phải LL(1) hay không; nếu KHÔNG, hãy tìm cặp chỉ số $(i, j)$ với $i < j$ thỏa: cùng thuộc về một non-terminal, $SELECT(i) \cap SELECT(j) \ne \emptyset$, và $i$ nhỏ nhất có thể (nếu có nhiều $j$ ứng với $i$ đó, chọn $j$ nhỏ nhất).

Ví dụ, văn phạm:

S -> A a
A -> a
A -> e

có $FOLLOW(A) = \{a\}$ (từ S -> A a), nên $SELECT(A \to a) = \{a\}$ và $SELECT(A \to \varepsilon) = FOLLOW(A) = \{a\}$ — hai luật sinh (chỉ số 2 và 3) cùng chọn khi lookahead là a. Kết quả in ra: CONFLICT 2 3.