Реализация атрибутных грамматик в технологии SYNTAX

• Автор: Лукичев, Александр Сергеевич
• Шифр специальности: 05.13.11, 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Санкт-Петербург
• Количество страниц: 117 с. : ил.

Оглавление
Введение.

Глава 1. Введение атрибутов.

Глава 2. Построение трансляции.

2.1. Введение атрибутов на прямом просмотре.

2.2. Введение атрибутов на обратном просмотре.

Глава 3. Применение атрибутных спецификаций

3.1. Алгоритмы процессирования и построения атрибутных процессоров .

3.2. Применение атрибутных грамматик в технологии X

Глава 4. Дополнительные возможности применения атрибутных спецификаций .

Заключение.
Список литературы


Выбор в качестве основы технологии SYNTAX определялся не только возможностью полнее раскрыть указанные теоретические аспекты, но и необходимостью устранения одно1Х) из серьезных, с точки зрения технологии программирования, недостатков SYNTAX: невозможности использования параметров у подпрограмм, реализующих семантические действия и резольверы. Цель работы заключается в разработке метода спецификации трансляций на атрибутных RBNF-грамматиках и его использовании в технологии синтаксически-управляемой обработки данных SYNTAX. Научная новизна. Построение диссертации. Основное содержание диссертации изложено в 4 главах. В ПЕРВОЙ ГЛАВЕ описаны подходы к описанию контекстно-зависимых языков на основе двухуровневых грамматик (аффиксные грамматики [], W-грамматики []) и к спецификации трансляции (атрибутная техника в КС-грамматиках []). Неформально в RBNF-спецификации системы SYNTAX вводятся атрибуты. Во ВТОРОЙ ГЛАВЕ дано формальное определение трансляции, задаваемой SYNTAX-спецификацией с использованием атрибутов (случай прямого просмотра), описание алгоритма сплайнового процессирования, приведены ограничения, накладываемые на атрибуты для обеспечения возможности их применения в сплайновом процессоре. Кроме того, описывается алгоритм обратного просмотра с использованием атрибутов, обсуждается вопрос передачи контекстной информации между просмотрами. В ТРЕТЬЕЙ ГЛАВЕ описывается модификация представления управляющих таблиц и алгоритма онлайнового процессирования, описанных в [4], с цслыо введения поддержки атрибутов. Рассмотрены примеры использования атрибутного подхода. В ЧЕТВЕРТОЙ ГЛАВЕ рассматриваются отдельные вопросы, которые не реализованы в разработанном прототипе системы, но, однако, могут быть реализованы с применением описанного атрибутного подхода. В ЗАКЛЮЧЕНИИ сформулированы основные выводы, полученные но результатам выполненных в диссертации исследований. Глава 1. Трансляция из языка Ь С в язык 1/2 С Т? С Ь х 1/2 [5]. На практике часто рассматривается обобщение этого определения, при котором трансляция определяет изменение состояния программы із зависимости от входного предложения. Существуют различные способы задания трансляций. Можно, например, задавать их в виде процедур на универсальных языках программирования. Спецификация в виде процедуры удовлетворяет только первому требованию. В современных системах построения трансляторов для задания синтаксиса входного языка наиболее часто используются грамматики Н. Хомского [С, 5], представляющие собой продукционную систему С = (Уу, Ух, Р, й), где Уя — алфавит нетерминалов, Уг — алфавит терминалов, Р — конечное множество правил вида а -»/? Удг и Ух)*, а € (Улг и Ух)* Ур), 5 € Улг — начальный нетерминал. В зависимости от от ограничений на форму правил выделяется 4 класса таких грамматик, вложенных последовательно один в другой. Тьюринга в том смысле, что для всякой грамматики типа 0 можно построить распознающую ее процедуру, а но всякой распознающей процедуре можно построить грамматику порождающую распознаваемый данной процедурой язык. Таким образом, грамматики тина 0 эквивалентны рекурсивно-перечислимым множествам, что творит об их большой выразительной мощности. Однако практическое использование таких грамматик сильно ограничено в виду отсутствия механизма построения эффективных анализаторов порождаемых ими языков. Таким образом, первое из указанных выше требований не выполняется. Чем уже класс грамматик, тем уже класс порождаемых ими языков, но тем более эффективный1 алгоритм анализа, а значит и трансляции, можно построить по спецификации. Поэтому на практике широко используется подкласс грамматик типа 0 — контекстно-свободные грамматики. Относительная простота позволяет применять для анализа контекстно-свободных языков эффективные (полиномиальные) алгоритмы. Так алгоритм Эрли (Earley), предназначенный для проведения анализа но произвольной КС-грамматике, имеет сложность 0(п3), где п — длина входной цепочки []. Еще более сильные ограничения на языки (LR(k) [, 5], LL(k) [, 5]) позволяют строить анализаторы, имеющие линейную сложность.