Chương trình học Bài 209 trên tổng số 250 · Dự án: xây những thứ thật
Dự án: xây những thứ thật

Dự án: một trình thông dịch tí hon

Đây là một nghi thức trưởng thành: viết một chương trình đọc một ngôn ngữ và chạy nó. Ngôn ngữ của bạn là số học, nhưng bạn sẽ xây nó theo cách các trình thông dịch thật được xây, để 2 + 3 * 4 cho ra 14, không phải 20. Python sẽ không giúp bạn ở đây - bạn tự phân tích chuỗi, không dùng eval().

Hai giai đoạn. Đầu tiên tách token: biến chuỗi thô thành một list các mảnh sạch sẽ. "2 + 30" thành ["2", "+", "30"]. Đi qua các ký tự, bỏ qua khoảng trắng, tạo mỗi ký hiệu trong + - * / ( ) thành một token riêng, và gom các loạt chữ số (và một dấu chấm) thành một token số. Một ký tự bất ngờ là một ValueError.

Rồi tính giá trị, dùng đệ quy đi xuống (recursive descent): một hàm nhỏ cho mỗi mức ưu tiên, mỗi hàm gọi hàm có độ liên kết chặt hơn ở dưới nó. Cấu trúc đó chính là thứ mã hóa thứ tự các phép toán:

def parse_expr():      # lowest precedence: + and -
    value = parse_term()
    while peek() in ("+", "-"):
        op = advance()
        value = value + parse_term() if op == "+" else value - parse_term()
    return value

def parse_term():      # higher: * and /
    value = parse_factor()
    while peek() in ("*", "/"):
        ...

def parse_factor():    # highest: a number, or ( expr )
    if peek() == "(":
        advance(); value = parse_expr()
        # then expect and consume the matching )
        ...
    return float(advance())

Vì parse_factor có thể gọi lại parse_expr cho một nhóm trong ngoặc, các dấu ngoặc tự nhiên được hỗ trợ, kể cả ngoặc lồng nhau. Giữ một con trỏ pos nhỏ với peek() (nhìn token hiện tại) và advance() (tiêu thụ nó). Đầu vào sai định dạng phải báo ValueError: một toán tử treo như 2 +, một (2 + 3 không cân bằng, hoặc các token thừa. Các mục tiêu cần đạt: evaluate('2 + 3 * 4') == 14.0, evaluate('(2 + 3) * 4') == 20.0, ngoặc lồng nhau, và một lần báo lỗi với '2 +'. Bấm Chạy để tính giá trị một vài biểu thức.

Đến lượt bạn

Viết tokenize(expr) (các số là token chuỗi cộng các ký hiệu + - * / ( ), bỏ qua khoảng trắng, từ chối ký tự lạ) và evaluate(expr) trả về một float ưu tiên * / hơn + - và tôn trọng dấu ngoặc (đệ quy đi xuống hoặc shunting-yard). Đầu vào sai định dạng phải báo ValueError. Mục tiêu: evaluate('2 + 3 * 4') == 14.0, evaluate('(2 + 3) * 4') == 20.0, ngoặc lồng nhau, và một lần báo lỗi với '2 +'.

Bạn thấy vấn đề gì trong bài học này? Hãy báo cáo nó · Hỏi về bài học này

Bài tập này sẽ sớm mở.

Hoàn thành bài học trước đó để mở khóa bài này. Toàn bộ khóa học là miễn phí, không cần tài khoản, và bạn có thể đọc bài học này ngay bây giờ.