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] Xây dựng tập mục chính tắc LR(0)

    Cho một văn phạm phi ngữ cảnh với kkk luật sinh (đánh số 1…k1 \ldots k1…k) và ký hiệu bắt đầu SSS. Hãy xây dựng toàn bộ tập mục chính tắc LR(0) (canonical collection of LR(0) item sets) cùng bảng chuyển trạng thái (transition/GOTO) của nó.

    Văn phạm mở rộng (augmented): thêm luật sinh số 000: S′→SS' \to SS′→S (S′S'S′ là ký hiệu mới, không trùng với bất kỳ ký hiệu nào trong văn phạm gốc).

    Xây dựng:

    1. Trạng thái ban đầu (trạng thái 000) là CLOSURE({[S′→. S]})\text{CLOSURE}(\{[S' \to .\,S]\})CLOSURE({[S′→.S]}) (tức tập mục lõi {(0,0)}\{(0,0)\}{(0,0)}, closure định nghĩa như bài CLOSURE ở trên, tính trên cả luật 000 và các luật 1..k1..k1..k).
    2. Với mỗi trạng thái III đã tạo (xét theo đúng thứ tự được tạo ra, bắt đầu từ trạng thái 000) và mỗi ký hiệu văn phạm XXX mà III có mục dạng […→α . Xβ][\ldots \to \alpha \,.\, X\beta][…→α.Xβ]: tính J=GOTO(I,X)J = \text{GOTO}(I,X)J=GOTO(I,X). Nếu JJJ (so sánh bằng đúng tập mục, không phân biệt cách tạo) chưa từng xuất hiện là một trạng thái nào trước đó, thêm JJJ như một trạng thái mới (được đánh số bằng số thứ tự tiếp theo, theo thứ tự được tạo ra). Dù JJJ mới hay cũ, ghi nhận một chuyển (I, X) -> J.
    3. Lặp lại bước 2 cho đến khi không còn trạng thái mới hoặc chuyển mới nào được tạo (duyệt theo kiểu BFS: xử lý các trạng thái theo đúng thứ tự chúng được tạo ra).

    Thứ tự ký hiệu XXX khi xét chuyển tại mỗi trạng thái: xác định một thứ tự toàn cục cố định các ký hiệu ALLSYMBOLS bằng cách quét lần lượt các luật sinh gốc 1,2,…,k1, 2, \ldots, k1,2,…,k (không tính luật 000) theo đúng thứ tự cho trong input; với mỗi luật, xét lần lượt vế trái rồi các ký hiệu vế phải từ trái sang phải; ký hiệu nào gặp lần đầu tiên (và khác ε) thì được thêm vào cuối ALLSYMBOLS. Khi xét các chuyển đi ra từ một trạng thái, phải xét XXX theo đúng thứ tự xuất hiện trong ALLSYMBOLS (bỏ qua XXX nếu GOTO(I,X)\text{GOTO}(I,X)GOTO(I,X) không tồn tại).

    Yêu cầu: in ra toàn bộ các trạng thái (theo thứ tự tạo ra 0,1,…0, 1, \ldots0,1,…) cùng tập mục của mỗi trạng thái, và toàn bộ các chuyển trạng thái.

    • Định dạng đầu vào:
      • Dòng 1: số nguyên kkk (1≤k≤151 \le k \le 151≤k≤15) và ký hiệu bắt đầu SSS, cách nhau bởi khoảng trắng.
      • kkk dòng tiếp theo: luật sinh dạng A -> X1 X2 ... Xm (nếu rỗng: A -> ε). Không có ký hiệu nào trùng tên S'.
    • Định dạng đầu ra:
      • Dòng đầu tiên: số nguyên TTT — tổng số trạng thái.
      • Với mỗi trạng thái t=0,1,…,T−1t = 0, 1, \ldots, T-1t=0,1,…,T−1 (theo thứ tự tạo ra): in dòng STATE t, sau đó in các mục của trạng thái đó, mỗi mục một dòng i p (luật 000 ứng với S′→SS' \to SS′→S), sắp xếp tăng dần theo (i,p)(i,p)(i,p).
      • Sau khi liệt kê hết các trạng thái: in dòng chứa số nguyên MMM — tổng số chuyển trạng thái. Sau đó in MMM dòng, mỗi dòng state X next_state, được liệt kê theo thứ tự: nhóm theo state tăng dần (đúng thứ tự trạng thái được tạo ra), trong mỗi trạng thái theo đúng thứ tự ALLSYMBOLS đã mô tả ở trên.

    Ví dụ:

    Đầu vào:

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

    Đầu ra:

    12
STATE 0
0 0
1 0
2 0
3 0
4 0
5 0
6 0
STATE 1
0 1
1 1
STATE 2
2 1
3 1
STATE 3
4 1
STATE 4
1 0
2 0
3 0
4 0
5 0
5 1
6 0
STATE 5
6 1
STATE 6
1 2
3 0
4 0
5 0
6 0
STATE 7
3 2
5 0
6 0
STATE 8
1 1
5 2
STATE 9
1 3
3 1
STATE 10
3 3
STATE 11
5 3
22
0 E 1
0 T 2
0 F 3
0 ( 4
0 id 5
1 + 6
2 * 7
4 E 8
4 T 2
4 F 3
4 ( 4
4 id 5
6 T 9
6 F 3
6 ( 4
6 id 5
7 F 10
7 ( 4
7 id 5
8 + 6
8 ) 11
9 * 7

    Đầu vào:

    1 S
S -> a

    Đầu ra:

    3
STATE 0
0 0
1 0
STATE 1
0 1
STATE 2
1 1
2
0 S 1
0 a 2

    Đang tải editor...