Довольно печатное выражение с минимальным количеством скобок? - PullRequest
Новая
       5

Довольно печатное выражение с минимальным количеством скобок?

14 голосов
/ 08 июня 2011

Мой вопрос: Какой самый чистый способ печати выражения без лишних скобок?

У меня есть следующее представление лямбда-выражений: 

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

По соглашению App является ассоциативным слева, то есть a b c интерпретируется как (a b) c, а функциональные тела растягиваются как можно дальше вправо, то есть λ x. x y интерпретируется как λ x. (x y).

У меня есть парсер, который хорошо работает, но теперь Мне нужен симпатичный принтер .Вот что у меня сейчас (псевдо-scala): 

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
}

Вышеуказанный принтер всегда помещает ( ) вокруг выражений (кроме атомарных переменных).Таким образом, для Fun(x, App(Fun(y, x), y)) он производит 

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

Я хотел бы иметь 

λ x.(λ y.x) y

Ответы [ 2 ]

4 голосов
/ 01 апреля 2016

Здесь я буду использовать простую грамматику для инфиксных выражений с ассоциативностью и приоритетом, определяемыми следующей грамматикой, операторы которой перечислены в порядке возрастания приоритета 

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

Учитывая абстрактное синтаксическое дерево (AST), мы конвертируем AST в строку только с необходимыми круглыми скобками, как описано в псевдокоде ниже. Мы исследуем относительный приоритет и ассоциативность, когда рекурсивно спускаемся по дереву, чтобы определить, когда нужны скобки. Обратите внимание, что все решения обернуть скобки вокруг выражения должны быть приняты в родительском узле. 

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;
    }
  }
3 голосов
/ 19 августа 2012

Разве вам не нужно просто проверять типы аргументов приложения?

Я не уверен, как написать это в Scala .. 

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
}
...