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

    Trong phân tích cú pháp LL(1), với một văn phạm phi ngữ cảnh (CFG) cho trước, tập FIRST(α)FIRST(\alpha)FIRST(α) của một chuỗi ký hiệu α=Y1Y2…Ym\alpha = Y_1 Y_2 \ldots Y_mα=Y1​Y2​…Ym​ (có thể trộn lẫn terminal và non-terminal, kể cả chuỗi rỗng) được định nghĩa:

    FIRST(α)={ a∣α⇒∗aβ, a laˋ terminal } ∪ {ε∣α⇒∗ε}FIRST(\alpha) = \{\, a \mid \alpha \Rightarrow^{*} a\beta,\ a \text{ là terminal} \,\} \ \cup\ \{\varepsilon \mid \alpha \Rightarrow^{*} \varepsilon\}FIRST(α)={a∣α⇒∗aβ, a laˋ terminal} ∪ {ε∣α⇒∗ε}

    Quy ước biểu diễn văn phạm dùng chung cho bài này:

    • Non-terminal: một chữ cái in hoa (A-Z).
    • Terminal: một token bất kỳ khác (chữ thường, số, hoặc ký hiệu như +, (, id, ...); không terminal nào được đặt tên e.
    • Ký hiệu e đứng một mình ở vế phải một luật sinh biểu diễn chuỗi rỗng ε\varepsilonε (ví dụ A -> e).

    Cho văn phạm và một chuỗi truy vấn α\alphaα, hãy tính FIRST(α)FIRST(\alpha)FIRST(α).

    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

    truy vấn chuỗi α=X F\alpha = X\,Fα=XF: vì XXX có thể sinh ε\varepsilonε nên FIRST(XF)=FIRST(X)∪FIRST(F)={+}∪{(,id}={(,+,id}FIRST(XF) = FIRST(X) \cup FIRST(F) = \{+\} \cup \{(, id\} = \{(, +, id\}FIRST(XF)=FIRST(X)∪FIRST(F)={+}∪{(,id}={(,+,id}. Kết quả in ra: (,+,id.

    • Định dạng đầu vào:
      • Dòng 1: ký hiệu bắt đầu SSS của văn phạm (một chữ cái in hoa) — không ảnh hưởng tới việc tính FIRST(α)FIRST(\alpha)FIRST(α) ở bài này nhưng vẫn 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 tiếp theo: mỗi dòng một luật sinh dạng A -> X1 X2 ... Xk, các ký hiệu trên vế phải cách nhau đúng một khoảng trắng. Vế phải rỗng được ghi là A -> e.
      • Dòng cuối cùng: chuỗi truy vấn α\alphaα — dãy ký hiệu cách nhau bởi khoảng trắng (mỗi ký hiệu là một terminal hoặc non-terminal xuất hiện trong văn phạm), hoặc chỉ gồm token e nếu muốn hỏi FIRST(ε)FIRST(\varepsilon)FIRST(ε).

      Đảm bảo mọi non-terminal xuất hiện ở vế phải bất kỳ luật sinh nào (hoặc trong chuỗi truy vấn) đều có ít nhất một luật sinh định nghĩa nó trong nnn dòng trên.

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

      In ra một dòng duy nhất: các terminal thuộc FIRST(α)FIRST(\alpha)FIRST(α), liệt kê theo thứ tự từ điển tăng dần (so sánh chuỗi theo mã ASCII), cách nhau bởi dấu phẩy , (không có khoảng trắng). Nếu ε∈FIRST(α)\varepsilon \in FIRST(\alpha)ε∈FIRST(α), thêm token e vào cuối danh sách (sau tất cả terminal khác, không xét theo thứ tự bảng chữ cái). Nếu FIRST(α)FIRST(\alpha)FIRST(α) hoàn toàn rỗng (không có terminal nào và ε∉FIRST(α)\varepsilon \notin FIRST(\alpha)ε∈/FIRST(α)), in ra một dòng trống.

    Ví dụ:

    Đầ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
E

    Đầu ra:

    (,id

    Đầ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
X F

    Đầu ra:

    (,+,id

    Đang tải editor...