solution

Cho một văn phạm phi ngữ cảnh (CFG) với ký hiệu bắt đầu $S$ (không đảm bảo là LL(1)).

Quy ước biểu diễn văn phạm phi ngữ cảnh (CFG) dùng chung cho đề này:

• Mỗi ký hiệu chưa kết thúc (non-terminal) là một chữ cái in hoa (A-Z).
• Mọi token khác (chữ thường, số, hoặc ký hiệu như (, ), +, *, id, num, ...) là ký hiệu kết thúc (terminal); terminal có thể dài nhiều ký tự nhưng không chứa khoảng trắng.
• Token đặc biệt e ở vế phải nghĩa là luật sinh sinh ra chuỗi rỗng $\varepsilon$ (ví dụ A -> e).
• Ký hiệu kết thúc đầu vào (end-of-input) được ký hiệu là $ khi cần dùng tới FOLLOW.
• Đảm bảo mọi ký hiệu chưa kết thúc xuất hiện ở vế phải của bất kỳ luật sinh nào cũng đều có ít nhất một luật sinh định nghĩa nó (văn phạm "đóng", không có non-terminal mồ côi).

Với mỗi ký hiệu chưa kết thúc $A$ có các luật sinh $A \to \alpha_1, \ldots, A \to \alpha_m$ ($m \ge 2$), xét mọi cặp chỉ số $i<j$. Gọi $SELECT(A \to \alpha_i) = FIRST(\alpha_i)\setminus\{\varepsilon\}$, cộng thêm $FOLLOW(A)$ nếu $\varepsilon \in FIRST(\alpha_i)$. Nếu $SELECT(A\to\alpha_i) \cap SELECT(A\to\alpha_j) \neq \emptyset$ thì cặp luật sinh này xung đột. Phân loại xung đột đó thành 2 nhóm:

• FIRST/FIRST: nếu $(FIRST(\alpha_i)\setminus\{\varepsilon\}) \cap (FIRST(\alpha_j)\setminus\{\varepsilon\}) \neq \emptyset$ (hai luật sinh có ký hiệu bắt đầu terminal trùng nhau thật sự).
• FIRST/FOLLOW: nếu không thuộc trường hợp trên (xung đột chỉ phát sinh do một trong hai luật sinh có thể sinh $\varepsilon$ và phần giao nằm trong $FOLLOW(A)$).

Hãy đếm tổng số cặp luật sinh xung đột trên toàn bộ văn phạm, tách riêng theo 2 loại trên (mỗi cặp $(i,j)$ chỉ thuộc đúng một trong hai loại).

Ví dụ

Với văn phạm S -> F, F -> id, F -> id, F -> num: cặp (luật sinh 1, luật sinh 2) của $F$ (hai lần id) xung đột kiểu FIRST/FIRST; cặp còn lại với num không xung đột. Kết quả: 1 0.