Việc sử dụng ngôn ngữ cấp cao để tạo ra các trình biên dịch bắt đầu ra đời vào đầu thập niên 1970 khi mà trình biên dịch Pascal và C đã được tạo nên từ chính ngôn ngữ của chúng. Xây dựng một trình biên dịch tự lập là một vấn đề về bẫy khởi động. Nghĩa là, phiên bản đầu tiên của trình biên dịch tự lập này cho một ngôn ngữ phải được biên dịch từ một trình biên dịch mà được viết trong một ngôn ngữ khác hay là, bắt chước theo cách của Hart va. | 54 MỘT TRÌNH BIÊN DỊCH MỘT LƯỢT ĐƠN GIẢN A expr a term và p term Ký hiệu chưa tận A ỉà đệ qui trái bởi vì luật sinh A - Act có A là ký hiệu tận trái ở vế phải Áp dụng ỉập lại luật sinh này sẽ sinh ra một chuỗi các a ở bên phải của A như trong Hình a . Cuôi cùng khi A được thay bằng p chủng ta có một p theo sau là một chuỗi gồm zero hoặc nhiều a. Chúng ta có thế có được cùng kết quá như trong Hình a bằng cách viết lại các luật sinh cho A theo cách sau. A - pR R - a R ị E ơ đây R là một chưa tận mới. Luật sinh R - Ct R là đệ qui phải bởi vì luật sinh cho R có R lồ ký hiệu cuối cùng ở vê phải. Các luật sinh đệ qui phải khiên các cây tâng trưởng xuống hướng sang phải như trong Hình b . Các cây tăng trưởng xuống hướng về bên phải gây khó khăn cho việc dịch các biểu thức có chứa các toán tử kết hợp trái như toán tử trừ chẳng hạn. Tuy nhiên trong phần kế tiếp chúng ta sẽ thây rằng bản dịch đúng đắn các biểu thức sang ký pháp hậu vị vần có thể thực hiện được bằng cách thiết kế cẩn thận lược đồ dịch dựa trên một văn phạm đệ qui phải. Trong Chương 4 chúng ta sẻ xét các dạng tổng quát hơn của đệ qui trái và trình bày một phương pháp loại bỏ tất cả đệ qui trái ra khỏi một văn phạm MỘT CHƯƠNG TRÌNH DỊCH CHO CÁC BlỂU THỨC ĐƠN GIẢN Sử dụng các kỹ thuật của ba phần vừa qua chúng ta sẽ xây dựng một chương trình dịch dựa cú pháp dưới dạng một chương trình C có khả năng dịch các biểu thức sô học thành dạng hậu vị. Để bảo đảm cho chương trình khởi đầu đủ nhỏ để dễ quản lý chúng ta bắt đầu với các biểu thức chứa các ký sô digit được phán cách bởi các dấu cộng và trừ. Ngôn ngữ này sẽ được mở rộng trong hai phần tiếp theo để bao gồm cá các số định danh identifier và những toán tử khác nữa. Bởi vì các biếu thức thường xuất hiện như những kết cấu trong rất nhiều ngôn ngữ nên rát có ích khi nghiên cứu chi tiết công việc phiên dịch chúng. expr expr term print expr expr - term 1 print expr term term. 0 print 0 term 1 print í 1 ị term - 9 print 9 Hình . Đặc tả khởi
