solution

Cho một văn phạm phi ngữ cảnh (CFG) dùng trong bộ phân tích cú pháp 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$, tập $FIRST(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 đầu tiên trong một chuỗi mà $A$ dẫn xuất ra, cùng với việc đánh dấu riêng liệu $A \Rightarrow^{*} \varepsilon$ hay không).

Thay vì liệt kê toàn bộ tập $FIRST(A)$, với mỗi ký hiệu chưa kết thúc $A$ (theo đúng thứ tự nó xuất hiện lần đầu ở vế trái một luật sinh trong dữ liệu vào), hãy in ra:

• Tên $A$,
• Số lượng ký hiệu kết thúc (không tính $\varepsilon$) có trong $FIRST(A)$,
• $1$ nếu $\varepsilon \in FIRST(A)$, ngược lại $0$.

Ví dụ

Với văn phạm biểu thức số học kinh điển:

E -> T X
X -> + T X
X -> e
T -> F Y
Y -> * F Y
Y -> e
F -> ( E )
F -> id

$FIRST(E)=\{(, id\}$ (2 terminal, không có $\varepsilon$) nên dòng đầu ra cho $E$ là E 2 0. $FIRST(X)=\{+, \varepsilon\}$ (1 terminal, có $\varepsilon$) nên dòng cho $X$ là X 1 1.