Trình thông dịch tùy chỉnh cho các biểu thức toán học

Question

Tôi phải đánh giá một số lượng lớn các biểu thức có chứa các biến và tôi đang nghĩ đến việc viết một trình thông dịch nhỏ để biên dịch nhanh và nhỏ. Tuy nhiên tôi không có kinh nghiệm với chủ đề này và có một vài câu hỏi.

Giả sử chúng tôi có tệp có biểu thức toán học và tập hợp các đối tượng có giới hạn. Các tập tin có thể trông giống như:

expr[x,y,z] = 2*x*y + x^2 + 28/14*z*(x*y^2 + 15*z) + ... 

Tôi muốn phân tích này bằng cách nào đó để tôi có thể đánh giá các biểu thức về số trong ứng dụng của tôi bằng cách đơn giản gọi một hàm expr(float x, float y, float z). Không được sửa số tham số (EDIT: mỗi biểu thức sẽ có định nghĩa riêng với số tham số thích hợp hoặc sẽ chấp nhận một mảng) và lồng vào dấu ngoặc đơn sẽ được phép giữ các tệp đầu vào hợp lý nhỏ.

Vì biểu thức là tất cả các loại đa thức, tôi có thể nghĩ cấu trúc dữ liệu trông như thế nào, nhưng việc phân tích cú pháp có vẻ khó khăn. Tôi đã tìm thấy một số câu trả lời cho một số câu hỏi tương tự ở đây trên SO, ví dụ bằng cách sử dụng Lua.

Câu hỏi lớn nhất, tuy nhiên, là hình phạt hiệu suất sẽ là khi tạo và gọi các đối tượng đó so với việc biên dịch trực tiếp các biểu thức này từ mã C được tạo tự động.

Cảm ơn trước!

CHỈNH SỬA: Vui lòng xem xét ví dụ về expr() ở trên chỉ như vậy. Tôi đoán cách tốt nhất là để có các đối tượng của một lớp templated giữ hệ số và quyền hạn của các biến trong mảng thưa thớt.

Answer 1

Hiệu suất là một vấn đề về độ dài của chuỗi. Các ngôn ngữ được phiên dịch khá nhiều luôn chậm hơn mã C đã biên dịch để đánh giá các biểu thức số học. Nhưng không phải là nhiều chương trình dành phần lớn thời gian của họ làm số học, vì vậy phần lớn thời gian không quan trọng. Nó cũng làm cho một sự khác biệt cho dù bạn phân tích cú pháp biểu thức mỗi khi bạn đánh giá nó hoặc (có vẻ như nhiều khả năng từ những gì bạn nói), phân tích nó thành một số hình thức trung gian. Không thể nói từ những gì bạn đã nói, cho dù điều đó có quan trọng với bạn hay không, hoặc bạn sẽ viết một thông dịch viên nhanh như thế nào, nhưng tôi sẽ không mong đợi nó tốt hơn 10 lần chậm hơn, theo thời gian đã đánh giá các biểu thức có liên quan. Những nỗ lực đầu tiên diễn giải đã tồi tệ hơn nhiều.

Đối với biểu mẫu trung gian đó - nơi thông thường để bắt đầu là sử dụng thuật toán "shunting-yard" của Dijkstra để chuyển đổi biểu thức của bạn thành dạng Ba Lan ngược. Điều đó cung cấp cho bạn một chuỗi các "ký hiệu", "mã byte", gọi chúng là những gì bạn thích và dễ dàng viết một bộ đánh giá biểu thức cho biểu mẫu đó - mỗi toán tử chỉ bật các toán hạng từ một chồng, thực hiện lệnh op, sau đó đẩy kết quả vào ngăn xếp, cho đến khi giá trị cuối cùng của biểu thức là điều duy nhất còn lại ở cuối. Chữ số và tên biến số giống như "toán tử" không bật toán hạng và đẩy giá trị của chúng.

[Chỉnh sửa - tùy thuộc vào người dùng của bạn là ai, có thể chương trình của bạn lấy tệp văn bản đó, tạo chương trình C từ nó, chạy trình biên dịch rồi chạy chương trình kết quả (hoặc mở và gọi vào dll kết quả). Rõ ràng là dựa vào rất nhiều công cụ cụ thể của hệ thống (một trình biên dịch được cài đặt, cho một), và các biểu thức sẽ cần phải được đánh giá đủ lần mà chi phí biên dịch được khắc phục.]

Answer 2

Có một ví dụ đơn giản trong số Bison Manual.

Answer 3

Bạn nói vấn đề là "biểu thức lớn phức tạp", và bạn lo lắng về hình phạt hiệu suất. Sau đó, bạn nên xem xét biên dịch chúng, không giải thích chúng. (trình thông dịch tốt có tốc độ chậm hơn 10 lần so với mã được biên dịch dưới dạng quy tắc chung; trình thông dịch lousy/ad hoc có xu hướng tồi tệ hơn đáng kể).

Các tuyến đường thường lệ cho điều này là để "biên dịch" các biểu thức bằng cách nào đó, trong đó bao gồm phân tích cú pháp xây dựng, máy phát điện mã, tối ưu hóa, vv

C trình biên dịch đã làm tất cả điều này. Vì vậy, tôi nghĩ bạn muốn được tốt hơn tắt dịch các biểu thức để C. Biên soạn họ là sau đó dễ dàng và thực hiện sẽ nhanh như chớp so với bất cứ điều gì bạn có thể hy vọng sẽ làm như thông dịch viên. Điều đó cũng có thể được thực hiện bằng cách sử dụng một trình phân tích cú pháp và cú pháp dịch hướng dịch đơn giản hơn nhiều.

Nhưng Nếu những biểu thức này được tạo ra bởi Mathematica, chúng sẽ có cấu trúc khá chuẩn nhưng không phức tạp. Trong trường hợp này, tôi đoán bạn có thể viết một dịch giả dựa trên regexp có thể ánh xạ các dạng Mathematica vào các hàm C mà không gặp nhiều rắc rối; Perl sẽ là lý tưởng cho việc này. Điều này mang lại cho bạn một giải pháp dễ thực hiện và rất nhanh.

Đối với những gì nó có giá trị, tôi tin rằng Mathematica có một tùy chọn để chuyển đổi biểu thức Mathematica trực tiếp vào C. Có vẻ rằng đó sẽ là giá trị kiểm tra ra, quá.