автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Модели и реализация транслирующих компонентов системы функционального программирования

Российская академия наук Сибирское отделение Институт систем информатики имени А. П. Ершова

На правах рукописи

аи^1» ■

Стасенко Александр Павлович

МОДЕЛИ И РЕАЛИЗАЦИЯ ТРАНСЛИРУЮЩИХ КОМПОНЕНТОВ СИСТЕМЫ ФУНКЦИОНАЛЬНОГО ПРОГРАММИРОВАНИЯ

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

28»»*

"■■■■я

Новосибирск 2009

003471282

Работа выполнена в Институте систем информатики имени А. П. Ершова СО РАН

Научный руководитель:

Касьянов Виктор Николаевич,

доктор физико-математических наук,

профессор

Официальные оппоненты:

Малышкин Виктор Эммануилович, доктор технических наук, профессор

Скопин Игорь Николаевич, кандидат физико-математических наук

Ведущая организация:

Сибирский федеральный университет

Защита состоится «5» июня 2009 г. в 16 ч. 00 мин. на заседании диссертационного совета ДМ 003.032.01 в Институте систем информатики имени А. П. Ершова Сибирского отделения РАН по адресу:

630090, г. Новосибирск, пр. ак. Лаврентьева, 6.

С диссертацией можно ознакомиться в читальном зале библиотеки ИСИ СО РАН (пр. ак. Лаврентьева, 6)

Автореферат разослан «4» мая 2009 г.

Ученый секретарь диссертационного совета, к. ф.-м. н.

Мурзин Ф. А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В настоящий момент намечается существенное замедление роста производительности вычислительных систем за счет увеличения тактовой частоты вычислительных устройств, связанное с ограниченностью современных технологических возможностей. Поэтому для сохранения существующих темпов роста скорости вычислений, косвенно декларируемых законом «Moore's Law», возобновляется интерес к параллельным вычислениям. Ярким тому подтверждением является появление процессоров с двумя независимыми вычислительными ядрами, ~ ориентирова1111ых^на_массовый^рынокг~Прослеживается_общая~те1тденция увеличения значимости роли многих процессорных ядер, что в обозримом будущем может привести к значительному росту возможностей вычислительных систем по параллельной обработке данных.

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

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

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

Однако и в функциональных языках существуют ограничивающие параллелизм факторы. Одной из таких причин является набор языковых операций, специально ориентированный на последовательные вычисления или ограниченный параллелизм. В частности, в функциональном языке Лисп (Lisp) операторы для работы с данными обеспечивают выборку только одного компонента, а функциональный язык FP не предусматривает распараллеливание на уровне независимых операторов. Также в модели вычислений, присущей функциональному языку, могут присутствовать элементы управления, тем или иным образом приводящие к разделению процессами общих вычислительных ресурсов. Например, в схемах потока данных Дениса таким ресурсом является узел слияния потоков данных.

Указанные недостатки обычно обходятся в потоковых языках программирования, явно описывающих вычисления в виде графа потока данных и обычно являющихся также и функциональными языками. Эти языки, как правило, содержат операторы размножения информационных потоков, их группирования в списки данных различного уровня вложенности и одновременного выделения из списков нескольких независимых и разнородных по составу групп. Потоковые языки программирования изначально ориентировались на потоковые архитектуры вычислительных систем, имевших распространение в 80-90-х гт. XX века, и с тех пор практически не развивались.

Тем самым, актуальность работы обуславливается:

1) технологическими трудностями роста производительности последовательных машинных архитектур и, как следствие, ростом интереса к параллельным вычислениям;

2) высокой изменчивостью параллельных машинных архитектур и, как следствие, необходимостью в машинно-независимом представлении параллелизма;

3) естественной пригодностью потоковых языков программирования для описания машинно-независимого параллелизма;

4) малой распространенностью и устарелостью существующих потоковых языков и систем программирования на их основе.

Язык лрограммирования S¡sal является одним из самых известных потоковых языков промышленного уровня и позиционируется как замена языка Fortran для научных применений. Язык Sisal имеет следующие особенности, облегчающие переход с популярных императивных языков програм мирования:

• приближенный к языку Паскаль синтаксис;

• развитая система типов;

• явно выделенные циклические выражения.

Последняя спецификация языка Sisal версии 2.0 датируется 1991 г., а последнее обновление транслятора OSC, работающего только с языком Sisal версии 1.2 от 1985 г., было в 1995 г. В 1995 г. также появилось пользовательское описание языка Sisal 90, не содержащее, однако, точных спецификаций языка.

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

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

1. Разработка языка Sisal версии 3.1, развивающего базовую, функциональную часть языка Sisal 3.0, являющегося входным языком системы SFP и основанную на языке Sisal 90.

1.1. Уточнение описания языка Sisal 90.

1.2. Расширение языка Sisal 90 средствами модульного программирования (Sisal 3.0) и пользовательскими типами.

1.3. Улучшение синтаксиса и семантики языка Sisal 90.

2. Разработка машинно-независимого ВП IR1 программ языка Sisal 3.1, основанного на графах информационных зависимостей.

2.1. Разработка модели внутреннего представления (ВП) IR1 для машинно-независимого описания функциональных программ и её специализация для языка Sisal 3.1.

2.2. Разработка и реализация вспомогательных компонентов ВП IRI для его сохранения, восстановления и визуализации.

3. Исследование методов трансляции и создание компилятора переднего плана из текста программ языка Sisal 3.1 в ВП IR1.

3.1. Разработка модели построения компоненты компилятора переднего плана, основанной на теории автоматов, и ее графического представления.

3.2. Разработка компоненты поддержки трансляции из текстового представления во ВП IRI (для поддержки нескольких входных языков системы SFP).

Методы исследования. В диссертационной работе использовались понятия и методы теории графов, теории алгоритмов и элементы теории множеств. Также применялась теория синтаксического анализа и построения трансляторов. В качестве сравнения применялись различные классы

потоковых схем. Для описания синтаксиса языка программирования использовались расширенные формы Бэкуса-Наура (БНФ).

Научная новизна. В диссертационной работе получены новые научные результаты.

1. Спроектирована и формально описана новая версия языка Sisal 3.1, развивающая функциональную часть предыдущих версий языка Sisal и приближающая её к уровню современных языков программирования.

2. Разработаны модели для удобного построения, хранения, анализа, преобразования и использования машилно-независимого внутреннего представления программ функциональных языков программирования.

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

4. Формализована модель описания графической составляющей компилятора переднего плана, основанная на упрощении классической модели магазинного автомата с расширениями, делающими возможным её практическое применение. Практическая ценность. Разработанные язык программирования

Sisal 3.1, его ВП 1R1 и транслятор из первого во второе являются неотъемлемой частью системы функционального программирования (SFP), разрабатываемой в рамках проекта ПРОГРЕСС. Данные разработки будут использоваться другими участниками проекта SFP в качестве основы для создания своих частей проекта и будут внедрены в учебный процесс в Новосибирском госуниверситете.

Апробация работы. Основные положения диссертации обсуждались на следующих конференциях и семинарах.

1. 9th International Conference on Parallel Computing Technologies, Pereslavl-Zalessky, 2007 r.

2. Европейская конференция по вычислениям (ЕСС-2007), г. Афины, 2527 сентября, 2007.

3. V Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (с участием иностранных ученых), Новосибирск, ИВТ СО РАН, 2004 г.

4. Конференция-конкурс «Технологии Microsoft в информатике и программировании», Новосибирск, 2005 г.

5. Конференция-конкурс «Технологии Microsoft в теории и практике программирования», Новосибирск, 2006 г.

6. XL1V Международная научная студенческая конференция «Студент и научно-технический прогресс», Новосибирск, 2006 г.

7. XII Международная научно-методическая конференции «Новые информационные технологии в университетском образовании», 2007 г.

8. Семинар спецкурса «Введение в функциональное программирование», 2007 г.

9. Семинары «Конструирование и оптимизация программ», Новосибирск, ИСИ СО РАН, 2002-2008 гг.

Публикации. Основные результаты диссертационной работы опубликованы в 19 печатных работах, из которых 2 препринта, 12 статей и 6 тезисов докладов. Исследования поддерживались грантами УР.04.01.027 и УР.04.01.0201 научной программы «Университеты России» Министерства науки и образования Российской Федерации. Исследования выполнялись в соответствии с планами научно-исследовательских работ ИСИ СО РАН по проекту 3.15 «Методы и средства трансляции и конструирования программ». Проект проводился в рамках программы 3.1 СО РАН «Информационное и математическое моделирование в различных областях знаний, задачи

поддержки принятия решений, экспертные системы, системное и теоретическое программирование».

Структура диссертации. Диссертация состоит из введения, четырёх глав, заключения, списка литературы и девяти приложений. Работа содержит 109 страниц машинописного текста (без приложений и библиографии), 78 рисунков и 22 таблиц. Список литературы содержит 99 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность темы диссертации, формулируются её цели, характеризуется научная новизна и практическая —ценность работы;

В главе 1 содержится краткий обзор потоковых языков программирования, историю развития языка Sisal и описание нововведений и особенностей его последней версии Sisal 3.1, представляемой в данной работе.

Раздел 1.1 рассматривает общие определяющие качества потоковых языков программирования и их преимущества над императивными языками программирования.

Раздел 1.2 содержит историю и краткий анализ развития версий языка Sisal, начиная с языка Val, являющегося прародителем языка Sisal, и заканчивая версией Sisal 3.1. Приводятся примеры основных нововведений каждой версии языка. Нововведения языка Sisal 3.0 заключаются в возможности задавать отдельные части программы на императивном языке Си, расширенной по,вдержке модульности программ, возможности их предварительной обработки (preprocessing) и аннотирования для упрощения оптимизирующих преобразований.

Раздел 1.3 представляет новую версию языка Sisal 3.1, являющуюся развитием языка Sisal 90 с помощью идей улучшенной поддержки модульности и механизмами предварительной обработки, предложенными в языке Sisal 3.0. Описание мультиязыкового программирования и

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

Пользовательский тип определяется через указание его базового типа. Детали реализации базового типа скрываются запретом на неявное наследование пользовательским типом операций его базового типа, что требует явного определения всех свойственных новому типу операций и способствует ясному разграничению операций определяемых иерархией типов.

Отделение внутреннего представления данных от внешнего возможно через переопределение операции неявного преобразования типов. Переопределение операции точки также позволяет задавать «мнимые» поля данных пользовательского типа. Ввиду функциональной природы языка Sisal, возможен естественный синтаксис вызова метода пользовательского типа, путём переопределения его операции точки, возвращающей значение функционального типа.

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

Раздел 1.4 посвящен обоснованию ограничений языка Sisal 3.1 по сравнению с языком Sisal 90, таких как отказ от глобальных констант и ограничение полиморфизма множества типов.

Раздел 1.5 содержит анализ изменений синтаксиса и семантики языка Sisal 90 в языке Sisal 3.1, направленных на улучшение межъязыкового взаимодействия с языком Си, повышение читаемости программ, улучшение

синтаксиса, упрощение синтаксического разбора и устранение его неоднозначностей.

В главе 2 описывается модель внутреннего представления (МВП) IR1 (Internal Representation 1). Раздел 2.1 состоит из требований к разрабатываемой МВП IR1:

1) машинная независимость представления параллелизма, без явного выделения нескольких потоков вычислений;

2) машинная независимость значений простых типов данных, независимость от разрядности машинной архитектуры;

3) полнота, позволяющая произвести ретрансляцию в программу на исходном языке, семантически эквивалентную исходной программе;

4) ретрансляция в синтаксически корректную программу после преобразований, корректных для исходного языка (приложение 6);

5) интерпретируемость без дополнительных преобразований;

6) простота преобразований, в том числе и оптимизирующих;

7) иерархичность сущностей ВП, задающих естественную вложенность конструкций функционального языка программирования;

8) представление всех неявных операций явным образом;

9) представление циклических конструкций в явном виде;

10) расширяемость - лёгкое введение новых сущностей ВП, задающих новые конструкции языков программирования и типы данных;

11) переносимость - применение сущностей в разных языковых средах.

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

Раздел 2.3 содержит описание языка промежуточного представления программ IFI (Intermediate Form 1), основывающегося на ациклических иерархических орграфах и являющегося основой разработанной МВП IR1. Приводятся способы представления последовательного исполнения, альтернативы и итерации в терминах языка IF1.

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

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

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

Раздел 2.4 состоит из описания МВП LR1, как набора сущностей, реализующих понятия основные понятия языка IF1. Особенности представления программ языка Sisal 3.1, заданные набором числовых и строковых свойств МВП IR1, вынесены в приложения 4, 5 и 6. Для МВП IR1 в этом разделе описываются разработанные алгоритмы удаления неиспользуемых строк и типов, слияния эквивалентных типов.

Во-первых, было принято решение отказаться от выделения дуги в качестве отдельной сущности (интерфейса) и переложить связи между портами на его интерфейс, поддерживающий типы передаваемых дугами значений. Такое решение позволило упростить реализацию обхода графа, так как для любого взятого порта можно сразу определить порт, поставляющий ему значения, и множество портов, принимающих, в свою очередь, от него значения. Это, например, позволило легко реализовать операцию удаления порта из ВП 1Ш. Далее термин дуга, однако, будет употребляться при описании взаимосвязей между портами.

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

Раздел 2.5 содержит описание моделей описания вспомогательных компонент МВП 1Ш: компоненты преобразования в эквивалентную ХМЬ-форму и компоненты визуализации и навигации. Даются краткие сведения, связанные с используемыми при реализации этих интерфейсов алгоритмами.

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

В разделе 3.2 вводится модель упрощенного магазинного автомата Ч', являющаяся классической моделью магазинного автомата с ограничениями на вид функции перехода, повышающими наглядность её графического представления. Доказывается, что подобное упрощение в случае недетерминированных автоматов не влияет на возможность задавать произвольные контекстно-свободные языки. Для детерминированных автоматов доказывается, что класс, задаваемых ими языков, равен классу 1Х| языков. Показывается, что в рамках модели детерминированного автомата У, не сужая класс представимых им языков, можно устранить все с-переходы первого и второго вида. Также вводится новый класс грамматик, в котором для каждого детерминированного автомата Ч' существует грамматика, задающая тот же язык, и наоборот.

Для визуального представления модели детерминированного автомата Ч* в разделе 3.3 описывается графический метаязык, программы на котором далее называются схемами Ч*. Схемы Ч' отображают модель автомата Ч' в виде ориентированного, размеченного графа, вершины которого, за исключением специального случая рор-вершин, соответствуют состояниям автомата, а связи между вершинами - переходам.

Раздел 3.4 содержит описание расширений графического метаязыка. Рассмотренная схема Ч* допускает эффективную реализацию, но ограничена узким классом ^ языков. Для исправления этой ситуации схемы Ч* были усилены за счёт добавления семантически зависимых переходов. В то же время неудобно и ненаглядно строить большие полностью определённые схемы Ч', где реакция на ошибки разбора легко унифицируема. Для устранения этих затруднений в схемы Ч' был внедрён механизм иерархической обработки ошибок разбора, сходный с обработкой исключений языка Си++.

В разделе 3.5 приводится схема механизм применения схем Ч* для описания работы транслятора, показывающая разделение разрабатываемого транслятора на автоматную и генерирующую части. Для функционирования

транслятора состояниям и переходам автомата приписывается дополнительная разметка, обозначающая идентификаторы процедур. Процедуры сопоставляются своим идентификаторам во время исполнения автомата.

В конце главы, в разделе 3.6 описывается преобразование графического представления из графового формата .GraphML, удобного для построения и навигации, во внутренний формат (приведенный в приложении 9), приспособленный для непосредственного исполнения. Для этого была написана специальная утилита, дополнительно осуществляющая с помощью описанных в разделе алгоритмов устранение мнимых дуг, удаление недостижимых состояний, оптимизацию тестовых условий На дугах7 минимизацию генерируемого автомата и разворачивание нерекурсивных зависимостей.

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

В главе 4 находится описание транслятора программ на языке Sisal 3.1 во ВП IR). Глава начинается с обзора в разделе 4.1 существующих трансляторов языка Sisal. Рассматривается «официальный» транслятор OSC и его развитие в рамках проекта «Sisal Lives». Также приводятся различные расширения OSC такие, как транслятор D-OSC, ориентированный на машины с распределённой памятью, и транслятор FSC, комбинирующий поддержку машин с общей и распределенной памятью.

В разделе 4.2 находится общая схема транслятора языка Sisal 3.1, написанного с использованием схем Ч' лексического и синтаксического анализа, совмещенного с семантическим разбором.

Раздел 4.3 содержит описание требований к модели транслятора из текстового представления во ВП IR1. Основное содержание раздела

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

Раздел 4.4 содержит общую информацию о подсистеме лексического анализа транслятора Sisal 3.1. Приводится описание лексем, задач лексического разбора, возможных лексических ошибок и предупреждений.

Раздел 4.5 занят общим описанием синтаксического и семантического анализа языка Sisal 3.1. Указываются причины объединения анализов синтаксиса и семантики в разрабатываемом трансляторе. Приводится общая структура разбора, задаваемого схемой Ч', и общее описание разбора, включая используемые стеки. Рассматриваются особенности разбора отдельных конструкций языка. Перечисляются сообщения об ошибках и предупреждениях транслятора. Освещается механизм восстановления после ошибок синтаксического и семантического разбора.

Приложение 1 содержит семантику языка Sisal 3.1 в нестрогом виде пользовательского описания, которое, по замыслу, претендует на полноту и непротивореч ивость.

Приложение 2 содержит полную грамматику языка Sisal 3.1 в расширенной форме Бэкуса-Наура (БНФ).

Приложение 3 состоит из текста интерфейса и реализации модуля языка Sisal 3.1, который описывает типы complex и double_complex, эквивалентные аналогичным типам языка Sisal 90.

Приложение 4 описывает синтаксис и семантику простых вершин МВП IR 1, необходимых для представления программ языка Sisal 3.1.

Приложение 5 описывает синтаксис и семаитику составных вершин МВП 1R1', используемых для представления условных и циклических конструкций языка Sisal 3.1.

Приложение 6 содержит описание специализации МВП IR1 для языка Sisal 3.1.

Приложение 7 состоит из описания структура XML-представления ВП IR1 и примера XML-представления простой программы языка Sisal 3.1.

Приложение 8 содержит схемы Ч*, описывающие простую грамматику, практически весь лексический разбор языка Sisal 3.1 и показательную часть семантико-синтаксического разбора языка Sisal 3.1.

Приложение 9 посвящено спецификации формата файла, задающего интерпретируемый автомат анализатора, т. е. конечной форме преобразования программы графического метаязыка, описанного в главе 3.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

В результате работы создан компилятор переднего плана новой версии языка Sisal 3.1, основывающийся на хорошо проработанных моделях интерфейса взаимодействия с пользователем и модели разделения реализации транслятора на графическую и текстовые части, связанные воедино частью интерпретирующей. Полученные научные и практические результаты работы далее сформулированы более точно.

1. Разработана и формально описана новая версия языка Sisal 3.1. Новая версия языка Sisal 3.1 получена путём упрощения, улучшения,

расширения и уточнения пользовательского описания языка Sisal 90, а также использования идей языка Sisal 3.0 и пользовательских типов. Формальное описание синтаксиса языка Sisal 3.1 является первым формальным описанием синтаксиса языка Sisal со времен языка Sisal 1.2. Семантика языка Sisal 3.1 приводится в нестрогом виде пользовательского описания, которое, по замыслу, претендует на полноту и непротиворечивость. Введение пользовательских типов в язык Sisal 3.1 повлекло введение средств переопределения операций и статического полиморфизма. Изменение языка Sisal 90 в языке Sisal 3.1 было обусловлено повышением удобства разбора и улучшением читаемости программ этого языка.

2. Разработаны модель внутреннего представления (МВП) IR1 для машинно-независимого описания функциональных программ и её специализация для языка Sisal 3.1.

Модель внутреннего представления (МВП) 1R1 основывается на языке промежуточной формы IF1 и описывается системой взаимосвязанных интерфейсов и определяющей их взаимодействие реализацией СОМ-компонента. МВП IR1 задаёт общую основу специализации ВП 1R1 для конкретного языка программирования, поэтому в терминах МВП IR1 выражаются лишь самые общие понятия языка IF1, не зависящие от конкретного языка. Дня МВП IRI разработаны и описаны алгоритмы удаления неиспользуемых строк и типов, слияния эквивалентных типов.

3. Разработаны и реализованы модели описания вспомогательных компонентов МВП IR1: компоненты преобразования в эквивалентную XML-форму и компоненты визуализации.

Модели вспомогательных компонентов ВП IRI описываются системой интерфейсов, не зависят от специализации МВП IR1 и реализуются с помощью СОМ-компонента. Модель компонента XML-преобразования описывает эквивалентные преобразования между ВП IR1 и несколькими уровнями наглядности XML-текста. В модель заложена поддержка расширения и модификации ВП IR1 за счёт независимости XML-текста от порядка нумерации объектов ВП IRL Модель компонента визуализации обеспечивает отображение и перемещение по ВП IR1 в терминах графического языка промежуточной формы IF1. Реализация модели основывается на тесно интегрированном исходном коде размещения графов свободно-распространяемой системы GraphViz и для визуализации использует интервальные деревья для эффективного отображения больших графов и проверки наличия их вершин и портов в данной точке.

4. Разработана и реализована модель описания компонента для поддержки трансляции из текстового представления во ВП IRL Модель компонента поддержки трансляции из текстового

представления во ВП IR1 также описывается системой интерфейсов и реализуются с помощью СОМ-компонента. Модель описывает общий вид компилятора переднего плана в виде лексического и синтаксически-

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

5. Разработана модель построения компонента компилятора переднего плана и её графическое представление.

Разработанная модель основывается на модели детерминированного магазинного автомата и упрощает общий вид функции перехода для более наглядного графического представления автомата. Доказывается, что такое упрощение не влияет на возможность недетерминированных автоматов задавать любые контекстно-свободные языки. Для детерминированных автоматов доказывается, что класс, задаваемых ими языков, равен классу LLi языков. Модель расширяется семантически-зависимыми переходами, реализующими «семантику отношений» (контекстные условия), и средствами иерархической обработки ошибок разбора. Разработаны и описаны алгоритмы преобразования наглядного описания автомата к его эффективно интерпретируемой форме представления.

6. Создан компонент компилятора переднего плана, позволяющий преобразовывать модуль программы на языке Sisal 3.1 во внутреннее представление 1R1.

Разработанный в виде СОМ-компонента транслятор переднего плана является первой реализацией языка Sisal со времен языка Sisal 1.2 и успешно апробирует предложенные модели. К особенностям реализации транслятора относится его разделение па графическую, текстовую и интерпретирующую части. Графическая часть описывает автомат, распознающий синтаксис языка. Текстовая часть содержит раздельное описание «семантики отношений» языка и «операционной семантики», порождающей объекты

внутреннего представления IR1. Интерпретирующая часть транслятора связывает воедино его графическую и текстовую части.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Kasyanov V.N., Stasenko А.Р., Gluhankov М.Р., Dortman Р.А., PyjovK.A., Sinyakov A. I. SFP - An interactive visual environment for supporting of functional programming and supercomputing // WSEAS Transactions on Computers. — Athens: WSEAS Press, 2006. — Vol. 5, N 9. — P. 2063-2070.

2. Стасснко А. П. Автоматная модель визуального описания синтаксического разбора И Вычислительные технологии. — Новосибирск: ИВТ СО РАН, 2008. — Т. 13, N. 5. — С. 70-87.

3. Стасснко А. П., Пыжов К. А., Идрнсов Р.И. Компилятор в системе функционального программирования SFP // Вестник НГУ. Сер. Информационные технологии. -— Новосибирск: Изд-во НГУ, 2008. — 11 с.

4. Kasyanov V.N., Stasenko А. P. Sisal 3.1 language structures decomposition // Parallel Computing Technologies. — Lecture Notes in Computer Science, 2007. — Vol. 4671/2007. — P. 62-73.

5. Kasyanov V. N., Stasenko A.P. A Functional Programming System SFP: Sisal 3.1 Language Structures Decomposition // Proceedings of 9th International Conference, PaCT 2007, Pereslavl-Zalessky, Russia, September 2007. — Berlin: Springer-Verlag, 2007. — P. 62^73.

6. Kasyanov V.N., Stasenko A. P. Sisal 3.1 language structures decomposition // European Computing Conference. Book of Abstracts. — Athens: WSEAS Press, 2007. — P. 92.

7. Kasyanov V.N., Stasenko A. P. Sisal 3.2 language structures decomposition // Lecture Notes in Electrical Engineering. — Berlin: Springer-Verlag, 2009. — Vol. 28. — P. 582-594.

8. Stascnko A. P. Sisal 3.1 language structures décomposition // Bull. Novosibirsk Сотр. Center. Ser. Computer Science. — Novosibirsk, 2006.

— Iss. 24. — 8 p.

9. Глуханков М.П., Дортмаи П. A., Павлов A. A., Стасенко A. П.

Транслирующие компоненты системы функционального программирования SFP // Современные проблемы конструирования программ. — Новосибирск: Институт систем информатики имени А. П. Ершова СО РАН, 2002. — С. 69-87.

10. Стасснко А.П. Система интерфейсов транслятора во внутреннее представление IR1 // Методы и инструменты конструирования и оптимизации программ. — Новосибирск: Институт систем информатики имени А. Г1. Ершова СО РАН, 2005. — С. 229-238.

11. 'Стасенко А.П. Обзор потоковых языков программирования //

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

— Новосибирск: Институт систем информатики имени А. П. Ершова СО РАН, 2006. — 12 с.

12. Стасенко А.П. Автоматная модель визуального описания синтаксического разбора // Методы и инструменты конструирования программ. — Новосибирск: ИСИ СО РАН, 2007. — С. 186-209.

13. Стасенко А.П. Графический метаязык для описания транслятора // Сборник трудов аспирантов и молодых ученых «Молодая информатика». — Новосибирск: Институт систем информатики имени А. П. Ершова СО РАН, 2005. — С. 105-113.

14. Стасенко А.П. Графический метаязык для описания транслятора // Тез. докл. V Всеросс. конф. молодых ученых по математическому моделированию и информационным технологиям. — Новосибирск: ИВТ СО РАН, 2004. — С. 53.

15. Стасенко А.П. Совмещение достоинств Microsoft Dynamic HTML и W3C-coBMecTHMbix HTML в системе HTML-справки // ЬСонф.-конкурс

«Технологии Microsoft в информатике и программировании»: Тез. докл. — 11овосибирск, 2005. — С. 45-47.

16. Стасенко А. П. Использование автоматного подхода для построения компилятора переднего плана // Конф.-конкурс «Технологии Microsoft в теории и практике программирования»: Тез. докл. — Новосибирск, 2006. — С. 37-39.

17. Стасенко А.П. Визуализация внутреннего представления системы функционального программирования в ActiveX компоненте // Тр. XLIV Междунар. науч. студенческой конф. «Студент и научно-технический прогресс»: Информационные технологии. — Новосибирск: НГУ, 2006. — С. 135-136.

18. Стасенко А. П. Система функционального программирования языка Sisal // XII Международная научно-методическая конференция «Новые информационные технологии в университетском образовании». — Новосибирск: НГУ, 2007. — С. 162-165.

19. Стасенко А. П. Внутреннее представление системы функционального программирования Sisal 3.0. — Новосибирск, 2004. — 54 с. — (Препр. / РАН. Сиб. отд-е. ИСИ; № 110).

20. Стасенко А.П., Синяков А.И. Базовые средства языка Sisal 3.1. — Новосибирск, 2006. — 60 с. — (Препр. / РАН. Сиб. отд-е. ИСИ; № 132).

Стасенко А. П.

Автореферат:

Формат 60*84 1/8, 2 п. л. Тираж 100 жг Закач№ 329. 30.04. 2009

Отпечатано ЗАО И1Ц «Прайс-курьер» ул. Кутагелад*, 4г. т 330 7202

Введение.

1. Язык Sisal 3.1.

1.1. Потоковые языки программирования.

1.2. История развития языка Sisal.

1.2.1. Язык Val.

1.2.2. Sisal 1.2.

1.2.3. Sisal 2.0.

1.2.4. Sisal 90.

1.2.5. Sisal 3.0.

1.3. Нововведения языка Sisal 3.1.

1.3.1. Пользовательские типы.

1.3.2. Другие нововведения.

1.4. Ограничения языка Sisal 3.1.

1.5. Анализ изменений в языке Sisal 3.1.

1.5.1. Улучшение межъязыкового взаимодействия с языком Си.

1.5.2. Повышение читаемости программ.

1.5.3. Упрощение синтаксического разбора.

1.5.4. Устранение неоднозначностей синтаксического разбора.

1.5.5. Улучшение синтаксиса.

Выводы по главе 1.

2. Первое внутреннее представление IR1.

2.1. Требования к внутреннему представлению.

2.2. Обзор промежуточных представлений программ.

2.2.1. Модель потока данных Дениса.

2.2.2. Расширяемая модель расширяемого языка Берса.

2.2.3. Модель вычислений языка Пифагор.

2.3. Описание языка промежуточной формы IF1.

2.3.1. Основные понятия.

2.3.2. Задание последовательного выполнения.

2.3.3. Альтернатива.

2.3.4. Итерация.

2.4. Модель внутреннего представления IR1.

2.4.1. Моделирование языково-независимых понятий языка IF1.

2.4.2. Система интерфейсов модели.

2.5. Система дополнительных интерфейсов.

2.5.1. Преобразование IR1 в XML и обратно.

2.5.2. Визуализация IR1 в ActiveX компоненте.

Выводы по главе 2.

3. Графический метаязык описания транслятора.

3.1. Обзор методов построения трансляторов.

3.1.1. Нисходящие методы.

3.1.2. Восходящие методы.

В настоящий момент намечается существенное замедление роста производительности вычислительных систем за счет увеличения тактовой частоты вычислительных устройств, связанное с ограниченностью современных технологических возможностей. Поэтому для сохранения существующих темпов роста скорости вычислений, косвенно декларируемых законом «Moore's Law» [1], возобновляется интерес к параллельным вычислениям. Ярким тому подтверждением является появление процессоров с двумя независимыми вычислительными ядрами, ориентированных на массовый рынок. Прослеживается общая тенденция увеличения значимости роли многих процессорных ядер, что в обозримом будущем может привести к значительному росту возможностей вычислительных систем по параллельной обработке данных.

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

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

Однако и в функциональных языках существуют ограничивающие параллелизм факторы. Одной из таких причин является набор языковых операций, специально ориентированный на последовательные вычисления или ограниченный параллелизм. В частности, в функциональном языке Лисп (Lisp) [2] операторы для работы с данными обеспечивают выборку только одного компонента, а функциональный язык FP [3] не предусматривает распараллеливание на уровне независимых операторов. Также в модели вычислений, присущей функциональному языку, могут присутствовать элементы управления, тем или иным образом приводящие к разделению процессами общих вычислительных ресурсов. Например, в схемах потока данных Дениса [4] таким ресурсом является узел слияния потоков данных.

Указанные недостатки обычно обходятся в потоковых языках программирования [5], явно описывающих вычисления в виде графа потока данных и обычно являющихся также и функциональными языками. Эти языки, как правило, содержат операторы размножения информационных потоков, их группирования в списки данных различного уровня вложенности и одновременного выделения из списков нескольких независимых и разнородных по составу групп. Потоковые языки программирования изначально ориентировались на потоковые архитектуры вычислительных систем [6], имевших распространение в 80-90-х годах XX века, и с тех пор практически не развивались.

Тем самым, актуальность работы обуславливается:

1) технологическими трудностями роста производительности последовательных машинных архитектур и, как следствие, ростом интереса к параллельным вычислениям;

2) высокой изменчивостью параллельных машинных архитектур и, как следствие, необходимостью в машинно-независимом представлении параллелизма;

3) естественной пригодностью потоковых языков программирования для описания машинно-независимого параллелизма;

4) малой распространенностью и устарелостью существующих потоковых языков и систем программирования на их основе.

Язык программирования Sisal (Сисал) [7] является одним из самых известных потоковых языков промышленного уровня и позиционируется [8] как замена языка Фортран (Fortran) [9] для научных применений. Язык Sisal имеет следующие отличия от других функциональных языков, упрощающие переход с популярных императивных языков программирования:

• приближенный к языку Паскаль (Pascal) [10] синтаксис;

• развитая система типов;

• явно выделенные циклические выражения.

Последняя спецификация языка Sisal версии 2.0 [11] датируется 1991 годом, а последнее обновление транслятора OSC [12], работающего только с языком Sisal версии 1.2 от 1985 года, было в 1995 году. В 1995 году также появилось пользовательское описание языка Sisal 90 [13], не содержащее, однако, точных спецификаций языка.

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

В виду того, что работа проводится в рамках коллективной деятельности по созданию системы функционального программирования, было принято решение выполнить её в виде независимых программных компонентов. В данной работе, в основном, рассматривается компилятор переднего плана языка Sisal 3.1 в разработанное для него внутреннее представление (ВП) IR1 (Internal Representation 1), так как за остальные крупные части компилятора ответственны другие участники проекта [80].

Во время работы над компилятором переднего плана возникало множество промежуточных задач, связанных с хранением, передачей и отладкой ВП IR1. Для решения этих задач были разработаны вспомогательные компоненты для преобразования ВП IR1 в XML-представление и обратно, а также для просмотра ВП IR1 в графическом виде.

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

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

Цель работы — разработка и реализация моделей транслирующих компонентов системы функционального программирования. Достижение цели работы связывается с решением следующих задач.

1. Разработка языка Sisal версии 3.1, развивающего базовую, функциональную часть языка Sisal 3.0, являющегося входным языком системы SFP и основанную на языке Sisal 90.

1.1. Уточнение описания языка Sisal 90.

1.2. Расширение языка Sisal 90 средствами модульного программирования (Sisal 3.0) и пользовательскими типами.

1.3. Улучшение синтаксиса и семантики языка Sisal 90.

2. Разработка машинно-независимого ВП IR1 программ языка Sisal 3.1, основанного на графах информационных зависимостей.

2.1. Разработка модели внутреннего представления (ВП) IR1 для машинно-независимого описания функциональных программ и её специализация для языка Sisal 3.1.

2.2. Разработка и реализация вспомогательных компонентов ВП IR1 для его сохранения, восстановления и визуализации.

3. Исследование методов трансляции и создание компилятора переднего плана из текста программ языка Sisal 3.1b ВП IR1.

3.1. Разработка модели построения компоненты компилятора переднего плана, основанной на теории автоматов, и её графического представления.

3.2. Разработка компоненты поддержки трансляции из текстового представления во ВП IR1 (для поддержки нескольких входных языков системы SFP).

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

Научная новизна. В диссертационной работе получены новые научные результаты.

1. Спроектирована и формально описана новая версия языка Sisal 3.1, развивающая функциональную часть предыдущих версий языка Sisal и приближающая её к уровню современных языков программирования.

2. Разработаны модели для удобного построения, хранения, анализа, преобразования и использования машинно-независимого внутреннего представления программ функциональных языков программирования.

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

4. Формализована модель описания графической составляющей компилятора переднего плана, основанная на упрощении классической модели магазинного автомата с расширениями, делающими возможным её практическое применение. Практическая ценность. Разработанные язык программирования

Sisal 3.1, его ВП IR1 и транслятор из первого во второе являются неотъемлемой частью системы функционального программирования (SFP) [81, 82], разрабатываемой в рамках проекта ПРОГРЕСС [14]. Данные разработки будут использоваться другими участниками проекта SFP в качестве основы для создания своих частей проекта и будут внедрены в учебный процесс в Новосибирском госуниверситете.

Апробация работы. Основные положения диссертации обсуждались на следующих конференциях и семинарах: th •

1. 9 International Conference on Parallel Computing Technologies,

Pereslavl-Zalessky, 2007 год.

2. Европейская конференция по вычислениям (ЕСС-2007), г. Афины, 25-27 сентября, 2007.

3. V Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (с участием иностранных ученых), Новосибирск, ИВТ СО РАН, 2004 год.

4. Конференция-конкурс «Технологии Microsoft в информатике и программировании», Новосибирск, 2005 год.

5. Конференция-конкурс «Технологии Microsoft в теории и практике программирования», Новосибирск, 2006 год.

6. XLIV Международная научная студенческая конференция «Студент и научно-технический прогресс», Новосибирск, 2006 год.

7. XII Международная научно-методическая конференции «Новые информационные технологии в университетском образовании», 2007 год.

8. Семинар спецкурса «Введение в функциональное программирование», 2007 год.

9. Семинары «Конструирование и оптимизация программ», Новосибирск, ИСИ СО РАН, 2002-2008 годы.

Публикации. Основные результаты диссертационной, работы опубликованы в 19 печатных работах, из которых 2 препринта [83, 84], 12 статей [85, 86, 87, 81, 88, 89, 80, 90, 91, 92, 93, 94] и 6 тезисов докладов [95, 96, 97, 98, 82, 99]. Исследования поддерживались грантами УР.04.01.027 и УР.04.01.0201 научной программы «Университеты России» Министерства науки и образования Российской Федерации. Исследования выполнялись в соответствии с планами научно-исследовательских работ ИСИ СО РАН по проекту 3.15 «Методы и средства трансляции и конструирования программ». Проект проводился в рамках программы 3.1 СО РАН «Информационное и математическое моделирование в различных областях знаний, задачи поддержки принятия решений, экспертные системы, системное и теоретическое программирование».

Структура диссертации. Диссертация состоит из введения, четырёх глав, заключения, списка литературы и девяти приложений. Работа содержит 109 страниц в формате машинописного текста (за исключением приложений и библиографии), 78 рисунков и 22 таблиц. Список литературы содержит 99 наименований.

Выводы по главе 4

В главе рассматриваются существующие компиляторы языка Sisal 1.2, а также общие характеристики построенного компилятора переднего плана языка Sisal 3.1, транслирующего текст модуля программы в ВП IR1. Описывается интерфейс взаимодействия с компилятором переднего плана, задачи лексического анализа, общая структура и устройство синтаксического и семантического разборов. В приложениях А8.2 и А8.3 частично приводятся схемы для лексического и семантически-синтаксического разбора.

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

С помощью формализма схем ^Р написан работоспособный, легко-встраиваемый компилятор переднего плана языка Sisal 3.1, обеспечивающий:

• простоту учёта модификаций языка;

• достаточно высокую скорость трансляции;

• довольно качественные сообщения об ошибках и предупреждениях;

• развитые механизмы восстановления после ошибок разбора.

Использование графического метаязыка позволило сократить объём текста транслятора переднего плана языка Sisal 3.1 до десяти тысяч строк, по сравнению с тридцатью тысячами строк кода аналогичной части транслятора OSC 12.0 для более простой версии языка Sisal 1.2.

ЗАКЛЮЧЕНИЕ

В результате работы создан компилятор переднего плана новой версии языка Sisal 3.1, основывающийся на хорошо проработанных моделях интерфейса взаимодействия с пользователем и модели разделения реализации транслятора на графическую и текстовые части, связанные воедино частью интерпретирующей. Полученные научные и практические результаты работы далее сформулированы более точно.

1. Разработана и формально описана новая версия языка Sisal 3.1. Новая версия языка Sisal 3.1 получена путём упрощения, улучшения, расширения и уточнения пользовательского описания языка Sisal 90, а также использования идей языка Sisal 3.0 и пользовательских типов. Формальное описание синтаксиса языка Sisal 3.1 является первым формальным описанием синтаксиса языка Sisal со времен языка Sisal Л .2. Семантика языка Sisal 3.1 приводится в нестрогом виде пользовательского описания, которое, по замыслу, претендует на полноту и непротиворечивость. Введение пользовательских типов в язык Sisal 3.1 повлекло введение средств переопределения операций и статического полиморфизма. Изменение языка Sisal 90 в языке Sisal 3.1 было обусловлено повышением удобства разбора и улучшением читаемости программ этого языка.

2. Разработаны модель внутреннего представления (МВП) IR1 для машинно-независимого описания функциональных программ и её специализация для языка Sisal 3.1.

Модель внутреннего представления (МВП) IR1 основывается на языке промежуточной формы IF1 и описывается системой взаимосвязанных интерфейсов и определяющей их взаимодействие реализацией СОМ-компонента. МВП IR1 задаёт общую основу специализации ВП IR1 для конкретного языка программирования, поэтому в терминах МВП IR1 выражаются лишь самые общие, понятия языка IF 1, не зависящие от конкретного языка. Для МВП IR1 разработаны и описаны алгоритмы удаления неиспользуемых строк и типов, слияния эквивалентных типов.

3. Разработаны и реализованы модели описания вспомогательных компонентов МВП IR1: компоненты преобразования в эквивалентную XML-форму и компоненты визуализации.

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

Модель компонента визуализации обеспечивает отображение и перемещение по ВП IR1 в терминах графического языка промежуточной формы IF1. Реализация модели основывается на тесно интегрированном исходном коде размещения графов свободно-распространяемой системы GraphViz и для визуализации использует интервальные деревья для эффективного отображения больших графов и проверки наличия их вершин и портов в данной точке.

4. Разработана и реализована модель описания компонента для поддержки трансляции из текстового представления во ВП IR1. Модель компонента поддержки трансляции из текстового представления во ВП IR1 также описывается системой интерфейсов и реализуются с помощью СОМ-компонента. Модель описывает общий вид компилятора переднего плана в виде лексического и синтаксически-семантического разборов. Моделью определяются понятия потока символа, потока лексем, средств сообщения о событиях трансляции и' поддержки модульности. Реализация модели задаёт стандартные реализации её понятий, а также дополнительную функциональность, наподобие порождения потока символов файла в заданной кодировке, перечисление элементов которого вызывает дисковое чтение.

5. Разработана модель построения компонента компилятора переднего плана и её графическое представление.

Разработанная модель основывается на модели детерминированного магазинного автомата и упрощает общий вид функции перехода для более наглядного графического представления автомата. Доказывается, что такое упрощение не влияет на возможность недетерминированных автоматов задавать любые контекстно-свободные языки. Для детерминированных автоматов доказывается, что класс, задаваемых ими языков, равен классу LL] языков. Модель расширяется семантически-зависимыми переходами, реализующими «семантику отношений» (контекстные условия), и средствами иерархической обработки ошибок разбора. Разработаны и описаны алгоритмы преобразования наглядного описания автомата к его эффективно интерпретируемой форме представления.

6. Создан компонент компилятора переднего плана, позволяющий преобразовывать модуль программы на языке Sisal 3.1 во внутреннее представление IR1.

Разработанный в виде СОМ-компонента транслятор переднего плана является первой реализацией языка Sisal со времен языка Sisal 1.2 и успешно апробирует предложенные модели. К особенностям реализации транслятора относится его разделение на графическую, текстовую и интерпретирующую части. Графическая часть описывает автомат, распознающий синтаксис языка. Текстовая часть содержит раздельное описание «семантики отношений» языка и «операционной семантики», порождающей объекты внутреннего представления IR1. Интерпретирующая часть транслятора связывает воедино его графическую и текстовую части.

1. Moore G. Е. Cramming more components onto integrated circuits // Electronics Magazine. — NY: McGraw-Hill, 1965. — Vol. 38, No. 8. — P. 114-117.

2. McCarthy J. Lisp 1.5 programmer's manual / McCarthy J., Abrahams P. W., Edwards D. J., Hart T. P. and Levin M. I. т- 2nd ed. — Cambridge, MA: M.I.T. Press, 1962. — 106 p.

3. Backus J. Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs // Communications of the ACM.—NY: ACM Press, 1978. — Vol. 21, No. 8. —P. 613-641.

4. Dennis J. B. Data flow schemas / Dennis J. В., Fosseen J. B. and Linderman J. P. // Proc. of the Internat. Symp. on Theoretical Programming. — London, UK: Springer-Verlag, 1972. — Lect. Notes Comput. Sci. —Vol. 5,—P. 187-216.

5. Ackerman W. B. Data flow languages // IEEE Computer Magazine. —■ Los Alamitos, CA: IEEE Computer Society Press, 1982. — Vol. 15, No. 2.1. P. 15-25.

6. Veen A. H. Dataflow machine architecture // ACM Computing Surveys.

7. NY: ACM Press, 1986. —Vol. 18, No. 4.— P. 365-396.

8. Cann D. C. Retire Fortran?: a debate rekindled // Communications of the ACM.—NY: ACM Press, 1992. — Vol. 35, No. 8. —P. 81-89.

9. ISO/IEC 1539-1:2004(E). Information technology: Programming languages: Fortran: Part 1: Base language. — Geneva: Internat. Organization for Standardization (ISO), Central Secretariat, 2004.

10. ISO 7185:1990(E). Information technology:, Programming languages: Pascal. — Geneva: Internat. Organization for Standardization (ISO), Central Secretariat, 1990.

11. Bohm A.,P. W. The Sisal 2.0 reference manual / Bohm A. P. W., Cann D. C., Feo J. T. and Oldehoeft R. R. — Livermore, CA, 1991. — 128 p. — (Tech. Rep. / Lawrence Livermore National Laboratory; UCRL-MA-109098).

12. Cann D. C. The optimizing Sisal compiler. — Livermore, CA, 1992. — 74 p. — (Tech. Rep. / Lawrence Livermore National Laboratory; UCRL1. MA-110080).

13. Feo J. T. Sisal 90 user's guide / Feo J. Т., Miller P. J., Skedzielewski S. K. and Denton S. M. — Livermore, CA: Lawrence Livermore National Laboratory, Draft 0.96, 1995. — 80 p.

14. Kasyanov V. N., Evstigneev V. A. et al. The system PROGRESS as a tool for parallelizing compiler prototyping // Proc. of Eighth SIAM Conf. on Parallel Processing for Scientific Computing (PPSC-97). — Minneapolis, 1997. — P. 301-306.

15. Church A. The calculi of lambda-conversion // Annals of Mathematics Studies. —New Jersey: Princeton University Press, 1941. — 77 p.

16. Ashcroft E. A. and Wadge W. W. Lucid: A formal system for writing and proving programs // SIAM J. on Computing. — 1976. — Vol. 5, No. 3. —P. 336-354.

17. Nikhil R. S. Id language reference manual (version 90.1). — Cambridge, MA, 1991. — 54 p. — (Tech. Rep. / Massachusetts Institute of Technology, Laboratory for Computer Science, Computation Structures Group; Memo-284-2).

18. McGraw J. R. Val language, description and analysis. — Livermore, CA, 1980. — 51. p. — (Tech. Rep. / Lawrence Livermore National Laboratory; UCRL-83251, Rev. 1).

19. Ravishankar С. V. Post: a language for dataflow programming // Ph.D. thesis. — Madison: University of Wisconsin, Computer Sciences Department, 1987. — 213 p.

20. McGraw J. R. Parallel functional programming in Sisal: fictions, facts, and future. — Livermore, CA, 1993. — 40 p. — (Tech. Rep. / Lawrence Livermore National Laboratory; UCRL-JC-114360).

21. Hemmendinger D. Lazy evaluation and cancellation of computations // Proc. of the IEEE Internat. Conf. on,Parallel Processing (ICPP'85). — University Park, PA: IEEE Computer Society Press, 1985. — P. 840-842.

22. Finkel R. A. Advanced programming language design. — Мёп1о Park, CA: Addison-Wesley, 1995. — 480 p.

23. Cann D. C. Compilation techniques for high-performance applicative computation. — Fort Collins, CO, 1989. — 145 p. — (Tech. Rep. / Colorado State University, Computer Science Department; CS-89-108).

24. Cann D. C. Sisal multiprocessing support / Cann D. C., Lee C.-C., Oldehoeft R. R. and Skedzielewski. S. K. — Livermore, CA, 1987. — (Tech. Rep. / Lawrence Livermore National Laboratory; UCID-21115).

25. Beard P. C. An implementation of Sisal for distributed-memory architectures. — Livermore, CA, 1995. — 45 p. — (Tech. Rep. / Lawrence Livermore National Laboratory; UCRL-LR-122353).

26. Gurd J. P., Kirkham С. C. and Watson I. The Manchester prototype data flow computer // Communications of the ACM. — NY: ACM Press, 1985. — Vol. 28, No. 1. — P. 34-52.

27. Ranelletti J. E. Graph transformation algorithms for array memory optimization in applicative languages // Ph.D. thesis. — Davis, CA: University of California, Computer Science Department, 1987. — 222 p.

28. Cann D. C., Wolski R. M. and Feo J. T. Sisal: Toward, resolving the parallel programming crisis. — Livermore, CA, 1992. — 8 p. -— (Tech. Rep. / Lawrence Livermore National Laboratory; UCRL-JC-109774).

29. Hendrickson C. PI Programming a real code in a functional language (part 1) // Proc. of the Cray User Group (CUG) conf., Santa Fe, New Mexico, September 23-27, 1991. — 1991. — P. 333-344.

30. Stapleton L. Livermore labs offers Cray time free // Supercomputing Review. — San Diego, CA: London Manhattan Group of Companies, 1991. —Vol. 4, No. 5. —P. 14-15.

31. Watson I. and Gurd J. R. A prototype data flow computer with token labeling // Proc. of the AFIPS National Computer Conf., June 1979. — 1979. — Vol. 48, No. 6. — P. 623-628.

32. Adams J. C. Fortran 90 handbook: complete ANSI/ISO reference / Adams J. C., Brainerd W. S., Martin J. Т., Smith В. T. and Wagener J. L. — NY: Intertext Publications, Inc. / McGraw-Hill, Inc., 1993. — 740 p.

33. Бирюкова Ю. В. Sisal 90 Руководство пользователя. — Новосибирск, 2000. — 84 с. — (Препр. / РАН. Сиб. Отд-е. ИСИ; № 72).

34. Skedzielewski S. К. and Yates R. K. Fibre: An external format for Sisal and IF1 data objects, version 1.1. — Livermore, CA, 1988. — lip. — (Tech. Rep. / Lawrence Livermore National Laboratory; M-154, Rev. 1).

35. Касьянов В. H., Бирюкова Ю. В. и Евстигнеев В. А. Функциональный язык Sisal // Поддержка супервычислений и интернет-ориентированные технологии. — Новосибирск, 2001. — С. 54-67.

36. Касьянов В. Н. Оптимизирующие преобразования программ. — М.: Наука, 1988, —336 с.

37. Котов В. E. Сети Петри. — M.: Наука, 1984. — 160 с.

38. Бсрс А. А. Операторные структуры // Тр. симпозиума теоретическому программированию, 7-11 августа, 1972. —Новосибирск: ВЦ СО АН СССР, 1972. — Ч. 2. — С. 44-82.

39. Касьянов В. Н. Иерархические графы и графовые модели: вопросы визуальной обработки // Проблемы систем информатики и программирования. — Новосибирск, 1999. — С. 7-32.

40. Легалов А. И., Казаков Ф. А. и Кузьмин Д. А. Потоковая модель параллельных вычислений // Вестник КГТУ. Сб. научных трудов. — Красноярск: КГТУ, 1996. — Вып. 6. — С. 60-67.

41. Дейкстра Э. Дисциплина программирования / Пер. с англ., под ред. Любимского Э. 3. — М.: Мир, 1978. — 275 с.

42. Cormen Т. Н. Introduction to algorithms / Cormen Т. H., Leiserson С. Е., Rivest R. L. and Stein C. — 2nd ed. — NY: McGraw-Hill, 2001. — 1180 P

43. Ахо А. и Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т.1. Синтаксический анализ. — М.: Мир, 1978. — 612 с.

44. Ершов А. П. и Грушецкий В. В. Метод описания алгоритмических языков, ориентированных на реализацию. — Новосибирск, 1977. — 40 с. — (Препр. / АН СССР. Сиб. отд-ние. ВЦ.; № 74).

45. Lesk М. Е. and Schmidt Е. Lex a lexical analyzer generator. — NY: Murray Hill, 1975. — 13 p. — (Tech. Rep. / AT&T Bell Labs; No. 39).i

46. Евстигнеев В. А. и Касьянов В. Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука, 1994. — 360 е.: ил.

47. Moll R. N., Arbib М. A. and Kfoury A. J. An introduction to formal language theory. —NY: Springer-Verlag, 1988. —203 p.

48. Appel A. W. and Palsberg J. Modern compiler implementation in Java. — 2nd ed. — UK: Cambridge University Press, 2002. — 501 p.

49. Johnson S. C. YACC yet another compiler compiler. — NY: Murray Hill, 1975. — 33 p. — (Tech. Rep. / AT&T Bell Labs; No. 32).

50. Gagnon E. M. SableCC, an object oriented compiler framework // M. S. thesis. — Montreal, Canada: McGill University, 1998. — 97 p.

51. Кузнецов Б. П. Психология автоматного программирования // Журнал BYTE. — 2000. — №11. — С. 22-29.

52. Легалов А. И. Разработка трансляторов в учебном курсе // Тез. t междунар. научно-методической конф. «Новые информационныетехнологии в университетском образовании», Новосибирск, 19-22 марта, 1996. — 1996.

53. Gurevich Y. Evolving algebras 1993: Lipari guide // Specification and validation methods. —NY: Oxford University Press, 1995. —P. 9-36.

54. Шалыто A. A. Switch-технология // Алгоритмизация и программирование задач логического управления. — СПб.: Наука, 1998. —628 с.

55. Штучкин А. А. и Шалыто А. А. Совместное использование теории построения компиляторов и SWITCH-технологии // Тр. X Всеросс. научно-методической конф. «Телематика-2003». — СПб.: СПбГИТМО (ТУ), 2003.

56. Любченко В. С. Конечно-автоматная технология программирования // Тр. междунар. научно-методической конф. «Телематика '2001». — СПб.: СПбГИТМО(ТУ), 2001. — С. 127-128.

57. Вирт Н. и Иенсен К. Паскаль. Руководство для пользователя и описание языка. — М.: Финансы и статистика, 1989. — 255 с.

58. Kutter P. W. and Pierantonio A. Montages specifications of realistic programming languages // J. of Universal Computer Science. — 1997. — Vol. 3, No. 5. —P. 416-442.

59. ITU-T Recommendation Z.100. Specification and Description Language (SDL). — Geneva: ITU-T, 1994.

60. Вельбицкий И. В. Технология программирования. — Киев: Техника, 1984. —274 с.

61. Касьянов В. И. и Поттосин И. В. Методы построения трансляторов / Отв. ред. Ершов. А. П. — Новосибирск: Наука, 1986. — 344 с.

62. Sarkar V. and Cann D. С. POSC: A partitioning and optimizing Sisal compiler. — Livermore, С A, 1990. — 14 p. — (Tech. Rep. / Lawrence Livermore National Laboratory; UCRL-102737).

63. Bohm A. P. W. and Sargeant J. Efficient dataflow code generation for Sisal. — Manchester, UK, 1985. — 29 p. — (Tech. Rep. / University of Manchester, Department of Computer Science; UMCS-85-10-2).

64. Freeh V. W. and Andrews G. R. fsc: A Sisal compiler for both distributed and shared-memory machines // Conf. on High-Performance Functional Computing, Denver, CO, April 9-11, 1995. — 1995. — 11 p.

65. Garza-Salazar D. A., Bohm A. P. W. D-OSC: A Sisal compiler for distributed memory machines // Proc. of the 2nd Parallel Computation and Scheduling Workshop (PCSW'97). — Ensenada, Mexico, 1997. — 13 p.

66. The Unicode Standard / The Unicode Consortium. — Version 4.0. — Boston, MA: Addison-Wesley, 2003.

67. ISO/IEC 10646:2003(E). Information technology: Universal Multiple-Octet Coded Character Set (UCS). — Geneva: Internat. Organization for Standardization (ISO), Central Secretariat, 2003.

68. ANSI X3.4:1986. Information systems: coded character sets: 7-Bit American national Standard Code for Information Interchange (7-Bit ASCII). — NY: American National Standards Institute (ANSI), 1986.

69. Робинсон У. C# без лишних слов / Пер. с англ. — М.: ДМК Пресс, 2002. — 352 е.: ил. (Серия «Для программистов»).

70. ISO/IEC 9899:1999(Е). Programming languages: С. — Geneva: Internat. Organization for Standardization (ISO), Central Secretariat, 1999."

71. ISO/IEG 14882:2003(E). Programming languages: С++.— Geneva: Internat. Organization for Standardization (ISO), Central Secretariat, 2003.

72. ISO/IEC 14977:1996(E). Information technology: Syntactic metalanguage: Extended BNF. — Geneva: Internat. Organization for Standardization (ISO), Central Secretariat, 1996.

73. ANSI/IEEE 754-1985. IEEE standard for binary floating-point arithmetic. — NY: Institute of Electrical and Electronics Engineers, 1985 (Reprinted in SIGPLAN Notices, 22(2):9-25, 1987).

74. Стасенко А. П., Пыжов К. А., Идрисов P. И. Компилятор в системе функционального программирования SFP // Вестник НГУ. Сер. Информационные технологии. — Новосибирск: Изд-во НГУ, 2008. — 11 с.

75. Kasyanov V. N., Stasenko А. P., Gluhankov М. P., Dortman Р. А., Pyjov К. A., Sinyakov A. I. SFP An interactive visual environment for supporting of functional programming and supercomputing // WSEAS

76. Transactions on Computers. — Athens: WSEAS Press, 2006. — Vol. 5, N 9. — P. 2063-2070.

77. Стасенко А. П. Система функционального программирования языка Sisal // XII Международная научно-методическая конференция «Новые информационные технологии в университетском образовании». — Новосибирск: НГУ, 2007. — С. 162-165.

78. Стасенко А. П. Внутреннее представление системы функционального программирования Sisal 3.0. — Новосибирск, 2004.54 с. — (Препр. / РАН. Сиб. отд-е. ИСИ; № 110).

79. Стасенко А. П., Синяков А. И. Базовые средства языка Sisal 3.1.

80. Новосибирск, 2006. — 60 с. — (Препр. / РАН. Сиб. отд-е. ИСИ; № 132).

81. Глуханков М. П., ДоргманП. А., Павлов А. А., Стасенко А. П.

82. Транслирующие компоненты системы функционального программирования SFP // Современные проблемы конструирования программ. — Новосибирск: Институт систем информатики имени А. П. Ершова СО РАН, 2002. — С. 69-87.

83. Стасенко А. П. Система интерфейсов транслятора во внутреннее представление IR1 // Методы и инструменты конструирования и оптимизации программ. — Новосибирск: Институт систем информатики имени А. П. Ершова СО РАН, 2005. — С. 229-238.

84. Стасенко А. П. Графический метаязык для описания транслятора // Сборник трудов аспирантов и молодых ученых «Молодая информатика». — Новосибирск: Институт систем информатики имени А. П. Ершова СО РАН, 2005. — С. 105-113.

85. Стасенко А. П. Обзор потоковых языков программирования // Проблемы интеллектуализации и качества систем программирования.

86. Новосибирск: Институт систем информатики имени А. П. Ершова СО РАН, 2006. — 12 с.

87. Stasenko A. P. Sisal 3.1 language structures decomposition // Bull. Novosibirsk Сотр. Center. Ser. Computer Science. — Novosibirsk, 2006. — Iss. 24. — 8 p.

88. Стасенко А. П. Автоматная модель визуального описания синтаксического разбора // Методы и инструменты конструирования программ. — Новосибирск: ИСИ СО РАН, 2007. — С. 186-209.

89. Стасенко А. П. Автоматная модель визуального описания синтаксического разбора // Вычислительные технологии. — Новосибирск: ИВТ СО РАН, 2008. — Т. 13, N. 5. — С. 70-87.

90. Kasyanov V. N., Stasenko A. P. Sisal 3.1 language structures decomposition // Parallel Computing Technologies. — Lecture Notes in Computer Science, 2007. — Vol. 4671/2007. — P. 62-73.

91. Kasyanov V. N., Stasenko A. P. Sisal 3.2 language structures decomposition // Lecture Notes in Electrical Engineering. — Berlin: Springer-Verlag, 2009. — Vol. 28. — P. 582-594.

92. Стасенко А. П. Графический метаязык для описания транслятора // Тез. докл. V Всеросс. конф. молодых ученых по математическому моделированию и информационным технологиям. — Новосибирск: ИВТ СО РАН, 2004. — С. 53.

93. Стасенко А. П. Совмещение достоинств Microsoft Dynamic HTML и W3C-coBMecTHMbix HTML в системе HTML-справки // Конф.-конкурс «Технологии Microsoft в информатике и программировании»: Тез. докл. — Новосибирск, 2005. — С. 45-47.

94. Стасенко А. П. Использование автоматного подхода для построения компилятора переднего плана // Конф.-конкурс

95. Технологии Microsoft в теории и практике программирования»: Тез. докл. — Новосибирск, 2006. — С. 37-39.

96. Kasyanov V. N., Stasenko А. P. Sisal 3.1 language structures decomposition // European Computing Conference. Book of Abstracts. — Athens: WSEAS Press, 2007. — P. 92.список иллюстрация

97. Рис. 1. Иерархия основных интерфейсов внутреннего представления.421. Рис. 2. Вход—>вход.461. Рис. 3. Выход—>вход.461. Рис. 4. Вход—>выход.461. Рис. 5. Выход—>выход.46

98. Рис. 6. Иерархия интерфейсов коллекций внутреннего представления.47

99. Рис. 7. Иерархия интерфейсов итераторов коллекций ВП.48

100. Рис. 8. Иерархия интерфейсов пар внутреннего представления.49

101. Рис. 9. Иерархия интерфейсов библиотеки irlxml.dll.49

102. Рис. 10. Иерархия интерфейсов библиотеки irlview.dll.51

103. Рис. 11. Иерархия эффективно разбираемых грамматик.56

104. Рис. 12. Иерархия языков эффективно разбираемых грамматик.57 '

105. Рис. 13. Переход 1-го типа.71

106. Рис. 14. Переход 2-го типа.71

107. Рис. 15. Переход 3-го типа.71

108. Рис. 16. Расширенная схема задающая контекстно-зависимые языки.75

109. Рис. 17. Аналог входа в блок try.76

110. Рис. 18. Аналог выхода из блока try.76

111. Рис. 19. Применение схем VF для разбора лексики и синтаксиса.77

112. Рис. 20. Схема транслятора модуля программы на языке Sisal 3.1 в ВП IR1 .86

113. Рис. 21. Иерархия основных интерфейсов транслятора (txt2irl.dll).89

114. Рис. 22. Иерархия интерфейсов потоков символов и лексем транслятора.91

115. Рис. 23. Иерархия интерфейсов событий трансляции.92

116. Рис. 24. Иерархия интерфейсов поддержки межмодульных связей.92

117. Рис. 25. Граф функции phi.180

118. Рис. 26. Граф составной вершины Select.180

119. Рис. 27. Первый граф составной вершины Select.181

120. Рис. 28. Второй граф составной вершины Select.181

121. Рис. 29. Третий граф составной вершины Select.181

122. Рис. 30. Четвертый граф составной вершины Select.181

123. Рис. 31. Граф функции nri.184

124. Рис. 32. Граф составной вершины LoopA.184

125. Рис. 33. Первый граф составной вершины LoopA.184

126. Рис. 34. Второй граф составной вершины LoopA.184

127. Рис. 35. Третий граф составной вершины LoopA.184

128. Рис. 36. Четвертый граф составной вершины LoopA.184

129. Рис. 37. Граф функции sum.193

130. Рис. 38. Пример схемы задающей регулярный язык.;.197

131. Рис. 39. Пример схемы задающей детерминированный КС язык.197

132. Рис. 40. Пример схемы задающей контекстно-зависимый язык.;.198

133. Рис. 41. Лексический анализ. Часть 1.199

134. Рис. 42. Лексический анализ. Часть 2.:.2001. Рис. 43. Комментарий.200

135. Рис. 44. Идентификатор или ключевое слово. Часть 1.201

136. Рис. 45. Идентификатор или ключевое слово. Часть 2.202

137. Рис. 46. Двойственные лексемы. Часть 1.203

138. Рис. 47. Двойственные лексемы. Часть 2.203

139. Рис. 48. Символьный литерал.204

140. Рис. 49. Символьный литерал, десятичный код.205

141. Рис. 50. Символьный литерал, шестнадцатеричный код.205

142. Рис. 51. Символьный литерал, восьмеричный код.206

143. Рис. 52. Числовой литерал.207

144. Рис. 53. Целочисленный литерал.208

145. Рис. 54. Вещественный литерал.208

146. Рис. 55. Вещественный литерал одинарной точности.209

147. Рис. 56. Вещественный литерал двойной точности.210

148. Рис. 57. Строковой литерал.211

149. Рис. 58. Буквальный строковой литерал.212

150. Рис. 59. Окончание строкового литерала.213

151. Рис. 60. Обычный строковой литерал.214

152. Рис. 61. Обычный строковой литерал, десятичный код.215

153. Рис. 62. Обычный строковой литерал, восьмеричиый код.216

154. Рис. 63. Обычный строковой литерал, шестнадцатеричный код.217

155. Рис. 64. Синтаксический анализ.218

156. Рис. 65. Трансляция типа.•.2191. Рис. 66. Тип массива.2201. Рис. 67. Тип потока.:.220

157. Рис. 68. Тип выражения.220

158. Рис. 69. Трансляция множества типов.220

159. Рис. 70. Трансляция типа записи.221

160. Рис. 71. Трансляция типа функции.222

161. Рис. 72. Трансляция имени типа.223

162. Рис. 73. Трансляция типа союза.224

163. Рис. 74. Трансляция операнда алгебраического выражения. Часть 1.225

164. Рис. 75. Трансляция операнда алгебраического выражения. Часть 2.225

165. Рис. 76. Трансляция выражения if.226

166. Рис. 77. Пропуск содержимого выражения if.227

167. Рис. 78. Разбор части else выражения if.228