Trình biên dịch của trình biên dịch

Một "trình biên dịch của trình biên dịch" hay "chương trình sinh trình biên dịch" (tiếng Anh: compiler-compiler) là một công cụ tạo ra bộ phân tích cú pháp, trình thông dịch hoặc trình biên dịch từ một dạng mô tả hình thức nào đó của một ngôn ngữ và máy tính. Dạng sơ khai nhất nhưng vẫn phổ biến của chương trình sinh trình biên dịch là trình sinh bộ phân tích cú pháp với đầu vào là một văn phạm (thường dưới dạng BNF của một ngôn ngữ lập trình và đầu ra là mã nguồn của một bộ phân tích cú pháp thường được sử dụng như một thành phần của trình biên dịch.

Compiler-compiler lý tưởng nhận một mô tả của ngôn ngữ lập trình và một kiến trúc tập lệnh đầu ra và tự động sinh ra một trình biên dịch có thể sử dụng được. Trong thực tế, mức độ phát triển hiện tại vẫn chưa đạt đến độ phức tạp này và hầu hết trình sinh trình biên dịch không thể xử lý được ngữ nghĩa của thông tin về kiến trúc đầu ra.

Các biến thể

sửa

Một trình sinh bộ phân tích cú pháp điển hình gắn mã nguồn thực thi được với mỗi luật của văn phạm. Mã nguồn sẽ được thực thi khi luật đó được áp dụng bởi bộ phân tích. Những đoạn mã nguồn này đôi khi được gọi là tiểu trình ngữ nghĩa vì chúng xác định ngữ nghĩa của cấu trúc ngữ pháp đang được phân tích. Dựa vào kiểu bộ phân tích cần sinh ra, các tiểu trình này có thể xây dựng cây phân tích (hoặc cây phân tích trừu tượng) hoặc sinh trực tiếp ra mã lệnh.

Một vài compiler-compiler thử nghiệm nhận đầu vào là mô tả hình thức của ngữ nghĩa của một ngôn ngữ lập trình, điển hình là sử dụng denotational semantics. Cách tiếp cận này thường được gọi là "biên dịch dựa ngữ nghĩa" mà người tiên phong là Peter Mosses' Semantic Implementation System (SIS) in 1978.[1] Tuy nhiên, cả trình biên dịch dược sinh ra và mã lệnh nó tạo ra đều không hiệu quả về thời gian và bộ nhớ. Hiện tại không có trình biên dịch thành phẩm nào được xây dựng theo cách này tuy nhiên các nghiên cứu vẫn đang tiếp tục.

Dự án Production Quality Compiler-Compiler ở Đại học Carnegie-Mellon không hình thức hoá ngữ nghĩa nhưng có một framework bán hình thức cho mô tả máy tính.

Compiler-compiler tồn tại dưới nhiều hình thức, bao gồm cả bottom-up rewrite machine generators (xem JBurg) và trình sinh bộ phân tích văn phạm thuộc tính (ví dụ ANTLR có thể được dùng để kiểm tra kiểu, lan truyền hằng số và hơn nữa đồng thời với pha phân tích cú pháp).

Lịch sử

sửa

Compiler-compiler đầu tiên sử dụng tên gọi này được viết bởi Tony Brooker năm 1960 và được sử dụng để tạo ra trình biên dịch cho máy tính AtlasĐại học Manchester, gồm cả trình biên dịch Atlas Autocode. Tuy nhiên nó khá khác so với các trình sinh trình biên dịch hiện đại và có thể được xếp vào giữa một trình biên dịch tổng quát có khả năng tuỳ chỉnh cao và một ngôn ngữ có khả năng mở rộng. Tên gọi "compiler-compiler" phù hợp với hệ thống của Brooker hơn nhiều so với những hệ thống ngày nay. Hầu như chắc chắn rằng cái tên "Compiler Compiler" đã trở nên phổ biến do Yacc hơn là công trình của Brooker's.[cần dẫn nguồn]

Một số ví dụ khác của trình sinh bộ phân tích cú pháp là ANTLR, Coco/R, CUP, GNU bison, Eli, FSL, SableCCJavaCC.

Một vài compiler-compiler

sửa

Các chủ đề liên quan

sửa

Chú thích

sửa
  1. ^ Peter Mosses, "SIS: A Compiler-Generator System Using Denotational Semantics," Report 78-4-3, Dept. of Computer Science, University of Aarhus, Denmark, June 1978

Tham khảo

sửa

Bài viết này dựa trên nguồn lấy từ Từ điển trực tuyến miễn phí về máy tính trước ngày 1 tháng 11 năm 2008 và được hợp nhất theo các điều khoản "cấp lại giấy phép" của GFDL, phiên bản 1.3 hoặc mới hơn.

Đọc thêm

sửa

Lịch sử

sửa
  • Brooker, R. A., et al., The Compiler-Compiler, Annual Review in Automatic Programming, Vol. 3, p. 229. (1963).
  • Brooker, R. A., Morris, D. and Rohl, J. S., Experience with the Compiler Compiler, Computer Journal, Vol. 9, p. 350. (February 1967).
  • Johnson, Stephen C., Yacc—yet another compiler-compiler, Computer Science Technical Report 32, Bell Laboratories, Murray Hill, NJ, July 1975
  • McKeeman, William Marshall; Horning, James J.; Wortman, David B., CS.toronto.edu, A Compiler Generator, Englewood Cliffs, N.J.: Prentice-Hall, 1970. ISBN 0-13-155077-2

Liên kết ngoài

sửa