Máy tính đơn giản với dấu ngoặc đơn hoạt động như thế nào?

Question

Tôi muốn tìm hiểu cách máy tính hoạt động. Ví dụ, nói rằng chúng ta có đầu vào trong ký hiệu ghi vào như thế này:

1 + 2 x 10-2

Các phân tích cú pháp sẽ phải tôn trọng quy tắc chung trong toán học. Trong ví dụ trên này có nghĩa là:

1 + (2 x 10) - 2 = 19 (chứ không phải là 3 x 10 - 2 = 28)

Và sau đó xem xét việc này:

1 + 2 x ((2/9) + 7) - 2

Nó có liên quan đến cây cú pháp trừu tượng không? Cây nhị phân? Làm thế nào là thứ tự các hoạt động đảm bảo được toán học chính xác? Tôi có phải sử dụng thuật toán shunting-yard để chuyển đổi nó thành ký hiệu postfix không? Và sau đó, làm thế nào tôi sẽ phân tích nó trong ký hiệu postfix? Tại sao lại chuyển đổi ngay từ đầu?

Có hướng dẫn nào cho thấy cách các máy tính tương đối đơn giản này được xây dựng không? Hoặc ai đó có thể giải thích?

Answer 1

Một cách để thực hiện đánh giá biểu thức là bằng trình phân tích cú pháp gốc đệ quy. http://en.wikipedia.org/wiki/Recursive_descent_parser

Dưới đây là một ví dụ ngữ pháp ở dạng BNF: http://en.wikipedia.org/wiki/Backus-Naur_form

Expr ::= Term ('+' Term | '-' Term)* 
Term ::= Factor ('*' Factor | '/' Factor)* 

Factor ::= ['-'] (Number | '(' Expr ')') 

Number ::= Digit+ 

đây * có nghĩa là các yếu tố trước được lặp lại không hay nhiều lần, + có nghĩa là một hoặc nhiều lặp đi lặp lại, dấu ngoặc vuông có nghĩa là không bắt buộc.

Ngữ pháp đảm bảo rằng các yếu tố ưu tiên cao nhất được thu thập cùng nhau trước tiên hoặc trong trường hợp này, được đánh giá trước tiên. Khi bạn truy cập từng nút trong ngữ pháp, thay vì xây dựng một cây cú pháp trừu tượng, bạn đánh giá nút hiện tại và trả về giá trị.

Ví dụ mã (không hoàn hảo nhưng sẽ cho bạn một ý tưởng về làm thế nào để lập bản đồ BNF để code):

def parse_expr(): 
    term = parse_term() 
    while 1: 
    if match('+'): 
     term = term + parse_term() 
    elif match('-'): 
     term = term - parse_term() 
    else: return term 

def parse_term(): 
    factor = parse_factor() 
    while 1: 
    if match('*'): 
     factor = factor * parse_factor() 
    elif match('/'): 
     factor = factor/parse_factor() 
    else: return factor 

def parse_factor(): 
    if match('-'): 
    negate = -1 
    else: negate = 1 
    if peek_digit(): 
    return negate * parse_number() 
    if match('('): 
    expr = parse_expr() 
    if not match(')'): error... 
    return negate * expr 
    error... 

def parse_number(): 
    num = 0 
    while peek_digit(): 
    num = num * 10 + read_digit() 
    return num 

Để hiển thị như thế nào ví dụ của bạn của 1 + 2 * 10 - 2 sẽ đánh giá:

call parse_expr        stream is 1 + 2 * 10 - 2 
    call parse term 
    call parse factor 
     call parse number which returns 1  stream is now + 2 * 10 - 2 
    match '+'        stream is now 2 * 10 - 2 
    call parse factor 
     call parse number which returns 2  stream is now * 10 - 2 
     match '*'        stream is now 10 - 2 
     call parse number which returns 10  stream is now - 2 
     computes 2 * 10, return 20 
    compute 1 + 20 -> 21 
    match '-'        stream is now 2 
    call parse factor 
     call parse number which returns 2  stream is empty 
    compute 21 - 2, return 19 
    return 19 

Answer 2

Hãy thử tìm kiếm tại Antlr. Đó là những gì tôi đã sử dụng để xây dựng một trình biên dịch/phân tích cú pháp tùy chỉnh ... và có thể dễ dàng liên quan đến một máy tính mà sẽ là một điều rất đơn giản để tạo ra.