Разбор с пользовательским приоритетом оператора

ОК, поэтому здесь возникает вопрос: учитывая, что Haskell позволяет вам определять новые операторы с произвольным приоритетом оператора... как можно фактически анализировать исходный код Haskell?

Вы не можете знать, какие приоритеты операторов установлены до тех пор, пока вы не разобрали источник. Но вы не можете разобрать источник, пока не знаете правильные приоритеты операторов. Итак... мм, как?

Рассмотрим, например, выражение

x *** y +++ z

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

(x *** y) +++ z

Или он должен возвращать

x *** (y +++ z)

Плохой парсер не знает. Это можно определить только после того, как вы выведете импорт, который приносит (+++) и (***) в область видимости, загружает этот файл с диска и узнает, что такое приоритеты оператора. Очевидно, что сам анализатор не собирается делать все эти операции ввода-вывода; парсер просто превращает поток символов в АСТ.

Очевидно, кто-то где-то выяснил, как это сделать. Но я не могу это решить... Любые подсказки?

Ответ 1

Цитирование страницы на трассе GHC для синтаксического анализатора:

Операторы Infix анализируются так, как будто они все лево-ассоциативные. renamer использует объявления фиксации для повторного ассоциирования дерева синтаксиса.

Ответ 2

Ответ András Kovács говорит, что действительно сделано в GHC, но есть какая-то история.

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

В частности, вы можете переопределить локальный оператор и его фиксированность, чтобы его использование имело место при повторном определении внутреннего блока where точно... когда этого не произошло. Итак, вы получили парадокс парсера. Я не могу найти ни одного из старых примеров, но это может быть один:

let (+) = (Prelude.+)
    infix 9 + -- make the inner + high precedence and non-associative
in 2 + 3 + 4
--       ^ this + cannot parse here as the inner operator, which means
--         the let ... in ... expression should end automatically first,
--         but then it the standard +, and its fixity says it should parse
--         as part of the inner expression...

В Haskell 2010 они официально изменили это так, что фиксированность оператора определяется на отдельном этапе после собственно разбора.

Так почему же это гипотетическое изменение? Поскольку все авторы компилятора уже сделали это способом Haskell 2010 и всегда имели, для их собственного здравомыслия.

Ответ 3

Подводя итог комментариям, кажется, что возможности таковы:

Возвращает дерево синтаксического анализа, где любые операторы infix оставлены как некоторая структура списка, а затем переупорядочиваются после того, как становятся известными предшественники.
Представьте, что вы знаете приоритеты операторов, а затем измените дерево разбора после факта.
Сделайте первый синтаксический анализ, который только считывает объявления импорта и фиксации, загружает импорт, а затем выполняет полный анализ с известными приоритетами.