Моноидальный разбор - что это?

Я просто наткнулся на термин моноидальный синтаксический анализ слайд под названием "Введение в моноиды" Эдвард Кемт. Слайд использует haskell повсюду.

Теперь, когда я искал термин, я не нашел ничего, кроме очень немногих упоминаний об этом, и больше всего от того же автора. Поэтому я думаю, что этот термин можно объяснить здесь.

Итак, моноидальный разбор чего-то интересного и нового? Является ли это появлением где угодно, кроме как на слайде, к которому я привязан? И самое главное, что это? Сам слайд, похоже, не дал определения и не выделял его настолько.

Ответ 1

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

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

Моноидальный синтаксический анализ просто означает, что анализатор имеет доступ к подходящей функции объединения. Моноид - это структура с нулевым элементом и двоичным ассоциативным оператором. Например, списки образуют моноид, где нуль - пустой список, а ассоциативный оператор - конкатенация. Помните, что ассоциативность означает (a++b)++c == a++(b++c). Бывает, что это необходимое свойство, чтобы мы могли разумно рекомбинировать результаты синтаксического анализа. Точный порядок рекомбинации субпарасов не имеет значения, если каждый подпараметр хранится в правильной позиции последовательности.

Конечно, для написания параллельного парсера необходимо также разделить куски. Если вы хотите параллельно анализировать определения верхнего уровня, необходимо уметь распознавать, где это определение начинается. Эта задача обычно выполняется самим парсером. Насколько я помню, большая часть его слайдов охватывает эту тему. Разделение на определения верхнего уровня довольно крупнозернистое; в идеале наш синтаксический анализатор мог бы начать с любого произвольного токена, а затем извлечь смысл из фрагментов позже, когда применяется моноидный оператор.

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

Ответ 2

Попробуйте его другое представление на этой странице, это номер два после того, который вы читаете. Это что-то новое, и все, что я действительно могу сделать, это перефразировать его слайды и сказать вам, что это попытка сделать монадический синтаксический разбор (например, Parsec) и использовать более слабую алгебраическую структуру, чтобы было больше возможностей для реструктуризации вычислений. Идея заключается в улучшении parallelism.

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