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 hàm chuyển GOTO(I, X) của automat LR(0)

    Hàm chuyển trạng thái GOTO(I,X)GOTO(I, X)GOTO(I,X) trong xây dựng automat LR(0) được định nghĩa:

    GOTO(I,X)=closure({ [A→αX⋅γ]  :  [A→α⋅X γ]∈I })GOTO(I, X) = \text{closure}\big(\{\, [A \to \alpha X \cdot \gamma] \;:\; [A \to \alpha \cdot X\,\gamma] \in I \,\}\big)GOTO(I,X)=closure({[A→αX⋅γ]:[A→α⋅Xγ]∈I})

    tức là: lấy tất cả các mục trong tập (đã đóng) III có ký hiệu ngay sau dấu chấm bằng đúng XXX, dịch dấu chấm qua phải một vị trí (vượt qua XXX), rồi tính bao đóng của tập mục thu được (theo quy tắc đóng LR(0) chuẩn, xem lại: nếu mục có ký hiệu ngay sau dấu chấm là phi kết thúc BBB thì thêm mọi mục [B→⋅ δ][B \to \cdot\,\delta][B→⋅δ]).

    Nếu không có mục nào trong III có ký hiệu ngay sau dấu chấm là XXX, thì GOTO(I,X)GOTO(I,X)GOTO(I,X) là tập rỗng.

    Cho văn phạm, một tập mục III đã đóng đầy đủ (là một trạng thái hợp lệ của automat LR(0)), và một ký hiệu XXX, hãy tính GOTO(I,X)GOTO(I, X)GOTO(I,X).

    • Đị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 (định dạng như bài toán tính closure ở trên: A -> X1 X2 ... Xk hoặc A -> #).
      • Dòng tiếp theo: số nguyên mmm (1≤m≤501 \le m \le 501≤m≤50) — số mục của tập III (đã đóng đầy đủ, cho sẵn).
      • mmm dòng tiếp theo: mỗi dòng một mục dạng A -> β . γ (định dạng dấu chấm như bài closure).
      • Dòng cuối cùng: ký hiệu XXX (một token duy nhất, có thể là ký hiệu kết thúc hoặc phi kết thúc).
    • Định dạng đầu ra:

      Nếu GOTO(I,X)GOTO(I, X)GOTO(I,X) là tập rỗng, in ra đúng một dòng EMPTY.

      Ngược lại, in ra:

      • Dòng 1: số lượng mục trong GOTO(I,X)GOTO(I, X)GOTO(I,X).
      • Các dòng tiếp theo: mỗi dòng một mục theo định dạng A -> β . γ, liệt kê theo thứ tự tăng dần khi so sánh chuỗi (thứ tự từ điển theo mã ASCII).

    Ví dụ:

    Đầu vào:

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

    Đầu ra:

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

    Đầu vào:

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

    Đầu ra:

    1
F -> id .

    Đang tải editor...