Ngày 3 - Ngữ pháp cho Bộ phân tích cú pháp

Chào mừng bạn trở lại! Hôm nay chúng ta sẽ khám phá một phần quan trọng trong quá trình phát triển trình thông dịch: Bộ phân tích cú pháp (Parser). Trong bài viết này, chúng ta sẽ tìm hiểu về ngữ pháp và cách mà bộ phân tích cú pháp hoạt động để tạo ra cây cú pháp từ các token được sinh ra từ Scanner.

Giới thiệu về Bộ phân tích cú pháp

Bộ phân tích cú pháp là giai đoạn thứ hai trong quá trình của trình thông dịch. Nó nhận các token từ Scanner và xây dựng một cây cú pháp dựa trên các quy tắc xác định trước - được gọi là Ngữ pháp miễn cưỡng (Context Free Grammar).

Ngữ pháp miễn cưỡng (CFG)

Ngữ pháp miễn cưỡng cho phép tạo ra các chuỗi mã phức tạp hơn so với ngôn ngữ thông thường, vì nó có khả năng xử lý các biểu thức lồng ghép một cách hiệu quả. Những quy tắc này sẽ giúp chúng ta định nghĩa cấu trúc của các biểu thức mà Bộ phân tích cú pháp sẽ xử lý.

Cấu trúc cây và quy tắc ngữ pháp

Khái niệm về cây và ngữ pháp

• Cây được tạo thành từ các nút, bao gồm các nút đầu (terminals) và nút không đầu (non-terminals).
• Scanner sẽ phát ra các token mà Bộ phân tích cú pháp sẽ tiêu thụ và nhóm theo các quy tắc của ngữ pháp để tạo ra các nút cho cây.
• Các literal (chuỗi/số) thường là các nút lá hoặc nút kết thúc, trong khi các toán tử là các nút bên trong.
• Quy tắc cũng có khả năng tham chiếu lại chính nó, cho phép tái hiện và từ đó tạo ra vô số khả năng.

Ví dụ về quy tắc

Giả sử chúng ta có một quy tắc đơn giản cho việc thư giãn:

• chilling → do activity;
• Chọn một quy tắc cho do, chẳng hạn: do → "watch";
• Thay thế do trong quy tắc ban đầu, ta có: chilling → "watch" activity;
• Tiếp tục với activity, ta chọn: activity → music; và cuối cùng là music → "piano";
• Kết hợp lại, ta có: chilling → "watch piano";

Ngữ pháp thực tế của Lox

Để thực hiện Bộ phân tích cú pháp cho ngôn ngữ Lox, chúng ta tạo một lớp cơ sở (hoặc quy tắc) gọi là Expr (biểu thức), tham chiếu đến các lớp con khác, và các lớp này có thể tham chiếu lại tới Expr. Điều này cho phép chúng ta xây dựng các biểu thức phức tạp hơn từ các biểu thức đơn giản hơn.

Tạo mã tự động với metaprogramming

Vì các lớp này sẽ có một mẫu tương tự, chúng ta có thể sử dụng metaprogramming để tạo mã tự động cho các lớp con. Dưới đây là một đoạn mã ví dụ:

// Định nghĩa cây biểu thức

defineAst(outputDir, "Expr", Arrays.asList(
     "Binary: Expr left, Token operator, Expr right",
     "Grouping: Expr expression",
     "Literal: Object value",
     "Unary: Token operator, Expr right"
));

Vấn đề về biểu thức

Vấn đề lớn trong lập trình

Khi làm việc với nhiều lớp con có hành vi tương tự (phương thức), chúng ta thường gặp phải vấn đề gọi là Vấn đề về biểu thức. Ví dụ, chúng ta có các lớp như Binary, Unary, Literal, v.v. và cần một số phương thức chung cho tất cả chúng.

Cách giải quyết

Một cách tiếp cận là thêm một phương thức in cho mỗi lớp con, tuy nhiên, điều này sẽ dẫn đến việc phải cập nhật mỗi lớp khi có phương thức mới. Một giải pháp khác là sử dụng một phương thức chung kiểm tra loại lớp con để thực hiện hành động tương ứng, nhưng điều này cũng không hiệu quả khi ta cần thêm loại mới.

Hành vi của các lớp - Nên như thế nào?

Các lớp Expr và các lớp con của nó nên chỉ là cấu trúc dữ liệu, không nên có bất kỳ hành vi nào. Điều này giúp chúng ta giữ nguyên nguyên tắc phân tách mối quan tâm, giúp mã dễ bảo trì và mở rộng.

Giải pháp: Mẫu thiết kế Visitor

Mẫu thiết kế Visitor là một phương pháp tiêu chuẩn để giải quyết Vấn đề về biểu thức trong các ngôn ngữ lập trình hướng đối tượng như Java. Đây là một cách tiếp cận hai chiều cho phép chúng ta mở rộng hành vi của các lớp con mà không thay đổi cấu trúc của chúng.

Cách thức hoạt động của Visitor

Chúng ta tạo một giao diện Visitor với danh sách các phương thức visitSubclass(). Mỗi lớp con sẽ cài đặt phương thức accept() để gọi phương thức liên quan trong Visitor.

Ví dụ về Visitor

abstract class Expr {
  abstract <R> R accept(Visitor<R> visitor);

  interface Visitor<R> {
    R visitBinaryExpr(Binary expr);
    R visitGroupingExpr(Grouping expr);
    R visitLiteralExpr(Literal expr);
    R visitUnaryExpr(Unary expr);
  }

  static class Binary extends Expr {
    Binary(Expr left, Token operator, Expr right) {
      this.left = left;
      this.operator = operator;
      this.right = right;
    }
    @Override
    <R> R accept(Visitor<R> visitor) {
      return visitor.visitBinaryExpr(this);
    }
    final Expr left;
    final Token operator;
    final Expr right;
  }
}

Kết luận

Hôm nay chúng ta đã tìm hiểu về Bộ phân tích cú pháp và ngữ pháp miễn cưỡng, cùng với các vấn đề và giải pháp liên quan đến việc xây dựng một trình thông dịch. Hãy tiếp tục theo dõi để khám phá thêm về cách thực hiện Bộ phân tích cú pháp thực sự trong các bài viết tiếp theo!

Câu hỏi thường gặp (FAQ)

Q: Bộ phân tích cú pháp là gì?
A: Bộ phân tích cú pháp là phần mềm nhận diện và phân tích cú pháp của mã nguồn, giúp xây dựng cây cú pháp từ các token.

Q: Ngữ pháp miễn cưỡng là gì?
A: Ngữ pháp miễn cưỡng là bộ quy tắc cho phép tạo ra các chuỗi mã phức tạp hơn, có khả năng xử lý các biểu thức lồng ghép.

Q: Mẫu thiết kế Visitor là gì?
A: Mẫu thiết kế Visitor là một phương pháp cho phép mở rộng hành vi của các lớp mà không thay đổi cấu trúc lớp, giúp dễ dàng thêm các hành vi mới.

Hãy theo dõi để cùng nhau khám phá các phần tiếp theo của trình thông dịch nhé!