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] Bảng ký hiệu cho dãy lệnh gán bằng phân tích đệ quy

    Xét một ngôn ngữ mini gồm nnn câu lệnh gán liên tiếp, mỗi câu lệnh có dạng:

    identifier=E\text{identifier} = Eidentifier=E

    trong đó EEE là một biểu thức số học theo văn phạm:

    E→T ((+∣−) T)∗,T→F ((∗∣/) F)∗,F→− F ∣ num ∣ identifier ∣ ( E )E \to T\ \big((+|-)\ T\big)^*, \quad T \to F\ \big((*|/)\ F\big)^*, \quad F \to -\ F \ \mid\ \text{num} \ \mid\ \text{identifier} \ \mid\ ( \ E \ )E→T ((+∣−) T)∗,T→F ((∗∣/) F)∗,F→− F ∣ num ∣ identifier ∣ ( E )

    Một identifier gồm chữ cái/số/gạch dưới, bắt đầu bằng chữ cái hoặc _. Một identifier xuất hiện trong EEE phải đã được gán giá trị ở một câu lệnh trước đó. Các phép chia có thể cho kết quả không nguyên; hãy tính toán chính xác bằng số hữu tỉ (phân số tối giản), tuyệt đối không dùng số thực dấu phẩy động.

    Hãy cài đặt bộ phân tích cú pháp đệ quy xuống để phân tích và tính giá trị của từng câu lệnh theo đúng thứ tự, cập nhật một bảng ký hiệu (symbol table) ánh xạ tên biến sang giá trị hữu tỉ hiện tại (một biến có thể được gán lại nhiều lần, giá trị mới sẽ ghi đè giá trị cũ). Sau khi xử lý xong toàn bộ nnn câu lệnh, in ra giá trị cuối cùng của mỗi biến khác nhau đã từng xuất hiện, theo đúng thứ tự lần đầu tiên biến đó được gán.

    Định dạng in giá trị: nếu giá trị là số nguyên, in số nguyên đó; nếu không, in dưới dạng p/q với q>0q > 0q>0 và phân số tối giản.

    Ví dụ: với 3 câu lệnh a = 4/2, b = a*3+1, b = b-1, kết quả là a = 2, sau đó b = 7, rồi b được gán lại thành 6; in ra hai dòng: a 2 và b 6.

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

      Dòng đầu chứa số nguyên nnn (1≤n≤2001 \le n \le 2001≤n≤200). nnn dòng tiếp theo, mỗi dòng có dạng identifier = E (có thể có khoảng trắng tùy ý quanh dấu = và trong EEE), với EEE hợp lệ theo văn phạm trên và mọi identifier xuất hiện bên phải đã được gán trước đó.

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

      In ra nhiều dòng, mỗi dòng dạng ten_bien gia_tri (cách nhau một khoảng trắng), theo thứ tự lần đầu xuất hiện của biến; giá trị là số nguyên hoặc phân số tối giản p/q.

    Ví dụ:

    Đầu vào:

    1
x = 7/2

    Đầu ra:

    x 7/2

    Đầu vào:

    3
a = 4/2
b = a*3+1
b = b-1

    Đầu ra:

    a 2
b 6

    Đang tải editor...