Обобщенные анализаторы снизу вверх в Хаскеле

Question

Меня интересует, почему в Haskell нет обобщенных синтаксических анализаторов для анализа снизу вверх, как комбинаторы Parsec для синтаксического анализа сверху вниз.
(Я мог найти какую-то исследовательскую работу в 2004 году, но ничего после
https://haskell-functional-parsing.googlecode.com/files/Ljunglof-2002a.pdf http://www.di.ubi.pt/~jpf/Site/Publications_files/technicalReport.pdf)

Есть ли какая-то конкретная причина не достичь этого?

Answer 1

Это из-за ссылочной прозрачности. Так же, как никакая функция не может определить разницу между

let x = 1:x
let x = 1:1:1:x
let x = 1:1:1:1:1:1:1:1:1:...  -- if this were writeable

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

Тот факт, что анализаторы сверху вниз видят свои входные данные как бесконечные деревья, позволяет им быть более мощными, поскольку дерево может быть вычислительно сложнее, чем любой граф; например,

numSequence n = string (show n) *> option () (numSequence (n+1))

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

Библиотеку комбинатора снизу вверх можно было бы написать, хотя это немного уродливо, если бы все парсеры были "помечены" таким образом, чтобы

• одна и та же метка всегда относится к одному и тому же парсеру, и
• есть только конечный набор меток

с этого момента он начинает больше походить на традиционную спецификацию грамматики, чем комбинаторную спецификацию. Тем не менее, это все еще может быть приятно; вам нужно будет только маркировать рекурсивные продукты, что исключит любые бесконечно большие правила, такие как numSequence,

Answer 2

Как показывает ответ Люки, библиотека комбинатора синтаксического анализа снизу вверх не является реалистичной. При вероятности того, что кто-то попадет на эту страницу в поисках восходящего генератора синтаксического анализатора haskell, то, что вы ищете, называется генератором счастливого синтаксического анализатора. Это как yacc для Haskell.

Answer 3

Как сказал Луки выше: обработка Хаскеллом рекурсивных определений синтаксического анализатора не позволяет определять восходящие библиотеки синтаксического анализа. Библиотеки синтаксического анализа снизу вверх возможны, хотя, если вы представляете рекурсивные грамматики по-другому. С извинениями за саморекламу, одна (исследовательская) библиотека синтаксических анализаторов, которая использует такой подход, - это грамматические комбинаторы. Он реализует грамматическое преобразование, называемое равномерным преобразованием Полла, которое можно комбинировать с алгоритмом синтаксического анализа сверху вниз для получения синтаксического анализатора снизу вверх для исходной грамматики.

Answer 4

@luqui, по сути, говорит, что есть случаи, когда совместное использование не наблюдается. Однако в целом дело обстоит иначе: существует множество подходов к наблюдаемому обмену. Например, http://www.ittc.ku.edu/~andygill/papers/reifyGraph.pdf упоминает несколько различных методов для достижения заметного обмена и предлагает свой собственный новый метод:

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

Обратите внимание, что "уродливое" решение @liqui упоминается в статье под названием явных меток. Решение, предложенное в документе, все еще "безобразно", поскольку использует так называемые "стабильные имена", но есть и другие решения, такие как http://www.cs.utexas.edu/~wcook/Drafts/2012/graphs.pdf (который полагается на PHOAS) может работать.