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 văn phạm

    Trong phân tích cú pháp LL(1)LL(1)LL(1), với mỗi kí hiệu chưa kết thúc AAA của văn phạm phi ngữ cảnh GGG, tập FIRST(A)\text{FIRST}(A)FIRST(A) gồm mọi kí hiệu kết thúc có thể xuất hiện ở vị trí đầu tiên của một chuỗi kí hiệu kết thúc dẫn xuất được từ AAA (tức A⇒∗aαA \Rightarrow^{*} a\alphaA⇒∗aα với aaa là kí hiệu kết thúc); nếu A⇒∗εA \Rightarrow^{*} \varepsilonA⇒∗ε thì kí hiệu rỗng ε\varepsilonε cũng được coi là một phần tử của FIRST(A)\text{FIRST}(A)FIRST(A).

    Cho văn phạm GGG, hãy tính FIRST(A)\text{FIRST}(A)FIRST(A) cho mọi kí hiệu chưa kết thúc AAA của GGG, sử dụng thuật toán điểm bất động (lặp cho đến khi mọi tập FIRST không còn thay đổi) trên hệ luật sinh đã cho.

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

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

    ta có FIRST(E)={id}\text{FIRST}(E) = \{id\}FIRST(E)={id}, FIRST(X)={+,ε}\text{FIRST}(X) = \{+, \varepsilon\}FIRST(X)={+,ε}, FIRST(T)={id}\text{FIRST}(T) = \{id\}FIRST(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à $.
    • Định dạng đầu ra:

      In ra đúng mmm dòng, với mmm là số kí hiệu chưa kết thúc phân biệt, theo ĐÚNG thứ tự chúng xuất hiện lần đầu tiên (đọc từ trên xuống) ở vế trái các luật sinh trong input. Mỗi dòng có dạng A: s1 s2 ... sm trong đó s1<s2<…s_1 < s_2 < \dotss1​<s2​<… là các kí hiệu kết thúc thuộc FIRST(A)\text{FIRST}(A)FIRST(A), sắp xếp tăng dần theo thứ tự từ điển (so sánh chuỗi thông thường theo mã kí tự), cách nhau đúng một khoảng trắng. Nếu ε∈FIRST(A)\varepsilon \in \text{FIRST}(A)ε∈FIRST(A), in thêm token eps ở CUỐI dòng (sau tất cả các kí hiệu kết thúc khác, bất kể vị trí của nó trong thứ tự từ điển). Nếu FIRST(A)\text{FIRST}(A)FIRST(A) không có phần tử nào (trường hợp suy biến), in dòng A: không có khoảng trắng thừa phía sau.

    Ví dụ:

    Đầu vào:

    1
S -> a

    Đầu ra:

    S: a

    Đầu vào:

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

    Đầu ra:

    E: id
X: + eps
T: id

    Đang tải editor...