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] FIRST của một chuỗi kí hiệu

    Khi xây dựng bảng phân tích LL(1)LL(1)LL(1), ta thường cần tính FIRST\text{FIRST}FIRST không chỉ của một kí hiệu chưa kết thúc mà của cả một CHUỖI kí hiệu β=X1X2…Xk\beta = X_1 X_2 \dots X_kβ=X1​X2​…Xk​ (mỗi XiX_iXi​ có thể là kí hiệu kết thúc hoặc chưa kết thúc), theo quy tắc nối tiếp:

    • Nếu k=0k = 0k=0 (chuỗi rỗng) thì FIRST(β)={ε}\text{FIRST}(\beta) = \{\varepsilon\}FIRST(β)={ε}.
    • Ngược lại, xét lần lượt X1,X2,…X_1, X_2, \dotsX1​,X2​,…: thêm FIRST(Xi)∖{ε}\text{FIRST}(X_i) \setminus \{\varepsilon\}FIRST(Xi​)∖{ε} vào kết quả; nếu ε∈FIRST(Xi)\varepsilon \in \text{FIRST}(X_i)ε∈FIRST(Xi​) thì tiếp tục xét Xi+1X_{i+1}Xi+1​, ngược lại dừng lại. Nếu TẤT CẢ X1,…,XkX_1,\dots,X_kX1​,…,Xk​ đều có ε\varepsilonε trong tập FIRST của chúng thì ε∈FIRST(β)\varepsilon \in \text{FIRST}(\beta)ε∈FIRST(β).

    Cho văn phạm GGG và một truy vấn là chuỗi kí hiệu β\betaβ (các kí hiệu của β\betaβ đều xuất hiện trong GGG, có thể là kết thúc hoặc chưa kết thúc, có thể lặp), hãy tính FIRST(β)\text{FIRST}(\beta)FIRST(β).

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

    E -> T X
X -> + T X
X -> eps
T -> id

    và truy vấn β=X T\beta = X\ Tβ=X T, ta có FIRST(X)={+,ε}\text{FIRST}(X) = \{+, \varepsilon\}FIRST(X)={+,ε}; vì ε∈FIRST(X)\varepsilon \in \text{FIRST}(X)ε∈FIRST(X) nên xét tiếp TTT: FIRST(T)={id}\text{FIRST}(T) = \{id\}FIRST(T)={id} (không chứa ε\varepsilonε). Kết quả: FIRST(X T)={+,id}\text{FIRST}(X\ T) = \{+, id\}FIRST(X T)={+,id}.

    • Định dạng đầu vào:
      • Dòng đầu tiên chứa số nguyên nnn (1≤n≤2001 \le n \le 2001≤n≤200) — số luật sinh (production) của văn phạm.
      • nnn dòng tiếp theo, mỗi dòng có dạng A -> X1 X2 ... Xk (giữa A và ->, giữa -> và X1X_1X1​, giữa các XiX_iXi​ luôn có khoảng trắng); AAA là kí hiệu ở vế trái, X1,…,XkX_1,\dots,X_kX1​,…,Xk​ là các kí hiệu ở vế phải. Nếu vế phải là chuỗi rỗng ε\varepsilonε, dòng có dạng A -> eps (đúng một kí hiệu eps).
      • Một kí hiệu là kí hiệu CHƯA KẾT THÚC (nonterminal) nếu nó xuất hiện ở vế trái của ít nhất một trong nnn luật sinh; mọi kí hiệu khác xuất hiện trong văn phạm (khác eps) là kí hiệu KẾT THÚC (terminal). Kí hiệu bắt đầu (start symbol) của văn phạm là vế trái của luật sinh ở dòng đầu tiên (dòng thứ hai của input). Có thể có nhiều luật sinh cùng vế trái, nằm ở các dòng khác nhau, không nhất thiết liền kề.
      • Kí hiệu kết thúc chuỗi vào (end-of-input marker), dùng khi tính FOLLOW, được kí hiệu là $.
      • Sau nnn dòng luật sinh là một dòng chứa số nguyên kkk (0≤k≤500 \le k \le 500≤k≤50) — độ dài chuỗi truy vấn β\betaβ.
      • Nếu k>0k > 0k>0, dòng tiếp theo chứa kkk kí hiệu của β\betaβ cách nhau bởi khoảng trắng (mỗi kí hiệu là một kí hiệu kết thúc hoặc chưa kết thúc đã xuất hiện trong văn phạm ở trên). Nếu k=0k = 0k=0, không có dòng nào tiếp theo (chuỗi truy vấn rỗng).
    • Định dạng đầu ra:

      In ra đúng một dòng là FIRST(β)\text{FIRST}(\beta)FIRST(β): các kí hiệu kết thúc sắp xếp tăng dần theo thứ tự từ điển, cách nhau đúng một khoảng trắng; nếu ε∈FIRST(β)\varepsilon \in \text{FIRST}(\beta)ε∈FIRST(β) (bao gồm cả trường hợp k=0k=0k=0), in thêm token eps ở CUỐI dòng.

    Ví dụ:

    Đầu vào:

    4
E -> T X
X -> + T X
X -> eps
T -> id
2
X T

    Đầu ra:

    + id

    Đầu vào:

    4
E -> T X
X -> + T X
X -> eps
T -> id
0

    Đầu ra:

    eps

    Đang tải editor...