Реализация аппарата развития на синтаксическом уровне

А. Н. Яковлев

В статье предлагается вариант реализации аппарата развития синтаксического уровня [1] на базе алгоритмического языка общего назначения Yalgol/03 [2]. В качестве базового инструмента определения синтаксиса используется контекстно-свободная грамматика в нотации, основанной на БНФ [3]. Расширенный вариант нотации, предлагаемый в настоящей статье, основан на использовании концепций объектно-ориентированного программирования (инкапсуляции, наследования и полиморфизма) применительно к правилам формальной грамматики. Рассматривается возможность построения языка программирования общего назначения, допускающего развитие на синтаксическом уровне.

1. Введение

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

Языки, построенные на одной семантической базе, могут иметь различный синтаксис. При всем их многообразии современные универсальные языки программирования предоставляют практически эквивалентный набор базовых сервисов (семантических элементов), однако синтаксически могут быть существенно различными [4]. Общность решаемых задач объясняет сходство семантики языков, различие же в синтаксисе обусловлено в основном историческими причинами.

Эволюция аппарата развития современных универсальных алгоритмических языков движется ко все более гибкому взаимоотношению между синтаксисом и семантикой. Современные языки позволяют определять пользовательские абстракции, синтаксически неотличимые от встроенных в язык фундаментальных средств. Например, в языках Ada 9x, Eiffel и C++, используя перегрузку, можно задать семантику операций над пользовательскими типами данных в арифметических выражениях. Перегрузка позволяет изменить смысл некоторых синтаксических конструкций языка, однако не позволяет описывать новых. Средства, позволяющие расширять исходный язык новыми синтаксическими конструкциями, являются закономерным этапом эволюции аппарата развития универсальных языков. Мы назвали их аппаратом развития на синтаксическом уровне [1].

2. Два подхода к реализации развития на синтаксическом уровне

Аппарат развития на синтаксическом уровне должен включать средства описания синтаксиса и соответствующей ему семантики (статической и динамической). Для формального описания синтаксиса языков наиболее часто используется нотация Бэкуса-Наура, или БНФ [3, 6]. Эта нотация хороша тем, что сама по себе является формальным языком — знаковой системой, которую можно описать с помощью грамматики (в отличие, например, от синтаксических диаграмм, которые не являются знаковой системой). Статическая семантика может быть описана с помощью расширений БНФ (атрибутивных грамматик); общепринятой нотации описания динамической семантики не существует.

В книге [6] упоминаются три наиболее распространенных варианта описания динамической семантики: операционная, аксиоматическая и денотационная семантика. Аксиоматическая и денотационная семантики построены на основе математической логики. Они ориентированы на человека и предназначены скорее для доказательства правильности программ, чем для формального определения семантики. Денотационные описания языка могут быть использованы для порождения компиляторов, однако ни одного работоспособного компилятора на основе этого метода до сих пор построено не было.

Операционная семантика основывается на исполнении операторов языка на некоей виртуальной машине. Смысл выполняемых оператором действий выражается в изменении состояния этой виртуальной машины. Подобный метод применялся для описания семантики языка PL/I в 1972 году. Как показала практика, описания, основанные на низкоуровневом моделировании, практически бесполезны, поскольку они слишком громоздки и неудобны для восприятия человеком [6]. Тем не менее, операционная семантика является фактически единственным способом описания формальной семантики, пригодным в нашем случае.

Для упрощения описаний можно предложить один достаточно очевидный способ: воспользоваться виртуальной машиной, основанной на языке высокого уровня. Поскольку в алгоритмическом языке синтаксис и семантика всегда взаимосвязаны, мы можем задавать семантику на основе синтаксиса какого-либо универсального языка высокого уровня (назовем его базовым языком). Следовательно, нашей целью является описание способа преобразования нового синтаксиса в базовый, то есть синтаксически управляемая трансляция [3]. В этом заключается ключевая идея аппарата развития синтаксического уровня.

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

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

Преимущества лексического подхода:

• Базовый язык может быть любым (Pascal, C, C++, Assembler и т.д.);
• Механизм можно использовать не только для преобразования алгоритмов, но и для автодокументирования, а также для широкого спектра приложений, основанных на синтаксически управляемой трансляции.

Недостатки лексического подхода:

• Небезопасность (отсутствие контроля над выходным потоком, поскольку его лексическая и синтаксическая структура не специфицирована);
• Сложность, проистекающая из универсальности средства;
• Плохая стандартизуемость, вызванная излишней свободой выбора.

Кроме того, на основе лексического подхода нельзя построить цельного языка, обладающего аппаратом развития синтаксического уровня. Вместо этого можно добавить этот аппарат как ортогональную надстройку над любым существующим языком программирования. Полученная система двух языков не будет новым полноценным языком, поскольку контроль ошибок будет распределен между двумя независимыми компиляторами, а отладочная информация будет сохранена только для базового языка. Это с необходимостью приведет к значительному усложнения процесса разработки программ. Несмотря на указанные недостатки, большинство систем автоматизированного построения компиляторов фактически используют этот подход. Например, языки Lex и Yacc, изначально ориентированные на язык C, были адаптированы к Pascal, Java, C# и другим языкам. Оба этих языка не являются надмножествами каких-либо языков общего назначения, и большинство известных инструментов (lex, flex, yacc, bison, jay) не занимаются каким-либо контролем синтаксиса выходного текста.

Семантический подход изначально ориентирован на генерацию программ. Он подразумевает, что выходной поток лексем соответствует синтаксису некоего базового языка (этим базовым языком может быть любой язык общего назначения), и, следовательно, задает операционную семантику транслируемого фрагмента. Этот подход мы считаем предпочтительным.

Преимущества семантического подхода:

• Наличие контроля выходного потока — безопасность, обработка ошибок синтаксиса/семантики на этапе генерации кода;
• Возможность семантических преобразований (например, оптимизации) выходного кода, поскольку семантика его известна;
• Возможность разработки цельного языка общего назначения, обладающего аппаратом развития на уровне синтаксиса (что позволяет добиться значительно большей выразительности языка — удобства чтения и написания программ).

Недостатки семантического подхода:

• Ограниченность — механизм пригоден для трансляции только в базовый язык;
• Необходимость разработки собственного компилятора базового языка (поскольку необходим синтаксический и семантический контроль над выходным потоком).

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

3. Семантический подход на базе Yalgol/03

В качестве базового языка программирования (языка описания операционной семантики) мы будем использовать алгоритмический язык Yalgol/03 [2]. Проектирование аппарата развития на базе этого языка программирования имеет ряд преимуществ по сравнению с использованием какого-либо стандартизованного языка.

Среди реально используемых языков программирования лишь некоторые языки обладают множеством необходимых семантических элементов. Это универсальные языки C++, Ada95, Java, C#, Object Pascal и Eiffel [6, 8, 9]. Все эти языки (за исключением Java и Eiffel) являются продуктами эволюции процедурных языков, в целях обратной совместимости наследующими устаревшие или небезопасные синтаксические конструкции и семантические элементы предшественников (C, Ada83, Pascal). Эти языки представляют собой инструменты проектирования программ, а не описания семантики, что во многих случаях определяет избыточность, перегруженность этих языков.

Реализация аппарата развития на базе одного из стандартных языков означала бы необходимость реализации компилятора этого языка, соответствующего последнему стандарту — в противном случае от использования стандартного языка не было бы никаких преимуществ. В качестве альтернативного решения мы предлагаем использование специализированного алгоритмического языка Yalgol. Преимуществами такого подхода являются:

• Возможность построения языка, ориентированного на описание семантики, а не на проектирование алгоритмов;
• Возможность произвольного изменения алгоритмического подмножества языка в целях обеспечения наибольшей совместимости с метаязыковым подмножеством;
• Свобода действий разработчика языка не ограничивается требованиями стандартов и необходимостью обеспечения обратной совместимости;
• Язык и компилятор Yalgol/02 существуют на самом деле; язык Yalgol/03 находится в процессе разработки.

Язык Yalgol/02 построен на подмножестве семантики Java, которая на наш взгляд наиболее удачно решает проблемы независимости от аппаратной и программной платформ. Компилятор Yalgol/02 был разработан на Yalgol/01, а затем портирован в Yalgol/02, что позволило улучшить многие проектные решения языка. Семантика следующего поколения языка расширяется некоторыми элементами, заимствованными из C# и Eiffel. При этом из Yalgol/03 исключаются некоторые элементы языка предыдущего поколения (например, встроенные типы данных), что делает его более ортогональным. По синтаксису Yalgol немного напоминает Algol68.

4. Метаязыковое подмножество Yalgol

Средства описания синтаксиса основаны на механизме контекстно-свободной грамматики, поэтому описание языка представляет собой совокупность правил вывода (продукций). Каждое правило включает левую и правую части, описывающие возможную замену нетерминала цепочкой символов в процессе вывода, и тело, которое служит для описания генерируемого кода [1]. В терминах Yalgol левая часть правила называется именем, а правая – аргументами правила. Аргументы могут использоваться в теле правила при описании целевого кода.

Правила грамматики, записанные в синтаксисе Yalgol, являются практически непосредственным отображением соответствующий правил БНФ. Одним из расширений БНФ, предложенных в языке Yalgol, является возможность присвоения имен символам, входящим в правую часть правил грамматики (аргументам правил). Два символа с одинаковым именем должны иметь одинаковые значения атрибутов либо эквивалентные деревья разбора. Это расширение позволяет проверять некоторые условия, относящиеся к статической семантике.

Например, правило грамматики языка Ada, описывающее процедуру, не является полным определением синтаксиса процедуры. БНФ не позволяет указать тот факт, что токен Identifier в обоих случаях должен иметь одно и то же значение:

AdaProcedure -> "procedure" Identifier "is"
                  { Declaration }
                "begin"
                  Statement { ";" Statement }
                "end" Identifier ";"

Yalgol позволяет разрешить эту проблему путем указания двух аргументов правила, имеющих одинаковое имя:

rule AdaProcedure(
  "procedure", Identifier Ident, "is",
    { Declaration },
  "begin",
    Statement, { ";", Statement },
  "end", Identifier Ident, ";"
)

Заметим, что на практике нам наверняка потребовалось бы указать в данном примере имена нетерминалов Declaration и обоих Statement (разумеется, эти имена должны быть уникальными), поскольку их значения понадобились бы в теле правила для генерации какого-то эквивалентного кода. Полное правило могло бы выглядеть следующим образом:

rule AdaProcedure("procedure", Identifier Ident, "is",
    { Declaration Decl }, "begin",
    Statement Stmt1, { ";", Statement Stmt2 },
    "end", Identifier Ident, ";") = (
  proc Ident = (
    Decl
    Stmt1
    Stmt2
  )
)

Приведенное правило пользуется правилами Identifier, Declaration и Statement, которые здесь не приводятся. Результатом работы этого правила является преобразование описания процедуры из синтаксиса Ada в синтаксис Yalgol, например:

5. Объектно-ориентированная идеология

Главной отличительной особенностью метаязыкового подмножества Yalgol является применение объектно-ориентированной идеологии. В данном случае ее основным назначением является упрощение описаний, построенных на основе базовых метаязыковых механизмов (формальной грамматики и операционной семантики). В Yalgol существует вполне осмысленная аналогия понятий объектно-ориентированной технологии алгоритмического и метаязыкового языковых подмножеств.

Можно привести еще несколько осмысленных примеров аналогии алгоритмической и метаязыковой объектно-ориентированных моделей. Метаязыковым аналогом виртуальных методов являются виртуальные правила, позволяющие переопределять языковые подмножества (например, расширить синтаксис выражений исходного языка, не меняя синтаксиса инструкций, деклараций и т.д). Абстрактный класс в обоих случаях является механизмом описания интерфейса (в метаязыке — синтаксиса), но не реализации (виртуальной машины). Инкапсуляция, трактуемая как сокрытие любого рода информации об объектах или классах, имеет один и тот же смысл в обеих моделях.

В языке, построенном на основе ортогонального синтеза алгоритмической и метаязыковой моделей, наибольшую ценность представляет сочетание этих моделей. Например, используя множественное наследование, пользователь может совместить абстрактный класс компилятора (алгоритмический) с классом какого-либо синтаксиса (метаязыковой) для порождения подкласса компилятора конкретного языка.

6. Выводы

Фундаментальными механизмами, на которых основывается аппарат развития синтаксического уровня, являются контекстно-свободная грамматика и операционная семантика. В качестве средства борьбы со сложностью метаязыковых описаний предлагается объектно-ориентированная идеология, концепции которой трактуются по аналогии с концепциями объектно-ориентированного программирования. Согласованность алгоритмического и метаязыкового подмножеств языка Yalgol обусловлена общностью понятия класса и концепций инкапсуляции, наследования и полиморфизма в обоих подмножествах, что позволяет говорить о цельном языке с аппаратом развития синтаксического уровня. Метаязыковое подмножество Yalgol охарактеризовано лишь в общих чертах, так как оно подлежит дальнейшей разработке.

Литература

1. Е. М. Ульяницкий, А. Н. Яковлев. Аппарат развития на синтаксическом уровне.
2. А. Н. Яковлев. Предварительный вариант спецификации алгоритмического языка Yalgol/03.
3. А. Ахо, Р. Сети, Дж. Ульман. Компиляторы. Принципы, технологии, инструменты. М.: Вильямс, 2001.
4. А. Ю. Андреев. Эволюция языков программирования.
5. В. Ш. Кауфман. Языки программирования. Концепции и принципы. М.: Радио и Связь, 1993.
6. Р. У. Себеста. Основные концепции языков программирования. Пятое издание. М.: Вильямс, 2001.
7. А. Шаллоуей, Дж. Р. Тротт. Шаблоны проектирования. Новый подход к объектно-ориентированному анализу и проектированию. М.: Вильямс, 2002.
8. Т. Пратт, М. Зелковиц. Языки программирования: разработка и реализация. 4-е издание. М.: Питер, 2002
9. М. Бен-Ари. Языки программирования. Практический сравнительный анализ. М.: Мир, 2000

Последнее обновление: 11 мая 2003