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

Question

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

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

• Узлы графа являются LR items, как A → B • C
• Края "переходы", начиная с A → B • C в C → • D

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

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

Answer 1

Я не думаю, что вы можете использовать алгоритм Варшалла для этого, потому что каждый раз, когда вы добавляете новый элемент, вам, возможно, придется добавлять другие элементы. Это итеративный процесс. Ориентированный граф или матрица связности будут меняться. Я мог ошибаться. Я вычислил закрытие наборов элементов LR (1) итеративным процессом, сохраняя массив элементов, уже включенных в набор замыканий. Вы можете загрузить мой LRSTAR Parser Generator и посмотреть исходный код, если хотите. Вы можете решить, что вам не нужно писать собственный генератор синтаксического анализатора и использовать LRSTAR. Примечание. Я использовал алгоритм Digraph из документа DeRemer вместо алгоритмов Варшалла для вычисления перспективных множеств. См. list of papers implemented in LRSTAR on the website.