Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Trình biên dịch] Xác định non-terminal nullable (⇒* ε)

    Một non-terminal AAA của văn phạm phi ngữ cảnh (CFG) được gọi là nullable nếu nó có thể sinh ra chuỗi rỗng, tức A⇒∗εA \Rightarrow^{*} \varepsilonA⇒∗ε. Việc xác định tập non-terminal nullable là bước đầu tiên, bắt buộc phải làm trước khi tính FIRSTFIRSTFIRST/FOLLOWFOLLOWFOLLOW trong thuật toán phân tích LL(1).

    Quy ước văn phạm giống bài "Tính tập FIRST của một chuỗi ký hiệu": non-terminal là một chữ in hoa, terminal là token khác, e đứng riêng ở vế phải biểu diễn ε\varepsilonε.

    Cho văn phạm, hãy liệt kê tất cả non-terminal nullable.

    Ví dụ. Với văn phạm:

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

    XXX nullable vì X -> e; YYY nullable vì Y -> e. E,T,FE, T, FE,T,F không nullable. Kết quả in ra: X,Y.

    • Định dạng đầu vào:
      • Dòng 1: ký hiệu bắt đầu SSS (không dùng để tính nullable nhưng có mặt để thống nhất định dạng).
      • Dòng 2: số luật sinh nnn (1≤n≤201 \le n \le 201≤n≤20).
      • nnn dòng luật sinh dạng A -> X1 X2 ... Xk (hoặc A -> e), quy ước như trên.

      Đảm bảo mọi non-terminal xuất hiện ở vế phải đều có ít nhất một luật sinh định nghĩa nó.

    • Định dạng đầu ra:

      In ra một dòng: tên các non-terminal nullable, sắp xếp theo thứ tự bảng chữ cái tăng dần, cách nhau bởi dấu phẩy , (không khoảng trắng). Nếu không có non-terminal nào nullable, in ra một dòng trống.

    Ví dụ:

    Đầu vào:

    S
2
S -> a S
S -> b

    Đầu ra:

    Đầu vào:

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

    Đầu ra:

    X,Y

    Đang tải editor...