Реализация атрибутных грамматик в технологии SYNTAX тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Лукичев, Александр Сергеевич

• Лукичев, Александр Сергеевич
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Лукичев, Александр Сергеевич

Введение.

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

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

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

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

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

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

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

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

Введение диссертации (часть автореферата) на тему «Реализация атрибутных грамматик в технологии SYNTAX»

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

Для решения задачи построения трансляции используются системы построения трансляторов, наиболее распространенными из которых являются средства, основанные на применении грамматик для описания входного языка. С правилами .таких грамматик связываются семантические правила, служащие для вычисления результата трансляции. Для передачи данных между семантическими правилами могут использоваться атрибуты, введенные Д. Кнутом [15]. Технически этот метод предполагает построение дерева разбора входного предложения в данной КС-грамматике, а затем вычисление значений атрибутов в каждой вершине этого дерева по семантическим правилам, связанным с правилами грамматики, участвующими в разборе.

Начиная с конца 60-х годов, для определения синтаксиса КС-языков применяются также синтаксические диаграммы (синтаксические графы) Вирта [3] и ШШР-грамматики. Каждому нетерминалу соответствует одна компонента диаграммы или одно правило 11ЕШР-грамматики, правая часть которого — регулярное выражение относительно символов объединенного алфавита грамматики.

Возникает задача спецификации трансляции с использованием RBNF-грам-матик в качестве синтаксической основы. Технологии, использующие явно RBNF-грамматики, обычно неявно преобразуют данную грамматику в эквивалентную однозначную КС-грамматику. В технологии SYNTAX [4], использующей граф-схемы (аналоги диаграмм Вирта) и RBNF-грамматики в качестве синтаксического базиса, применяется другой подход. Здесь регулярные выражения в правых частях правил грамматики явно интерпретируются. Кроме того, данная технология позволяет задавать трансляции с контекстно-зависимых языков и использовать синтаксически-неоднозначные входные грамматики.

Передача данных между семантическими действиями в технологии SYNTAX не специфицируется на уровне грамматики. Задачей данной работы является реализация атрибутов в SYNTAX для обеспечения возможности задания потоков данных средствами атрибутных RBNF-грамматик. Актуальность темы следует из перечисленных ниже аргументов: во-первых, использование атрибутов в RBNF-грамматиках требует специального оформления правил грамматик и разработки метода применения атрибутов в механизме реализации трансляции; во-вторых, анализ на RBNF-грамматиках при линейном ограничении времени относительно длины входной цепочки приводит к ограничениям на класс применяемых грамматик и, как следствие, на использование атрибутов. Данные ограничения следует определить с учетом используемого механизма анализа; в-третьих, SYNTAX позволяет задавать контекстно-зависимые языки. Это достигается введением резольверов — предикатов, ограничивающих выбор альтернатив при анализе в зависимости от контекста. Атрибуты могут использоваться для задания этого контекста; в-четвертых, ограничения, накладываемые на RBNF-грамматики в SYNTAX, позволяют использовать синтаксически-неоднозначные грамматики. Для уточнения синтаксической структуры входного предложения может применяться обратный просмотр, где также могут использоваться атрибуты.

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

Цель работы заключается в разработке метода спецификации трансляций на атрибутных RBNF-грамматиках и его использовании в технологии синтаксически-управляемой обработки данных SYNTAX.

Научная новизна. Впервые атрибутная техника применяется непосредственно в RBNF-грамматиках для построения средств синтаксически-управляемой обработки данных в контексте следующих особенностей алгоритма трансляции:

• атрибуты вычисляются на не полностью построенном дереве вывода;

• само дерево вывода строится с учетом контекста, определяемого значениями атрибутов;

• атрибуты применяются для контекстно-зависимого разрешения синтаксической неоднозначности грамматики относительно результата трансляции.

Основные результаты работы:

• разработан способ применения атрибутов в RBNF-грамматиках;

• дано формальное определение трансляции, задаваемой атрибутной спецификацией;

• выявлены ограничения, накладываемые на атрибуты для их использования в алгоритме сплайнового процессирования, применяемом в технологии SYNTAX;

• модифицированы алгоритмы построения управляющих таблиц сплайнового челночного процессора для реализации поддержки атрибутов;

• модифицирован алгоритм сплайнового процессирования, реализующий прямой и обратный просмотры в технологии SYNTAX;

• разработан механизм передачи контекстной информации между просмотрами с использованием атрибутов.

Построение диссертации. Основное содержание диссертации изложено в 4 главах.

В ПЕРВОЙ ГЛАВЕ описаны подходы к описанию контекстно-зависимых языков на основе двухуровневых грамматик (аффиксные грамматики [17], W-грамматики [26]) и к спецификации трансляции (атрибутная техника в КС-грамматиках [15]). Неформально в RBNF-спецификации системы SYNTAX вводятся атрибуты.

Во ВТОРОЙ ГЛАВЕ дано формальное определение трансляции, задаваемой SYNTAX-спецификацией с использованием атрибутов (случай прямого просмотра), описание алгоритма сплайнового процессирования, приведены ограничения, накладываемые на атрибуты для обеспечения возможности их применения в сплайновом процессоре. Кроме того, описывается алгоритм обратного просмотра с использованием атрибутов, обсуждается вопрос передачи контекстной информации между просмотрами.

В ТРЕТЬЕЙ ГЛАВЕ описывается модификация представления управляющих таблиц и алгоритма сплайнового процессирования, описанных в [4], с целью введения поддержки атрибутов. Рассмотрены примеры использования атрибутного подхода.

В ЧЕТВЕРТОЙ ГЛАВЕ рассматриваются отдельные вопросы, которые не реализованы в разработанном прототипе системы, но, однако, могут быть реализованы с применением описанного атрибутного подхода.

В ЗАКЛЮЧЕНИИ сформулированы основные выводы, полученные по результатам выполненных в диссертации исследований.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Лукичев, Александр Сергеевич

Заключение

В ходе выполнения работы были достигнуты все основные цели исследований, получены следующие результаты:

1. Разработан способ применения атрибутов в RBNF-грамматиках и, в частности, в SYNTAX-спецификациях. Описана мотивация использования такого подхода. В рамках предложенного подхода рассмотрено применение атрибутов на прямом и обратном просмотрах, выявлены ограничения, накладываемые на атрибуты, разработан механизм передачи контекстной информации между просмотрами.

2. Дано формальное определение трансляции, осуществляемой на прямом просмотре с использованием атрибутов в технологии SYNTAX. На основе описанных в [4] алгоритмов процессирования и построения управляющих таблиц построены модифицированные алгоритмы, поддерживающие атрибутные спецификации.

3. Реализован прототип системы на языке Pascal. В качестве основы для данной реализации был взят код технологического комплекса SYNTAX, разработанного в СПбГУ. Описаны изменения, внесенные в представление управляющих таблиц.

4. С использованием разработанного прототипа проведен сравнительный анализ предлагаемого подхода с технологией SYNTAX без поддержки атрибутов. Получены следующие выводы:

• применение предлагаемого подхода делает процесс разработки семантических действий более прозрачным, избавляя разработчика от необходимости реализации своего метода передачи контекстной информации, согласованного с синтаксическим механизмом;

• использование семантик и резольверов с параметрами делает структуру семантической части спецификации более прозрачной и модульной;

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

Сформулированы основные направления дальнейшего развития технологического комплекса SYNTAX на основе разработанного прототипа, .включающие в себя:

• использование атрибутов у терминальных символов;

• применение атрибутов для передачи контекстной информации между челночными процессорами;

• введение типизированных атрибутов;

• применение атрибутов при макроподстановке;

• оптимизация атрибутных синтаксических процессоров.

Список литературы диссертационного исследования кандидат физико-математических наук Лукичев, Александр Сергеевич, 2006 год

1. Алгол 68. Методы реализации. / Под. ред. Г.С. Цейтина. Изд. ЛГУ, J1. 1976

2. Ахо А., Сети Р., Ульман Дою. Компиляторы: принципы, технологии и инструменты. Пер. с англ. — М., 2001 г.

3. Вирт Я. Алгоритмы+структуры данных=программы. Пер. с англ. — М., 1984 г.

4. Мартыненко Б. К. Синтаксически управляемая обработка данных. Изд. 2-е. СПб, 2004 г.

5. Мартыненко Б.К. Языки и трансляции. СПб, 2004 г.

6. Chomsky N. On certain formal properties of grammars // Inf. Contr. 2,1959, pp. 137-167.

7. Farnum C. Pattern-based tree attribution // Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 1992, pp. 211-222.

8. Farrow R., Marlowe T.J., Yettin D.M. Composable Attribute Grammars: Support for Modularity in Translator Design and Implementation // Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 1992, pp. 223-234.

9. Gray R.W., Heuring V.P., Levi S.P. et al Eli: a complete, flexible compiler construction system // Communications of ACM, Vol. 35, No. 2, 1992, pp. 121-130.

10. Early J. An Efficient Context-Free Parsing Algorithm // Communications of the ACM, Vol. 13, No. 2, 1970, pp. 94-102.

11. Johnson S.C. Yacc — yet another compiler compiler. Computer Science Technical Report 32. AT&T Bell Laboratories, Murray Hill, N.J., 1975.

12. Jullig R.K., DeRemer F. Regular Right-Part Attribute Grammars // Proceedings of the ACM SIGPLAN '84 Symposium on Compiler Construction, SIGPLAN Notices Vol. 19, No. 6, 1984, pp. 171-178.

13. Kastens U., Hütt D., Zimmermann E. GAG: A Practical Compiler Generator // Lecture Notes in Computer Science, Vol. 141, 1982.

14. Knuth D.E. On the translation of languages from left to right // Inf. Contr. 8, Vol. 6, 1965, pp. 607-639.

15. Knuth D.E. Semantics of context-free languages // Mathematical Systems Theory 2:2, 1968, pp. 127-145.

16. Koster C.H.A. On the Construction of ALGOL-Procedures for Generating, Analyzing and Translating Sentences in Natural Languages. Report MR72, Mathematisch Centrum, Amsterdam, 1965.

17. Köster C.H.A. Affix Grammars 11 Proceedings of IFIP Conference on ALGOL 68 Implementation. 1970. Munich, pp. 95-109.

18. Köster C.H.A. Affix Grammars for Programming Languages // In: Attribute Grammars, Applications and Systems. International Summer School SAGA. 1991. Prague.

19. Koster C.H.A., Beney J.G. On the Borderline Between Grammars and Programs // Springer Lecture Notes in Computer Science 528,1991, pp. 219230.

20. Lee J.A.N., Dorocak J. Conditional Syntactic Specification // ACM '73: Proceedings of the annual conference, 1973, pp. 101-105.

21. Lewis P.M., Stearns R.E. Syntax-directed transduction // Journal of ACM, Vol. 15, No. 3, 1968, pp. 465-488.

22. Mejier H. The Project of Extended Affix Grammars at Nijmegen // Attribute Grammars and their Applications. Lecture Notes in Computer Science 461, Springer, 1990.

23. Odersky M. Defining Context-Dependent Syntax Without Using Contexts // ACM Transactions on Programming Languages and Systems, Vol. 15, No. 3, 1993, pp. 535-562.

24. Olsen D.R., Jr. Pushdown Automata for User Interface Management// ACM Transactions on Graphics, Vol. 3, No. 3, 1984, pp. 177-203.