Как изменить семантические действия при удалении левой рекурсии из граммата

Question

Существует ли какой-либо алгоритм, который говорит нам, как изменить семантические действия, связанные с левой рекурсивной грамматикой? Например, у нас есть следующая грамматика и связанные с ней семантические действия:

$ S rightarrow id = expr $ {ss = expr.size}

S $ rightArrow $ if expr, то $ s_1 $ else $ s_2 $ {$ s_1.t = st + 2; $ $ S_2.t = st + 2; $ $ ss = expr.size + s_1.size + s_2.size + 2; $}

S $ rightArrow $ wies expr do $ s_1 $ {$ s_1.t = st + 4; $ $ ss = expr.size + s_1.s + 1; $}

S $ RightArrow $ $ S_1 $; $ S_2 $ {$ s_1.t = s_2.t = st; $ $ ss = s_1.s + s_2.s; $}

Очевидно, что нерекурсивная версия граммара такова:

S $ rightArrow $ id = expr t

S $ rightArrow $ if expr, то $ s_1 $ else $ s_2 $ t t t

S $ rightArrow $, пока экспрессируйте $ s_1 $ t

T $ rightarrow $; $ S_2 $ t

T $ rightarrow $ $ epsilon $

Но мы также должны соответственно изменить семантические действия. Есть идеи, как это можно сделать?

Answer 1

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

Answer 2

У меня есть частичное решение (я ищу общее). Если в вашей грамматике нет Epsilon Productions, то никакие непомощные не являются нулевыми. Это означает, что алгоритм для удаления левой рекурсии проходит (хотя он вводит Epsilon Productions).

Если вы добавите семантические действия действия формы (метка, граф), которые распознают пустую строку, используете сиятель смены/уменьшения и изучите все ** альтернативы, вообще нет необходимости реорганизовать дерево анализа. При анализе, если терминал распознается, он нажимает атрибут в стек анализатора, это действие сдвига. Когда возникает действие, оно вынимает значения n из стека и нажимает узел с указанной меткой, а значения выскочили из стека, в обратном направлении, как дети. Это сокращение действия.

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

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

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