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ân loại mục LR(0)

    Trong lý thuyết phân tích LR, một mục LR(0) (LR(0) item) là một luật sinh có đánh dấu vị trí đọc bằng một dấu chấm . ở đâu đó trong vế phải. Ví dụ mục A -> a . B c nghĩa là đã đọc được a, tiếp theo bộ phân tích cần xử lý B rồi c.

    Cho một danh sách mục LR(0) (vế trái mỗi luật sinh là một chữ cái in hoa A-Z — ký hiệu chưa kết thúc; mọi token khác trong vế phải, ngoại trừ dấu chấm ., đều là ký hiệu kết thúc trừ khi bản thân nó cũng là một chữ cái in hoa đơn), hãy phân loại từng mục theo quy tắc:

    • Nếu dấu chấm nằm ở cuối vế phải (không còn ký hiệu nào sau dấu chấm) → mục thuộc loại REDUCE.
    • Ngược lại, xét ký hiệu ngay sau dấu chấm: nếu đó là một ký hiệu chưa kết thúc (một chữ cái in hoa) → loại GOTO; nếu đó là ký hiệu kết thúc → loại SHIFT.

    Ví dụ: mục E -> E + . T có ký hiệu ngay sau dấu chấm là T (chữ in hoa) → GOTO. Mục T -> id . có dấu chấm ở cuối → REDUCE. Mục F -> . ( E ) có ký hiệu ngay sau dấu chấm là ( (không phải chữ in hoa) → SHIFT.

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

      Dòng đầu là số nguyên nnn (1≤n≤2001 \le n \le 2001≤n≤200) — số mục cần phân loại. nnn dòng tiếp theo, mỗi dòng là một mục LR(0) dạng A -> t1 t2 ... tm, trong đó A là một chữ cái in hoa, -> là ký hiệu phân cách, và đúng một trong các token t1,…,tmt_1,\dots,t_mt1​,…,tm​ là dấu chấm . (các token cách nhau bởi đúng một khoảng trắng). Vế phải có thể chỉ chứa dấu chấm (mục A -> . ứng với luật sinh rỗng).

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

      In ra nnn dòng, dòng thứ iii là loại của mục thứ iii: REDUCE, GOTO, hoặc SHIFT.

    Ví dụ:

    Đầu vào:

    1
A -> a . B c

    Đầu ra:

    GOTO

    Đầu vào:

    4
S -> . E
E -> E + . T
T -> id .
S -> .

    Đầu ra:

    GOTO
GOTO
REDUCE
REDUCE

    Đang tải editor...