Tài liệu tham khảo Cần thiết để thực hiện một thông dịch viên trong C/C++

Question

Tôi thấy mình gắn liền với một dự án để tích hợp một thông dịch viên vào một ứng dụng hiện có. Ngôn ngữ được hiểu là một dẫn xuất của Lisp, với các nội trang ứng dụng cụ thể. Cá nhân 'chương trình' sẽ được chạy theo lô theo phong cách trong ứng dụng.

Tôi ngạc nhiên rằng trong những năm qua tôi đã viết một vài trình biên dịch và một số trình dịch/trình phân tích ngôn ngữ dữ liệu, nhưng trước đây tôi chưa bao giờ viết một thông dịch viên. Các mẫu thử nghiệm là khá xa cùng, thực hiện như là một walker cây cú pháp, trong C + +. Tôi có thể có thể ảnh hưởng đến kiến ​​trúc ngoài nguyên mẫu, nhưng không ảnh hưởng đến ngôn ngữ thực hiện (C++). Vì vậy, những hạn chế:

• thi sẽ nằm trong C++
• phân tích cú pháp có thể sẽ bị xử lý với một yacc/bò rừng bizon ngữ pháp (bây giờ)
• gợi ý của toàn hệ sinh thái VM/Interpreter như NekoVM và LLVM có lẽ không thực tế cho dự án này. Khép kín là tốt hơn, ngay cả khi điều này nghe có vẻ như NIH.

Điều tôi thực sự tìm kiếm là đọc tài liệu về nguyên tắc cơ bản của việc triển khai phiên dịch. Tôi đã thực hiện một số lượt duyệt SO và một trang web khác được gọi là Lambda the Ultimate, mặc dù chúng được định hướng nhiều hơn về lý thuyết ngôn ngữ lập trình.

Một số mẩu tin tôi đã thu thập được cho đến nay:

• Lisp in Small Pieces, Christian Queinnec. Người đề xuất nó nói rằng nó "đi từ trình thông dịch tầm thường đến các kỹ thuật nâng cao và kết thúc trình bày các trình biên dịch bytecode và" Scheme to C '. "

• NekoVM. Như tôi đã đề cập ở trên, tôi nghi ngờ rằng chúng tôi sẽ được phép kết hợp toàn bộ khung công tác VM để hỗ trợ dự án này.

• Structure and Interpretation of Computer Programs. Ban đầu tôi đề nghị rằng điều này có thể là quá mức cần thiết, nhưng đã làm việc thông qua một đoạn khỏe mạnh, tôi đồng ý với @JBF. Rất thông tin và mở rộng tâm trí.

• On Lisp bởi Paul Graham. Tôi đã đọc điều này, và trong khi nó là một giới thiệu thông tin về các nguyên tắc Lisp, thì không đủ để bắt đầu xây dựng một thông dịch viên.

• Parrot Implementation. Điều này có vẻ như một niềm vui đọc. Không chắc chắn nó sẽ cung cấp cho tôi với các nguyên tắc cơ bản.

• Scheme from Scratch. Peter Michaux đang tấn công các cách triển khai khác nhau của Scheme, từ một trình thông dịch Scheme nhanh chóng và bẩn được viết bằng C (để sử dụng như một bootstrap trong các dự án sau này) để biên dịch mã Scheme. Rất thú vị cho đến nay.

• Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages, được đề xuất trong chuỗi nhận xét cho Books On Creating Interpreted Languages. Cuốn sách chứa hai chương dành cho việc thực hành phiên dịch, vì vậy tôi sẽ thêm nó vào hàng đợi đọc của mình.

• New (và chưa Cũ, ví dụ: 1979): Writing Interactive Compilers and Interpreters bởi P. J. Brown. Điều này là không còn in ấn nữa, nhưng thú vị trong việc cung cấp một phác thảo về các nhiệm vụ khác nhau liên quan đến việc thực hiện một thông dịch viên cơ bản.Tôi đã nhìn thấy đánh giá hỗn hợp cho điều này nhưng vì nó là giá rẻ (tôi có nó theo thứ tự được sử dụng cho khoảng $ 3,50) Tôi sẽ cung cấp cho nó một spin.

Vậy còn cách nào? Có một cuốn sách tốt mà phải mất neophyte bằng tay và cho thấy làm thế nào để xây dựng một thông dịch viên trong C/C + + cho một ngôn ngữ giống như Lisp? Bạn có sở thích cho người đi bộ cú pháp-cây hoặc thông dịch viên bytecode không?

Để trả lời @JBF:

• nguyên mẫu hiện nay là một thông dịch viên, và nó có ý nghĩa với tôi như chúng ta chấp nhận một đường dẫn đến một tập tin mã độc đoán và thực hiện nó trong môi trường ứng dụng của chúng tôi. Các nội trang được sử dụng để ảnh hưởng đến biểu diễn dữ liệu trong bộ nhớ của chúng tôi.

• không được làm chậm quá mức. Cây đi bộ hiện tại có vẻ chấp nhận được.

• Ngôn ngữ là dựa trên trên Lisp, nhưng không phải là Lisp, vì vậy không yêu cầu tuân thủ tiêu chuẩn.

• Như đã đề cập ở trên, có khả năng chúng tôi sẽ không được phép thêm dự án VM/thông dịch viên bên ngoài đầy đủ để giải quyết vấn đề này.

Với các áp phích khác, tôi cũng sẽ kiểm tra các trích dẫn của bạn. Cảm ơn tất cả!

Answer 1

Câu trả lời ngắn:

Danh sách đọc cơ bản cho trình thông dịch lisp là SICP. Tôi sẽ không gọi nó là quá mức cần thiết, nếu bạn cảm thấy mình bị vượt trội cho những phần đầu tiên của cuốn sách chuyển sang chương 4 và bắt đầu diễn giải (mặc dù tôi cảm thấy điều này sẽ là một mất mát vì các chương 1-3 thực sự là tốt!) .

Thêm LISP vào các phần nhỏ (LISP từ bây giờ), chương 1-3. Đặc biệt là chương 3 nếu bạn cần thực hiện bất kỳ hình thức kiểm soát không tầm thường nào.

Xem bài đăng này của Jens Axel Søgaard trên sơ đồ tự lưu trữ tối thiểu: http://www.scheme.dk/blog/2006/12/self-evaluating-evaluator.html.

Câu trả lời dài hơn một chút:

Thật khó để đưa ra lời khuyên mà không biết những gì bạn yêu cầu từ thông dịch viên của bạn.

• thực sự thực sự cần phải là thông dịch viên hay bạn thực sự cần có khả năng thực thi mã lisp?
• có cần nhanh không?
• có cần tuân thủ các tiêu chuẩn không? Môi chung? R5RS? R6RS? Bạn có cần bất kỳ SFRI nào không?

Nếu bạn cần bất kỳ điều gì lạ mắt hơn một trình đơn cây cú pháp đơn giản, tôi thực sự khuyên bạn nên nhúng một hệ thống con lược đồ nhanh. Sơ đồ Gambit xuất hiện trong đầu: http://dynamo.iro.umontreal.ca/~gambit/wiki/index.php/Main_Page.

Nếu đó không phải là tùy chọn chương 5 trong SICP và chương 5 - trong biên dịch mục tiêu LISP để thực hiện nhanh hơn.

Để diễn giải nhanh hơn, tôi sẽ xem qua các trình biên dịch/trình biên dịch JavaScript gần đây nhất. Dường như có rất nhiều suy nghĩ đi vào thực thi JavaScript nhanh và bạn có thể học hỏi từ chúng. V8 trích dẫn hai giấy tờ quan trọng: http://code.google.com/apis/v8/design.html và squirrelfish trích dẫn một cặp vợ chồng: http://webkit.org/blog/189/announcing-squirrelfish/.

Ngoài ra còn có các giấy tờ sơ đồ kinh điển: http://library.readscheme.org/page1.html cho trình biên dịch RABBIT.

Nếu tôi tham gia vào một chút đầu cơ sớm, quản lý bộ nhớ có thể là hạt khó khăn để crack. Nils M Holm đã xuất bản một cuốn sách "Đề án 9 từ không gian trống" http://www.t3x.org/s9fes/ trong đó bao gồm một dấu hiệu đơn giản stop-the-thế giới và thu gom rác quét. Nguồn bao gồm.

John Rose (của danh tiếng JVM mới hơn) đã viết một bài báo về tích hợp Đề án vào C: http://library.readscheme.org/servlets/cite.ss?pattern=AcmDL-Ros-92.

Answer 2

Khám phá JScheme from Peter Norvig. Tôi thấy điều này thật đơn giản để hiểu và chuyển sang C++. Uh, dunno về cách sử dụng chương trình như một ngôn ngữ kịch bản mặc dù - dạy nó để jnrs là cồng kềnh và cảm thấy ngày (helloooo 1980's).

Answer 3

The Kamin Interpreters từ sách của Samuel Kamin Ngôn ngữ lập trình, Phương pháp tiếp cận dựa trên phiên dịch, được dịch sang tiếng C++ của Timothy Budd. Tôi không chắc mã nguồn trống sẽ hữu ích như thế nào, vì nó có nghĩa là đi cùng với cuốn sách, nhưng nó là một cuốn sách hay bao gồm các khái niệm cơ bản của việc triển khai Lisp bằng một ngôn ngữ cấp thấp hơn, bao gồm thu gom rác, v.v. Đó không phải là trọng tâm của cuốn sách, đó là ngôn ngữ lập trình nói chung, nhưng nó được bảo hiểm.)

Lisp in Pieces nhỏ đi sâu hơn, nhưng đó là cả tốt và xấu cho trường hợp của bạn. Có rất nhiều tài liệu về biên dịch và như vậy sẽ không có liên quan đến bạn, và các trình thông dịch đơn giản của nó là trong Đề án, không phải C++.

SICP là tốt, chắc chắn. Không quá mức cần thiết, nhưng tất nhiên việc viết thông dịch viên chỉ là một phần nhỏ của cuốn sách.

Đề xuất JScheme cũng là một gợi ý hay (và nó kết hợp một số mã của tôi), nhưng sẽ không giúp bạn với những thứ như GC.

Tôi có thể xác định điều này với nhiều đề xuất hơn sau.

Chỉnh sửa: Một vài người đã nói rằng họ đã học được từ số awklisp của tôi. Điều này được thừa nhận là một gợi ý kỳ lạ, nhưng nó rất nhỏ, dễ đọc, thực sự có thể sử dụng được, và không giống như đồ chơi nhỏ bé khác, Lisps thực hiện bộ thu gom rác và biểu diễn dữ liệu thay vì dựa vào ngôn ngữ thực hiện ở mức cao cung cấp cho họ.

Answer 4

Có trên SICP.

Tôi đã thực hiện tác vụ này nhiều lần và đây là những gì tôi sẽ làm nếu tôi là bạn:

Thiết kế mô hình bộ nhớ của bạn trước. Bạn sẽ muốn có một hệ thống GC của một số loại. Nó WAAAAY dễ dàng hơn để làm điều này đầu tiên hơn để bu lông nó về sau.

Thiết kế cấu trúc dữ liệu của bạn. Trong các triển khai của tôi, tôi đã có một hộp điều khiển cơ bản với một số loại cơ sở: atom, string, number, list, bool, primitive-function.

Thiết kế máy ảo của bạn và đảm bảo giữ sạch API.thực hiện cuối cùng của tôi có điều này như một API cấp cao nhất (tha thứ cho các định dạng - SO được pooching xem trước của tôi)

ConsBoxFactory &GetConsBoxFactory() { return mConsFactory; } 
AtomFactory &GetAtomFactory() { return mAtomFactory; } 
Environment &GetEnvironment() { return mEnvironment; } 
t_ConsBox *Read(iostream &stm); 
t_ConsBox *Eval(t_ConsBox *box); 
void Print(basic_ostream<char> &stm, t_ConsBox *box); 
void RunProgram(char *program); 
void RunProgram(iostream &stm); 

RunProgram là không cần thiết - đó là thực hiện về đọc, Eval, và Print. REPL là một mô hình phổ biến cho phiên dịch, đặc biệt là LISP.

Một ConsBoxFactory có sẵn để tạo các hộp điều khiển mới và hoạt động trên chúng. Một AtomFactory được sử dụng để các nguyên tử tượng trưng tương đương ánh xạ chính xác tới một đối tượng. Một môi trường được sử dụng để duy trì sự ràng buộc của các ký hiệu đối với các ô đối lập.

Hầu hết công việc của bạn nên đi vào ba bước này. Sau đó, bạn sẽ thấy rằng mã khách hàng của bạn và mã hỗ trợ bắt đầu trông rất giống như LISP quá:

t_ConsBox *ConsBoxFactory::Cadr(t_ConsBox *list) 
{ 
    return Car(Cdr(list)); 
} 

Bạn có thể viết phân tích cú pháp trong yacc/lex, nhưng tại sao bận tâm? Lisp là một trình phân tích ngữ pháp và máy quét/đệ quy-đệ quy cực kỳ đơn giản cho nó là khoảng hai giờ làm việc. Phần tồi tệ nhất là viết các biến vị ngữ để xác định các mã thông báo (ví dụ, IsString, IsNumber, IsQuotedExpr, vv) và sau đó viết các thường trình để chuyển đổi các thẻ thành các hộp điều khiển.

Giúp dễ dàng viết keo vào và ra khỏi mã C và giúp dễ dàng gỡ lỗi các vấn đề khi mọi thứ xảy ra sự cố.

Answer 5

Tôi muốn mở rộng đề xuất của mình cho Programming Languages: Application and Interpretation. Nếu bạn muốn viết một thông dịch viên, cuốn sách đó sẽ đưa bạn đến đó trong một con đường rất ngắn. Nếu bạn đọc thông qua viết mã bạn đọc và thực hiện bài tập bạn kết thúc với một loạt các thông dịch viên tương tự nhưng khác (một là háo hức, người kia lười, người kia là năng động, người kia có một số cách gõ, một người có phạm vi động, khác có phạm vi từ vựng, vv).