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

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

Tập $FOLLOW(A)$ của một ký hiệu chưa kết thúc $A$ được định nghĩa như thường lệ: tập các ký hiệu kết thúc có thể xuất hiện ngay sau $A$ trong một dạng câu nào đó dẫn xuất từ $S$ ; riêng $FOLLOW(S)$ luôn chứa ký hiệu kết thúc đầu vào $.

Hãy xác định ký hiệu chưa kết thúc $A^*$ có $|FOLLOW(A^*)|$ (số lượng phần tử, tính cả $ nếu có) lớn nhất. Nếu có nhiều ký hiệu cùng đạt giá trị lớn nhất, chọn ký hiệu có tên nhỏ hơn theo thứ tự từ điển (so sánh chuỗi thông thường).

Ví dụ

Với văn phạm biểu thức số học kinh điển, có thể tính được $FOLLOW(F) = \{*, +, ), \$ }$ với 4 phần tử — nhiều hơn mọi ký hiệu chưa kết thúc khác — nên đáp án là F 4.

Định dạng đầu vào:
- Dòng 1: ký hiệu bắt đầu $S$ của văn phạm (một chữ cái in hoa).
- Dòng 2: số luật sinh $n$ ( $1 \le n \le 30$ ).
- $n$ dòng luật sinh dạng A -> X1 X2 ... Xk hoặc A -> e.
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:
In ra đúng một dòng dạng A k, trong đó A là tên ký hiệu chưa kết thúc có $|FOLLOW(A)|$ lớn nhất (ưu tiên tên nhỏ hơn theo từ điển nếu bằng nhau), và k là giá trị $|FOLLOW(A)|$ tương ứng.

solution

Đề bài: [Trình biên dịch] Ký hiệu chưa kết thúc có FOLLOW lớn nhất

Ví dụ