Красивая печать AST с минимальными круглыми скобками

Я сам наткнулся на ваш вопрос в поисках ответа. Хотя я не нашел канонического алгоритма, я обнаружил, что, как вы говорите, одного приоритета операторов недостаточно для минимального заключения в скобки выражений. Я попытался написать симпатичный JavaScript-принтер на Haskell, хотя мне показалось утомительным писать надежный парсер, поэтому я изменил конкретный синтаксис: https://gist.github.com/kputnam/5625856

Помимо приоритета, вы должны учитывать ассоциативность операторов. Бинарные операции, такие как / и -, анализируются как левоассоциативные. Однако присваивание =, возведение в степень ^ и равенство == являются правоассоциативными. Это означает, что выражение Div (Div a b) c может быть записано a / b / c без скобок, но Exp (Exp a b) c должно быть заключено в скобки как (a ^ b) ^ c.

Ваша интуиция верна: для левоассоциативных операторов, если выражение левого операнда связывает менее жестко, чем его родительский элемент, его следует заключить в круглые скобки. Если выражение правого операнда связывает так же жестко или менее жестко, чем его родительский элемент, его следует заключить в круглые скобки. Таким образом, Div (Div a b) (Div c d) не требует скобок вокруг левого подвыражения, но правое подвыражение требует: a / b / (c / d).

Далее, унарные операторы, в частности операторы, которые могут быть как двоичными, так и унарными, например отрицание и вычитание -, принуждение и сложение + и т. Д., Возможно, потребуется обрабатывать в индивидуальном порядке. Например, Sub a (Neg b) должен быть напечатан как a - (-b), даже если унарное отрицание связывает сильнее, чем вычитание. Думаю, это зависит от вашего парсера, a - -b может быть не двусмысленным, а просто некрасивым.

Я не уверен, как должны работать унарные операторы, которые могут быть как префиксными, так и постфиксными. В таких выражениях, как ++ (a ++) и (++ a) ++, один из операторов должен связываться более жестко, чем другой, иначе ++ a ++ будет неоднозначным. Но я подозреваю, что даже если круглые скобки в одном из них не нужны, для удобства чтения вы все равно можете добавить круглые скобки.

Это зависит от правил конкретной грамматики. Думаю, у вас есть право на операторы с разным приоритетом и право на вычитание и деление.

Однако возведение в степень часто трактуется по-другому, в том смысле, что его правый операнд оценивается первым. Значит тебе нужно

 (a ** b) ** c

когда c - правый дочерний элемент корня.

То, как идут скобки, определяется тем, что определяют правила грамматики. Если ваша грамматика имеет вид

exp = sub1exp ;
exp = sub1exp op exp ;
sub1exp = sub1exp ;  
sub1exp = sub1exp op1 sub2exp ;
sub2exp = sub3exp ;
sub2exp = sub3exp op2 sub2exp ;
sub3exp = ....
subNexp = '(' exp ')' ;

если op1 и op2 не ассоциативны, тогда вы хотите заключить в скобки правое поддерево op1, если корень поддерева также op1, и вы хотите заключить в скобки левое поддерево op2, если левое поддерево имеет корень op2.

Существует общий подход к красивым печатным выражениям с минимальным количеством скобок. Начните с определения однозначной грамматики для вашего языка выражений, которая кодирует правила приоритета и ассоциативности. Например, скажем, у меня есть язык с тремя бинарными операторами (*, +, @) и унарным оператором (~), тогда моя грамматика может выглядеть так:

E -> E0

E0 -> E1 '+' E0       (+ right associative, lowest precedence)
E0 -> E1

E1 -> E1 '*' E2       (* left associative; @ non-associative; same precedence)
E1 -> E2 '@' E2
E1 -> E2

E2 -> '~' E2          (~ binds the tightest)
E2 -> E3

E3 -> Num             (atomic expressions are numbers and parenthesized expressions)
E3 -> '(' E0 ')'

Деревья синтаксического анализа для грамматики содержат все необходимые (и ненужные) круглые скобки, и невозможно построить дерево синтаксического анализа, выравнивание которого приводит к неоднозначному выражению. Например, нет дерева синтаксического анализа для строки

1 @ 2 @ 3

потому что "@" не ассоциативно и всегда требует скобок. С другой стороны, строка

1 @ (2 @ 3)

имеет дерево синтаксического анализа

E(E0(E1( E2(E3(Num(1)))
         '@'
         E2(E3( '('
                E0(E1(E2(E3(Num(2)))
                      '@'
                      E2(E3(Num(3)))))
                ')')))

Таким образом, проблема сводится к проблеме принуждения абстрактного синтаксического дерева к синтаксическому дереву. Минимальное количество круглых скобок достигается за счет избегания принуждения узла AST к атомарному выражению, когда это возможно. Это легко сделать систематическим образом:

Поддерживайте пару, состоящую из указателя на текущий узел в AST и текущего расширяемого производства. Инициализируйте пару с корневым узлом AST и продукцией "E". В каждом случае для возможных форм узла AST расширьте грамматику настолько, насколько это необходимо для кодирования узла AST. Это оставит нерасширенную грамматику для каждого поддерева AST. Примените метод рекурсивно к каждой паре (поддерево, продукция).

Например, если AST - (* (+ 1 2) 3), действуйте следующим образом:

expand[ (* (+ 1 2) 3); E ]  -->  E( E0( E1( expand[(+ 1 2) ; E1]
                                            '*'
                                            expand[3 ; E2] ) ) )

expand[ (+ 1 2) ; E1 ] --> E1(E2(E3( '('
                                     E0( expand[ 1 ; E1 ]
                                         '+'
                                         expand[ 2 ; E0 ] )
                                     ')' )))

...

Алгоритм, конечно, можно реализовать гораздо менее явным образом, но этот метод можно использовать для руководства реализацией, не сойдя с ума :).