Parantezli basit bir hesap makinesi nasıl çalışır?

Question

Hesap makinelerinin nasıl çalıştığını öğrenmek istiyorum. 2

ayrıştırıcı matematik ortak kurallar saygı olurdu -

1 + 2 x 10: Örneğin, böyle infix gösterimde girdi derler. 2 = 19 (yerine 3 x 10 - - 2 = 28)

ve bu göz önünde

1 + (2 x 10):

1 + 2 x Yukarıdaki örnekte, bu demektir ((2/9) + 7) - 2

Özet Sözdizim Ağacı içerir mi? Bir ikili ağaç mı? Operasyonların sırası matematiksel olarak doğru bir şekilde nasıl sağlandı? Postfix gösterimine dönüştürmek için şant çözüm algoritmasını kullanmalı mıyım? Ve sonra, postfix gösterimde nasıl ayrıştırırdım? Neden ilk etapta dönüyoruz?

Bu nispeten basit hesap makinelerinin nasıl oluşturulduğunu gösteren bir öğretici var mı? Ya da birisi açıklayabilir mi?

Answer 1

Bir ifadeyi değerlendirmenin bir yolu, yinelemeli bir yoklama ayrıştırıcısıdır. http://en.wikipedia.org/wiki/Recursive_descent_parser

Burada BNF formunda bir örnek dilbilgisi verilmiştir: Burada http://en.wikipedia.org/wiki/Backus-Naur_form

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

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

Number ::= Digit+ 

* köşeli parantez isteğe bağlı anlamına gelir, önceki eleman + bir ya da daha çok tekrar ettiği anlamına gelir, sıfır ya da daha fazla kez tekrar edilir demektir.

Dilbilgisi, en yüksek önceliğe sahip öğelerin önce bir araya getirilmesini veya bu durumda ilk önce değerlendirilmesini sağlar. Dilbilgisindeki her düğümü ziyaret ettiğinizde, soyut bir sözdizimi ağacı oluşturmak yerine geçerli düğümü değerlendirir ve değeri döndürürsünüz.

Örnek kodu (mükemmel değil ama size koduna BNF eşleme hakkında bir fikir vermelidir):

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 

1 + 2 * 10 - 2 sizin örnek değerlendirmek nasıl göstermek için: Deneyin görünümlü

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

Antlr. Özel bir derleyici/ayrıştırıcı oluşturmak için kullandığım şey ... ve kolayca oluşturulacak çok basit bir hesap makinesiyle ilişkilendirilebilir.