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 FOLLOW của văn phạm

    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 có kí hiệu bắt đầu SSS, tập FOLLOW(A)\text{FOLLOW}(A)FOLLOW(A) gồm mọi kí hiệu kết thúc bbb sao cho tồn tại một dẫn xuất S⇒∗αAbβS \Rightarrow^{*} \alpha A b \betaS⇒∗αAbβ; ngoài ra nếu S⇒∗αAS \Rightarrow^{*} \alpha AS⇒∗αA (tức AAA có thể là kí hiệu cuối cùng của một câu dẫn xuất từ SSS) thì kí hiệu kết thúc chuỗi \$$ cũng thuộc \text{FOLLOW}(A)$.

    Cho văn phạm GGG (kí hiệu bắt đầu là vế trái của luật sinh đầu tiên), hãy tính FOLLOW(A)\text{FOLLOW}(A)FOLLOW(A) cho mọi kí hiệu chưa kết thúc AAA, dùng thuật toán điểm bất động chuẩn dựa trên tập FIRST đã tính trước.

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

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

    ta có \text{FOLLOW}(E) = \{\},, ,\text{FOLLOW}(X) = {$},, ,\text{FOLLOW}(T) = {+, $}$.

    • Đị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 (mỗi kí hiệu chưa kết thúc một dòng), theo ĐÚNG thứ tự xuất hiện lần đầu ở vế trái trong input. Mỗi dòng có dạng A: s1 s2 ... sm với s1<s2<…s_1 < s_2 < \dotss1​<s2​<… là các kí hiệu kết thúc thuộc FOLLOW(A)\text{FOLLOW}(A)FOLLOW(A) 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 \ \in \text{FOLLOW}(A),inthe^mtoken‘, in thêm token `,inthe^mtoken‘ở CUỐI dòng (sau mọi kí hiệu kết thúc khác). Nếu $\text{FOLLOW}(A) = \emptyset$ (kí hiệu $A$ không xuất hiện ở vế phải luật sinh nào và cũng không phải kí hiệu bắt đầu), in dòngA:` không có khoảng trắng thừa phía sau.

    Ví dụ:

    Đầu vào:

    1
S -> a

    Đầu ra:

    S: $

    Đầu vào:

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

    Đầu ra:

    E: $
X: $
T: + $

    Đang tải editor...