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] LR(0): Liệt kê cạnh GOTO của automaton

    Đề bài

    Sau khi xây automaton LR(0), mỗi cặp (trạng thái I, ký hiệu X) mà GOTO(I, X) khác rỗng tạo một cạnh chuyển. Hãy liệt kê toàn bộ cạnh.

    Quy ước đánh số trạng thái: I0 là 0; duyệt theo BFS, tại mỗi trạng thái xét các ký hiệu (xuất hiện sau dấu chấm) theo thứ tự từ điển, trạng thái mới được cấp số tăng dần theo thứ tự phát hiện.

    Khái niệm

    • Cách đánh số này đảm bảo kết quả xác định và tái lập được.

    Ví dụ

    Văn phạm S -> a có cạnh 0 S 1 và 0 a 2.

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

      Dòng đầu n. n dòng luật sinh. Ký hiệu bắt đầu là vế trái luật đầu.

    • Ràng buộc đầu vào:

      1 ≤ n ≤ 20. Vế phải ≤ 8 ký hiệu. Ký hiệu không kết thúc là chữ in hoa.

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

      In các cạnh GOTO dạng from symbol to, mỗi cạnh một dòng, sắp xếp tăng dần theo (from, symbol, to).

    Ví dụ:

    Đầu vào:

    1
S -> a

    Đầu ra:

    0 S 1
0 a 2

    Giải thích:

    I0={S'->.S, S->.a}. Theo thứ tự từ điển các ký hiệu S rồi a: GOTO(I0,S)=I1 cho cạnh 0 S 1; GOTO(I0,a)=I2 cho cạnh 0 a 2.

    Đang tải editor...