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] Phát hiện xung đột trong bảng phân tích SLR(1)

    Một văn phạm là SLR(1) nếu bảng phân tích SLR(1) xây dựng từ tự động hóa LR(0) và tập FOLLOW không chứa ô nào có nhiều hơn một hành động (không có xung đột shift-reduce hay reduce-reduce).

    Xét trạng thái III của tự động hóa LR(0) (được xây dựng như bài đếm trạng thái LR(0), có tăng cường S′→SS' \to SS′→S). Với mỗi mục hoàn chỉnh A→α⋅A \to \alpha \cdotA→α⋅ trong III (A≠S′A \ne S'A=S′), luật quy tắc SLR(1) cho phép rút gọn (reduce) theo luật này khi ký hiệu nhìn trước thuộc FOLLOW(A)\text{FOLLOW}(A)FOLLOW(A). Mục S′→S⋅S' \to S \cdotS′→S⋅ tương ứng hành động chấp nhận (accept) khi ký hiệu nhìn trước là $.

    Tại trạng thái III:

    • Có xung đột shift-reduce nếu tồn tại ký hiệu kết thúc aaa vừa có thể dịch chuyển (shift) — tức tồn tại mục dạng B→β⋅aγB \to \beta \cdot a\gammaB→β⋅aγ trong III — vừa thuộc FOLLOW của LHS của một mục hoàn chỉnh khác trong III (cho phép reduce trên aaa).
    • Có xung đột reduce-reduce nếu tồn tại ký hiệu kết thúc (hoặc $ cho accept) được từ hai mục hoàn chỉnh khác nhau (khác luật sinh) cùng "đòi" áp dụng (kể cả một bên là accept).

    Hãy liệt kê tất cả các trạng thái có xung đột và loại xung đột tương ứng.

    Ví dụ (văn phạm if-then-else nhập nhằng):

    4
S -> if E then S
S -> if E then S else S
S -> a
E -> b

    văn phạm này có xung đột shift-reduce tại trạng thái 7 (kết quả in ra 7 shift-reduce).

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

      Dòng 1: số nguyên nnn (1≤n≤151 \le n \le 151≤n≤15) — số luật sinh. nnn dòng tiếp theo: mỗi dòng dạng LHS -> s1 s2 ... sk, luật rỗng ghi là LHS -> #.

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

      Nếu không có trạng thái nào xung đột, in ra đúng một dòng SLR(1). Ngược lại, in ra danh sách các dòng, mỗi dòng dạng <chỉ số trạng thái> <loại> với <loại> là shift-reduce hoặc reduce-reduce. Chỉ số trạng thái được đánh số bắt đầu từ 0 theo thứ tự trạng thái được sinh ra khi duyệt theo chiều rộng (BFS) từ trạng thái ban đầu, duyệt các ký hiệu chuyển theo thứ tự từ điển tăng dần tại mỗi trạng thái. Các dòng được sắp theo chỉ số trạng thái tăng dần; nếu một trạng thái có cả hai loại xung đột, in dòng shift-reduce trước rồi đến reduce-reduce.

    Ví dụ:

    Đầu vào:

    4
S -> if E then S
S -> if E then S else S
S -> a
E -> b

    Đầu ra:

    7 shift-reduce

    Đầu vào:

    6
E -> E + T
E -> T
T -> T * F
T -> F
F -> ( E )
F -> id

    Đầu ra:

    SLR(1)

    Đang tải editor...