язык с двумя бинарными операторами одинакового приоритета, левоассоциативный и правосторонний

11

Существуют ли какое - либо программирование (или сценарии) язык (или домен конкретного языка) , имеющие два бинарных операторов oplи oprв том же старшинство с oplтого левоассоциативными и oprбыть правоассоциативным?

(Я не могу найти такой пример, но я пытаюсь закодировать некоторый общий синтаксический анализатор, чтобы справиться с этим странным случаем)

Как бы проанализировать выражения вида x opl y opr z или x opr y opl z ? И вообще с еще большим количеством операндов?

Василий Старынкевич
источник
4
Если это больно, не делай этого.
CodesInChaos
1
В Haskell вы можете определять свои собственные инфиксные операторы с их собственными приоритетами, и в этом случае вы получаете ошибку; если у вас есть x <@ y @> zс <@того левоассоциативным и @>быть правоассоциативным, GHC дает вам «ошибку анализа Precedence»: «не может смешивать„ <@“[infixl 0] и„ @>“[infixr 0] в том же выражении инфиксного» (где я определен эти операторы на уровне 0 для примера).
Антал Спектор-Забуский,
@ AntalSpector-Zabusky: Это был бы отличный ответ!
Василий Старынкевич
@ AntalSpector-Zabusky: То же самое в Swift. Я думаю, что вы можете определить операторы, но в выражении вы должны использовать все левые ассоциативные или все правые ассоциативные операторы с одинаковым приоритетом. Таким образом, вы можете использовать x leftop y leftop z или x righttop y righttop z, но не x x leftop y righttop z.
gnasher729
@BasileStarynkevitch: Как вы хотите! Так как вы упомянули «гибкие парсеры», я включил несколько более непонятных языков, которые имеют очень гибкие парсеры (когда-либо желаемые if_then_else_или [1;2;3]определяемые в библиотеках?).
Antal Spector-Zabusky

Ответы:

10

Вот три языка, которые позволяют вам определять своих собственных операторов, которые делают две с половиной разные вещи! Haskell и Coq оба запрещают эти виды махинаций - но по-разному - в то время как Agda допускает такое смешение ассоциаций.


Во-первых, в Haskell вам просто не разрешено это делать. Вы можете определить свои собственные операторы и дать им приоритет (от 0 до 9) и ассоциативность по вашему выбору. Тем не менее, отчет Haskell запрещает вам смешивать ассоциации :

Последовательные операторы без скобок с одинаковым приоритетом должны быть либо левыми, либо правыми, чтобы избежать синтаксической ошибки. [Haskell 2010 Report, Ch. 3]

Таким образом, в GHC , если мы определим левоассоциативныйinfixl оператор ( ) <@и правоассоциативный оператор @>на одном и том же уровне приоритета - скажем, 0 - тогда вычисление x <@ y @> zдаст ошибку

Ошибка разбора приоритета
    не может смешивать ' <@' [ infixl 0] и ' @>' [ infixr 0] в одном и том же инфиксном выражении

(На самом деле, вы также можете объявить оператор инфиксным, но неассоциативным, например ==, так что x == y == zэто синтаксическая ошибка!)


С другой стороны, есть агда-зависимый провайдер языка / теорем Agda (который, по общему признанию, является значительно менее распространенным). Agda имеет один из самых податливых синтаксисов из всех известных мне языков, поддерживающих операторы mixfix : стандартная библиотека содержит функцию

if_then_else_ : ∀ {a} {A : Set a} → Bool → A → A → A

который при вызове написан

if b then t else f

с аргументами, заполняющими подчеркивание! Я упоминаю об этом, потому что это означает, что он должен поддерживать невероятно гибкий анализ. Естественно, Agda также имеет декларации фиксированности (хотя ее уровни приоритета варьируются по произвольным натуральным числам и обычно находятся в диапазоне от 0 до 100), и Agda действительно позволяет смешивать операторы с одинаковым приоритетом, но с разными фиксированностями. Однако я не могу найти информацию об этом в документации, поэтому мне пришлось экспериментировать.

Давайте использовать наши <@и @>сверху. В двух простых случаях мы имеем

  • x <@ y @> zразбор как x <@ (y @> z); и
  • x @> y <@ zразбор как (x @> y) <@ z.

Я думаю, что Агда группирует строку в «левый ассоциативный» и «правый ассоциативный» чанки, и - если я не думаю о неправильных вещах - правый ассоциативный чанк получает «приоритет» при захвате смежных аргументов. Так что это дает нам

a <@ b <@ c @> d @> e @> f <@ g

разбор как

(((a <@ b) <@ (c @> (d @> (e @> f)))) <@ g

или же

Дерево разбора <code> (((a <@ b) <@ (c @> (d </ code> @> (e @> f)))) <@ g

Однако, несмотря на мои эксперименты, я догадался неправильно, когда впервые написал это, что может быть поучительно :-)

(А у Agda, как и у Haskell, есть неассоциативные операторы, которые правильно выдают ошибки разбора, поэтому смешанные ассоциации могут также привести к ошибке разбора.)


Наконец, существует язык Coq для проверки теорем / зависимо-типизированного типа , который имеет даже более гибкий синтаксис, чем Agda, потому что его синтаксические расширения фактически реализованы путем предоставления спецификаций для новых синтаксических конструкций и затем переписывания их в основной язык (смутно похожий на макрос , Я предполагаю). В Coq синтаксис списка [1; 2; 3]- это необязательный импорт из стандартной библиотеки. Новые синтаксисы могут даже связывать переменные!

Еще раз, в Coq, мы можем определить наши собственные инфиксные операторы и дать им уровни приоритета (в основном от 0 до 99) и ассоциативности. Однако в Coq каждый уровень приоритета может иметь только одну ассоциативность . Поэтому, если мы определим <@как левоассоциативную, а затем попытаемся определить @>как ассоциативную справа на том же уровне - скажем, 50 - мы получим

Ошибка: 50-й уровень уже объявлен левоассоциативным, а теперь ожидается, что он ассоциирован справа

Большинство операторов в Coq находятся на уровнях, которые делятся на 10; если у меня были проблемы ассоциативности (эти ассоциации уровня глобальны), я обычно просто увеличивал уровень на единицу в любом направлении (обычно вверх).

Антал Спектор-Забуский
источник
2
(Ну и дела, какой странный выбор языков. Можете ли вы сказать, что я изучаю теорию языков программирования? :-P)
Antal Spector-Zabusky
Большое спасибо за ваш подробный ответ. Кстати, как вы нарисовали картинку (с помощью какого инструмента graphviz??)
Василий Старынкевич,
Кстати, почему «фикс» вместо «приоритет»?
Василий Старынкевич
@BasileStarynkevitch: Это зависит от того, где вы имеете в виду. Если вы имеете в виду в разделе Coq, это была просто ошибка :-) (И та, которая сейчас исправлена!)
Antal Spector-Zabusky
1
@BasileStarynkevitch: Кроме того, я пропустил ваш вопрос о картине! Я нарисовал это с помощью пакета LaTeX qtree и отобразил его в LaTeXit , рендерере фрагментов LaTeX для Mac. Соответствующий исходный код был \ttfamily \Tree[.<@ [.<@ [.<@ a b ] [.@> c [.@> d [.@> e f ]]]] g ].
Антал Спектор-Забуский,
2

С тех пор, как они были популяризированы Дугласом Крокфордом, парсеры Pratt (или парсеры приоритетов операторов сверху вниз) стали более распространенными. Эти синтаксические анализаторы работают с таблицей приоритетов операторов и ассоциативности, а не с правилами, встроенными в фиксированную грамматику, поэтому они полезны для языков, которые позволяют пользователям определять свои собственные операторы.

У них есть функция синтаксического анализа, которая работает, сначала разбирая крайний левый член выражения, а затем рекурсивно связывая новые операторы и правые термины, пока они связываются соответствующим образом. Левоассоциативные операторы будут связывать правые термины, которые имеют приоритет до одного и того же приоритета, в то время как правоассоциативные операторы только связываются с их уровнем приоритета, но не включают его. Я считаю, что это приводит к тому же самому дереву разбора, что и для Agda, приведенному выше.

Жюль
источник