Haskell допускает только несколько уровней приоритета.Так что вам не нужна динамическая грамматика;Вы могли бы просто написать грамматику, используя классы токенов уровня приоритета вместо отдельных операторов, оставив лексеру проблему с ассоциированием данного символа с заданным уровнем приоритета.
По сути, это перемещает динамическое добавлениеоператоры для лексера.Это немного неудобное дизайнерское решение, хотя в некоторых случаях оно может быть не слишком сложным для реализации.Это неудобный дизайн, потому что он требует семантической обратной связи с лексером;как минимум, лексеру нужно обратиться к таблице символов, чтобы выяснить, на какой тип токена он смотрит.По крайней мере, в случае с Haskell это становится более неудобным из-за того, что декларации фиксированности ограничены, поэтому для отслеживания информации о фиксированности лексеру также необходимо понимать правила области видимости.
На практике,большинство языков, которые позволяют программному тексту определять операторы и приоритет операторов, работают точно так же, как это делает компилятор Haskell: выражения разбираются грамматикой в простой список элементов (где заключенные в скобки подвыражения считаются одним элементом), а в более позднемПри семантическом анализе список преобразуется в фактическое дерево с учетом правил приоритета и ассоциативности, используя простую версию алгоритма маневрового двора.(Это простая версия, потому что она не должна иметь дело с заключенными в скобки подконструкциями.)
Есть несколько причин для этого проектного решения:
Как упомянуто выше, длялексер, чтобы выяснить, каков приоритет символа (или даже если символ является оператором с приоритетом), требует тесного сотрудничества между лексером и синтаксическим анализатором, что, по мнению многих, нарушает разделение задач.Хуже того, это затрудняет или делает невозможным использование технологий синтаксического анализа без небольшого фиксированного просмотра, таких как анализаторы GLR.
Многие языки имеют больше уровней приоритета, чем Haskell.В некоторых случаях даже количество уровней приоритета не определяется грамматикой.Например, в Swift вы можете объявить свои собственные уровни приоритета и определить уровень не с числом, а со сравнением с другим ранее определенным уровнем, что приведет к частичному порядку между уровнями приоритета.
ИМХО, это на самом деле лучшее проектное решение, чем Haskell, отчасти потому, что он позволяет избежать двусмысленности уровня приоритета, имеющего как левую, так и правую ассоциативные операторы, но что более важно, потому что объявления относительного приоритета избегают магических чисел и позволяютпарсер для отметки неоднозначного использования операторов из разных модулей.Другими словами, это не заставляет механически применяться объявление приоритета к любой паре совершенно не связанных операторов;в этом смысле это упрощает составление операторов.
Грамматика намного проще и, возможно, легче для понимания, так как большинство людей в любом случае полагаются на таблицы приоритетов, а не анализируют грамматические произведения для выяснениякак операторы взаимодействуют друг с другом.В этом смысле наличие приоритета, установленного грамматикой, больше отвлекает, чем документация.См. Грамматику C ++ как хороший пример того, почему таблицы приоритетов легче читать, чем грамматики.
С другой стороны, как показывает и грамматика C ++, грамматика намного более общая, чем простые объявления предшествования, потому что онаможет выражать асимметричные приоритеты.(Грамматика не всегда выражает их изящно, но они могут быть выражены.) Классическим примером асимметричного приоритета является лямбда-конструкция (λ ID expr), которая очень слабо связывается справа и очень плотно слева: ожидаемыйанализ a ∘ λ b b ∘ a никогда не обращается к ассоциативности ∘, потому что между ними стоит λ.
На практике, построить дерево позже будет очень мало.Алгоритм построения дерева хорошо известен, прост и дешев.