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] Mô phỏng bộ điều khiển LR (LR Driver) với bảng ACTION/GOTO cho trước

    Cho đầy đủ bảng ACTION và bảng GOTO đã được xây dựng sẵn cho một bộ phân tích LR (không nhất thiết phải cho biết trạng thái nào ứng với mục nào — chỉ cần dùng bảng như một "máy" để chạy), cùng danh sách các sản xuất của văn phạm (đánh số 1-based). Hãy mô phỏng bộ điều khiển LR (LR driver) tiêu chuẩn để phân tích một chuỗi token đầu vào (bảng được đảm bảo không có xung đột — mỗi cặp (trạng thái, ký hiệu) có tối đa một hành động).

    Bộ điều khiển LR hoạt động với một ngăn xếp trạng thái, khởi tạo là [0][0][0], và một con trỏ vào vị trí đầu chuỗi token (chuỗi token luôn được ngầm định kết thúc bằng ký hiệu $):

    • Gọi sss là trạng thái ở đỉnh ngăn xếp, aaa là token hiện tại. Tra ACTION[s][a]:
      • Nếu là shift s2s_2s2​: đẩy s2s_2s2​ vào đỉnh ngăn xếp trạng thái, con trỏ dịch sang token kế tiếp.
      • Nếu là reduce iii (sản xuất thứ iii: A→γA \to \gammaA→γ với ∣γ∣=L|\gamma| = L∣γ∣=L): loại bỏ LLL trạng thái ở đỉnh ngăn xếp (nếu L=0L=0L=0 thì không loại bỏ gì); gọi s′s's′ là trạng thái mới ở đỉnh; tra GOTO[s'][A] để lấy trạng thái s3s_3s3​, đẩy s3s_3s3​ vào ngăn xếp; ghi nhận sản xuất iii vừa dùng.
      • Nếu là accept: dừng, phân tích thành công.
      • Nếu không có hành động nào được định nghĩa cho (s,a)(s,a)(s,a): dừng với lỗi tại token hiện tại (token thứ ppp, 1-based, trong đó ký hiệu $ được đánh số n+1n+1n+1 với nnn là số token đầu vào thực sự).

    Yêu cầu: nếu phân tích thành công, in ra danh sách các sản xuất đã REDUCE, theo đúng thứ tự thực hiện; nếu có lỗi, in vị trí lỗi.

    • Định dạng đầu vào:
      • Dòng 1: số nguyên PPP — số sản xuất.
      • PPP dòng tiếp theo: mỗi dòng dạng LHS -> s1 s2 ... sk (sản xuất thứ iii được đánh số theo thứ tự xuất hiện, 1-based).
      • Dòng tiếp theo: số nguyên AAA — số mục trong bảng ACTION.
      • AAA dòng tiếp theo, mỗi dòng có một trong các dạng:
        • s a S s2 — tại trạng thái sss, với terminal aaa: SHIFT sang trạng thái s2s2s2;
        • s a R i — tại trạng thái sss, với terminal aaa: REDUCE theo sản xuất iii;
        • s a ACC — tại trạng thái sss, với terminal $: ACCEPT.
      • Dòng tiếp theo: số nguyên GGG — số mục trong bảng GOTO.
      • GGG dòng tiếp theo, mỗi dòng dạng s A s2 (tại trạng thái sss, với non-terminal AAA: chuyển tới trạng thái s2s2s2).
      • Dòng cuối: chuỗi token đầu vào, cách nhau khoảng trắng (không bao gồm $; dòng trống nếu không có token nào).
    • Định dạng đầu ra:

      Nếu phân tích thành công: in 2 dòng — dòng 1 là ACCEPT; dòng 2 là danh sách số hiệu các sản xuất đã REDUCE theo đúng thứ tự thực hiện, cách nhau một dấu cách (dòng trống nếu không có REDUCE nào). Nếu có lỗi tại vị trí ppp (1-based, p=n+1p = n+1p=n+1 ứng với ký hiệu $ nếu lỗi xảy ra ở cuối, nnn là số token đầu vào): in đúng một dòng ERROR p.

    Ví dụ:

    Đầu vào:

    6
E -> E + T
E -> T
T -> T * F
T -> F
F -> ( E )
F -> id
36
0 ( S 2
0 id S 1
1 ) R 6
1 * R 6
1 $ R 6
1 + R 6
2 ( S 2
2 id S 1
3 * S 8
3 $ R 2
3 + R 2
3 ) R 2
4 ) R 4
4 * R 4
4 $ R 4
4 + R 4
5 $ ACC
5 + S 6
6 ( S 2
6 id S 1
7 * S 8
7 $ R 1
7 + R 1
7 ) R 1
8 ( S 2
8 id S 1
9 ) R 3
9 * R 3
9 $ R 3
9 + R 3
10 + S 6
10 ) S 11
11 ) R 5
11 * R 5
11 $ R 5
11 + R 5
9
0 T 3
0 F 4
0 E 5
6 F 4
6 T 7
8 F 9
2 T 3
2 F 4
2 E 10
id + id * id

    Đầu ra:

    ACCEPT
6 4 2 6 4 6 3 1

    Đầu vào:

    6
E -> E + T
E -> T
T -> T * F
T -> F
F -> ( E )
F -> id
36
0 ( S 2
0 id S 1
1 ) R 6
1 * R 6
1 $ R 6
1 + R 6
2 ( S 2
2 id S 1
3 * S 8
3 $ R 2
3 + R 2
3 ) R 2
4 ) R 4
4 * R 4
4 $ R 4
4 + R 4
5 $ ACC
5 + S 6
6 ( S 2
6 id S 1
7 * S 8
7 $ R 1
7 + R 1
7 ) R 1
8 ( S 2
8 id S 1
9 ) R 3
9 * R 3
9 $ R 3
9 + R 3
10 + S 6
10 ) S 11
11 ) R 5
11 * R 5
11 $ R 5
11 + R 5
9
0 T 3
0 F 4
0 E 5
6 F 4
6 T 7
8 F 9
2 T 3
2 F 4
2 E 10
( id + id ) * id

    Đầu ra:

    ACCEPT
6 4 2 6 4 1 5 4 6 3 2

    Đang tải editor...