Как включить тройные операторы в алгоритм восхождения на приоритет?

Ответ 1

Чтобы быть конкретным, я буду использовать C/С++/Java ?: в качестве примера.

Похоже, что в этих языках оператор ?: допускает любое допустимое выражение между ? и :, включая выражения, сформированные с помощью ?: и те, которые сформированы с операторами, приоритет которых ниже приоритета ?:, например = и , (примеры: a ? b = c : d, a ? b , c : d, a ? b ? c : d : e).

Это говорит о том, что вы должны рассматривать ? и : точно так же, как ( и ) во время разбора выражений. Когда вы разобрали ? expr :, он, в целом, является двоичным оператором. Итак, вы разбираете ( expr ) и ? expr : таким же образом, но первое является выражением, а второе является двоичным оператором (с встроенным в него выражением).

Теперь, когда ? expr : является двоичным оператором (a ?-expr-: b не отличается от a * b с точки зрения "двоичности" ), вы должны быть в состоянии поддерживать его почти так же, как и любой другой двоичный оператор, который вы уже поддерживаете.

Лично я не стал бы расколоть ?: на отдельные собственные бинарные операторы. В конце концов, он все еще является тройным оператором и должен быть связан с 3 операндами и рассматриваться как целое во время оценки выражения. Если вы следуете подходу в статье, который вы упомянули в вопросе, и создаете AST, тогда вы идете, ?: имеет левый дочерний элемент node, правый дочерний node (как любой другой двоичный оператор) и, кроме того, средний ребенок node.

Приоритет ?-expr-: в целом должен быть низким. В C/С++ (и в Java?) Это не самое низкое. Вам решать, что вы хотите.

До сих пор мы не рассматривали ассоциативность ?:. В C/С++ и Java, ?-expr-: является право-ассоциативным, как оператор присваивания =. Опять же, это зависит от вас, чтобы сделать его лево-ассоциативным или сохранить его право-ассоциативным.

И это:

E --> P {B P}
P --> v | "(" E ")" | U P
B --> "+" | "-" | "*" | "/" | "^"
U --> "-"

должен выглядеть примерно так:

E --> P {B P}
P --> v | "(" E ")" | U P
B --> "+" | "-" | "*" | "/" | "^" | "?" E ":"
U --> "-"

Ответ 2

Я столкнулся с этим вопросом, ища информацию о преобразовании тернарных операторов в обратные польские обозначения (RPN), поэтому, хотя у меня нет четкой реализации для реализации оператора ?: с восхождением на приоритет, я думаю, что могу уметь дать ключ к преобразованию оператора ?: в RPN с использованием двух стеков... который аналогичен алгоритму Shunting Yard на веб-странице, которую вы указали.

(Edit) Я должен указать, что я здесь не очень эффективен (обе ветки тернарного оператора должны быть оценены), но чтобы продемонстрировать, как легко включить новый оператор (?:) в существующей структуре (код преобразования RPN) (путем объявления ? и : с двумя наименьшими уровнями приоритета).

Я хочу начать с некоторых примеров того, как выражения с ?: преобразуются в RPN на основе моего анализатора... Я добавляю два оператора вместо одного, ? и : , но я не думаю, что это имеет большое значение, поскольку : и ? всегда будут объединены (Это более удобно, если RPN и исходное выражение имеют одинаковое количество токенов). В примерах вы можете увидеть, как это работает.

Пример 1: 1 + ((0+1) ? 2 : 3 + 8) + 4

RPN: 1 0 1 + 2 3 8 + : ? + 4 +

Теперь дайте оценку RPN.

1 - Нажатие первых элементов в стеке, и мы сталкиваемся с первым двоичным оператором:

1 0 1 и оператора +, мы добавляем верхние 2 элемента, превращая стек в 1 1

2 - Затем нажимаем еще три элемента, и мы сталкиваемся со вторым двоичным оператором:

1 1 2 3 8 + ------ > 1 1 2 11

3 - Теперь мы имеем : и ?. Это на самом деле говорит нам выбрать либо последующую ветвь (второй верхний элемент поверх стека, 2), либо альтернативную ветку (самый верхний элемент в стеке, 11), основанный на предикате (третий верхний элемент в стеке, 1). Поскольку предикат равен 1 (истина), мы выбираем 2 и отбрасываем 11. Парсер выталкивает 3 элемента (предикат/последовательный/альтернативный) и отбрасывает выбранный (в данном случае последующую ветвь), поэтому стек становится

1 2

4 - Используйте оставшиеся элементы:

1 2 + ------ > 3

3 4 + ------ > 7

Пример 2: 1 + ((0+0+0?0:0) ? 2 : (3 + 8)) + 4

RPN: 1 0 0 + 0 + 0 0 : ? 2 3 8 + : ? + 4 +

Оценка:

Начало:

После добавления 0 к 0:

После добавления 0 к 0:

После первого :? выбирает 0:

1 0 2 3 8 + : ? + 4 +

После добавления 3 и 8:

1 0 2 11 : ? + 4 +

После ?: выбирает 11:

1 11 + 4 +

После добавления 1 и 11:

12 4 +

Наконец:

16

Это может означать, что можно преобразовать выражение с помощью ?: в обратную полировку. Поскольку веб-страница говорит, что RPN и AST эквивалентны тому, что они могут быть преобразованы друг в друга и друг от друга, троичный оператор должен быть реализован с помощью восхождения по приоритету аналогичным образом.

Одна вещь, которая должна быть выполнена, кажется, является "приоритетом" (или приоритетом) оператора ?:. И я действительно сталкивался с этим при попытке преобразования RPN. Я дал вопросительные знаки и двоеточия самый низкий приоритет:

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

Ниже приведена таблица приоритета (приоритета).

! ~ > * / % > + - > & > ^ > | > && > || > ? > :

? и : имеют наименьший приоритет, что означает, что в выражениях типа 1? 2 + 3: 4 + 5, ? и : никогда не будут использоваться операнды вокруг них.

? предшествует : , чтобы сделать : перед ? в RPN. По моему мнению, это только выбор дизайна, потому что : и ? даже не обязательно должны сначала разбиваться на 2 оператора.

Надеюсь, что это поможет.

Ссылка: http://en.cppreference.com/w/cpp/language/operator_precedence

Ответ 3

Определите, что двоеточие имеет более низкий приоритет, чем знак вопроса. Другими словами, a? b: c будет анализироваться как (a? b): c. Это позволяет синтаксическому анализатору (if/then/empty-else) абстрактному синтаксису node, который затем будет использоваться оператором ":" для предоставления желаемого компонента.

Связи с приоритетами также сохраняют сложность оператора. Например, a? До нашей эры? d: e анализирует как (a? b): (c? d): e, как и следовало ожидать.

Надеюсь, что это поможет.