Interpreter và Visitor cho ngôn ngữ và cấu trúc
Thông dịch cú pháp đơn giản bằng cây biểu thức, và khách thăm thêm việc mới cho cấu trúc ổn định của Visitor.
Chuyên giaDesign pattern ~60 phút
Ôn lại trước khi học
Giới thiệu
Bài này học thông dịch lệnh đơn giản và thêm việc mới. Hai mẫu này giúp code gọn khi yêu cầu đổi liên tục.
Kiến thức cần nhớ
Interpreter là gì
- Interpreter diễn giải ngôn ngữ nhỏ thành hành động.
- Mỗi quy tắc ngữ pháp là 1 lớp nút trong cây.
- Ví dụ đời thường: đọc công thức nấu ăn rồi làm từng bước.
- Câu lệnh lặp 4 lần tiến 10 bước thành cây có nút lặp và nút tiến.
Diễn giải bằng đệ quy
- Diễn giải là gọi đệ quy từ gốc xuống lá.
- Nút lặp gọi lại cây con đúng số lần.
- Nút tiến đi thẳng, nút quay xoay đúng độ.
- Ví dụ: lặp 4 lần tiến rồi quay tạo hình vuông.
Visitor là gì
- Visitor mang việc mới tới cấu trúc đã chốt.
- Thêm việc chỉ cần thêm khách mới, cấu trúc giữ nguyên.
- Ví dụ đời thường: đoàn kiểm tra tới từng phòng, phòng không đổi.
- Kỹ thuật gọi kép: phần tử gọi ngược khách đúng kiểu của mình.
| Cách | Thêm việc mới | Thêm phần tử mới |
|---|---|---|
| Nhồi vào cấu trúc | Mở hết mọi lớp | Thêm 1 lớp |
| Visitor | Thêm 1 khách mới | Sửa hết khách cũ |
Ví dụ
- Input: cây lặp 4 lần tiến 10 quay 90. Output: rùa vẽ hình vuông khép kín.
- Giải thích: mỗi nút chỉ làm việc của mình, đệ quy lo phần còn lại.
- Input: khách thuế thăm 3 phần tử cư dân, doanh nghiệp, nhà hàng. Output: mỗi kiểu tính đúng công thức riêng.
- Giải thích: gọi kép chọn đúng việc cho đúng kiểu.
💻 Bài tập
Ngôn ngữ: C++17 (hoặc Java/Python). Nộp vào day-124/.
Bài 1: Interpreter cho ngôn ngữ rùa
Ngữ pháp:
program := command*
command := "tien" NUMBER | "quay" NUMBER | "lap" NUMBER "[" command* "]"
| Thành phần | Yêu cầu |
|---|---|
Lexer | Tách token: từ khóa, số, [, ] |
Parser | Đệ quy xuống, dựng cây Program, Forward, Turn, Repeat. Lỗi cú pháp báo dòng và cột |
interpret(Context&) | Mỗi nút tự diễn giải. Context giữ vị trí (x, y), hướng, danh sách đoạn thẳng đã vẽ |
"lap 4 [ tien 10 quay 90 ]" -> 4 đoạn, quay về (0, 0)
"lap 36 [ lap 4 [ tien 5 quay 90 ] quay 10 ]" -> 144 đoạn
"lap 4 [ tien 10" -> lỗi cú pháp: thiếu "]" ở dòng 1
Xuất đường vẽ ra file SVG.
Bài 2: Visitor cho cây cú pháp
struct Visitor { virtual void visit(Forward&) = 0; virtual void visit(Turn&) = 0; virtual void visit(Repeat&) = 0; virtual void visit(Program&) = 0; };
Viết 3 visitor mà không sửa lớp nút nào:
| Visitor | Việc |
|---|---|
PrettyPrinter | In lại chương trình có thụt lề |
StepCounter | Đếm tổng số lệnh tien thực sự chạy (tính cả lặp) |
Optimizer | Gộp tien a tien b thành tien (a+b), bỏ quay 0 và quay 360 |
Bài 3: Visitor tính thuế (nâng cao)
Cấu trúc: Resident(income), Business(revenue, expenses), Restaurant(revenue, alcoholRevenue).
TaxVisitor: cư dân 10% thu nhập trên 11 triệu, doanh nghiệp 20% lợi nhuận, nhà hàng 8% doanh thu cộng 10% doanh thu rượu.ReportVisitorin báo cáo từng đối tượng.- Thêm loại mới
Farm. Đếm số file phải sửa. Ghi vàoREADME.md: đây là điểm yếu của Visitor (thêm kiểu khó, thêm việc dễ). So với cách dùngvirtualthường.
✅ Tiêu chí hoàn thành
- 3 test Interpreter pass, có file SVG.
- 3 visitor không sửa lớp nút.
-
Optimizergiữ nguyên hình vẽ (so đoạn thẳng trước và sau). - Bảng "thêm kiểu" và "thêm việc" giữa Visitor và virtual thường.
❓ Câu hỏi ôn tập
- Interpreter biến câu lệnh thành cây thế nào?
- Diễn giải đệ quy chạy từ đâu tới đâu?
- Visitor thêm việc mới mà không sửa cấu trúc ra sao?
- Khi nào Visitor thắng và khi nào thua?
🌕 Bạn đã hoàn thành ngày 124. Làm hết bài tập phía trên rồi sang ngày tiếp theo.