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 SELECT (PREDICT) của một luật sinh

    Trong bảng phân tích LL(1), mỗi luật sinh A→αA \to \alphaA→α được gắn với một tập lookahead — gọi là tập SELECT (hay PREDICT) — xác định khi nào bộ phân tích sẽ CHỌN luật sinh đó:

    SELECT(A→α)=FIRST(α) ∪ (FOLLOW(A) neˆˊu α⇒∗ε)SELECT(A \to \alpha) = FIRST(\alpha) \ \cup\ \big(FOLLOW(A) \text{ nếu } \alpha \Rightarrow^{*} \varepsilon\big)SELECT(A→α)=FIRST(α) ∪ (FOLLOW(A) neˆˊu α⇒∗ε)

    (ở đây FIRST(α)FIRST(\alpha)FIRST(α) chỉ gồm terminal, không chứa ε\varepsilonε). Quy ước văn phạm và ký hiệu e/ε\varepsilonε như các bài trước.

    Cho văn phạm, các luật sinh được đánh số 1,2,…,n1, 2, \ldots, n1,2,…,n theo đúng thứ tự xuất hiện trong input. Cho một chỉ số kkk, hãy tính SELECTSELECTSELECT của luật sinh thứ kkk.

    Ví dụ, với văn phạm biểu thức số học kinh điển, luật sinh thứ 3 là X -> e. Vì đây là luật sinh rỗng nên SELECT(X \to \varepsilon) = FOLLOW(X) = \{), \}.Ke^ˊtquảinra:‘),. Kết quả in ra: `),.Ke^ˊtquảinra:‘),`.

    • Định dạng đầu vào:
      • Dòng 1: ký hiệu bắt đầu SSS.
      • 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), theo đúng thứ tự sẽ được đánh số 1..n1..n1..n.
      • Dòng cuối: một số nguyên kkk (1≤k≤n1 \le k \le n1≤k≤n) — chỉ số luật sinh cần tính SELECT.

      Đả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: các terminal thuộc SELECT(A→α)SELECT(A \to \alpha)SELECT(A→α) (với A→αA \to \alphaA→α là luật sinh thứ kkk), sắp xếp theo thứ tự bảng chữ cái (ASCII) tăng dần, cách nhau bởi dấu phẩy (không khoảng trắng); nếu \ \in SELECT(A \to \alpha)thıˋđặt‘ thì đặt `thıˋđặt‘` ở cuối danh sách. Nếu tập này rỗng, 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
1

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

    Đầu ra:

    ),$

    Đang tải editor...