Bài tập | NEU OJ

Cho một văn phạm phi ngữ cảnh (CFG) với ký hiệu bắt đầu $S$ , gồm $n$ luật sinh ban đầu.

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).

Sau đó, một luật sinh mới được đề xuất bổ sung vào văn phạm (thêm làm một lựa chọn thay thế cho một ký hiệu chưa kết thúc đã có sẵn, hoặc cho một ký hiệu hoàn toàn mới). Gọi văn phạm sau khi thêm luật sinh này là văn phạm mở rộng.

Hãy kiểm tra xem văn phạm mở rộng có còn thỏa điều kiện LL(1) hay không. Cụ thể, với mỗi ký hiệu chưa kết thúc $A$ có từ 2 luật sinh trở lên $A \to \alpha_1 \mid \alpha_2 \mid \ldots$ , 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)$ (đây chính là tập các ký hiệu kết thúc/$ khiến bộ phân tích LL(1) chọn luật sinh này). Văn phạm là LL(1) khi và chỉ khi với mọi $A$ , các tập $SELECT$ của các luật sinh khác nhau của $A$ đôi một rời nhau.

Lưu ý quan trọng: việc thêm luật sinh mới có thể làm thay đổi $FIRST$ / $FOLLOW$ của toàn bộ văn phạm (ví dụ nếu luật sinh mới là $A \to \varepsilon$ khiến $A$ trở nên nullable), vì vậy phải tính lại FIRST/FOLLOW trên toàn bộ văn phạm mở rộng rồi mới kiểm tra.

Ví dụ

Với văn phạm biểu thức số học kinh điển, nếu thêm luật sinh X -> - T X (một lựa chọn mới cho $X$ dùng dấu trừ), văn phạm mở rộng vẫn là LL(1) (in ra LL1) vì - không trùng với SELECT của các luật sinh khác của $X$ .

Định dạng đầu vào:
- Dòng 1: ký hiệu bắt đầu $S$ .
- Dòng 2: số luật sinh ban đầu $n$ ( $1 \le n \le 25$ ).
- $n$ dòng luật sinh dạng A -> X1 X2 ... Xk hoặc A -> e.
- Dòng cuối cùng: đúng một luật sinh mới cần thêm vào, cùng định dạng A -> X1 X2 ... Xk hoặc A -> e (ký hiệu A ở vế trái có thể trùng hoặc không trùng với các ký hiệu đã có).
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).
Định dạng đầu ra:
Nếu văn phạm mở rộng (sau khi thêm luật sinh) vẫn là LL(1), in ra đúng một dòng LL1.

Ngược lại, in dòng đầu tiên là KHONG-LL1, sau đó in danh sách tất cả các cặp (A, a) — với $A$ là ký hiệu chưa kết thúc và $a$ là một terminal hoặc $ — sao cho tồn tại ít nhất 2 luật sinh của $A$ mà $a$ thuộc $SELECT$ của cả hai (tức $a$ gây xung đột tại $A$ ). Mỗi cặp in trên một dòng riêng theo định dạng A a, các dòng được sắp xếp tăng dần trước hết theo tên $A$ (từ điển), sau đó theo tên $a$ (từ điển); mỗi cặp (A,a) chỉ in một lần dù có thể có nhiều hơn 2 luật sinh cùng gây xung đột tại đó.

solution

Đề bài: [Trình biên dịch] Thêm luật sinh mới có phá vỡ tính LL(1)?

Ví dụ