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 cho toàn bộ ký hiệu chưa kết thúc

    Tập FOLLOW(A)\mathrm{FOLLOW}(A)FOLLOW(A) của một ký hiệu chưa kết thúc AAA là tập các ký hiệu kết thúc aaa có thể xuất hiện ngay sau AAA trong một dạng câu nào đó xuất phát từ ký hiệu bắt đầu SSS, cộng thêm ký hiệu kết thúc xâu $ nếu AAA có thể là ký hiệu cuối cùng của một dạng câu (đặc biệt FOLLOW(S)\mathrm{FOLLOW}(S)FOLLOW(S) luôn chứa $). Đây là thành phần bắt buộc khi xây dựng bảng phân tích SLR(1) (quyết định khi nào được rút gọn theo một luật sinh).

    Quy ước ký hiệu văn phạm (áp dụng cho toàn bộ đề bài này): mỗi luật sinh được cho ở dạng A -> X1 X2 ... Xk (các ký hiệu cách nhau bởi dấu cách); nếu vế phải là rỗng thì ghi A -> eps. Một ký hiệu được coi là ký hiệu chưa kết thúc (non-terminal) nếu và chỉ nếu ký tự đầu tiên của nó là một chữ cái in hoa (A-Z); mọi ký hiệu còn lại (chữ thường, chữ số, dấu (, ), +, id, ... ) đều là ký hiệu kết thúc (terminal). Ký hiệu đặc biệt eps chỉ dùng để biểu diễn xâu rỗng ε\varepsilonε và không phải là một terminal thật sự. Ký hiệu $ là ký hiệu kết thúc xâu vào (end-marker).

    Cho văn phạm phi ngữ cảnh GGG với ký hiệu bắt đầu SSS, hãy tính FOLLOW(A)\mathrm{FOLLOW}(A)FOLLOW(A) cho mọi ký hiệu chưa kết thúc AAA xuất hiện là vế trái của ít nhất một luật sinh, theo đúng thứ tự lần đầu tiên các ký hiệu này xuất hiện làm vế trái trong danh sách luật sinh của đề bài.

    Ví dụ: văn phạm S -> A\nA -> a\nC -> c với ký hiệu bắt đầu S: \mathrm{FOLLOW}(S)=\{\},, ,\mathrm{FOLLOW}(A)={$}(vıˋ(vì(vıˋAđứngcuo^ˊiluật‘S−>A‘),coˋnđứng cuối luật `S -> A`), cònđứngcuo^ˊiluật‘S−>A‘),coˋnCkho^ngxua^ˊthiệnởve^ˊphảiluậtsinhnaˋovaˋkho^ngphảikyˊhiệuba˘ˊtđa^ˋune^nkhông xuất hiện ở vế phải luật sinh nào và không phải ký hiệu bắt đầu nênkho^ngxua^ˊthiệnởve^ˊphảiluậtsinhnaˋovaˋkho^ngphảikyˊ​hiệuba˘ˊtđa^ˋune^n\mathrm{FOLLOW}(C) = \varnothing$ (tập rỗng).

    • Định dạng đầu vào:

      Dòng đầu tiên là số nguyên nnn (1≤n≤1001 \le n \le 1001≤n≤100) — số luật sinh. nnn dòng tiếp theo, mỗi dòng một luật sinh dạng A -> X1 X2 ... Xk hoặc A -> eps. Dòng cuối cùng là ký hiệu bắt đầu SSS (một ký hiệu chưa kết thúc, đảm bảo có xuất hiện làm vế trái).

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

      In ra một dòng cho mỗi ký hiệu chưa kết thúc AAA (theo thứ tự xuất hiện lần đầu làm vế trái trong danh sách luật sinh), dạng A: t1,t2,..., trong đó t1,t2,…t_1,t_2,\ldotst1​,t2​,… là các phần tử của FOLLOW(A)\mathrm{FOLLOW}(A)FOLLOW(A) sắp xếp tăng dần theo từ điển, cách nhau bởi dấu phẩy , không có khoảng trắng thừa. Nếu FOLLOW(A)=∅\mathrm{FOLLOW}(A) = \varnothingFOLLOW(A)=∅, in A: (không có gì sau dấu hai chấm và khoảng trắng).

    Ví dụ:

    Đầu vào:

    1
A -> a
A

    Đầu ra:

    A: $

    Đầu vào:

    8
E -> T E1
E1 -> + T E1
E1 -> eps
T -> F T1
T1 -> * F T1
T1 -> eps
F -> ( E )
F -> id
E

    Đầu ra:

    E: $,)
E1: $,)
T: $,),+
T1: $,),+
F: $,),*,+

    Đang tải editor...