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 bao đóng (closure) của tập mục LR(0)

    Trong xây dựng automat LR(0), một mục (item) LR(0) của sản xuất A→βA \to \betaA→β được viết dưới dạng A→α⋅γA \to \alpha \cdot \gammaA→α⋅γ trong đó αγ=β\alpha\gamma = \betaαγ=β và dấu chấm . đánh dấu vị trí đã đọc tới đâu. Phép đóng (closure) của một tập mục III được tính bằng quy tắc điểm bất động:

    Nếu [A→α⋅B γ]∈I[A \to \alpha \cdot B\,\gamma] \in I[A→α⋅Bγ]∈I với BBB là ký hiệu phi kết thúc, thì với mọi sản xuất B→δB \to \deltaB→δ của văn phạm, thêm mục [B→⋅ δ][B \to \cdot\,\delta][B→⋅δ] vào III (nếu chưa có). Lặp lại đến khi không còn mục nào được thêm mới.

    Lưu ý: quy tắc trên chỉ xét ký hiệu ngay sau dấu chấm của từng mục hiện có; nó không "nhìn xuyên qua" các ký hiệu phi kết thúc có khả năng sinh ra chuỗi rỗng ở các mục khác.

    Cho văn phạm và một tập mục hạt nhân (kernel) ban đầu, hãy tính tập đóng đầy đủ của nó.

    Ví dụ: văn phạm gồm S→AS \to AS→A và A→aA \to aA→a; hạt nhân {S→⋅ A}\{S \to \cdot\,A\}{S→⋅A}. Đóng: vì mục S→⋅ AS \to \cdot\,AS→⋅A có ký hiệu ngay sau dấu chấm là AAA (phi kết thúc), ta thêm A→⋅ aA \to \cdot\,aA→⋅a. Kết quả đóng gồm 2 mục: {S→⋅ A, A→⋅ a}\{S \to \cdot\,A,\ A \to \cdot\,a\}{S→⋅A, A→⋅a}.

    • Định dạng đầu vào:
      • Dòng 1: số nguyên nnn (1≤n≤1001 \le n \le 1001≤n≤100) — số sản xuất của văn phạm.
      • nnn dòng tiếp theo: mỗi dòng có dạng A -> X1 X2 ... Xk (vế phải cách nhau khoảng trắng), hoặc A -> # nếu vế phải rỗng. Tập ký hiệu phi kết thúc là tập hợp các vế trái xuất hiện trong nnn sản xuất này; mọi ký hiệu khác là ký hiệu kết thúc.
      • Dòng tiếp theo: số nguyên kkk (1≤k≤501 \le k \le 501≤k≤50) — số mục trong tập hạt nhân ban đầu.
      • kkk dòng tiếp theo: mỗi dòng là một mục dưới dạng A -> β . γ — vế phải được viết đầy đủ với dấu chấm . là một token riêng biệt đặt đúng vị trí (nếu β\betaβ rỗng, dòng bắt đầu ngay bằng .; nếu γ\gammaγ rỗng, dòng kết thúc bằng .; nếu vế phải sản xuất rỗng, mục được viết là A -> .).
    • Định dạng đầu ra:
      • Dòng 1: số nguyên là số lượng mục trong tập đóng (kể cả các mục hạt nhân ban đầu).
      • Các dòng tiếp theo: mỗi dòng một mục theo đúng định dạng A -> β . γ như mô tả ở phần input, liệt kê theo thứ tự tăng dần khi so sánh chuỗi (thứ tự từ điển theo mã ASCII), không lặp lại mục trùng nhau.

    Ví dụ:

    Đầu vào:

    2
S -> A
A -> a
1
S -> . A

    Đầu ra:

    2
A -> . a
S -> . A

    Đầu vào:

    7
E -> E + T
E -> T
T -> T * F
T -> F
F -> ( E )
F -> id
E' -> E
1
E' -> . E

    Đầu ra:

    7
E -> . E + T
E -> . T
E' -> . E
F -> . ( E )
F -> . id
T -> . F
T -> . T * F

    Đang tải editor...