Xây dựng trình thông dịch biểu thức nhỏ
14 tháng 6, 2026
Khi học lập trình, chúng ta thường viết biểu thức như 1 + 2 * 3 rồi mặc nhiên tin rằng máy tính hiểu đúng thứ tự phép tính. Nhưng nếu bạn từng tự hỏi trình thông dịch biến đoạn văn bản đó thành cây dữ liệu ra sao, bài viết này sẽ giúp bạn tự xây một trình thông dịch nhỏ bằng Python. Mục tiêu không phải tạo ngôn ngữ mới, mà là thấy rõ ba bước cốt lõi: tách từ khóa, dựng cây cú pháp trừu tượng và duyệt cây để tính kết quả.
Vì sao cần cây cú pháp trừu tượng
Một biểu thức không chỉ là chuỗi ký tự. Chuỗi 1 + 2 * 3 có dấu cộng, dấu nhân và khoảng trắng, nhưng ý nghĩa của nó nằm ở cấu trúc: phép nhân phải được tính trước, rồi mới cộng với số 1. Cây cú pháp trừu tượng biểu diễn cấu trúc đó bằng các nút. Nút số giữ giá trị, nút biến giữ tên, còn nút phép toán giữ hai nhánh con.
Với biểu thức trên, cây gần như có dạng sau:
PhepCong
/ \
1 PhepNhan
/ \
2 3
Dạng cây này giúp trình thông dịch tách việc hiểu cú pháp khỏi việc tính toán. Bộ phân tích cú pháp chỉ cần tạo cây đúng, còn bộ duyệt cây mới quyết định cách lấy giá trị từng nút. Khi thêm phép chia, biến, câu lệnh gán hoặc hàm, bạn không cần viết lại toàn bộ bộ tính toán; chỉ cần thêm nút mới và quy tắc duyệt tương ứng.
Tách từ khóa trước khi phân tích
Bước đầu tiên là biến chuỗi đầu vào thành danh sách từ khóa. Ở đây từ khóa không phải if hay for, mà là số, dấu cộng, dấu trừ, dấu nhân, dấu chia và tên biến. Việc này gọi là tách từ khóa. Nó giúp bộ phân tích cú pháp không phải quét từng ký tự nhiều lần.
Đoạn mã sau minh họa bộ tách từ khóa đơn giản:
from __future__ import annotations
from dataclasses import dataclass
from typing import Union, Dict
@dataclass
class So:
gia_tri: float
@dataclass
class Bien:
ten: str
@dataclass
class PhepCong:
trai: BieuThuc
phai: BieuThuc
@dataclass
class PhepTru:
trai: BieuThuc
phai: BieuThuc
@dataclass
class PhepNhan:
trai: BieuThuc
phai: BieuThuc
@dataclass
class PhepChia:
trai: BieuThuc
phai: BieuThuc
BieuThuc = Union[So, Bien, PhepCong, PhepTru, PhepNhan, PhepChia]
def token_hoa(text: str):
ket_qua = []
i = 0
while i < len(text):
ky_tu = text[i]
if ky_tu.isspace():
i += 1
elif ky_tu.isdigit():
j = i
while j < len(text) and text[j].isdigit():
j += 1
ket_qua.append(('SO', float(text[i:j])))
i = j
elif ky_tu == '+':
ket_qua.append(('CONG', '+'))
i += 1
elif ky_tu == '-':
ket_qua.append(('TRU', '-'))
i += 1
elif ky_tu == '*':
ket_qua.append(('NHAN', '*'))
i = i + 1
elif ky_tu == '/':
ket_qua.append(('CHIA', '/'))
i = i + 1
else:
raise ValueError('Ky tu khong hop le: ' + ky_tu)
return ket_qua
Bạn sẽ thấy mã khá trực quan. Nếu gặp khoảng trắng thì bỏ qua, nếu gặp chữ số thì gom nhiều chữ số liên tiếp thành một số, nếu gặp dấu toán tử thì tạo một từ khóa tương ứng. Phần này chưa kiểm tra dấu thập phân, số âm hay tên biến, nhưng đủ để làm nền cho phần tiếp theo.
Dựng cây theo thứ tự ưu tiên
Sau khi có từ khóa, bộ phân tích cú pháp đọc chúng và tạo nút. Cách dễ hiểu là dùng đệ quy. Hàm đọc tổng và hiệu sẽ gọi hàm đọc tích và thương. Hàm đọc tích và thương lại gọi hàm đọc thành phần cơ bản như số hoặc biến. Nhờ vậy, phép nhân và chia nằm sâu hơn trong cây, nên được tính trước.
Mã minh họa:
class Parser:
def __init__(self, tokens):
self.tokens = tokens
self.vi_tri = 0
def bieu_thuc(self):
return self.tong_hieu()
def tong_hieu(self):
node = self.tich_thuong()
while self.kiem('CONG') or self.kiem('TRU'):
loai = self.an()
phai = self.tich_thuong()
if loai == 'CONG':
node = PhepCong(node, phai)
else:
node = PhepTru(node, phai)
return node
def tich_thuong(self):
node = self.nguyen_to()
while self.kiem('NHAN') or self.kiem('CHIA'):
loai = self.an()
phai = self.nguyen_to()
if loai == 'NHAN':
node = PhepNhan(node, phai)
else:
node = PhepChia(node, phai)
return node
def nguyen_to(self):
if self.kiem('SO'):
return So(self.an()[1])
if self.kiem('BIEN'):
return Bien(self.an()[1])
raise ValueError('Khong tim thay bieu thuc')
def kiem(self, loai):
return self.vi_tri < len(self.tokens) and self.tokens[self.vi_tri][0] == loai
def an(self):
token = self.tokens[self.vi_tri]
self.vi_tri = self.vi_tri + 1
return token
Điểm quan trọng là mỗi hàm chỉ chịu trách nhiệm một mức ưu tiên. Hàm tổng và hiệu dừng lại khi gặp dấu nhân hoặc chia, còn hàm tích và thương dừng lại khi gặp dấu cộng hoặc trừ. Cơ chế này tạo ra cây đúng mà không cần dấu ngoặc trong ví dụ cơ bản. Khi muốn hỗ trợ ngoặc, bạn chỉ cần thêm nhánh trong hàm nguyên tố để nhận một biểu thức nằm giữa dấu mở và dấu đóng.
Duyệt cây để tính kết quả
Khi cây đã được dựng, việc tính toán trở thành một hàm duyệt đệ quy. Với nút số, trả về giá trị. Với nút biến, tra trong môi trường. Với nút phép toán, tính nhánh trái và nhánh phải rồi áp dụng phép tính. Đây là mẫu thiết kế rất phổ biến: dữ liệu có cấu trúc cây, hành vi được triển khai bằng duyệt cây.
def danh_gia(node: BieuThuc, moi_truong: Dict[str, float]) -> float:
if isinstance(node, So):
return node.gia_tri
if isinstance(node, Bien):
return moi_truong[node.ten]
if isinstance(node, PhepCong):
return danh_gia(node.trai, moi_truong) + danh_gia(node.phai, moi_truong)
if isinstance(node, PhepTru):
return danh_gia(node.trai, moi_truong) - danh_gia(node.phai, moi_truong)
if isinstance(node, PhepNhan):
return danh_gia(node.trai, moi_truong) * danh_gia(node.phai, moi_truong)
if isinstance(node, PhepChia):
return danh_gia(node.trai, moi_truong) / danh_gia(node.phai, moi_truong)
raise TypeError('Khong biet danh gia node')
tokens = token_hoa('1 + 2 * 3')
cay = Parser(tokens).bieu_thuc()
print(danh_gia(cay, {}))
Kết quả in ra là 7. Điều thú vị nằm ở chỗ trình thông dịch không nhìn chuỗi ban đầu nữa. Nó chỉ làm việc với cây. Nhờ vậy, bạn có thể chèn thêm bước kiểm tra kiểu, tối ưu biểu thức hoặc sinh mã mà không làm rối phần phân tích cú pháp.
Mở rộng thành ngôn ngữ nhỏ
Từ nền tảng này, bạn có thể thêm nhiều khái niệm theo từng lớp.
Thêm gán biến
Để hỗ trợ gán biến, hãy thêm nút lệnh và môi trường có khả năng ghi giá trị. Một câu lệnh gán không trả về biểu thức theo nghĩa thông thường, mà thay đổi trạng thái của môi trường. Khi đó chương trình là danh sách lệnh, còn biểu thức chỉ là một phần bên trong lệnh.
Thêm hàm
Hàm cần ba thành phần: danh sách tham số, thân hàm và bảng lưu hàm. Khi gọi hàm, trình thông dịch tạo môi trường mới, gắn tham số với đối số, rồi duyệt thân hàm trong môi trường đó. Đây là lúc bạn bắt đầu thấy sự giống nhau giữa trình thông dịch nhỏ và các ngôn ngữ thực tế.
Thêm thông báo lỗi hữu ích
Trình thông dịch giáo dục không nên chỉ ném lỗi chung chung. Hãy lưu số dòng, số cột và đoạn văn bản đang đọc. Khi gặp dấu đóng ngoặc không khớp hoặc phép chia cho số không, thông báo nên chỉ rõ vị trí và nguyên nhân. Kinh nghiệm này rất hữu ích khi bạn làm việc với trình biên dịch, công cụ kiểm tra mã hoặc trình xử lý tệp cấu hình.
Bài học mang sang dự án thực tế
Dự án nhỏ này dạy nhiều kỹ năng có thể dùng trong phần mềm lớn. Bạn học cách tách biểu diễn dữ liệu khỏi hành vi, cách dùng đệ quy để xử lý cấu trúc lồng nhau và cách thiết kế từng lớp đủ nhỏ để kiểm thử. Trong thực tế, các công cụ như trình định dạng mã, trình phân tích truy vấn, bộ xử lý biểu thức điều kiện hay trình đọc tệp cấu hình đều dùng ý tưởng tương tự.
Nếu muốn tự luyện tập, hãy thêm một tính năng mỗi tuần: ngoặc, số thập phân, so sánh, câu điều kiện, vòng lặp, rồi hàm. Sau mỗi lần mở rộng, hãy viết vài ca kiểm thử đơn giản để chắc rằng cây được dựng đúng. Khi bạn có thể nhìn một biểu thức và tưởng tượng ra cây của nó, bạn đã nắm được một trong những nền tảng quan trọng nhất của trình biên dịch và trình thông dịch.