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ửaMộ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ửaCompiler-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, SableCC và JavaCC.
Một vài compiler-compiler
sửaCác chủ đề liên quan
sửaChú thích
sửa- ^ 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ửaBà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ửaLị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- Computer50.org Lưu trữ 2004-10-31 tại Wayback Machine, Brooker Autocodes
- Catalog.compilertools.net Lưu trữ 2011-08-13 tại Wayback Machine, The Catalog of Compiler Construction Tools
- Labraj.uni-mb.si, Lisa
- Skenz.it, Jflex and Cup resources (tiếng Ý)
- Gentle.compilertools.net Lưu trữ 2010-05-07 tại Wayback Machine, The Gentile Compiler Construction System
- Accent.compilertools.net Lưu trữ 2010-05-16 tại Wayback Machine, Accent: a Compiler for the Entire Class of Context-Free Languages
- Grammatica.percederberg.net , an open-source parser-generator for.NET and Java