Вы не получите хорошего ответа, если не зададите подробный c подробный вопрос. Вот расплывчатый набросок подхода.
Синтезированные атрибуты, очевидно, не являются проблемой для анализатора снизу вверх, поскольку они вычисляются в окончательном действии сокращения для соответствующего терминала. Итак, вопрос сводится к тому, «Как может анализатор снизу вверх вычислить унаследованные атрибуты?»
Поскольку грамматика является L-атрибутированной, мы знаем, что любой унаследованный атрибут вычисляется из атрибутов его левых братьев и сестер. Yacc / bison позволяет вставлять действия в любом месте с правой стороны, и эти «Действия среднего правила» (MRA) выполняются по мере их появления. MRA имеет в своем распоряжении именно своих братьев и сестер, так что это все, что нужно для вычисления унаследованного атрибута.
Однако это не показывает, как этот атрибут может быть на самом деле наследован. MRA, вставленный непосредственно перед символом грамматики в каком-то правиле, безусловно, может использоваться для частичного вычисления унаследованного атрибута этого символа, но унаследованный атрибут также может использовать синтезированные атрибуты дочерних элементов.
Для выполнения sh, что нам нужно сделать две вещи:
Вставить MRA непосредственно перед нетерминалом, который собирает вместе атрибуты левого брата. Поскольку MRA также являются грамматическими символами, этот MRA будет последним левым братом, по сути, самым младшим дядей из детей терминала. (Вам не обязательно нужен MRA; вы можете вставить «маркер»: нетерминал, чья единственная продукция пуста, а действие - это тело MRA. Но это не так удобно, потому что действие должно быть в семантике. c значения предыдущих грамматических символов. Или вы можете разделить производство на две части, чтобы оба действия были окончательными.)
Доступ к атрибутам дяди в действии сокращения терминала.
Bison / ya cc позволяют второй шаг, позволяя использовать индекс непопозитивных символов для ссылки на слоты в стеке анализатора. В частности, $0 относится к символу, непосредственно предшествующему нетерминалу в родительском производстве (то, что я назвал дядей выше). Конечно, чтобы это работало, вы должны убедиться, что дядя является одним и тем же нетерминалом (или, по крайней мере, имеет тот же тип semanti c) в каждом производстве, в котором появляется нетерминал. Это может потребовать добавления некоторых маркеров.
Говоря о значениях semanti c, вы можете быть уверены, что все дяди данного нетерминала одинаковы или, по крайней мере, имеют одинаковый тип. Но бизон не делает этот анализ, поэтому он не может предупредить вас, если вы ошиблись. Быть осторожен! И, как еще одно следствие, вы должны указать bison, какой это тип, так что вы не можете просто написать $0: вам нужно $<tag>0.
Примечание:
Не всегда возможно обрабатывать унаследованные атрибуты в L-атрибутной грамматике LR, потому что в момент, когда встречается нетерминал, синтаксический анализатор может еще не знать, что нетерминал будет фактически является частью дерева разбора. Эта проблема не возникает в грамматиках LL, потому что при синтаксическом анализе LL синтаксический анализатор может предсказать только нетерминал, который гарантированно будет присутствовать при разборе, если остальные входные данные верны.
Любая грамматика LL может анализировать снизу вверх, чтобы не было проблем с L-атрибутированными LL-грамматиками. Но анализатор снизу вверх может сделать это лучше; это не требует, чтобы полная грамматика была LL. Только те точки принятия решения для нетерминалов, которым предстоит присвоить унаследованный атрибут, должны быть LL-детерминированными c.
. Это ограничение применяется техникой размещения MRA или маркера непосредственно перед не-терминал. Другими словами, добавление маркера (или MRA) в определенных точках грамматики LR может сделать недействительным свойство LR. В руководстве по бизонам 1039 * подробно обсуждается этот вопрос, поэтому я не буду здесь подробно останавливаться на этом, за исключением одной детали.
Методика, описанная выше для распространения унаследованных атрибутов, использует MRA (или маркеры) в стратегиях c для хранения унаследованных атрибутов. Эти произведения должны быть сокращены, чтобы приступить к анализу, так как, как отмечено в вышеупомянутом разделе руководства по бизонам, может потребоваться изменить грамматику, чтобы устранить конфликты. В редких случаях такое переписывание невозможно даже.
Однако удаление конфликта может привести к грамматике, в которой передается унаследованный атрибут в случае, если какое-то нетерминальное значение требуется, без какой-либо гарантии того, что нетерминал со временем будет уменьшен. В этом случае унаследованный атрибут будет вычислен без необходимости, а затем проигнорирован. Но это не должно быть проблемой. Понятию атрибутов присуща идея, что атрибуты являются функциональными; другими словами, что вычисление не имеет побочных эффектов.
Отсутствие побочных эффектов означает, что синтаксический анализатор грамматики атрибута должен иметь возможность оценивать атрибуты в любом порядке, который учитывает зависимость атрибута. В частности, это означает, что вы можете легко добиться правильной оценки атрибутов, превратив вычисления атрибутов в продолжения, метод, который иногда называют ленивым вычислением или «thunking».
Но всегда есть соблазн использовать MRA. именно для того, чтобы выполнить побочные эффекты. Одним из распространенных побочных эффектов является печать трехадресного кода в выходной поток. Другим является мутирование постоянных структур данных, таких как таблицы символов. Это больше не L-атрибутный анализ, и поэтому предлагаемые здесь предложения могут не работать для таких приложений.