Bài tập | NEU OJ

Khi xây dựng bảng phân tích $LL(1)$ $M[A, a]$ từ các tập $\text{SELECT}$ (xem định nghĩa $\text{SELECT}(A \to \alpha) = (\text{FIRST}(\alpha)\setminus\{\varepsilon\}) \cup \text{FOLLOW}(A)\,[\varepsilon \in \text{FIRST}(\alpha)]$ ), một Ô $M[A, a]$ được gọi là XUNG ĐỘT (conflict) nếu có TỪ HAI luật sinh $A \to \alpha_i$ trở lên cùng thỏa $a \in \text{SELECT}(A \to \alpha_i)$ — khi đó bộ phân tích không thể quyết định dùng luật sinh nào chỉ dựa vào kí hiệu tra trước $a$ , và văn phạm không phải $LL(1)$ .

Cho văn phạm $G$ gồm $n$ luật sinh được đánh số $1,\dots,n$ theo thứ tự trong input, hãy tìm TẤT CẢ các ô xung đột của bảng $LL(1)$ : với mỗi kí hiệu chưa kết thúc $A$ và kí hiệu kết thúc $a$ (kể cả $) sao cho ô $M[A,a]$ có từ 2 luật sinh trở lên, báo cáo cặp $(A, a)$ cùng danh sách CHỈ SỐ (1-based, theo thứ tự input) của các luật sinh gây xung đột tại đó.

Ví dụ: với văn phạm dangling-else

S -> if E then S S1
S1 -> else S
S1 -> eps
E -> id

ô $M[S1, else]$ có cả luật sinh 2 ( $S1 \to \text{else } S$ , vì else $\in \text{FIRST}$ của vế phải) và luật sinh 3 ( $S1 \to \varepsilon$ , vì else $\in \text{FOLLOW}(S1)$ ) — đây là xung đột duy nhất.

Định dạng đầu vào:
- Dòng đầu tiên chứa số nguyên $n$ ( $1 \le n \le 200$ ) — số luật sinh (production) của văn phạm.
- $n$ dòng tiếp theo, mỗi dòng có dạng A -> X1 X2 ... Xk (giữa A và ->, giữa -> và $X_1$ , giữa các $X_i$ luôn có khoảng trắng); $A$ là kí hiệu ở vế trái, $X_1,\dots,X_k$ là các kí hiệu ở vế phải. Nếu vế phải là chuỗi rỗng $\varepsilon$ , dòng có dạng A -> eps (đúng một kí hiệu eps).
- Một kí hiệu là kí hiệu CHƯA KẾT THÚC (nonterminal) nếu nó xuất hiện ở vế trái của ít nhất một trong $n$ luật sinh; mọi kí hiệu khác xuất hiện trong văn phạm (khác eps) là kí hiệu KẾT THÚC (terminal). Kí hiệu bắt đầu (start symbol) của văn phạm là vế trái của luật sinh ở dòng đầu tiên (dòng thứ hai của input). Có thể có nhiều luật sinh cùng vế trái, nằm ở các dòng khác nhau, không nhất thiết liền kề.
- Kí hiệu kết thúc chuỗi vào (end-of-input marker), dùng khi tính FOLLOW, được kí hiệu là $.
Định dạng đầu ra:
Nếu văn phạm KHÔNG có ô xung đột nào (là $LL(1)$ ), in ra đúng một dòng LL(1). Ngược lại, dòng đầu tiên in số nguyên $C$ — tổng số ô xung đột. $C$ dòng tiếp theo, mỗi dòng ứng với một ô xung đột, có dạng A a: i1 i2 ... trong đó $A$ là kí hiệu chưa kết thúc, $a$ là kí hiệu kết thúc (hoặc $) gây xung đột, và $i_1 < i_2 < \dots$ là chỉ số (tăng dần) của các luật sinh xung đột tại ô đó, cách nhau đúng một khoảng trắng. Các dòng xung đột được sắp xếp tăng dần trước hết theo tên $A$ (thứ tự từ điển), sau đó theo $a$ (thứ tự từ điển, riêng $ luôn xếp SAU cùng mọi kí hiệu kết thúc khác của cùng một $A$ ).

solution

Đề bài: [Trình biên dịch] Phát hiện và báo cáo xung đột trong bảng LL(1)