Существуют ли какое - либо программирование (или сценарии) язык (или домен конкретного языка) , имеющие два бинарных операторов opl
и opr
в том же старшинство с opl
того левоассоциативными и opr
быть правоассоциативным?
(Я не могу найти такой пример, но я пытаюсь закодировать некоторый общий синтаксический анализатор, чтобы справиться с этим странным случаем)
Как бы проанализировать выражения вида x opl
y opr
z или x opr
y opl
z ? И вообще с еще большим количеством операндов?
language-design
parsing
Василий Старынкевич
источник
источник
x <@ y @> z
с<@
того левоассоциативным и@>
быть правоассоциативным, GHC дает вам «ошибку анализа Precedence»: «не может смешивать„<@
“[infixl 0] и„@>
“[infixr 0] в том же выражении инфиксного» (где я определен эти операторы на уровне 0 для примера).if_then_else_
или[1;2;3]
определяемые в библиотеках?).Ответы:
Вот три языка, которые позволяют вам определять своих собственных операторов, которые делают две с половиной разные вещи! Haskell и Coq оба запрещают эти виды махинаций - но по-разному - в то время как Agda допускает такое смешение ассоциаций.
Во-первых, в Haskell вам просто не разрешено это делать. Вы можете определить свои собственные операторы и дать им приоритет (от 0 до 9) и ассоциативность по вашему выбору. Тем не менее, отчет Haskell запрещает вам смешивать ассоциации :
Таким образом, в GHC , если мы определим левоассоциативный
infixl
оператор ( )<@
и правоассоциативный оператор@>
на одном и том же уровне приоритета - скажем, 0 - тогда вычислениеx <@ y @> z
даст ошибку(На самом деле, вы также можете объявить оператор инфиксным, но неассоциативным, например
==
, так чтоx == y == z
это синтаксическая ошибка!)С другой стороны, есть агда-зависимый провайдер языка / теорем Agda (который, по общему признанию, является значительно менее распространенным). Agda имеет один из самых податливых синтаксисов из всех известных мне языков, поддерживающих операторы mixfix : стандартная библиотека содержит функцию
который при вызове написан
с аргументами, заполняющими подчеркивание! Я упоминаю об этом, потому что это означает, что он должен поддерживать невероятно гибкий анализ. Естественно, Agda также имеет декларации фиксированности (хотя ее уровни приоритета варьируются по произвольным натуральным числам и обычно находятся в диапазоне от 0 до 100), и Agda действительно позволяет смешивать операторы с одинаковым приоритетом, но с разными фиксированностями. Однако я не могу найти информацию об этом в документации, поэтому мне пришлось экспериментировать.
Давайте использовать наши
<@
и@>
сверху. В двух простых случаях мы имеемx <@ y @> z
разбор какx <@ (y @> z)
; иx @> y <@ z
разбор как(x @> y) <@ z
.Я думаю, что Агда группирует строку в «левый ассоциативный» и «правый ассоциативный» чанки, и - если я не думаю о неправильных вещах - правый ассоциативный чанк получает «приоритет» при захвате смежных аргументов. Так что это дает нам
разбор как
или же
Однако, несмотря на мои эксперименты, я догадался неправильно, когда впервые написал это, что может быть поучительно :-)
(А у Agda, как и у Haskell, есть неассоциативные операторы, которые правильно выдают ошибки разбора, поэтому смешанные ассоциации могут также привести к ошибке разбора.)
Наконец, существует язык Coq для проверки теорем / зависимо-типизированного типа , который имеет даже более гибкий синтаксис, чем Agda, потому что его синтаксические расширения фактически реализованы путем предоставления спецификаций для новых синтаксических конструкций и затем переписывания их в основной язык (смутно похожий на макрос , Я предполагаю). В Coq синтаксис списка
[1; 2; 3]
- это необязательный импорт из стандартной библиотеки. Новые синтаксисы могут даже связывать переменные!Еще раз, в Coq, мы можем определить наши собственные инфиксные операторы и дать им уровни приоритета (в основном от 0 до 99) и ассоциативности. Однако в Coq каждый уровень приоритета может иметь только одну ассоциативность . Поэтому, если мы определим
<@
как левоассоциативную, а затем попытаемся определить@>
как ассоциативную справа на том же уровне - скажем, 50 - мы получимБольшинство операторов в Coq находятся на уровнях, которые делятся на 10; если у меня были проблемы ассоциативности (эти ассоциации уровня глобальны), я обычно просто увеличивал уровень на единицу в любом направлении (обычно вверх).
источник
graphviz
??)\ttfamily \Tree[.<@ [.<@ [.<@ a b ] [.@> c [.@> d [.@> e f ]]]] g ]
.С тех пор, как они были популяризированы Дугласом Крокфордом, парсеры Pratt (или парсеры приоритетов операторов сверху вниз) стали более распространенными. Эти синтаксические анализаторы работают с таблицей приоритетов операторов и ассоциативности, а не с правилами, встроенными в фиксированную грамматику, поэтому они полезны для языков, которые позволяют пользователям определять свои собственные операторы.
У них есть функция синтаксического анализа, которая работает, сначала разбирая крайний левый член выражения, а затем рекурсивно связывая новые операторы и правые термины, пока они связываются соответствующим образом. Левоассоциативные операторы будут связывать правые термины, которые имеют приоритет до одного и того же приоритета, в то время как правоассоциативные операторы только связываются с их уровнем приоритета, но не включают его. Я считаю, что это приводит к тому же самому дереву разбора, что и для Agda, приведенному выше.
источник