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ể
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. 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ử
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.

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

ANTLR
Bison
Coco/R
ELI, bộ công cụ tích hợp cho việc xây dựng trình biên dịch.
Lemon
parboiled, thư viện Java cho bộ phân tích cú pháp.
Packrat parser
PQCC
Yacc

Các chủ đề liên quan
LL,
LR,
SLR,
LALR,
GLR,

Chú thích

Tham khảo

Đọc thêm
Lịch sử
Brooker, R. A., et al., The Compiler-Compiler, Annual Review in Automatic Programming, Vol. 3, p.&nbsp;229. (1963).
Brooker, R. A., Morris, D. and Rohl, J. S., Experience with the Compiler Compiler, Computer Journal, Vol. 9, p.&nbsp;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
Computer50.org , Brooker Autocodes
Catalog.compilertools.net , The Catalog of Compiler Construction Tools
Labraj.uni-mb.si , Lisa
Skenz.it, Jflex and Cup resources
Gentle.compilertools.net , The Gentile Compiler Construction System
Accent.compilertools.net , Accent: a Compiler for the Entire Class of Context-Free Languages
Grammatica.percederberg.net , an open-source parser-generator for.NET and Java