Lập trình biên dịch: Các thành phần cơ bản nhất là gì?

Question

Tôi quan tâm đến việc viết một trình biên dịch rất tối giản.

Tôi muốn viết một mảnh nhỏ của phần mềm (trong C/C++) nhằm thoả mãn các tiêu chí sau:

• đầu ra ở định dạng ELF (* nix)
• đầu vào là một textfile đơn
• C-như ngữ pháp và cú pháp
• không mối liên kết
• không Preprocessor
• rất nhỏ (max. 1-2 KLOC)

Tính năng ngôn ngữ:

• mẹ đẻ kiểu dữ liệu: char, int và nổi
• mảng (đối với tất cả các loại dữ liệu bản địa)
• biến
• cấu trúc điều khiển (if-else)
• chức năng
• vòng lặp (sẽ đẹp)
• đại số đơn giản (div, thêm, phụ, mul, biểu thức boolean, chút ca, vv)
• inline asm (cho các cuộc gọi hệ thống)

Ai có thể cho tôi biết làm thế nào để bắt đầu? Tôi không biết những gì các bộ phận một trình biên dịch bao gồm (ít nhất là không có nghĩa là tôi chỉ có thể bắt đầu ngay từ kệ) và làm thế nào để chương trình chúng. Cảm ơn về những ý tưởng của bạn.

Answer 1

Thứ nhất, bạn cần quyết định xem bạn sẽ làm trình biên dịch hay thông dịch viên. Một trình biên dịch dịch mã của bạn thành một thứ có thể chạy trực tiếp trên phần cứng, trong một trình thông dịch, hoặc được biên dịch sang một ngôn ngữ khác mà sau đó được diễn giải theo một cách nào đó. Cả hai loại ngôn ngữ đều được hoàn thiện để chúng có cùng khả năng diễn đạt. Tôi sẽ đề nghị bạn tạo một trình biên dịch biên dịch mã của bạn thành một trong hai .net hoặc bytecode Java, vì nó cung cấp cho bạn một trình thông dịch rất được tối ưu hóa để chạy trên cũng như nhiều thư viện chuẩn.

Khi bạn đã thực hiện quyết định của bạn có một số bước chung để làm theo

1. định nghĩa ngôn ngữ Trước hết, bạn phải xác định cách ngôn ngữ của bạn nên xem xét cú pháp.

2. Lexer Bước thứ hai là tạo từ khóa mã của bạn, được gọi là mã thông báo. Ở đây, chúng ta đang nói về các yếu tố rất cơ bản như số, dấu cộng và chuỗi.

3. Phân tích cú pháp Bước tiếp theo là tạo ngữ pháp khớp với danh sách mã thông báo của bạn. Bạn có thể xác định ngữ pháp của mình bằng cách sử dụng ví dụ: ngữ pháp không có ngữ cảnh. Một số công cụ có thể được cung cấp với một trong các ngữ pháp này và tạo trình phân tích cú pháp cho bạn. Thông thường, các thẻ được phân tích cú pháp được sắp xếp thành một cây phân tích cú pháp. Cây phân tích cú pháp là biểu diễn ngữ pháp của bạn dưới dạng cấu trúc dữ liệu mà bạn có thể di chuyển xung quanh.

4. Biên dịch hoặc giải thích Bước cuối cùng là chạy một số logic trên cây phân tích cú pháp của bạn. Một cách đơn giản để làm cho trình thông dịch của riêng bạn là tạo ra một số logic liên quan đến từng loại nút trong cây của bạn và đi qua cây từ dưới lên trên hoặc từ trên xuống dưới. Nếu bạn muốn biên dịch sang ngôn ngữ khác, bạn có thể chèn logic về cách dịch mã trong các nút thay thế.

Wikipedia tuyệt vời để tìm hiểu thêm, bạn có thể muốn bắt đầu here.

Liên quan đến tài liệu đọc trong thế giới thực, tôi sẽ đề xuất "Bộ xử lý ngôn ngữ lập trình trong JAVA" của David A Watt & Deryck F Brown. Tôi đã sử dụng cuốn sách đó trong khóa học trình biên dịch của tôi và học bằng ví dụ là rất tốt trong lĩnh vực này.

Answer 2

Đây là những phần vô cùng quan trọng:

• Scanner: Điều này phá vỡ các tập tin đầu vào vào thẻ
• Parser: Đây xây dựng một cây cú pháp trừu tượng (AST) từ thẻ xác định bởi máy quét.
• Tạo mã: Điều này tạo ra đầu ra từ AST.

Bạn cũng sẽ có thể muốn:

• Lỗi xử lý: Điều này cho bộ phân tích phải làm gì nếu nó gặp một bất ngờ thẻ
• Tối ưu hóa: Điều này sẽ cho phép trình biên dịch để sản xuất máy hiệu quả hơn mã

Chỉnh sửa: Bạn đã thiết kế ngôn ngữ chưa? Nếu không, bạn cũng sẽ muốn xem xét thiết kế ngôn ngữ.

Answer 3

Số một cần thiết là một cuốn sách viết về trình biên dịch. Rất nhiều người sẽ bảo bạn đọc cuốn sách "Dragon Book" của Aho và cộng sự, nhưng cuốn sách hay nhất tôi đã đọc trên các trình biên dịch là "Brinch Hansen trên Pascal Compilers". Tôi nghi ngờ nó không được in (Amazon là bạn của bạn), nhưng nó sẽ đưa bạn qua tất cả các bước thiết kế và viết một trình biên dịch bằng cách sử dụng đệ quy gốc, đó là phương pháp dễ nhất để người mới biên dịch hiểu.

Mặc dù sách sử dụng Pascal là ngôn ngữ triển khai và đích, các bài học và kỹ thuật được trình bày áp dụng như nhau cho tất cả các ngôn ngữ khác.

Answer 4

Tôi không biết những gì bạn hy vọng sẽ thoát khỏi điều này, nhưng nếu nó đang học và nhìn vào mã hiện có phù hợp với bạn, luôn có tcc.

Answer 5

Các ví dụ là tất cả trong Perl, nhưng Exploring Programming Language Architecture in Perl là một cuốn sách hay (và miễn phí).

Answer 6

Với tất cả những gì bạn hy vọng đạt được, yêu cầu khó khăn nhất có thể là "rất nhỏ (tối đa 1-2 KLOC)". Tôi nghĩ rằng yêu cầu đầu tiên của bạn một mình (tạo ra đầu ra ELF) có thể mất hơn một nghìn dòng mã của chính nó.

Một cách để đơn giản hóa vấn đề, ít nhất là để bắt đầu, là tạo mã trong văn bản ngôn ngữ assembly mà sau đó bạn nạp vào bộ kết hợp hiện có (nasm sẽ là một lựa chọn tốt).Người lắp ráp sẽ chăm sóc tạo ra mã máy thực tế, cũng như tất cả các mã ELF cụ thể cần thiết để xây dựng một thực thi runnable thực tế. Sau đó, công việc của bạn được giảm xuống để phân tích ngôn ngữ và tạo mã assembly. Khi dự án của bạn trưởng thành đến điểm mà bạn muốn loại bỏ sự phụ thuộc vào một bộ lắp ráp, bạn có thể tự viết lại phần này và cắm nó vào bất cứ lúc nào.

Nếu tôi là bạn, tôi có thể bắt đầu với một người lắp ráp và xây dựng các phần trên nó. Trình biên dịch "đơn giản" nhất có thể lấy một ngôn ngữ chỉ với một vài câu lệnh rất đơn giản:

print "hello" 
a = 5 
print a 

và dịch sang ngôn ngữ lắp ráp. Một khi bạn nhận được rằng làm việc, sau đó bạn có thể xây dựng một lexer và phân tích cú pháp và trừu tượng cây cú pháp và máy phát mã, đó là hầu hết các phần bạn sẽ cần cho một ngôn ngữ có cấu trúc khối hiện đại.

Chúc may mắn!

Answer 7

Tôi luôn khuyên bạn nên flex và bison cho loại công việc này làm người mới bắt đầu. Bạn luôn có thể tìm hiểu các ins and outs của văn bản máy quét của riêng bạn và phân tích cú pháp sau này, mặc dù họ có thể tăng kích thước mã ít nhất họ sẽ được tạo ra cho bạn bởi các công cụ. :)

Answer 8

Một tập thực sự tốt tài liệu tham khảo miễn phí, IMHO, bao gồm:

Nhìn chung trình biên dịch hướng dẫn: Hãy xây dựng một trình biên dịch bởi Jack Crenshaw (http://compilers.iecc.com/crenshaw/) Đó là dài dòng, nhưng tôi thích nó.

Bộ vi xử lý: NASM (nasm.us) phù hợp cho Linux và Windows/DOS và quan trọng nhất là rất nhiều tài liệu và ví dụ/hướng dẫn. (FASM cũng tốt nhưng ít tài liệu hướng dẫn/hướng dẫn trên mạng)

nguồn khác Các PC hội sách (http://www.drpaulcarter.com/pcasm/index.php)

Tôi đang cố gắng để viết một LISP, vì vậy tôi đang sử dụng Lisp 1.5 Manual. Bạn có thể muốn lấy thông số ngôn ngữ cho bất kỳ ngôn ngữ nào bạn đang viết.

Theo như 1-2KLOC, giả sử bạn sử dụng ngôn ngữ cấp cao (như Py hoặc Rb) bạn nên đóng nếu bạn không quá tham vọng.