Cây cú pháp trừu tượng trong lập trình: hướng dẫn đầy đủ

Informatec Digital » Recursos » Cây cú pháp trừu tượng trong lập trình: hướng dẫn đầy đủ

Cây cú pháp trừu tượng trong lập trình là một trong những khái niệm ban đầu nghe có vẻ rất lý thuyết, nhưng một khi bạn hiểu được chúng, bạn sẽ nhận ra chúng có mặt ở khắp mọi nơi: trình biên dịch, trình thông dịch , phân tích mã, công cụ tái cấu trúc, thậm chí cả trong ngôn ngữ truy vấn dữ liệu có cấu trúc. Về bản chất, chúng là cách mà máy tính "hiểu" cấu trúc của một chương trình vượt ra ngoài văn bản thuần túy.

Mặc dù đôi khi bị nhầm lẫn với cây phân tích cú pháp cổ điển, cây cú pháp trừu tượng (AST) có những quy tắc riêng. Cây cú pháp trừu tượng không chỉ là một hình vẽ đẹp mắt: đó là một cấu trúc dữ liệu nhỏ gọn và được thiết kế tốt, loại bỏ mọi thứ thừa thãi khỏi cú pháp cụ thể (dấu ngoặc đơn, dấu phẩy, từ khóa dư thừa, v.v.) và tập trung vào những yếu tố thiết yếu: các thao tác nào được thực hiện, trên những giá trị nào và theo thứ tự nào.

Cây cú pháp trừu tượng (AST) thực chất là gì?

Trong lý thuyết ngôn ngữ lập trình, cây cú pháp trừu tượng (AST) là một cấu trúc dạng cây biểu diễn cú pháp của chương trình, nhưng ở dạng đơn giản hơn so với cây phân tích cú pháp cụ thể. Nó chứa cùng những thông tin thiết yếu như cây phân tích cú pháp, nhưng được tổ chức theo cách gọn gàng và dễ quản lý hơn.

Cây phân tích cú pháp chứa tất cả các quy tắc ngữ pháp và tất cả các ký hiệu cuối cùng, bao gồm dấu ngoặc đơn, dấu phẩy, dấu chấm phẩy và các yếu tố cú pháp thuần túy khác. Mặt khác, cây cú pháp trừu tượng (AST) loại bỏ những chi tiết không đóng góp vào ý nghĩa ngữ nghĩa và chỉ giữ lại cấu trúc logic của các biểu thức và câu.

Về mặt triển khai, cây cú pháp trừu tượng (AST) thường được tạo thành từ các đối tượng nút với một kiểu dữ liệu chỉ ra loại cấu trúc cú pháp mà nó đại diện (hằng số, định danh, ứng dụng hàm, toán tử nhị phân, v.v.), và các thuộc tính bổ sung mô tả nội dung của nó: giá trị, tên, các phần tử con, danh sách đối số, v.v.

Ưu điểm của cây cú pháp trừu tượng (AST) là nó tạo điều kiện thuận lợi cho các giai đoạn sau của trình biên dịch hoặc trình thông dịch, chẳng hạn như kiểm tra kiểu dữ liệu, tối ưu hóa hoặc tạo mã , bởi vì nó cung cấp một cái nhìn rõ ràng về cấu trúc chương trình mà không có sự nhiễu loạn cú pháp.

Sự khác biệt giữa cây cú pháp cụ thể và cây cú pháp trừu tượng

Để hiểu đầy đủ những đóng góp của AST, trước tiên cần so sánh cây phân tích cú pháp cụ thể với cây phân tích cú pháp trừu tượng. Hãy tưởng tượng một ngữ pháp đơn giản nhận dạng các biểu thức số học như "a + 4 * 5" . Cây phân tích cú pháp cụ thể phản ánh chính xác việc áp dụng từng quy tắc ngữ pháp: ký hiệu không kết thúc, ký hiệu kết thúc, dấu ngoặc đơn, toán tử, v.v.

Cây cú pháp này thường sâu và có nhiều nút trung gian chỉ dùng để duy trì cấu trúc hình thức của ngữ pháp. Ví dụ, có thể có các nút cho "Biểu thức", "Thuật ngữ", "Yếu tố", và sau đó là các ký hiệu đầu cuối như "+" , "*" , định danh và số. Mỗi quy tắc sản sinh trở thành một nhánh của cây, làm tăng độ phức tạp về cấu trúc.

Mặt khác, cây cú pháp trừu tượng cho cùng một biểu thức đó lại chỉ giới hạn ở việc biểu diễn các phép toán và toán hạng thực tế . Do đó, thay vì nhiều cấp độ "Biểu thức" và "Thuật ngữ", ta có thể có một nút gốc biểu diễn phép cộng, với hai nút con: bên trái là một định danh a và bên phải là một nút phép nhân có các nút con là các giá trị 4 và 5. Các nút thuần túy ngữ pháp biến mất và các phần của cấu trúc được sắp xếp lại hoặc thu gọn.

Điều này có nghĩa là AST và cây cú pháp cụ thể chứa cùng một thông tin ngữ nghĩa , nhưng AST trình bày thông tin đó một cách trực tiếp và cô đọng hơn nhiều. Sự cô đọng này là chìa khóa để làm việc hiệu quả với mã nguồn trong các công cụ phân tích hoặc thực thi.

Cây và bảng chữ cái với hàm arity

Để hình thức hóa các cây này từ quan điểm toán học, người ta thường sử dụng ý tưởng về một bảng chữ cái với hàm số bậc . Thay vì chỉ đơn giản là một tập hợp các ký hiệu, một bảng chữ cái được định nghĩa trong đó mỗi ký hiệu được liên kết với một số cho biết nó có thể có bao nhiêu nhánh con trong cây.

Theo cách hiểu không chính thức, bảng chữ cái với hàm gán bậc (arity function) là một cặp gồm một tập hợp hữu hạn các ký hiệu và một hàm gán cho mỗi ký hiệu một số tự nhiên (bao gồm cả số 0). Số này cho biết bậc của ký hiệu: nếu là 0, ký hiệu hoạt động như một nút lá; nếu là 1, nó hoạt động như một nút đơn; nếu là 2, nó là nút nhị phân; và cứ thế tiếp tục. Người ta cũng thường cho phép các ký hiệu có bậc thay đổi được sử dụng làm danh sách đối số cho các toán tử.

Các ký hiệu có bậc 0 tương ứng với các nút lá của cây (ví dụ: hằng số hoặc định danh). Các ký hiệu có bậc 1 được sử dụng cho các cấu trúc liên quan đến một biểu thức con duy nhất. Các ký hiệu có bậc 2 biểu diễn các phép toán nhị phân cổ điển như cộng, nhân, gán, v.v. Và các ký hiệu có bậc biến đổi cho phép mô hình hóa các cấu trúc chấp nhận một số lượng cây con không xác định, chẳng hạn như một lời gọi hàm với nhiều tham số.

Từ bảng chữ cái có bậc này, tập hợp tất cả các cây có thể được định nghĩa: bắt đầu với cây rỗng (khi được xem xét), thêm tất cả các ký hiệu có bậc 0 và biến đổi, và mở rộng theo phương pháp quy nạp: nếu một ký hiệu là k-ary, nó có thể được đặt làm nút cha của k cây con đã được xây dựng. Điều này tạo ra ngôn ngữ cây (hoặc thuật ngữ) liên kết với bảng chữ cái.

Ngôn ngữ cây và khái niệm về nút

Tập hợp tất cả các cây được tạo thành từ một bảng chữ cái và hàm số lượng tham số của nó được gọi, trong ngữ cảnh này, là ngôn ngữ cây hoặc ngôn ngữ thuật ngữ . Nó tương đương, nhưng dành cho cấu trúc cây, với cái mà bao đóng Kleene dành cho chuỗi ký tự.

Cũng giống như khi phân tích chuỗi ký tự, chúng ta sử dụng thuật ngữ " token" để chỉ sự xuất hiện của các ký hiệu chữ cái trong một chuỗi, khi làm việc với cây, chúng ta thường sử dụng thuật ngữ " nút" . Về cơ bản, một nút là một sự xuất hiện cụ thể của một ký hiệu chữ cái với số lượng tham số nhất định, nằm ở một vị trí cụ thể trong cây.

Từ góc nhìn này, ngôn ngữ cây này đối với các nút cũng giống như một tập hợp các chuỗi ký tự đối với các lần xuất hiện của token. Mỗi cây được hiểu là một cấu trúc được xây dựng từng bước từ bảng chữ cái, và các nút là các mảnh riêng lẻ hiện thực hóa các ký hiệu của nó về mặt vật lý.

Cách nhìn nhận này rất hữu ích khi thiết kế trình phân tích cú pháp và trình tạo cây cú pháp trừu tượng (AST) , bởi vì nó cho phép suy luận về các quy tắc xây dựng của các cây này theo cách tương tự như ngữ pháp chuỗi, nhưng hoạt động trực tiếp trên các cấu trúc phân cấp.

Độ đa dạng của các nút trong một cây cú pháp trừu tượng (AST) cụ thể: trường hợp của Egg

Từ lý thuyết chuyển sang ví dụ thực tiễn, nhiều tài liệu giảng dạy sử dụng ngôn ngữ Egg để minh họa việc xây dựng và thao tác với cây cú pháp trừu tượng (AST). Trong ngữ cảnh này, một số loại nút chính được sử dụng, mỗi loại có số lượng tham số được xác định rõ ràng , giúp việc thao tác với chúng trở nên rất dễ dàng.

Trong một cây cú pháp trừu tượng (AST) điển hình của Egg, các nút VALUE được coi là lá: chúng đại diện cho các giá trị cố định như chuỗi ký tự hoặc số. Chúng không có con; chúng chỉ lưu trữ một giá trị. Tương tự, các nút WORD , được sử dụng cho các định danh (tên biến, tên hàm, v.v.), cũng được coi là lá với một thuộc tính lưu trữ tên.

Nút quan trọng nhất trong Egg là kiểu APPLY , đại diện cho việc áp dụng một hàm hoặc toán tử. Kiểu nút này có hai nút con về mặt khái niệm: một nút con OPERATOR trỏ đến biểu thức được áp dụng; và một nút con ARGS , thực chất là một nút ARRAY đặc biệt chịu trách nhiệm duy trì một tập hợp các cây con, mỗi cây con tương ứng với một đối số.

Do đó, mảng là một cách tự nhiên để đưa số lượng tham số thay đổi vào AST: một lệnh APPLY luôn có hai thành phần (toán tử và danh sách tham số), nhưng danh sách bên trong đó có thể chứa không, một hoặc nhiều cây con tùy thuộc vào lệnh gọi cụ thể đang được biểu diễn.

Cấu trúc giải phẫu chi tiết của các hạch AST trong trứng

Ở cấp độ triển khai, các nút AST của Egg thường được biểu diễn dưới dạng các đối tượng có thuộc tính , điều này hoàn toàn phù hợp với các ngôn ngữ như JavaScript. Tất cả các nút đều có chung một thuộc tính: `type` , dùng để xác định loại nút (VALUE, WORD, APPLY, ARRAY, v.v.) và do đó, cấu trúc mà phần còn lại của đối tượng sẽ có.

Các nút VALUE được sử dụng cho các hằng số cố định . Chúng chứa một thuộc tính, thường được gọi là giá trị , nơi lưu trữ số hoặc chuỗi mà chúng đại diện. Chúng không có các nút con bổ sung vì nội dung của chúng được mô tả hoàn toàn bởi hằng số đó.

Các nút kiểu "từ" được dành riêng cho các định danh : tên biến, tên hàm, tên tham số, v.v. Chúng thường có thuộc tính `name` lưu trữ định danh dưới dạng chuỗi. Tương tự như các nút kiểu "giá trị", chúng hoạt động như các lá trong cây, vì mục đích duy nhất của chúng là cung cấp tên đó.

Các nút Apply đại diện cho các ứng dụng hoặc lời gọi hàm. Chúng bao gồm một thuộc tính operator , trỏ đến biểu thức (một nút khác) đang được áp dụng, và một thuộc tính args , liên kết đến một nút ARRAY. Nút ARRAY là một nút cụ thể trong AST, có mục đích là chứa danh sách đối số của ứng dụng .

Nút ARRAY có thể được hiểu như một vùng chứa có cấu trúc cho các nút khác, đại diện cho một chuỗi các cây con. Từ góc độ số lượng tham số, nó mang lại tính linh hoạt vì cho phép gọi hàm không có tham số, với một tham số hoặc với nhiều tham số trong cùng một câu lệnh APPLY mà không cần phải thay đổi định nghĩa của kiểu nút chính.

Ví dụ về AST: ứng dụng đơn giản với một giá trị

Để hình dung tất cả những điều trên, hãy nghĩ về cách biểu diễn một lệnh đơn giản, chẳng hạn như việc áp dụng một hàm X với một đối số duy nhất là 5. Cây cú pháp trừu tượng (AST) do trình phân tích cú pháp tạo ra tương ứng với một thuật ngữ được xây dựng bằng các nút VALUE, WORD và APPLY , tuân theo các quy tắc của Egg.

Về mặt khái niệm, chúng ta sẽ có một nút APPLY ở gốc. Thuộc tính operator của nó sẽ trỏ đến một nút WORD có tên là X, và thuộc tính args của nó sẽ tham chiếu đến một nút ARRAY chứa một phần tử duy nhất: một nút VALUE với giá trị số là 5. Bằng cách này, cấu trúc phản ánh rõ ràng đối tượng được áp dụng và đối tượng được áp dụng.

Nếu muốn làm rõ tất cả các thuộc tính, chúng ta có thể viết một ký hiệu chi tiết hơn thể hiện kiểu dữ liệu, toán tử, đối số, tên và giá trị. Ký hiệu chi tiết hơn này rất hữu ích cho việc gỡ lỗi trình phân tích cú pháp hoặc để hiểu cách một biểu thức văn bản được dịch thành một đối tượng cây trong trình thông dịch.

Trong các triển khai thực tế, cây này thường được tuần tự hóa thành JSON để dễ dàng lưu trữ, truyền tải hoặc kiểm tra. Trên thực tế, các công cụ và mô-đun, chẳng hạn như gói evm2term trong hệ sinh thái npm, cung cấp các biểu diễn nhỏ gọn của các AST này để dễ dàng phân tích hoặc chuyển đổi.

Ví dụ về AST: phép cộng và phép nhân lồng nhau

Một trường hợp điển hình khác là biểu thức phức tạp hơn một chút, chẳng hạn như "+(a, *(4, 5))" . Ở đây, ta có một phép cộng mà đối số đầu tiên là định danh a và đối số thứ hai là kết quả của phép nhân 4 với 5. Cây cú pháp trừu tượng (AST) thu được từ biểu thức này phản ánh cấu trúc lồng nhau đó.

Ở gốc của cây, chúng ta sẽ lại có một nút APPLY đại diện cho phép cộng. Toán tử của nó sẽ là một nút WORD có tên là "+", trong khi các đối số của nó sẽ nằm trong một nút ARRAY với hai phần tử: phần tử đầu tiên là một WORD có tên là "a"; phần tử thứ hai là một nút APPLY khác đại diện cho phép nhân.

Lệnh APPLY thứ hai sẽ có toán tử là một WORD có tên là "*" và các đối số là một MẢNG với hai nút VALUE: một nút có giá trị là 4 và nút kia có giá trị là 5. Nhìn tổng thể, cấu trúc cho thấy rõ ràng thứ tự đánh giá bao gồm việc nhân 4 với 5 rồi cộng kết quả đó với a.

Nếu mở rộng ký hiệu để bao gồm tất cả các thuộc tính, ta sẽ thấy kiểu dữ liệu của tất cả các nút, tên hoặc giá trị cụ thể của chúng, và mối quan hệ giữa chúng. Mô tả rõ ràng này tương ứng với cách triển khai thực tế trong trình thông dịch Egg, trong đó mỗi nút là một đối tượng với các thuộc tính đã đề cập ở trên.

Ngữ pháp cây và ngữ pháp máy phân tích cú pháp

Cách thức tạo ra các cây cú pháp trừu tượng (AST) này không phải là tùy ý: nó dựa trên cái gọi là Ngữ pháp Cây . Trong một công thức điển hình, ngữ pháp như vậy được định nghĩa là một bộ bốn phần tử bao gồm một bảng chữ cái có bậc, một tập hợp hữu hạn các biến cú pháp (phi thiết bị đầu cuối), một tập hợp hữu hạn các quy tắc sản xuất và một ký hiệu bắt đầu.

Trong mỗi quy tắc sản xuất, một biến được thay thế bằng một cây có gốc là một ký hiệu của bảng chữ cái với số lượng tham số nhất định, và các con của cây lần lượt là các biến hoặc các cây đã được định nghĩa trước đó. Cấu trúc này gợi nhớ đến các ngữ pháp chính quy hoặc ngữ pháp phi ngữ cảnh cổ điển, nhưng được điều chỉnh để tạo ra trực tiếp các cây thay vì các chuỗi ký hiệu.

Liên quan đến định nghĩa chính thức hơn đó là ngữ pháp cụ thể mà trình phân tích cú pháp của Egg sử dụng để tạo ra các cây. Ngữ pháp này, thường được trình bày một cách không chính thức trong tài liệu, mô tả chính xác những tổ hợp từ khóa, toán tử, dấu ngoặc đơn, v.v. nào được chấp nhận trong ngôn ngữ và cách chúng được chuyển đổi thành các nút thuộc loại VALUE, WORD, APPLY và ARRAY.

Ngữ pháp cây này có thể được xem như một trường hợp đặc biệt của cái được biết đến trong tài liệu là Ngữ pháp cây chính quy . Ý tưởng là có các quy tắc được xác định rõ ràng để chuyển đổi một chuỗi các token đầu vào thành một cây cú pháp trừu tượng (AST) có cấu trúc, sau đó có thể được diễn giải hoặc biên dịch.

Ký hiệu Dewey: tọa độ trong cây

Khi đã có cây cú pháp trừu tượng (AST), chúng ta thường cần tham chiếu đến các cây con cụ thể : ví dụ, đối số thứ hai của một hàm, toán tử của một biểu thức, v.v. Một cách rất thanh lịch để làm điều này là sử dụng ký hiệu thập phân Dewey, mượn sơ đồ được sử dụng để đánh số các phần và tiểu phần trong tài liệu.

Trong ký hiệu này, bắt đầu từ một cây t, một cây con được biểu thị bằng một chuỗi các số được phân tách bởi dấu chấm . Mỗi số chỉ ra vị trí của một nút con (thường bắt đầu từ 1) và chuỗi này đi xuống cây. Do đó, một biểu thức như t/2.1.3 đề cập đến nút con thứ ba của nút con đầu tiên của nút con thứ hai của t.

Định nghĩa quy nạp của ký hiệu này rất đơn giản: chuỗi rỗng biểu thị toàn bộ cây; nếu một chuỗi gồm một số theo sau là nhiều số khác được phân tách bởi dấu chấm, nó được diễn giải bằng cách trước tiên lấy cây con tương ứng với chỉ số được chỉ định và sau đó áp dụng cùng một logic một cách đệ quy cho phần còn lại của chuỗi.

Ví dụ, nếu ta có một cây t biểu diễn một biểu thức như "+(a, *(4,5))", với nút gốc APPLY cho phép cộng, một nút con WORD có tên là "+", và một nút con APPLY khác cho phép nhân, ta có thể xác định các vị trí cụ thể. Do đó, t/1 có thể là nút WORD với toán tử "+", t/2.1 là định danh "a", và t/2.2.2.1 là nút VALUE với giá trị 4, nếu ta đánh số các nút con một cách thích hợp.

Cách thức cung cấp "tọa độ" trong cây cú pháp trừu tượng (AST) này rất hữu ích để chỉ ra các vị trí cụ thể khi báo cáo lỗi, điều hướng cây hoặc áp dụng các phép biến đổi cục bộ cho các nút cụ thể mà không gây nhầm lẫn.

Các ký hiệu tương đương trong lập trình và công cụ

Ý tưởng đằng sau ký hiệu Dewey không chỉ giới hạn trong lý thuyết cây; trên thực tế, nó xuất hiện nhiều lần trong nhiều ký hiệu thực tiễn mà chúng ta sử dụng hàng ngày trong lập trình và xử lý dữ liệu có cấu trúc, ngay cả khi chúng ta không phải lúc nào cũng nhận thức được điều đó.

Khi chúng ta viết các biểu thức với toán tử dấu chấm trong ngôn ngữ lập trình , chẳng hạn như object.property.subproperty, chúng ta đang thực hiện một việc rất tương tự: duyệt qua một cây các đối tượng lồng nhau, chọn một phần tử con ở mỗi bước theo tên thay vì theo số thứ tự vị trí. Bắt đầu từ nút gốc, chúng ta đi xuống các nút bên trong hơn.

Mẫu tương tự cũng xuất hiện trong các hệ thống tệp giống Unix, nơi toán tử dấu gạch chéo (/) được sử dụng để phân tách các thư mục: /src/js/tutu.js mô tả đường dẫn từ thư mục gốc của hệ thống tệp đến một tài nguyên cụ thể, đi qua các cấp độ liên tiếp của cấu trúc cây.

Trong thế giới của các tài liệu có cấu trúc, các ngôn ngữ như XPath sử dụng các ký hiệu rất giống nhau để chọn các nút trong cây XML. Một truy vấn như "A//B/*" sẽ chọn phần tử con đầu tiên (bất kể tên của nó là gì) của mọi phần tử B là hậu duệ của phần tử A ở vị trí thích hợp so với ngữ cảnh hiện tại, sử dụng dấu gạch chéo đơn và kép để chỉ ra các cấp độ sâu.

Một công cụ nổi tiếng khác, ngôn ngữ jq , sử dụng hệ thống song song để điều hướng cấu trúc JSON, cho phép chọn các đối tượng con thông qua các đường dẫn phức hợp, bộ lọc và biểu thức. Tất cả các ký hiệu này chỉ đơn giản là những cách khác nhau để thể hiện các đường dẫn trong một cây , rất phù hợp với ký hiệu Dewey Decimal nhưng được điều chỉnh cho các lĩnh vực tương ứng của chúng.

Cây phân tích cú pháp trong ngôn ngữ học và lập trình.

Ngoài lĩnh vực trình biên dịch, cây cú pháp còn được sử dụng trong ngôn ngữ học để biểu diễn cấu trúc câu. Ở đó, chúng được gọi là cây dẫn xuất hoặc cây phân tích cú pháp, cho thấy cách một câu được phân tách thành các cụm từ, từ và phạm trù ngữ pháp.

Trong các cây này, cũng giống như trong lập trình, chúng ta tìm thấy ba loại nút cơ bản: nút gốc , đại diện cho toàn bộ câu hoặc cấu trúc tổng thể; các nút bên trong hoặc nút phân nhánh, hoạt động như các nút cha và nhóm các tập con của câu; và các nút lá, thường tương ứng với các từ cụ thể xuất hiện trong chuỗi đầu vào.

Nút gốc là duy nhất: toàn bộ cấu trúc cây đều bắt nguồn từ nó. Các nút nhánh nằm ngay bên dưới nút gốc hoặc các nút cha khác, và có chức năng tổ chức thứ bậc các phần của câu hoặc chương trình. Mặt khác, các nút lá nằm ở cấp thấp nhất của cây và không có nút con, do đó khép kín cấu trúc phân nhánh.

Các cây cú pháp trừu tượng (AST) được coi là công cụ sư phạm mạnh mẽ vì chúng giúp phân tích các câu phức tạp thành các yếu tố dễ quản lý. Điều tương tự cũng áp dụng cho lập trình: một AST được xây dựng tốt cho phép bạn dễ dàng nhận thấy các thao tác nào được xâu chuỗi với nhau, biểu thức nào được lồng nhau và quá trình đánh giá diễn ra như thế nào.

Tùy thuộc vào mục tiêu phân tích, chúng ta có thể tìm thấy các loại cây phân tích khác nhau . Một số nhấn mạnh mối quan hệ phụ thuộc giữa các từ hoặc thành phần (ví dụ: ai phụ thuộc vào ai trong câu), trong khi những loại khác tập trung vào việc nhóm các từ hoặc thành phần lại với nhau, dẫn đến hai nhóm chính.

Cây cú pháp theo sự phụ thuộc và theo thành phần.

Một trong những loại nổi tiếng nhất là cây cú pháp dựa trên sự phụ thuộc . Trong biến thể này, tất cả các từ trong câu hoặc tất cả các yếu tố liên quan được coi là các nút lá, và các liên kết giữa chúng biểu thị các mối quan hệ phụ thuộc trực tiếp (ví dụ: động từ chính và chủ ngữ của nó). Kết quả là, cây thường có ít nút hơn so với các sơ đồ khác.

Sự đơn giản này khiến chúng đặc biệt thuận tiện cho người mới bắt đầu và cho một số tác vụ xử lý ngôn ngữ nhất định, bởi vì cấu trúc tập trung vào mối quan hệ phụ thuộc lẫn nhau mà không cần đưa ra quá nhiều nút trung gian. Áp dụng vào lập trình, ý tưởng là chỉ bám sát các mối quan hệ thiết yếu, bỏ qua các yếu tố ngữ pháp rườm rà.

Ở thái cực khác, chúng ta có cây cú pháp dựa trên thành phần hoặc các thành phần cấu tạo, phân biệt giữa các nút gốc, các nút phân nhánh bên trong và các nút lá, đồng thời hiển thị tất cả các nhóm liên quan. Những cây này thường chứa nhiều nút hơn và phản ánh cấu trúc phân cấp của câu hoặc chương trình một cách chi tiết hơn.

Các mẫu cây cấu trúc thường thấy hiển thị các câu dài với nhiều nút lá, nhiều cấp độ phân nhánh và một nút gốc được xác định rõ ràng. Chúng đặc biệt hữu ích để phân tích các câu phức tạp hoặc các chương trình có nhiều lớp cấu trúc lồng nhau.

Cả sơ đồ cây phụ thuộc và sơ đồ cây thành phần đều có sẵn các ví dụ và tài nguyên trực quan dưới dạng mẫu, cho phép bạn dễ dàng điền thông tin mong muốn vào các nút. Điều này giúp tiết kiệm thời gian và tránh phải thiết kế lại sơ đồ từ đầu mỗi khi bạn muốn minh họa một cấu trúc.

Các ứng dụng và công cụ thực tiễn liên quan đến AST

Cây cú pháp trừu tượng (AST) không chỉ là một khái niệm lý thuyết: chúng được sử dụng rộng rãi trong vô số công cụ hàng ngày bởi bất kỳ ai làm việc với mã nguồn. Trình biên dịch, trình thông dịch, trình thu nhỏ mã, trình định dạng mã và trình phân tích tĩnh hầu như luôn dựa vào AST để thực hiện chức năng của chúng.

Một trình biên dịch điển hình sẽ nhận mã nguồn, phân tách nó thành các token, phân tích cú pháp và tạo ra cây cú pháp trừu tượng. Từ đó, nó thực hiện kiểm tra ngữ nghĩa (kiểu dữ liệu, phạm vi biến, sử dụng sai cấu trúc) và áp dụng tối ưu hóa mã bằng cách duyệt và biến đổi cây cú pháp trừu tượng trước khi tạo ra mã máy, hay mã byte.

Các công cụ như linter hoặc formatter cũng hoạt động trên AST: chúng phân tích cấu trúc để phát hiện các mẫu có vấn đề, các thực tiễn xấu hoặc sự không nhất quán và đề xuất các thay đổi duy trì cấu trúc ngữ nghĩa của cây nhưng điều chỉnh cách trình bày mã.

Ví dụ, trong hệ sinh thái JavaScript, có nhiều thư viện cung cấp cây cú pháp trừu tượng (AST) ở định dạng JSON, giúp các công cụ khác dễ dàng dựa vào đó để thực hiện tái cấu trúc, tạo tài liệu tự động hoặc tạo hình ảnh trực quan về cấu trúc của các chương trình phức tạp.

Ngay cả trong những lĩnh vực chuyên biệt hơn, chẳng hạn như công cụ đo lường độ phủ kiểm thử hoặc chuyển đổi mã nguồn sang các ngôn ngữ khác, AST vẫn là nền tảng mà nhiều giải pháp hiện đại dựa trên đó, vì nó cho phép làm việc ở mức độ trừu tượng rất thuận lợi giữa văn bản thô và mã máy.

Nhìn chung, cây cú pháp trừu tượng là mảnh ghép quan trọng kết nối ngữ pháp hình thức của một ngôn ngữ, biểu diễn nội bộ của nó trong trình biên dịch hoặc trình thông dịch, và các công cụ tiên tiến mà chúng ta sử dụng để viết, phân tích và chuyển đổi mã một cách an toàn và hiệu quả. Hiểu được cách chúng được xây dựng, cách điều hướng chúng (với các khái niệm như ký hiệu thập phân Dewey), và các loại nút liên quan (VALUE, WORD, APPLY, cấu trúc có số lượng tham số cố định hoặc thay đổi, v.v.) giúp chúng ta thấy rõ hơn nhiều những gì máy thực sự đang làm khi xử lý một chương trình.