Как использовать алгоритм Уоршелла для транзитивного закрытия, чтобы определить канонические замыкания синтаксического анализатора LR (1)?

Я пытаюсь реализовать алгоритм Уоршалла для быстрого вычисления замыканий LR(1).

Думаю, я понимаю, как это работает для LR(0):

  • Узлы графа — это элементы LR, например A → B • C
  • Ребра являются «переходами», начиная с A → B • C до C → • D

Проблема в том, что LR(1) требует вычисления опережающего просмотра, и я не могу понять, как включить их в алгоритм.
Мне кажется, что даже если я знаю транзитивное замыкание любого заданного элемента LR мне все еще нужно выполнить все те же вычисления только для того, чтобы выяснить, какой упреждающий набор для каждого элемента.

Можно ли вообще использовать алгоритм Уоршелла для вычисления канонических замыканий LR(1) или это возможно только для более ограниченных случаев (таких как LR(0), SLR(1) и т. д.)?


parsing floyd-warshall lr transitive-closure
person user541686    schedule 08.06.2013    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Я не думаю, что вы можете использовать для этого алгоритм Уоршалла, потому что каждый раз, когда вы добавляете новый элемент, вам, возможно, придется добавлять другие элементы. Это повторяющийся процесс. Ориентированный граф или матрица связности будут постоянно меняться. Я могу ошибаться в этом. Я вычислил закрытие наборов элементов LR(1) с помощью итеративного процесса, сохраняя при этом массив элементов, уже включенных в набор замыкания. Вы можете скачать мой генератор синтаксического анализатора LSTAR и решить, что вам не нужно писать собственный генератор синтаксического анализа. Примечание. Я использовал алгоритм Диграфа из статьи ДеРемера вместо алгоритма Уоршалла для вычисления упреждающих множеств. См. список документов, реализованных в LRSTAR.

person Community    schedule 13.05.2014
comment
+1 спасибо! На самом деле (много времени спустя) я перестал использовать какой-либо конкретный алгоритм, потому что чем дольше я смотрел на него, тем меньше возможностей для улучшения я видел. В итоге я сделал свой собственный генератор парсеров LR(k), хотя это было довольно мучительно! (Это работает для каждого k, но может занять экспоненциально долгое время для k в зависимости от грамматики.) - person user541686; 13.05.2014