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] Backpatching sinh mã điều khiển cho biểu thức logic

    Kỹ thuật backpatching dùng để dịch biểu thức logic có đánh giá ngắn mạch (short-circuit) thành mã ba địa chỉ mà không cần biết trước nhãn đích, bằng cách để trống trường goto rồi vá (backpatch) sau. Mỗi biểu thức con EEE mang hai thuộc tính tổng hợp: E.truelist — danh sách chỉ số các lệnh nhảy cần vá tới nơi thực thi khi EEE đúng, và E.falselist — tương tự khi EEE sai. Văn phạm và luật ngữ nghĩa (mở rộng đầy đủ với NOT, AND, OR lồng nhau tuỳ ý, và toán tử so sánh bất kỳ trong {<,>,==,!=,≤,≥}\{<, >, ==, !=, \le, \ge\}{<,>,==,!=,≤,≥}):

    • E→REL a op bE \to \text{REL}\ a\ op\ bE→REL a op b: sinh 2 lệnh liên tiếp bắt đầu tại chỉ số hiện tại nextinstr: (i): if a op b goto _ và (i+1): goto _; E.truelist={i}E.\text{truelist}=\{i\}E.truelist={i}, E.falselist={i+1}E.\text{falselist}=\{i+1\}E.falselist={i+1}.
    • E→NOT E1E \to \text{NOT}\ E_1E→NOT E1​: E.truelist=E1.falselistE.\text{truelist}=E_1.\text{falselist}E.truelist=E1​.falselist, E.falselist=E1.truelistE.\text{falselist}=E_1.\text{truelist}E.falselist=E1​.truelist (chỉ hoán đổi, không sinh lệnh mới).
    • E→AND E1 E2E \to \text{AND}\ E_1\ E_2E→AND E1​ E2​: ngay trước khi dịch E2E_2E2​, gọi MMM là nextinstr lúc đó; backpatch(E1.truelist,ME_1.\text{truelist}, ME1​.truelist,M); E.truelist=E2.truelistE.\text{truelist}=E_2.\text{truelist}E.truelist=E2​.truelist, E.falselist=E1.falselist∪E2.falselistE.\text{falselist}=E_1.\text{falselist} \cup E_2.\text{falselist}E.falselist=E1​.falselist∪E2​.falselist.
    • E→OR E1 E2E \to \text{OR}\ E_1\ E_2E→OR E1​ E2​: tương tự nhưng backpatch(E1.falselist,ME_1.\text{falselist}, ME1​.falselist,M); E.truelist=E1.truelist∪E2.truelistE.\text{truelist}=E_1.\text{truelist} \cup E_2.\text{truelist}E.truelist=E1​.truelist∪E2​.truelist, E.falselist=E2.falselistE.\text{falselist}=E_2.\text{falselist}E.falselist=E2​.falselist.

    Sau khi dịch xong toàn bộ EEE, đề bài cho hai nhãn đích Ltrue,LfalseL_{true}, L_{false}Ltrue​,Lfalse​ (chỉ số lệnh mà chương trình sẽ nhảy tới khi EEE đúng/sai); thực hiện backpatch(E.truelist,LtrueE.\text{truelist}, L_{true}E.truelist,Ltrue​) và backpatch(E.falselist,LfalseE.\text{falselist}, L_{false}E.falselist,Lfalse​). In ra toàn bộ dãy lệnh đã sinh (đã vá đầy đủ, không còn chỗ trống nào).

    Biểu thức được cho ở dạng tiền tố (prefix), token cách nhau bởi khoảng trắng, ví dụ AND REL a < b REL c < d tương ứng a<b  &&  c<da<b \;\&\&\; c<da<b&&c<d.

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

      Dòng 1: số nguyên start — chỉ số của lệnh đầu tiên sẽ sinh ra (nextinstr ban đầu). Dòng 2: biểu thức tiền tố, chỉ gồm các từ khoá REL a op b, NOT E, AND E1 E2, OR E1 E2 (lồng nhau tuỳ ý), với a, b là định danh/hằng không chứa khoảng trắng và op ∈{<,>,==,!=,≤,≥}\in \{<,>,==,!=,\le,\ge\}∈{<,>,==,!=,≤,≥} được biểu diễn bằng đúng các ký hiệu < > == != <= >=. Dòng 3: hai số nguyên Ltrue LfalseL_{true}\ L_{false}Ltrue​ Lfalse​.

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

      In mỗi lệnh trên một dòng, theo đúng thứ tự chỉ số tăng dần, dạng <i>: if <a> <op> <b> goto <target> hoặc <i>: goto <target>, với <target> là giá trị đã được backpatch (không còn dấu _).

    Ví dụ:

    Đầu vào:

    10
NOT OR REL a == b REL c != d
50 60

    Đầu ra:

    10: if a == b goto 60
11: goto 12
12: if c != d goto 60
13: goto 50

    Đầu vào:

    100
AND REL a < b REL c < d
200 300

    Đầu ra:

    100: if a < b goto 102
101: goto 300
102: if c < d goto 200
103: goto 300

    Đang tải editor...