Mümkün olduğu kadar az parantez içeren güzel baskı ifadesi?

Question

Benim Soru: Bir ifadeyi gereksiz parantez olmadan güzel yazdırmanın en temiz yolu nedir?

---

Ben lambda ifadeleri aşağıdaki gösterimi: Kongre App By

Term ::= Fun(String x, Term t) 
     | App(Term t1, Term t2) 
     | Var(String x) 

önce sol taraf, yani o, a b c(a b) c olarak yorumlanır ve işlev organları olabildiğince sağa kadarıyla germek olduğunu λ x. x y, λ x. (x y) olarak yorumlanır.

İyi bir iş yapan bir çözümleyici var, ancak şimdi Güzel bir yazıcı istiyorum.

term match { 
    case Fun(v, t) => "(λ %s.%s)".format(v, prettyPrint(t)) 
    case App(s, t) => "(%s %s)".format(prettyPrint(s), prettyPrint(t)) 
    case Var(v) => v 
} 

yukarıdaki yazıcı her zaman (atomik değişkenler hariç) ifadeler etrafında () koyar: İşte şu anda (sözde scala) yanı da bu. Böylece Fun(x, App(Fun(y, x), y)) için o sadece App parametre tiplerini kontrol etmeleri ben

λ x.(λ y.x) y 

Answer 1

istiyorum

(λ x.((λ y.x) y)) 

değil mi üretir?

Ben

İşte

term match { 
    case Fun(v: String, t: Term) => "λ %s.%s".format(v, prettyPrint(t)) 
    case App(s: Fun, t: App) => "(%s) (%s)".format(prettyPrint(s), prettyPrint(t)) 
    case App(s: Term, t: App) => "%s (%s)".format(prettyPrint(s), prettyPrint(t)) 
    case App(s: Fun, t: Term) => "(%s) %s".format(prettyPrint(s), prettyPrint(t)) 
    case App(s: Term, t: Term) => "%s %s".format(prettyPrint(s), prettyPrint(t)) 
    case Var(v: String)   => v 
} 

Answer 2

Kimin operatörler listelenmiştir aşağıdaki dilbilgisi tarafından tanımlanan çağrışımsal ve önceliğiyle infix ifadeleri basit dilbilgisi kullanacağız .. scala bu yazma emin değilim öncelik

E -> E + T | E - T | T  left associative 
T -> T * F | T/F | F  left associative 
F -> G^F | G    right associative 
G -> - G | (E) | NUM 

ait küçükten büyüğe aşağıda pseudocode açıklandığı gibi sadece gerekli parantez bir dizeye AST dönüştürmek bir soyut sözdizimi ağacı (AST) Verilen. Parantezin ne zaman gerekli olduğunu belirlemek için tekrar tekrar ağacın inişini yaparken göreli önceliği ve birliği inceliyoruz. Parentezleri ifadesinin etrafına sarmak için tüm kararların, ebeveyn düğümde olması gerektiğini unutmayın.

toParenString(AST) { 
    if (AST.type == NUM) // simple atomic type (no operator) 
     return toString(AST) 
    else if (AST.TYPE == UNARY_MINUS) // prefix unary operator 
     if (AST.arg.type != NUM AND 
      precedence(AST.op) > precedence(AST.arg.op)) 
       return "-(" + toParenString(AST.arg) + ")" 
     else 
       return "-" + toParenString(AST.arg) 
    else { // binary operation 
     var useLeftParen = 
      AST.leftarg.type != NUM AND 
      (precedence(AST.op) > precedence(AST.leftarg.op) OR 
       (precedence(AST.op) == precedence(AST.leftarg.op) AND 
       isRightAssociative(AST.op))) 

     var useRightParen = 
      AST.rightarg.type != NUM AND 
      (precedence(AST.op) > precedence(AST.rightarg.op) OR 
       (precedence(AST.op) == precedence(AST.rightarg.op) AND 
       isLeftAssociative(AST.op))) 

     var leftString; 
     if (useLeftParen) { 
      leftString = "(" + toParenString(AST.leftarg) + ")" 
     else 
      leftString = toParenString(AST.leftarg) 

     var rightString; 
     if (useRightParen) { 
      rightString = "(" + toParenString(AST.rightarg) + ")" 
     else 
      rightString = toParenString(AST.rightarg) 

     return leftString + AST.op + rightString; 
    } 
    }