solution

Trong lược đồ dịch (translation scheme) kinh điển cho biểu thức số học, văn phạm S-attributed sau gắn hành động ngữ nghĩa để sinh ra dạng hậu tố ngay trong lúc phân tích cú pháp:

$E \to E_1 + T \{\text{print}('+')\} \mid E_1 - T \{\text{print}('-')\} \mid T$ $T \to T_1 * F \{\text{print}('*')\} \mid T_1 / F \{\text{print}('/')\} \mid F$ $F \to (E) \mid \text{id} \mid \text{num}$

Các hành động print được thực hiện đúng theo thứ tự mà bộ phân tích cú pháp thu giảm (reduce) các luật sinh (tức là ngay sau khi phân tích xong toán hạng thứ hai của một phép toán). Toán hạng id/num được in ra ngay khi được nhận dạng.

Cho một biểu thức trung tố hợp lệ, chỉ gồm các phép + - * /, dấu ngoặc (), các toán hạng là số nguyên không âm (một hoặc nhiều chữ số) hoặc định danh (chữ cái/_ theo sau bởi chữ, số, _), không có khoảng trắng bên trong toán hạng. Hãy mô phỏng lược đồ dịch trên và in ra chuỗi các token theo đúng thứ tự được print, cách nhau bởi một khoảng trắng.

Ví dụ: với a+b*(c-3), các bước reduce theo văn phạm trên sinh ra dãy in a b c 3 - * +.