LR-атрибутивный парсер Техника

Question

Я хотел бы знать, что могут сделать парсерные парсы, которые могут быть LR, и как они реализованы.

Созданные yacc синтаксические анализаторы позволяют унаследованным атрибутам, когда источник атрибута является родным братом, который расположен слева, используя синтаксис спецификации $ 0, $ -1 и т. Д. С S -> A B B мог бы наследовать синтезированный атрибут от A, но не смог бы наследовать что-то из S. Я думаю, что это делается путем просмотра 1 элемента из B в стеке, который будет A.

Теперь zyacc doc says, что они допускают грамматики LR-атрибутов, которые, я думаю, более или менее такие же, как и yacc. Только то, что с zyacc эти атрибуты указаны с нетерминалом (например, параметры), а не только в семантическом действии. Существуют ли другие отличия, такие как LR-атрибуты, более сильные, чем унаследованные атрибуты yacc, или подобные LR-атрибуты реализованы по-разному (не просто глядя вниз на стек).

Answer 1

Точка атрибутов, приписываемых LR, состоит в том, чтобы сделать информацию в левом контексте, доступной для правомерного расширения.

Представьте, что ваша грамматика была

 R -> X S Y; 
     S -> A B; 

Вы уже согласились, что S может видеть атрибуты, синтезированные из X. В самом деле, эти атрибуты могут быть доступны по завершении разбора X. Было сделано правильно, эти атрибуты должны быть доступны для A и B по мере их анализа в качестве унаследованных атрибутов из S.

YACC не реализует ничего из этого, насколько мне известно, если вы не хотите считать существование дерева синтаксиса для X как «синтезированный» атрибут разбора X.

Как вы реализуете атрибутивные грамматики, зависит от того, что вы хотите сделать. Основной продукт нашей компании, DMS, сильно использует грамматики атрибутов, без ограничений по направлениям. Мы просто строим полное дерево и распространяем атрибуты по мере необходимости.

Мы делаем предварительные вычисления для каждого типа узлов, набора атрибутов [и их типов], которые он может наследовать, и набора, который он может синтезировать, и синтезировать структуру для каждого. При времени оценки атрибута эти структуры связаны с узлами дерева через хэш-таблицу с очень быстрым доступом. Для каждого типа узла мы проверяем потоки данных (какой ребенок использует тот, который унаследовал атрибут, дети используют синтезированные атрибуты, из которых другие дети). Из этого мы вычисляем порядок выполнения, чтобы вычислить все атрибуты в безопасном (сгенерированном перед потреблением) порядке и создать процедуру для этого для этого типа узла, который вызывает дочерние процедуры. Затем оценка атрибута состоит в вызове сгенерированной процедуры для корня грамматики. (Фактически, мы фактически генерируем частичный заказ для оценки детей и генерируем параллельный вызов частичного порядка с использованием возможностей параллельного языка программирования DMS, обеспечивая быструю оценку с использованием нескольких ядер на очень больших АСТ).

Нет причин, по которым вы не можете ограничить этот процесс атрибутами LR. (Когда-нибудь мы будем нажимать LR-совместимые атрибуты на фазу синтаксического анализа, чтобы позволить их использование в семантических проверках).

Не удивительно, что устройство, которое генерирует процесс оценки атрибутов, само по себе является атрибутором-оценщиком, который работает с грамматиками. Загрузочная игра была немного забавной.