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] Shift-Reduce: Phân tích ưu tiên toán tử

    Đề bài

    Phân tích ưu tiên toán tử (operator-precedence parsing) là một dạng shift-reduce dùng quan hệ ưu tiên ⋖ (<), ≐ (=), ⋗ (>) giữa các ký hiệu kết thúc để quyết định shift hay reduce.

    Thuật toán (đơn giản hóa): ngăn xếp bắt đầu ['$']. Gọi a là ký hiệu kết thúc trên đỉnh, b là token hiện tại:

    • a < b hoặc a = b → shift b.
    • a > b → reduce (pop một ký hiệu khỏi đỉnh).
    • a = $ và b = $ → accept.
    • không có quan hệ → error và dừng.

    Cho bảng quan hệ và chuỗi, hãy in dãy thao tác.

    Khái niệm

    • Mô hình đơn giản hóa: mỗi reduce pop đúng một ký hiệu.

    Ví dụ

    $ < id, id > $: với chuỗi $ id $ → shift id, reduce, accept.

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

      Dòng đầu nr. nr dòng a REL b với REL là <, = hoặc >. Dòng cuối là chuỗi ký hiệu kết thúc, bắt đầu và kết thúc bằng $, cách nhau bởi dấu cách.

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

      1 ≤ nr ≤ 200. Chuỗi vào có tối đa 100 token.

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

      In dãy thao tác, mỗi thao tác một dòng: shift <tok>, reduce, accept, hoặc error.

    Ví dụ:

    Đầu vào:

    2
$ < id
id > $
$ id $

    Đầu ra:

    shift id
reduce
accept

    Giải thích:

    Đỉnh $ với token id: $ < id -> shift id. Đỉnh id với token $: id > $ -> reduce (pop id), đỉnh lại là $. $ và $ -> accept.

    Đang tải editor...