Ответ 1
Я начну с того, как обычно работают парсеры. В общем случае парсер принимает входные токены в последовательном порядке. В какой-то момент (как правило, после того, как все токены исчерпаны), синтаксический анализатор возвращает результат. Один недостаток этой модели заключается в том, что она по своей сути является последовательной: поскольку парсер работает по последовательности токенов по порядку, неясно, как распараллелить процесс.
Однако разбор может быть распараллелен, если у нас есть доступ к операции, способной объединять частичные результаты синтаксического анализа в один результат. Например, если наш язык представлен с помощью контекстно-свободной грамматики, мы могли бы разобрать каждое определение верхнего уровня отдельно и параллельно, а затем собрать фрагменты позже, используя операцию объединения.
Моноидальный синтаксический анализ просто означает, что анализатор имеет доступ к подходящей функции объединения. Моноид - это структура с нулевым элементом и двоичным ассоциативным оператором. Например, списки образуют моноид, где нуль - пустой список, а ассоциативный оператор - конкатенация. Помните, что ассоциативность означает (a++b)++c == a++(b++c). Бывает, что это необходимое свойство, чтобы мы могли разумно рекомбинировать результаты синтаксического анализа. Точный порядок рекомбинации субпарасов не имеет значения, если каждый подпараметр хранится в правильной позиции последовательности.
Конечно, для написания параллельного парсера необходимо также разделить куски. Если вы хотите параллельно анализировать определения верхнего уровня, необходимо уметь распознавать, где это определение начинается. Эта задача обычно выполняется самим парсером. Насколько я помню, большая часть его слайдов охватывает эту тему. Разделение на определения верхнего уровня довольно крупнозернистое; в идеале наш синтаксический анализатор мог бы начать с любого произвольного токена, а затем извлечь смысл из фрагментов позже, когда применяется моноидный оператор.
К сожалению, я не могу сказать, что "моноидальный синтаксический анализ" является новым, поскольку я не особенно знаком с литературой. Однако я подозреваю, что любые модели или алгоритмы параллельного синтаксического анализа связаны с моноидной структурой, даже если она явно не указана. В течение некоторого времени было известно, что моноиды подходят для распараллеливания проблем, поэтому я не удивлюсь, если эта методика распространена среди исследователей парсеров.