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 máy phân tích LR bằng bảng ACTION/GOTO

    Một bộ phân tích LR hoạt động dựa trên một ngăn xếp trạng thái cùng hai bảng: bảng ACTION (tra theo trạng thái đỉnh ngăn xếp và ký hiệu kết thúc hiện tại) và bảng GOTO (tra theo trạng thái và ký hiệu phi kết thúc). Thuật toán mô phỏng chuẩn như sau, với ngăn xếp ban đầu chỉ chứa trạng thái 000 và con trỏ đọc token bắt đầu từ token đầu tiên (chuỗi vào luôn kết thúc bằng ký hiệu quy ước $):

    • 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 N: đẩy trạng thái NNN vào ngăn xếp, chuyển sang token kế tiếp.
      • Nếu là reduce N (rút gọn theo sản xuất số NNN, sản xuất có vế phải độ dài kkk, có thể k=0k = 0k=0 với sản xuất rỗng): rút kkk trạng thái khỏi đỉnh ngăn xếp; gọi s′s's′ là trạng thái mới ở đỉnh; đẩy vào ngăn xếp trạng thái GOTO[s'][A] (với AAA là vế trái của sản xuất NNN); không tiêu thụ token hiện tại.
      • Nếu là accept: dừng, chuỗi được chấp nhận.
      • Nếu ô đó không có hành động (lỗi): dừng, chuỗi bị từ chối.

    Mỗi lần shift hoặc reduce được tính là một bước. Cho bảng ACTION/GOTO và văn phạm tường minh, hãy mô phỏng thuật toán trên với một chuỗi token đầu vào và cho biết chuỗi có được chấp nhận không, cùng số bước đã thực hiện.

    Ví dụ nhỏ minh hoạ định dạng ô bảng: ô s4 nghĩa là shift tới trạng thái 4; r6 nghĩa là reduce theo sản xuất số 6; acc nghĩa là accept; e nghĩa là ô lỗi (không có hành động).

    • Định dạng đầu vào:
      • Dòng 1: số nguyên sss (1≤s≤501 \le s \le 501≤s≤50) — số trạng thái, đánh số 0,1,…,s−10, 1, \ldots, s-10,1,…,s−1 (trạng thái bắt đầu luôn là 000).
      • Dòng 2: số nguyên ttt — số ký hiệu kết thúc (bao gồm cả ký hiệu kết thúc chuỗi $).
      • Dòng 3: ttt ký hiệu kết thúc cách nhau bởi khoảng trắng, theo đúng thứ tự cột sẽ dùng trong bảng ACTION (bắt buộc phải có mặt token $).
      • Dòng 4: số nguyên ntntnt — số ký hiệu phi kết thúc.
      • Dòng 5: ntntnt ký hiệu phi kết thúc cách nhau bởi khoảng trắng, theo đúng thứ tự cột dùng trong bảng GOTO.
      • sss dòng tiếp theo (bảng ACTION, dòng iii ứng với trạng thái i−1i-1i−1): mỗi dòng gồm ttt token cách nhau bởi khoảng trắng, mỗi token là một trong các dạng sN (shift tới trạng thái N), rN (reduce theo sản xuất N, N đánh số từ 1), acc (accept), hoặc e (lỗi/ô trống), theo đúng thứ tự các ký hiệu kết thúc ở dòng 3.
      • Dòng tiếp theo: số nguyên ppp — số sản xuất.
      • ppp dòng tiếp theo: mỗi dòng có dạng A -> X1 X2 ... Xk (các ký hiệu vế phải cách nhau khoảng trắng), hoặc A -> # nếu vế phải rỗng (k=0k=0k=0). Sản xuất được đánh số 1,…,p1, \ldots, p1,…,p theo đúng thứ tự xuất hiện.
      • sss dòng tiếp theo (bảng GOTO, dòng iii ứng với trạng thái i−1i-1i−1): mỗi dòng gồm ntntnt token cách nhau bởi khoảng trắng, mỗi token là số hiệu trạng thái đích hoặc dấu - nếu không có, theo đúng thứ tự các ký hiệu phi kết thúc ở dòng 5.
      • Dòng cuối cùng: chuỗi token đầu vào (không bao gồm $), cách nhau bởi khoảng trắng; có thể là dòng trống nếu chuỗi vào rỗng.
    • Định dạng đầu ra:

      In ra đúng 3 dòng:

      • Dòng 1: ACCEPT nếu chuỗi được chấp nhận, ngược lại REJECT.
      • Dòng 2: tổng số bước shift/reduce đã thực hiện trước khi dừng (accept hoặc gặp lỗi).
      • Dòng 3: nếu REJECT, in vị trí (đánh số từ 1, tính cả ký hiệu $ được thêm vào cuối chuỗi là vị trí cuối cùng) của token đang xét tại thời điểm gặp lỗi; nếu ACCEPT, in dấu -.

    Ví dụ:

    Đầu vào:

    12
6
id ( ) + * $
3
E T F
s2 s5 e e e e
e e r4 r4 r4 r4
e e r6 r6 r6 r6
e e e s6 e acc
e e r2 r2 s7 r2
s2 s5 e e e e
s2 s5 e e e e
s2 s5 e e e e
e e s11 s6 e e
e e r1 r1 s7 r1
e e r3 r3 r3 r3
e e r5 r5 r5 r5
6
E -> E + T
E -> T
T -> T * F
T -> F
F -> ( E )
F -> id
3 4 1
- - -
- - -
- - -
- - -
8 4 1
- 9 1
- - 10
- - -
- - -
- - -
- - -
id + id * id

    Đầu ra:

    ACCEPT
13
-

    Đầu vào:

    12
6
id ( ) + * $
3
E T F
s2 s5 e e e e
e e r4 r4 r4 r4
e e r6 r6 r6 r6
e e e s6 e acc
e e r2 r2 s7 r2
s2 s5 e e e e
s2 s5 e e e e
s2 s5 e e e e
e e s11 s6 e e
e e r1 r1 s7 r1
e e r3 r3 r3 r3
e e r5 r5 r5 r5
6
E -> E + T
E -> T
T -> T * F
T -> F
F -> ( E )
F -> id
3 4 1
- - -
- - -
- - -
- - -
8 4 1
- 9 1
- - 10
- - -
- - -
- - -
- - -
id + + id

    Đầu ra:

    REJECT
5
3

    Đang tải editor...