solution

Với mỗi luật sinh $A \to \alpha$, định nghĩa tập LỰA CHỌN $\text{SELECT}(A \to \alpha)$ như sau: $\text{SELECT}(A \to \alpha) = \big(\text{FIRST}(\alpha) \setminus \{\varepsilon\}\big) \cup \begin{cases}\text{FOLLOW}(A) & \text{nếu } \varepsilon \in \text{FIRST}(\alpha)\\ \emptyset & \text{ngược lại}\end{cases}$ Văn phạm $G$ (không có kí hiệu chưa kết thúc vô ích, không đệ quy trái gián tiếp gây vòng lặp vô hạn khi tính FIRST/FOLLOW) được gọi là $LL(1)$ nếu và chỉ nếu: với mọi kí hiệu chưa kết thúc $A$ có từ hai luật sinh $A \to \alpha_i$ trở lên, các tập $\text{SELECT}(A \to \alpha_i)$ ĐÔI MỘT RỜI NHAU (không có kí hiệu kết thúc nào thuộc về từ hai tập SELECT của cùng $A$ trở lên).

Cho văn phạm $G$, hãy xác định $G$ có phải là văn phạm $LL(1)$ hay không.

Ví dụ kinh điển KHÔNG phải $LL(1)$ (mơ hồ dangling-else):

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

vì $\text{SELECT}(S1 \to \text{else } S) = \{else\}$ và \text{SELECT}(S1 \to \varepsilon) = \text{FOLLOW}(S1) = \{else, \}$ giao nhau tại else.