Если вы можете построить дерево синтаксического анализа снизу вверх слева направо, то вы можете вычислить L-атрибуты. Это тавтология, потому что L-атрибуты - это те атрибуты, которые вы можете вычислять снизу вверх слева направо. Как вам удастся выполнить синтаксический анализ, не имеет значения.
Обобщенные алгоритмы синтаксического анализа LR позволяют анализировать снизу вверх слева направо, при условии, что в данный момент может быть доступно более одного возможного синтаксического анализа . (Фактически, если грамматика не обязана быть однозначной, возможно более одного синтаксического анализа всего ввода.)
На практике вычисление атрибутов для узлов синтаксического анализа до того, как вы узнаете, что они являются частью финальный синтаксический анализ может быть крайне неэффективным. Также на практике здесь можно было бы вставить предупреждение о действиях с побочными эффектами, но вычисление атрибута узла синтаксического анализа само по себе не является побочным эффектом, и если он оказывает какое-либо другое влияние на вселенную, мы больше не находимся в территория математической теории.
Более того, если грамматика недвусмысленна, количество возможных синтаксических разборов может быть экспоненциальным по отношению к длине ввода. Большинство обобщенных алгоритмов LR строят графы разбора, а не деревья синтаксического анализа, что можно сделать, используя только полиномиальное пространство для представления экспоненциального числа возможных деревьев. Но для этого требуется совместное использование узлов между разными синтаксическими анализаторами, что может оказаться невозможным при вычислении атрибутов, поскольку узлы, которые будут использоваться совместно, могут иметь разные атрибуты. вопрос о побочных эффектах, упомянутых выше, потому что на самом деле вычисление значения атрибута для узла не может быть побочным эффектом. Если вы создаете постоянную структуру (дерево синтаксического анализа), которую можно наблюдать во время ее построения, то присвоение атрибута компоненту этой структуры, безусловно, является побочным эффектом. С другой стороны, если структура не видна извне во время ее создания, то не имеет значения, когда вы назначаете атрибуты компонентам. В этом случае было бы лучше думать о L-атрибутах как о тех атрибутах, которые могут быть вычислены за один проход слева направо (полностью построенное) дерева синтаксического анализа с первым перемещением в глубину.