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] Giao của các tập FIRST theo nhiều truy vấn

    Cho một văn phạm phi ngữ cảnh (CFG).

    Quy ước biểu diễn văn phạm phi ngữ cảnh (CFG) dùng chung cho đề này:

    • Mỗi ký hiệu chưa kết thúc (non-terminal) là một chữ cái in hoa (A-Z).
    • Mọi token khác (chữ thường, số, hoặc ký hiệu như (, ), +, *, id, num, ...) là ký hiệu kết thúc (terminal); terminal có thể dài nhiều ký tự nhưng không chứa khoảng trắng.
    • Token đặc biệt e ở vế phải nghĩa là luật sinh sinh ra chuỗi rỗng ε\varepsilonε (ví dụ A -> e).
    • Ký hiệu kết thúc đầu vào (end-of-input) được ký hiệu là $ khi cần dùng tới FOLLOW.
    • Đảm bảo mọi ký hiệu chưa kết thúc xuất hiện ở vế phải của bất kỳ luật sinh nào cũng đều có ít nhất một luật sinh định nghĩa nó (văn phạm "đóng", không có non-terminal mồ côi).

    Với một chuỗi ký hiệu α=X1X2…Xk\alpha = X_1 X_2 \ldots X_kα=X1​X2​…Xk​ (mỗi XiX_iXi​ là terminal hoặc non-terminal của văn phạm, k≥0k \ge 0k≥0), tập FIRST(α)FIRST(\alpha)FIRST(α) được tính theo quy tắc chuẩn: duyệt lần lượt X1,X2,…X_1, X_2, \ldotsX1​,X2​,…, cộng dồn FIRST(Xi)∖{ε}FIRST(X_i) \setminus \{\varepsilon\}FIRST(Xi​)∖{ε} cho đến khi gặp XiX_iXi​ không thể dẫn xuất ε\varepsilonε thì dừng; nếu tất cả X1,…,XkX_1, \ldots, X_kX1​,…,Xk​ đều dẫn xuất được ε\varepsilonε (kể cả khi k=0k=0k=0, tức α=ε\alpha=\varepsilonα=ε) thì ε∈FIRST(α)\varepsilon \in FIRST(\alpha)ε∈FIRST(α).

    Cho qqq truy vấn, mỗi truy vấn là một chuỗi ký hiệu αi\alpha_iαi​ (dòng chỉ chứa token e nghĩa là αi=ε\alpha_i=\varepsilonαi​=ε, chuỗi rỗng). Hãy tính giao (intersection) của tất cả qqq tập FIRST(α1),FIRST(α2),…,FIRST(αq)FIRST(\alpha_1), FIRST(\alpha_2), \ldots, FIRST(\alpha_q)FIRST(α1​),FIRST(α2​),…,FIRST(αq​).

    Ví dụ

    Với văn phạm biểu thức số học kinh điển (như bài trước) và 3 truy vấn E, T, F: vì FIRST(E)=FIRST(T)=FIRST(F)={(,id}FIRST(E)=FIRST(T)=FIRST(F)=\{(, id\}FIRST(E)=FIRST(T)=FIRST(F)={(,id} nên giao của chúng là {(,id}\{(, id\}{(,id}, in ra ( id (terminal ( xếp trước id theo thứ tự từ điển ASCII).

    • Định dạng đầu vào:
      • Dòng 1: ký hiệu bắt đầu SSS (không ảnh hưởng kết quả, chỉ để thống nhất định dạng).
      • Dòng 2: số luật sinh nnn (1≤n≤301 \le n \le 301≤n≤30).
      • nnn dòng luật sinh dạng A -> X1 X2 ... Xk hoặc A -> e.
      • Dòng tiếp theo: số truy vấn qqq (1≤q≤101 \le q \le 101≤q≤10).
      • qqq dòng tiếp theo: mỗi dòng một chuỗi ký hiệu (các ký hiệu cách nhau bởi khoảng trắng), hoặc chỉ chứa token e nếu chuỗi đó là ε\varepsilonε.

      Quy ước biểu diễn văn phạm phi ngữ cảnh (CFG) dùng chung cho đề này:

      • Mỗi ký hiệu chưa kết thúc (non-terminal) là một chữ cái in hoa (A-Z).
      • Mọi token khác (chữ thường, số, hoặc ký hiệu như (, ), +, *, id, num, ...) là ký hiệu kết thúc (terminal); terminal có thể dài nhiều ký tự nhưng không chứa khoảng trắng.
      • Token đặc biệt e ở vế phải nghĩa là luật sinh sinh ra chuỗi rỗng ε\varepsilonε (ví dụ A -> e).
      • Ký hiệu kết thúc đầu vào (end-of-input) được ký hiệu là $ khi cần dùng tới FOLLOW.
      • Đảm bảo mọi ký hiệu chưa kết thúc xuất hiện ở vế phải của bất kỳ luật sinh nào cũng đều có ít nhất một luật sinh định nghĩa nó (văn phạm "đóng", không có non-terminal mồ côi).
    • Định dạng đầu ra:

      In ra một dòng duy nhất: các ký hiệu kết thúc thuộc giao của qqq tập FIRST, sắp xếp theo thứ tự từ điển (so sánh chuỗi ASCII thông thường), cách nhau đúng một khoảng trắng. Nếu ε\varepsilonε thuộc giao (tức mọi αi\alpha_iαi​ đều dẫn xuất được chuỗi rỗng), in thêm token eps ở cuối cùng của dòng (sau các terminal). Nếu giao là tập rỗng, in ra dấu -.

    Ví dụ:

    Đầu vào:

    S
1
S -> a
2
S
S

    Đầu ra:

    a

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

    Đầu ra:

    ( id

    Đang tải editor...