Design Patterns: Mẫu Interperter

Vấn đề đặt ra

Nếu một dạng bài toán có tần suất xuất hiện tương đối lớn, người ta thường biểu diễn các thể hiện cụ thể của nó bằng các câu trong một ngôn ngữ đơn giản. Sau đó ta có thể xây dựng một trình biên dịch để giải quyết bài toán bằng cách biên dịch các câu.

Lấy ví dụ, tìm kiếm các xâu thoả mãn một mẫu cho trước là một bài toán thường gặp và các “biểu diễn thông thường” tạo thành ngôn ngữ dùng để diễn tả các mẫu của xâu. Thay vì xây dựng từng thuật toán riêng biệt để tương ứng mỗi mẫu với một tập các xâu, người ta xây dựng thuật toán tổng quát có thể phiên dịch các “biểu diễn thông thường” thành tập các xâu tương ứng.

Mẫu Interpreter miêu tả cách thức xây dựng cấu trúc ngữ pháp cho những ngôn ngữ đơn giản, cách thức biểu diễn câu trong ngôn ngữ và cách thúc phiên dịch các câu đó. Trong ví dụ cụ thể này, nó miêu tả cách thức xây dựng cấu trúc ngữ pháp cho các biểu diễn thông thường, cách thức xây dựng biểu diễn thông thường và cách thúc phiên dịch các biểu diễn thông thường đó.

Giả sử cấy trúc ngữ pháp sau xác định các biểu diễn thông thường :

Mẫu Interpreter sử dụng các lớp để diễn tả các quy luật ngữ pháp. Khi đó cấu trúc ngữ pháp trên được diễn tả bởi năm lớp : lớp trừu tượng RegularExpression và bốn lớp con của nó : LiteralExpression, AlternationExpression, SequenceExpression và RepetitionExpression trong đó ba lớp cuối có các biến để chứa các biểu thức con.

Mỗi biểu diễn thông thường xác định bởi cấu trúc ngữ pháp trên đều đựơc miêu tả bởi một cây cú pháp có thành phần là các đối tượng của các lớp trên. Lấy ví dụ biểu diễn raining & (dogs | cats) * được miêu tả bởi cây sau:

Chúng ta có thể tạo ra trình biên dịch cho các biểu diễn trên bằng cách định nghĩa thủ tục Interpret trên từng lớp con của RegularExpression. Hàm này nhận tham số đầu vào là ngữ cảnh phiên dịch biểu diễn bao gồm xâu đầu vào và thông tin về lượng xâu đã đựơc ghép. Nó sẽ tiếp tục ghép phần tiếp theo của xâu dựa trên ngữ cảnh đó. Ví dụ:

• LiteralExpression sẽ kiểm tra xem đầu vào có trùng với bảng chữ cái nó định nghĩa không.
• AlternationExpression sẽ kiểm tra xem thông tin đầu vào có phải là một trong các lựa chọn của nó không.
• ...

Định nghĩa

Interpreter đưa ra một ngôn ngữ, xây dựng cách diễn đạt ngôn ngữ đó cùng với một trình phiên dịch sử dụng cách diễn tả trên để phiên dịch các câu.

Sơ đồ UML

AbstractExpression (Expression)

• Khai báo một giao diện cho việc thực hiện một thao tác

TerminalExpression (ThousandExpression, HundredExpression, TenExpression, OneExpression )

• Cài đặt một thao tác thông dịch liên kết với những ký pháp đầu cuối
• Một thể nghiệm được yêu cầu cho mọi ký pháp đầu cuối trong câu

NonterminalExpression (không sử dụng)

• Một lớp như vậy được yêu cầu cho các luật R::=R1R2..Rn trong dãy cú pháp
• Duy trì một biến thể nghiệm của kiểu AbstractExpression cho mỗi một ký pháp R1 đến Rn
• Cài đặt một phương thức thông dịch cho các ký pháp không phải đầu cuối.
• Thông dịch tự gọi đệ quy cho các biến đại diện từ R1 đến Rn

Context (Context)

• Chứa thông tin toàn cục cho việc thông dịch

Client (InterpreterApp)