Phân tích các biểu thức toán học bằng JavaScript

bởi Shalvah

Cách đây một thời gian, tôi đã viết về việc mã hóa một biểu thức toán học, với Javascript là ngôn ngữ được lựa chọn. Trình mã thông báo mà tôi đã tạo trong bài viết đó là thành phần đầu tiên trong nhiệm vụ của tôi để hiển thị và giải các biểu thức toán học bằng Javascript hoặc bất kỳ ngôn ngữ nào khác. Trong bài viết này, tôi sẽ hướng dẫn cách xây dựng thành phần tiếp theo: trình phân tích cú pháp.

Công việc của trình phân tích cú pháp là gì? Khá đơn giản. Nó phân tích biểu thức. (Duh.) Được rồi, thật ra, Wikipedia có một câu trả lời hay:

Trình phân tích cú pháp là một thành phần phần mềm lấy dữ liệu đầu vào (thường là văn bản) và xây dựng cấu trúc dữ liệu — thường là một số loại cây phân tích cú pháp, cây cú pháp trừu tượng hoặc cấu trúc phân cấp khác — đưa ra biểu diễn cấu trúc của đầu vào, kiểm tra cú pháp chính xác trong quy trình . Việc phân tích cú pháp có thể được thực hiện trước hoặc sau các bước khác hoặc các bước này có thể được kết hợp thành một bước duy nhất. Trình phân tích cú pháp thường đi trước một bộ phân tích từ vựng riêng biệt, tạo ra các mã thông báo từ chuỗi các ký tự đầu vào

Vì vậy, về bản chất, đây là những gì chúng tôi đang cố gắng đạt được:

math expression => [parser] => some data structure (we'll get to this in a bit)

Hãy bỏ qua một chút: “… Trình phân tích cú pháp thường đi trước một bộ phân tích từ vựng riêng biệt, tạo mã thông báo từ chuỗi ký tự đầu vào”. Đây là nói về mã thông báo mà chúng tôi đã xây dựng trước đó. Vì vậy, trình phân tích cú pháp của chúng tôi sẽ không nhận được biểu thức toán học thô, mà là một mảng mã thông báo. Vì vậy, bây giờ, chúng tôi có:

math expression => [tokenizer] => list of tokens => [parser] => some data structure

Đối với mã thông báo, chúng tôi phải đưa ra thuật toán theo cách thủ công. Đối với trình phân tích cú pháp, chúng tôi sẽ triển khai một thuật toán hiện có, thuật toán Shunting-yard. Hãy nhớ “một số cấu trúc dữ liệu” ở trên? Với thuật toán này, trình phân tích cú pháp của chúng tôi có thể cung cấp cho chúng tôi cấu trúc dữ liệu được gọi là Cây cú pháp trừu tượng (AST) hoặc một biểu diễn thay thế của biểu thức, được gọi là Ký hiệu đánh bóng ngược (RPN).

Ký hiệu đảo ngược tiếng Ba Lan

Tôi sẽ bắt đầu với RPN. Một lần nữa từ Wikipedia, RPN là “một ký hiệu toán học trong đó mọi toán tử tuân theo tất cả các toán hạng của nó”. Thay vì có, giả sử, 3+4, RPN sẽ là 3 4 +. Thật kỳ lạ, tôi biết. Nhưng quy tắc là người điều hành phải đến sau đó tất cả các toán hạng của nó.

Hãy ghi nhớ quy tắc đó khi chúng ta xem xét một số ví dụ phức tạp hơn. Cũng nên nhớ rằng một toán hạng cho một thao tác có thể là kết quả của một thao tác trước đó).

Algebraic: 3 - 4                        RPN: 3 4 -

Algebraic: 3 - 4 + 5                    RPN: 3 4 - 5 +

Algebraic: 2^3                          RPN: 2 3 ^

Algebraic: 5 + ((1 + 2) × 4) − 3        RPN: 5 1 2 + 4 * + 3 -

Algebraic: sin(45)                      RPN: 45 sin

Algebraic: tan(x^2 + 2*x + 6)           RPN: x 2 ^ 2 x * + 6 + tan

Vì toán tử phải đứng sau toán hạng của nó nên RPN còn được gọi là ký hiệu hậu tốvà ký hiệu đại số “chính quy” của chúng ta được gọi là trung tố.

Làm thế nào để bạn đánh giá một biểu thức trong RPN? Có một thuật toán đơn giản tôi sử dụng:

Đọc tất cả các mã thông báo từ trái sang phải cho đến khi bạn đến Nhà điều hành hoặc Chức năng. Biết rằng Toán tử/Hàm nhận N đối số (ví dụ, cho +, N = 2; vì cos(), N = 1), đánh giá lần cuối N các đối số trước bằng Toán tử/Hàm và thay thế tất cả chúng (Toán tử/Hàm + toán hạng) bằng kết quả. Tiếp tục như trước, cho đến khi không còn Toán tử/Hàm nào để đọc. Mã thông báo (Chữ hoặc Biến) duy nhất còn lại là câu trả lời của bạn.

(Đây là một thuật toán được đơn giản hóa, giả định rằng biểu thức là hợp lệ. Một vài dấu hiệu cho thấy biểu thức không hợp lệ là nếu bạn còn nhiều hơn một mã thông báo ở cuối hoặc nếu mã thông báo cuối cùng còn lại là Toán tử/Hàm.)

Vì vậy, đối với một cái gì đó như 5 1 2 + 4 * + 3 −:

read 5read 1read 2read +. + is an operator which takes 2 args, so calculate 1+2 and replace with the result (3). The expression is now 5 3 4 * + 3 -read 4read *. * is an operator which takes two args, so calculate 3*4 and replace with the result, 12. The expression is reduced to 5 12 + 3 -read +. + is an operator which takes two args, so calculate 5+12, replace by the result, 17. Now, we have 17 3 -read 3read -. - is an operator which takes two args, so calculate 17-3. The result is 14.

Hy vọng bạn đã đạt điểm A trong khóa học cấp tốc nhỏ của tôi về RPN. Bạn đã làm? OK, chúng ta hãy tiếp tục.

Cây cú pháp trừu tượng

Định nghĩa của Wikipedia ở đây có thể không quá hữu ích đối với nhiều người trong chúng ta: “một biểu diễn dạng cây của cấu trúc cú pháp trừu tượng của mã nguồn được viết bằng ngôn ngữ lập trình.” Đối với trường hợp sử dụng này, chúng ta có thể coi AST là cấu trúc dữ liệu đại diện cho cấu trúc toán học của biểu thức. Điều này được nhìn thấy tốt hơn là nói, vì vậy hãy vẽ một sơ đồ sơ bộ. Tôi sẽ bắt đầu với một AST cho biểu thức đơn giản 3+4:

  [+] /   \[3] [4]

Mỗi [] đại diện cho một nút trong cây. Vì vậy, bạn có thể thấy trong nháy mắt rằng hai mã thông báo được kết hợp với nhau bằng toán tử +.

Một biểu thức phức tạp hơn, 5 + ((1 + 2) * 4) − 3:

           [-]          /   \        [+]    \___[3]          /  \ [5]__/   [*]         /   \        [+]  [4]       /   \       [1]  [2]

Ah, một cây cú pháp nhỏ đáng yêu. Nó liên kết tất cả các mã thông báo và toán tử một cách hoàn hảo. Bạn có thể thấy rằng việc đánh giá biểu thức này dễ dàng hơn nhiều — chỉ cần đi theo cái cây.

Vậy, tại sao AST lại hữu ích? Nó giúp bạn biểu diễn logic và cấu trúc của biểu thức một cách chính xác, giúp đánh giá biểu thức dễ dàng hơn. Chẳng hạn, để đánh giá biểu thức trên, trên phần phụ trợ của chúng tôi, chúng tôi có thể làm điều gì đó như thế này:

result = binaryoperation(+, 1, 2)result = binaryoperation(*, result, 4)result = binaryoperation(+, 5, result)result = binaryoperation(-, result, 3)return result

Nói cách khác, đối với mỗi nút toán tử (hoặc chức năng) mà trình đánh giá/trình biên dịch/trình thông dịch gặp phải, nó sẽ kiểm tra xem có bao nhiêu nhánh và sau đó đánh giá kết quả của tất cả các nhánh đó với toán tử.

Được rồi, khóa học về sự cố đã kết thúc, giờ hãy quay lại trình phân tích cú pháp của chúng ta. Trình phân tích cú pháp của chúng tôi sẽ chuyển đổi biểu thức (được mã hóa) thành RPN và sau đó thành AST. Vì vậy, hãy bắt đầu thực hiện nó.

Thuật toán Shunting-yard

Đây là phiên bản RPN của thuật toán đầy đủ (từ người bạn Wikipedia của chúng tôi) và được sửa đổi để phù hợp với mã thông báo của chúng tôi:

Trong khi có các mã thông báo được đọc:

1. Đọc mã thông báo. Hãy gọi nó là t

2. Nếu t là một chữ hoặc biến, đẩy nó vào hàng đợi đầu ra.

3. Nếu t là một Hàm, hãy đẩy nó vào ngăn xếp.

4. Nếu t là Dấu phân cách đối số chức năng (dấu phẩy), bật các toán tử ra khỏi ngăn xếp vào hàng đợi đầu ra cho đến khi mã thông báo ở đầu ngăn xếp là Dấu ngoặc đơn trái.

5. Nếu t là một nhà điều hành:

một. trong khi có một mã thông báo Nhà điều hành o ở đầu ngăn toán tử và một trong hai t là liên kết trái và có mức độ ưu tiên nhỏ hơn hoặc bằng ohoặc t là liên kết đúng và có độ ưu tiên thấp hơn so với onhạc pop o ra khỏi ngăn toán tử, vào hàng đợi đầu ra;

b. ở cuối lần lặp đẩy t vào ngăn xếp toán tử.

6. Nếu mã thông báo là Dấu ngoặc đơn trái, hãy đẩy mã thông báo vào ngăn xếp.

7. Nếu mã thông báo là Dấu ngoặc đơn phải, bật các toán tử ra khỏi ngăn xếp vào hàng đợi đầu ra cho đến khi mã thông báo ở đầu ngăn xếp là một dấu ngoặc đơn bên trái. Sau đó bật dấu ngoặc đơn bên trái từ ngăn xếp, nhưng không vào hàng đợi đầu ra.

8. Nếu mã thông báo ở đầu ngăn xếp là Hàm, hãy đưa mã thông báo đó vào hàng đợi đầu ra.

Khi không còn mã thông báo nào để đọc, hãy đưa bất kỳ mã thông báo Người vận hành nào trên ngăn xếp vào hàng đợi đầu ra.

Lối ra.

(Lưu ý bên lề: trong trường hợp bạn đọc bài báo trước, tôi‘đã cập nhật danh sách các mã thông báo được công nhận để bao gồm Dấu phân cách đối số chức năng, hay còn gọi là dấu phẩy).

Thuật toán trên giả định rằng biểu thức là hợp lệ. Tôi đã làm nó theo cách này để nó dễ hiểu trong ngữ cảnh của một bài viết. Bạn có thể xem thuật toán đầy đủ trên Wikipedia.

Bạn sẽ quan sát một vài điều:

• Chúng ta cần hai cấu trúc dữ liệu: a cây rơm để giữ các hàm và toán tử, và một xếp hàng cho đầu ra. Nếu bạn không quen thuộc với hai cấu trúc dữ liệu này, thì đây là kiến ​​thức cơ bản dành cho bạn: nếu bạn muốn truy xuất một giá trị từ ngăn xếp, bạn bắt đầu với giá trị cuối cùng mà bạn đưa vào, trong khi đối với hàng đợi, bạn bắt đầu với giá trị đầu tiên bạn đưa vào. đưa vào.

// we'll use arrays to represent both of themvar outQueue=[];var opStack=[];

• Chúng ta cần biết những tính kết hợp của các nhà khai thác. Tính kết hợp đơn giản có nghĩa là một biểu thức chứa một số thao tác cùng loại được nhóm theo thứ tự nào mà không có dấu ngoặc đơn. Chẳng hạn, 2 + 3 + 4 được đánh giá theo quy tắc từ trái sang phải (2+ 3 = 5, sau đó 5 + 4 = 9), do đó + có tính kết hợp trái. So sánh với 2^3^4, được đánh giá là 2^81, không phải 8^4. Do đó ^ có tính kết hợp đúng. Chúng tôi sẽ đóng gói các liên kết của các toán tử gặp phải trong Javascriptobject:

var assoc = {  "^" : "right",  "*" : "left",  "/" : "left",  "+" : "left",  "-" : "left" };

• Chúng ta cũng cần biết những quyền ưu tiên của các nhà khai thác. Quyền ưu tiên là một loại xếp hạng được gán cho các toán tử, vì vậy chúng ta có thể biết thứ tự chúng sẽ được đánh giá nếu chúng xuất hiện trong cùng một biểu thức. Các toán tử có mức độ ưu tiên cao hơn sẽ được đánh giá trước. Chẳng hạn, * có mức độ ưu tiên cao hơn +, vì vậy 2 + 3 * 4 được đánh giá là 2 + 12 chứ không phải 5 * 4, trừ khi sử dụng dấu ngoặc đơn. + và – có cùng mức độ ưu tiên, vì vậy 3 + 5 – 2 có thể được đánh giá là 8–2 hoặc 3+3. Một lần nữa, chúng ta sẽ gói toán tử ưu tiên trong một đối tượng:

var prec = {  "^" : 4,  "*" : 3,  "/" : 3,  "+" : 2,  "-" : 2 };

Bây giờ, hãy cập nhật của chúng tôi Token class để chúng ta có thể dễ dàng truy cập mức độ ưu tiên và tính kết hợp thông qua các phương thức:

Token.prototype.precedence = function() {  return prec[this.value]; };  Token.prototype.associativity = function() {  return assoc[this.value]; };

• Chúng ta cần một phương pháp cho phép chúng ta nhìn trộm tại ngăn xếp (để kiểm tra phần tử ở trên cùng mà không cần xóa nó) và phần tử cho phép chúng tôi nhạc pop khỏi ngăn xếp (lấy và loại bỏ mục ở trên cùng). May mắn thay, các mảng Javascript đã có một pop() phương pháp, vì vậy tất cả những gì chúng ta cần làm là triển khai một peek() phương pháp. (Hãy nhớ rằng, đối với ngăn xếp, phần tử ở trên cùng là phần tử mà chúng ta đã thêm vào cuối cùng.)

Array.prototype.peek = function() {  return this.slice(-1)[0]; //retrieve the last element of the array };

Vì vậy, đây là những gì chúng ta có:

function tokenize(expr) {  ...   // just paste the tokenizer code here}

function parse(inp){ var outQueue=[]; var opStack=[];

Array.prototype.peek = function() {  return this.slice(-1)[0]; };

var assoc = {  "^" : "right",  "*" : "left",  "/" : "left",  "+" : "left",  "-" : "left" };

var prec = {  "^" : 4,  "*" : 3,  "/" : 3,  "+" : 2,  "-" : 2 };

Token.prototype.precedence = function() {  return prec[this.value]; };  Token.prototype.associativity = function() {  return assoc[this.value]; };

 //tokenize var tokens=tokenize(inp);

 tokens.forEach(function(v) {   ...   //apply the algorithm here });

 return outQueue.concat(opStack.reverse());  // list of tokens in RPN}

Tôi sẽ không đi sâu vào việc triển khai thuật toán nên tôi không làm phiền bạn. Đó là một nhiệm vụ khá đơn giản, thực tế là dịch từng từ của thuật toán sang mã, vì vậy, vào cuối ngày, đây là những gì chúng tôi có:

Các toString chỉ đơn giản là định dạng danh sách mã thông báo RPN của chúng tôi ở định dạng có thể đọc được.

Và chúng ta có thể kiểm tra trình phân tích cú pháp infix-to-postfix:

var rpn = parse("3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3");console.log(toString(rpn));

Đầu ra:

3 4 2 * 1 5 - 2 3 ^ ^ / +

RPN!!

Đã đến lúc trồng cây

Bây giờ, hãy sửa đổi trình phân tích cú pháp của chúng ta để nó trả về AST.

Để tạo AST thay vì RPN, chúng tôi cần thực hiện một vài sửa đổi:

• Chúng tôi sẽ tạo một đối tượng để đại diện cho một nút trong AST của chúng tôi. Mỗi nút có một giá trị và hai nhánh (có thể là null):

function ASTNode(token, leftChildNode, rightChildNode) {   this.token = token.value;   this.leftChildNode = leftChildNode;   this.rightChildNode = rightChildNode;}

• Điều thứ hai chúng ta sẽ làm là thay đổi cấu trúc dữ liệu đầu ra thành ngăn xếp. Trong khi mã thực tế cho điều này chỉ là để thay đổi dòng var outQueue = [] đến var outStack = [] (vì nó vẫn là một mảng), sự thay đổi chính nằm ở cách chúng ta hiểu và xử lý mảng này.

Bây giờ, thuật toán infix-to-AST của chúng ta sẽ chạy như thế nào? Về cơ bản, cùng một thuật toán, với một vài sửa đổi:

1. Thay vì đẩy mã thông báo Nghĩa đen hoặc Biến đổi lên outQueuechúng tôi đẩy một nút mới có giá trị là mã thông báo và có các nhánh là null lên của chúng tôi outStack
2. Thay vì bật mã thông báo Toán tử/Chức năng từ opStack chúng tôi thay thế hai nút trên cùng trên outStack với một nút duy nhất có giá trị là mã thông báo và có hai nút đó làm nhánh của nó. Hãy tạo một hàm thực hiện điều đó:

Array.prototype.addNode = function (operatorToken) {  rightChildNode = this.pop();  leftChildNode = this.pop();  this.push(new ASTNode(operatorToken, leftChildNode, rightChildNode)); }

3. Trình phân tích cú pháp của chúng tôi bây giờ sẽ trả về một nút duy nhất, nút ở đầu AST của chúng tôi. Hai nhánh của nó sẽ chứa hai nút con, các nhánh của chúng sẽ chứa các nút con của chúng, v.v., theo cách đệ quy. Chẳng hạn, đối với một biểu thức như 3 + 4 * 2 / ( 1–5 ) ^ 2 ^ 3, chúng ta mong muốn cấu trúc của nút đầu ra sẽ như thế này (ở dạng nằm ngang):

+ => 3 => null       => null  => / => * => 4 => null                 => null            => 2 => null                 => null       => ^ => - => 1 => null                      => null                 => 5 => null                      => null            => ^ => 2 => null                      => null                 => 3 => null                      => null

Trong sơ đồ trên, dấu => đại diện cho các nhánh của nút (nút trên cùng là nhánh trái, nút dưới cùng là nhánh phải). Mỗi nút có hai nhánh và các nút ở cuối cây có hướng của chúng to nuể oải

Vì vậy, nếu chúng ta đặt tất cả những thứ này lại với nhau, đây là mã chúng ta nghĩ ra:

Và nếu chúng tôi demo nó:

//a little hack I put together so it prints out in a readable formASTNode.prototype.toString = function(count) {   if (!this.leftChildNode && !this.rightChildNode)     return this.token + "\t=>null\n" + Array(count+1).join("\t") + "=>null";   var count = count || 1;   count++;   return this.token + "\t=>" + this.leftChildNode.toString(count) + "\n" + Array(count).join("\t") + "=>" + this.rightChildNode.toString(count);};

var ast = parse("3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3");console.log("" + ast);

Và kết quả:

Dần dần, nhưng chắc chắn, chúng ta đang tiến gần hơn đến việc hiểu điều gì khiến trình biên dịch và trình thông dịch đánh dấu! Phải thừa nhận rằng hoạt động của các ngôn ngữ lập trình hiện đại và bộ công cụ của chúng phức tạp hơn nhiều so với những gì chúng ta đã xem xét cho đến nay, nhưng tôi hy vọng đây là phần giới thiệu dễ hiểu về chúng. Như một số người đã chỉ ra, tồn tại các công cụ để tự động tạo mã thông báo và trình phân tích cú pháp, nhưng thật tuyệt khi biết một thứ thực sự hoạt động như thế nào.

Các khái niệm chúng tôi đề cập trong bài viết này và trước đó là những chủ đề rất thú vị trong lĩnh vực khoa học máy tính và lý thuyết ngôn ngữ. Tôi vẫn còn nhiều điều để tìm hiểu về chúng, và tôi khuyến khích bạn tiếp tục và nghiên cứu chúng nếu bạn quan tâm. Và gửi cho tôi một dòng để cho tôi biết về sự tiến bộ của bạn. Hòa bình!