Параллельные алгоритмы синтаксического анализа

Question

Существуют ли алгоритмы синтаксического анализа (аналогичные LALR, SLR и LL), которые могут анализировать один вход, а не только несколько входов, параллельно?

Редактировать: Извините, я на самом деле не искал исследовательские работы, скорее, "Есть компиляторы-компиляторы, которые генерируют параллельные парсеры" или "Этот компилятор для этого языка анализирует его параллельно" - примеры из реального мира. *

Answer 1

Известных нет: -}

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

Можно представить представление массива токенов сразу для одного парсера, а затем иметь синтаксический анализ подстрок в разных точках массива, сшивая совместимые деревья для подстрок.все вместе.Процесс сшивания, вероятно, будет сложным, но может быть управляемым, если управляется синтаксическим анализатором L (AL) R [лучше GLR], который проглатывал нетерминалы слева направо после того, как было создано большинство деревьев разбора для подстрок;думайте об этом как о «аккумуляторе».

[Шейдс, быстрый поиск в Google выдает 1990 японскую статью о выполнении параллельного GLR с тем, что равносильно прологу ]

Теперь у вас есть проблема создания магического параллельного набора токенов.Теперь вам нужен параллельный лексер: -}

РЕДАКТИРОВАТЬ Июнь 2013: я наконец-то вспомнил статью МакКимана 1982 года о параллельном разборе LR .

Answer 2

Я работаю над детерминированным контекстно-свободным алгоритмом синтаксического анализа с O (N) сложностью работы, O (log N) временной сложностью, детализированным параллелизмом, который пропорционален длине входной строки, и эквивалентным поведением для LR parser. Я отправлю его на рецензию в ближайшее время.

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

Существует некоторая сложность, связанная с обработкой токенов с подстановочными знаками, которые могут частично вкладываться, и необходим шаг постобработки для их обработки и поддержания сложности O (log N) в худшем случае. Этот шаг, вероятно, не нужен на практике.