Москва: ДМК Пресс, 2010. - 192с.
Книга известного специалиста в области информатики Никлауса Вирта написана по материалам его лекций по вводному курсу проектирования компиляторов. На примере простого языка Оберон-0 рассмотрены все элементы транслятора, включая оптимизацию и генерацию кода. Приведен полный текст компилятора на языке программирования Оберон. Для программистов, преподавателей и студентов, изучающих системное программирование и методы трансляции.
Содержание
Введение
Язык и синтаксис
Упражнения
Регулярные языки
Упражнение
Анализ контекстно-свободных языков
Метод рекурсивного спуска;
Таблично-управляемый нисходящий синтаксический анализ
Восходящий синтаксический анализ
Упражнения
Атрибутные грамматики и семантики
Правила типов
Правила вычислений
Правила трансляции
Упражнение
Язык программирования Оберон-0
Упражнение
Синтаксический анализатор для Оберона-0
Лексический анализатор
Синтаксический анализатор
Устранение синтаксических ошибок
Упражнения
Учет контекста, заданного объявлениями
Объявления
Записи о типах данных
Представление данных во время выполнения
Упражнения
RISC-архитектура как цель
Ресурсы и регистры
Выражения и присваивания
Прямая генерация кода по принципу стека
Отсроченная генерация кода
Индексированные переменные и поля записей
Упражнения
Условные и циклические операторы и логические выражения
Сравнения и переходы
Условные и циклические операторы
Логические операции
Присваивание логическим переменным
Упражнения
Процедуры и концепция локализации
Организация памяти во время выполнения
Адресация переменных
Параметры
Объявления и вызовы процедур
Стандартные процедуры
Процедуры-функции
Упражнения
Элементарные типы данных
Типы REAL и LONGREAL
Совместимость между числовыми типами данных
Тип данных SET
Упражнения
Открытые массивы, указательный и процедурный типы
Открытые массивы
Динамические структуры данных и указатели
Процедурные типы
Упражнения
Модули и раздельная компиляция
Принцип скрытия информации
Раздельная компиляция
Реализация символьных файлов
Адресация внешних объектов
Проверка конфигурационной совместимости
Упражнения
Оптимизация и структура пре/постпроцессора
Общие соображения
Простые оптимизации
Исключение повторных вычислений
Распределение регистров
Структура пре/постпроцессорного компилятора
Упражнения
Приложение А.
Синтаксис
Оберон-0
Оберон
Символьные файлы
Приложение В.
Набор символов ASCII
Приложение С.
Компилятор Оберон-0
Лексический анализатор
Синтаксический анализатор
Генератор кода
Литература
Скачать файл
- 2.16 МБ
- добавлен 19.09.2009
В книге известного английского автора рассматриваются проблемы проектирования и построения компиляторов для языков программирования высокого уровня, в частности Алгола 60, ПЛ/1, Алгола 68, Паскаля и Ады. Основное внимание уделяется целям проектирования надежных компиляторов и средствам их достижения. Практические вопросы разъясн...
- 1.57 МБ
- добавлен 17.12.2008
Лекции по построению компилятора на Pascal. 255 с.
Эта серия статей является руководством по теории и практике разработки синтаксических анализаторов и компиляторов языков программирования. Прежде чем вы закончите чтение этой книги, мы раскроем все аспекты конструирования компиляторов, создадим новый язык программирования, и...
- 1.25 МБ
- добавлен 16.05.2009
Эта серия статей является руководством по теории и практике разработки синтаксических анализаторов и компиляторов языков программирования. Прежде чем вы
закончите чтение этой книги, мы раскроем все аспекты конструирования компиляторов, создадим новый язык программирования, и построим работающий компилятор.
- 5.49 МБ
- добавлен 10.10.2007
М.: Издательский дом "Вильямс", 2003. - 768 с.: ил.
Каждый, кто интересовался разработкой компиляторов, несомненно, слышал о знаменитой "Книге Дракона" - "Dragon Book", классическом труде Ахо и Ульмана "Принципы разработки компиляторов". Бурное развитие технологий компиляции привело к рождению нового дракона - книги "К...
- 1.22 МБ
- добавлен 16.05.2009
Предмета: лексический и синтаксический анализ, организация памяти, генерация кода. Сделана попытка на протяжении всего изложения провести единую "атрибутную" точку зрения на процесс разработки компилятора. В книге не затрагиваются чрезвычайно важные вопросы глобальной оптимизации и разработки компиляторов для машин с параллельно...
- 59.93 МБ
- добавлен 07.12.2010
Эта небольшая, но емкая книга является введением в теорию создания компиляторов, а также кратким описанием принципов их работы. Материал изложен в расчете на читателя, не знакомого с данным предметом. В тексте предлагаются рекомендации по дополнительной литературе и даны подсказки по средствам инструментальной поддержки.
Язык должен быть очевидным и естественным отражением фундаментальных и наиболее важных концепций алгоритмов.
Никлаус Вирт
Никлаус Вирт
Никлаус Вирт прежде всего известен как создатель языка программирования PASCAL. Кроме этого, на его счету такие великолепные разработки, как MODULA-2, OBERON и многое-многое другое.
Родился Никлаус 15 февраля 1934 года в Винтерхуре (Швейцария). Родители Никлауса - Уолтер и Хедвиг (Келер) Вирт. Он женился на Нани Такер, у них трое детей: дочери Кэролин и Тина, сын Христиан. Вирт приятный в общении и добродушный человек, который выглядит моложе своих лет. Все свободное от работы время он проводит с семьей, часто совершая пешие походы по холмистым возвышенностям северной Швейцарии.
В сферу информатики Вирт погрузился в 1960 году, когда ей не уделялось должного внимания ни в коммерческой рекламе, ни в академических учебных планах. Никлаус рассказывает: "…Во время моего обучения в Швейцарском государственном технологическом институте единственное упоминание о компьютерах, которое я услышал, прозвучало в факультативном курсе, читавшемся Амброзом Спайзером, ставшим позднее президентом IFIP. Разработанный им компьютер ERMETH был малодоступен обычным студентам, и поэтому мое посвящение в информатику оказалось отложенным до того момента, как я прослушал курс численного анализа в Лавальском университете в Канаде. Тогда мне стало очевидно, что программирование будущих компьютеров должно было быть более эффективным. Поэтому я учился в первую очередь не проектировать аппаратную часть, а правильно и элегантно ее использовать".
Вирт присоединился к группе, участвовавшей в разработке - или, скорее, в доработке - компилятора и языка для компьютера IBM-704. Этот язык был назван NELIAC и являлся диалектом языка ALGOL-58.
С этого момента и начались приключения Никлауса в области языков программирования. Первый эксперимент привел к диссертации и к языку EULER, который оказался академически элегантным, но имел малую практическую ценность - он был почти антитезой более поздним языкам с типами данных и структурным программированием. Но этот язык заложил фундамент систематической разработки компиляторов, позволявших без потери ясности расширять их, чтобы включить новые возможности.
Выдающийся же этап в карьере Вирта начался в Стэнфордском университете, где он работал в качестве адъюнкт-профессора информатики вновь созданного факультета вычислительной техники с 1963 по 1967 год. Язык EULER привлек внимание рабочей группы Международной федерации по обработке информации (IFIP), участвовавшей в составлении планов, относительно будущего ALGOL.
Сейчас можно сказать, что работа Вирта над языком PASCAL началась именно тогда, в 1965 году, когда IFIP пригласила его принять участие в разработке нового языка, который должен был стать преемником ALGOL-60. Разработчики разделились на два направления, и Вирт оказался в том из них, которое пошло по пути расширения ALGOL. В 1966 году в Стэнфордском университете был создан язык под названием ALGOL-W.
С осени 1967 по 1968 год, когда Вирт вернулся в Швейцарию и служил в качестве адъюнкт-профессора в университете Цюриха, освободившись от обязательств перед IFIP, он разработал язык, ставший преемником ALGOL-W. Вирт назвал этот язык PASCAL, в честь французского математика и физика XVII столетия Блеза Паскаля, который в 1642 году сконструировал вычислительную машину, чтобы помочь своему отцу в работе по сбору налогов. "Кроме того, слово "PASCAL" звучит довольно мелодично", - говорит Вирт. Язык PASCAL первоначально разрабатывался как язык для обучения, но этим его функции не ограничились. В 1972 году PASCAL начал использоваться на занятиях по программированию в Швейцарском государственном технологическом институте. Свою работу над языком Никлаус закончил в 1974 году, создав высококачественный компилятор, а подлинное признание PASCAL получил после разработки Кеном Боулесом P-кода для микрокомпьютеров, который позволил использовать PASCAL на новых машинах различной конфигурации.
После этого он переключил свое внимание на изучение мультипрограммирования, в результате чего появился язык MODULA, предназначенный главным образом для программирования специализированных систем, в том числе и миникомпьютеров. Основой для нового языка послужил "Параллельный PASCAL", в котором был применен принцип модульной организации комплексов программ, позволяющий программисту "прятать" определенные части программ. Первоначальный вариант MODULA-1 "никогда не рассматривался как полноправный язык программирования", подчеркивает Вирт. Языком модульного программирования стал MODULA-2, ориентированный на персональные компьютеры.
В эти годы работа Вирта была связана с конструированием персонального компьютера "Лилит" и использованием языка MODULA-2.
OBERON - еще один язык программирования, созданный доктором Виртом в 1987 году и названный в честь спутника Урана - OBERON, открытого "Вояджером" в 1977 году.
При создании всех своих языков программирования Вирт придерживался принципа: "Сущности не следует умножать без необходимости", который получил название "бритва Оккама" В языке OBERON этот принцип реализован особенно явно. OBERON стал продолжением линии языков ALGOL-60, PASCAL, MODULA-2. OBERON создан на основе языка MODULA-2, однако, в отличие от PASCAL и MODULA-2, это комбинация языка программирования и операционной системы "для отдельного пользователя персональной рабочей станции". Удивительно простой и даже аскетичный, OBERON представляет собой, пожалуй, минимальный язык высокого уровня.
Работа продолжалась там же в Цюрихе, где Вирт находился уже в качестве профессора информатики с 1968 по 1975 год. Одновременно, начиная с 1968 года, доктор Никлаус Вирт стал профессором информатики в Федеральном Институте технологий Цюриха в Швейцарии, где и работает в этом звании по сей день и продолжает активное исследование в области языков программирования.
Талант Вирта как разработчика языков программирования дополняется писательским даром. В апрельском номере 1971 года журнала "Communications of the ASM" Вирт опубликовал основополагающую статью по "нисходящему" методу проектирования программ ("Разработка программы методом поэтапного усовершенствования"), в которой сформулированы принципы нисходящего построения программы (с последовательным уточнением ее фрагментов). Полученный в результате элегантный и мощный метод проектирования не утратил своей значимости и сегодня. Две другие его статьи "О дисциплине программирования в реальном времени" и "Что мы можем сделать с необязательным разнообразием обозначений", опубликованные в том же журнале, посвящены проблемам поиска адекватного языкового формализма.
Вирт написал несколько книг по программистской тематике: "Алгоритмы и структуры данных", "Программирование на OBERON", "PASCAL - руководство пользователя и справочник" и "Проект цифровых операций".
Сейчас доктор Вирт совместно с тремя другими коллегами занимается вопросами автоматизированного проектирования аппаратных средств компьютерных систем.
Все работы доктора Вирта внесли большой вклад в компьютерную науку. PASCAL сделал языки программирования более легкими для использования и изучения, а компьютеры более доступными для массового пользователя. Его проекты, от EULER до OBERON, стремились упростить и уничтожить барьеры между аппаратными средствами и программным обеспечением, сделать языки программирования более легкими в использовании.
Конечно, известно много других компьютерных языков программирования, помимо PASCAL, OBERON или MODULA-2, но вклад Вирта в создание и развитие языков программирования очень значителен.
За большой вклад в информатику доктор Никлаус Вирт получил многочисленные награды и почести. Американский Совет Магистров присвоил ему звание член-корреспондента; Компьютерное Общество Института Инженеров по электронике и радиотехнике - звание компьютерного пионера; он получил приз IBM европейской науки и техники; стал членом Швейцарской Академии Инженерии и иностранным партнером Американской Академии Инженерии, а также получил орден "Pur le merte" и премию Тьюринга. Вирт получил почетные докторские степени от многих университетов: университет Лаваль, Квебек (Канада), университет Калифорнии, Беркли, университет Йорк (Англия), университет Лине Иоганна Кеплера (Австрия), университет Новосибирска (Россия), Открытый университет Англии, университет Претории (Южная Африка).
Из книги Средневековая Франция автора Поло де Болье Мари-Анн Из книги Повседневная жизнь Европы в 1000 году автора Поньон ЭдмонОбразование «вульгарных языков» После того как латинский язык еще в античную эпоху вытеснил разнообразные италийские диалекты, он стал внедряться также в завоеванные Галлию и Испанию. Конечно, это не был язык Цицерона, Тита Ливия и Сенеки. На языке, который мы находим у
Из книги Молотов. Полудержавный властелин автора Чуев Феликс ИвановичЗнание языков Молотов говорит, что не знает иностранных языков. Однако, читает Мопассана по-французски, Каутского - по-немецки… Я помню из детства, что в газетах писали, как он в ООН поправил переводчика, неточно переведшего с английского.Сказал, что языки учил в
Из книги Тюремные тетради [Избранное] автора Грамши АнтониоВЗАИМОПЕРЕВОДИМОСТЬ НАУЧНЫХ И ФИЛОСОФСКИХ ЯЗЫКОВ В 1921 году по поводу организационных вопросов Виличи писал или говорил (примерно) так: мы не сумели «перевести» наш язык на европейские языки.Необходимо решить следующий вопрос: является ли взаимопереводимость различных
Из книги Тайны Беларуской Истории. автора Деружинский Вадим ВладимировичО смене языков. Как мне кажется, сегодня сами носители древнего наследия предков путают - идет речь о ятвягах или пруссах. Плюс тут еще и лаборский язык, который вполне может оказаться прусским языком. Хотя недавно в одной телепередаче о лаборах было высказано мнение, что,
Из книги Новая теория происхождения человека и его вырождения автора Мошков Валентин Александрович30. ПРОИСХОЖДЕНИЕ ЯЗЫКОВ Порча звуков от недостатков органов речи. Разнообразие языков произошло от разнообразия способов расселения и от его разновременности. Арийцы азиатские сравнительно недавно выселились из Европы.Происхождение того множества языков, которые мы
Из книги От тайны к знанию автора Кондратов Александр МихайловичГде была колыбель языков? Малайско-индонезийская, или австронезийская, семья языков не имеет родства с другими семьями мира. Правда в последнее время добыты факты, говорящие о том, что в глубокой древности, примерно 9 тысяч лет назад, эта семья образовывала вместе с
Из книги История русской литературы XIX века. Часть 2. 1840-1860 годы автора Прокофьева Наталья Николаевна автора Из книги Славянская энциклопедия автора Артемов Владислав Владимирович Из книги Дорогами тысячелетий автора Драчук Виктор СеменовичОстров разных языков В третьем и втором тысячелетиях до нашей эры на островах Эгейского моря, на западе Малой Азии, в Греции и на острове Крит существовала яркая, высокоразвитая культура. Ее многочисленные следы находят до сих пор. Наиболее крупные археологические
Из книги Краткая история славян автора Таевский Д АИерархия славянских языков Иллирийский язык Албанский языкo Гегийские говоры o Тоскский диалект Латынь (Романская группа языков) Балкано-романская подгруппа (romana comuna)o Арумынский (аромунский) язык? Северная зона Фаршеротский диалект Москопольский диалект
Из книги Вагрия. Варяги Руси Яра: очерк деполитизированной историографии автора Чудинов Валерий АлексеевичБЛИЗОСТЬ ЯЗЫКОВ «Зубы», или Начало цепи странных совпадений Первым на наличие «странностей» обратила мое внимание преподаватель английского языка Российского университета дружбы народов, казашка по национальности Улданай Бахтикиреева, которая очень удивилась
Из книги Архитекторы компьютерного мира автора Частиков АркадийАлексей Андреевич Ляпунов Автор первых нотаций языков программирования Имеется ряд способов описания строения алгоритмов: машины Тьюринга, продукция Поста, нормальные алгоритмы Маркова, рекурсии и т. п. Однако для интересов кибернетики эти способы неудобны. Общее
Из книги Полное собрание сочинений. Том 8. Сентябрь 1903 - сентябрь 1904 автора Ленин Владимир Ильичд) Инцидент с равноправием языков Вернемся к порядку заседаний съезда.Мы убедились теперь, что еще до перехода к обсуждению вопросов по существу на съезде ясно обнаружилась не только совершенно определенная группа антиискровцев (8 голосов), но и группа промежуточных,
Из книги Всемирная история в изречениях и цитатах автора Душенко Константин ВасильевичАЛГОРИТМЫ + СТРУКТУРЫ ДАННЫХ = ПРОГРАММЫ
Монография известного швейцарского специалиста по системному программированию, знакомого советским читателям по переводу его книги «Систематическое программирование. Введение.» (М.: Мир. 1977). Она содержит описание и анализ основных алгоритмов, методов построения программ. Книгу можно использовать и как руководство по применению языка Паскаль в задачах математического обеспечения ЭВМ.
Для научных работников, преподавателей, аспирантов и студентов, специализирующихся по математическому обеспечению ЭВМ.
Предисловие редактора перевода | |
Предисловие | |
1. Фундаментальные структуры данных | |
1.1. Введение | |
1.2. Концепция типа для данных | |
1.3. Простые типы данных | |
1.4. Стандартные простые типы | |
1.5. Ограниченные тисы | |
1.6. Массивы | |
1.7. Записи | |
1.8. Записи с вариантами | |
1.9. Множество | |
1.10. Представление массивов, записей и множеств | |
1.11. Последовательный файл | |
Упражнения | |
Литература | |
2. Сортировка | |
2.1. Введение | |
2.2. Сортировка массивов | |
2.3. Сортировка последовательных файлов | |
Упражнения | |
Литература | |
3. Рекурсивные алгоритмы | |
3.1. Введение | |
3.2. Когда не нужно использовать рекурсию | |
3.3. Два примера рекурсивных программ | |
3.4. Алгоритмы с возвратом | |
3.5. Задача о восьми ферзях | |
3.6 Задача об устойчивых браках | |
3.7. Задача оптимального выбора | |
Упражнения | |
Литература | |
4. Динамические информационные структуры |
4.1. Рекурсивные типы данных | |||||
4.3. Линейные списки | |||||
4.4. Древовидные структуры | |||||
4.5. Сильно ветвящиеся деревья | |||||
4.6. Преобразования ключа (расстановка) | |||||
Упражнения | |||||
Литература | |||||
5. Структура языков и трансляторы | |||||
5.1. Определение и структура языка | |||||
5.2. Анализ предложений | |||||
5.3. Построение синтаксического графа | |||||
5.4. Построение программы грамматического разбора для заданного | |||||
синтаксиса | |||||
5.5. Построение таблично-управляемой программы грамматического | |||||
5.6. Преобразование БНФ в структуру данных, управляющую | |||||
грамматическим разбором | |||||
5.7. Язык программирования ПЛ/0 | |||||
5.8. Программа грамматического разбора для ПЛ/0 | |||||
5.9. Восстановление при синтаксических ошибках | |||||
5.10. Процессор ПЛ/0 | |||||
5.11. Формирование команд | |||||
Упражнения | |||||
Литература | |||||
Приложение А | |||||
Множество символов ASCII | |||||
Приложение В | |||||
Синтаксические диаграммы Паскаля | |||||
Указатель программ | |||||
Указатель | Указатель программ | ||||
1.1. Вычисление степеней двойки 30 | 2.6. Сортировка Шелла 89 | ||||
1.2. Сканер 42 | 2.7. Просеивание 93 | ||||
1.3. Чтение вещественного числа 63 | 2.8. Пирамидальная сортировка 95 |
||||
1.4. Печать вещественного числа 65 | 2.9. Разделение 97 | ||||
Сортировка | простыми | 2.10. Быстрая сортировка 99 | |||
включениями 79 | 2.11. Нерекурсивная версия быстрой |
||||
Сортировка | бинарными | сортировки 100 | |||
включениями 80 | 2.12. Поиск k-го элемента 105 | ||||
2.3. Сортировка простым выбором 82 | 2.13. Сортировка простым слиянием |
||||
Сортировка методом | пузырька | ||||
2.! 4. Сортировка естественным | |||||
2.5. Шейкер-сортировка 86 | слиянием 121 |
2.15. Сортировка сбалансированным | 4.6. Построение оптимального дерева |
|||||
слиянием 126 | поиска 274 | |||||
2.16. Многофазная сортировка 138 | 4.7. Поиск, включение и удаление в |
|||||
2.17. Распределение начальных серий | Б-дереве 290 | |||||
с помощью пирамиды 145 | Построение | |||||
3.1. Кривые Гильберта 157 | перекрестных | |||||
3.2. Кривые Серпинского 161 | использованием | |||||
3.3. Ход коня 167 | расстановки 308 | |||||
3.4. Восемь ферзей (одно решение) | Грамматический | |||||
синтаксиса из примера 5 334 | ||||||
3.5. Восемь ферзей (все решения) 174 | Грамматический | |||||
3.6. Устойчивые браки 180 | языка (5.12) 343 | |||||
3.7. Оптимальная выборка 184 | 5.3. Транслятор для языка (5.13) 345 |
|||||
4.1. Включение в список 204 | 5.4. Грамматический разбор для ПЛ/0 |
|||||
4.2. Топологическая сортировка 218 | ||||||
Построение | идеально | 5.5. Грамматический разбор для ПЛ/0 |
||||
сбалансированного дерева 227 | с восстановлением при ошибках |
|||||
4.4. Поиск с включениями 236 | ||||||
Построение | 5.6. Транслятор для ПЛ/0 380 | |||||
перекрестных ссылок 240 | ||||||
Адельсон-Вельский 248 | Указатель | |||||
Выбором простым 81 | ||||||
Адрес 44, 48 | Обменом простым 83 | |||||
Абсолютный 374 | Пирамидальной 90 | |||||
Базовый 374 | С разделением 96 | |||||
Возврата 374 | Слиянием естественным 115 | |||||
Относительный 374 | Слиянием многофазным 137 | |||||
Алгол-60 17, 320 | Простым 109 | |||||
Алгоритм включения в Б-дерево 285 | Сбалансированным N - | |||||
В ББ-дерево 296 | путевым 122 | |||||
В сбалансированное дерево 254 | Удаления из Б-дерева 288 | |||||
В список 200 | Из сбалансированного дерева |
|||||
Вычисления n -го факториального | ||||||
Шейкер-сортировки 85 | ||||||
Грамматического разбора 324 | Алгоритмы рекурсивные 9 | |||||
Линейного просмотра 203 | С возвратом 9, 168 | |||||
Поиска медианы 103 | Анализ алгоритмов сортировки 79, |
|||||
По дереву с включением 233 | 80, 82, 85, 88, 94, 100, 113 | |||||
Построения кустарников 300 | Балансировка 288 | |||||
Сортировки включениями | Банки данных 58 | |||||
бинарными 79 | Барабаны магнитные 57 | |||||
Простыми 78 | Барьер 79, 203, 233 | |||||
С убывающим приращением | ББ-дерево см. Б-дерево бинарное | |||||
(сортировка Шелла) 87 | Б-дерево 282 |
Б-дерево бинарное 295
- - симметричное 298 Буквы латинские 24 Буфер 54
Бэйер 282, 289, 295, 298
Варианты в записях 35 Вес дерева 264 Ветвь 223
Возврат 9, 168, 325
Вольтер 13
Восстановление при ошибках 373 Время патентное 58 Выборочное изменение 28 Выравнивание 46 Выражение 17
Индексное 27
Высота дерева 220
Гаусс 169 Гильберт156
Глубина дерева 220 Горизонтальное распределение 134
Готлиб 267
Грамматический разбор 10, 328
Нисходящий 323
- - целеориентированный 328 Граф распознавания 328
- синтаксический 328
- - детерминированный 332 Графы 19 Данные 11
Дейкстра 7, 12
Дерево 10, 19, 219
АВЛ-сбалансированное 248
Бинарное 223
Вырожденное 220
- идеально сбалансированное 226
- лексикографическое 238
Оптимальное 263
Поиска 231
- сильно ветвящееся 223
Сортировки 91
- упорядоченное 220
Фибоначчи 249 2-3 дерево 295
Диаграмма зависимости 361 Дизъюнкция логическая 23 Диски магнитные 57 Дискриминант типа 36 Длина пути 220
Взвешенная 261
Внешнего 220
- - внутреннего 220 Доступ последовательный 53
Прямой 58
- случайный 25 Заглядывание вперед 55, 68 Заголовок списка 314
Задача об устойчивых браках 174
- о восьми ферзях 169
О ходе коня 164
- оптимального выбора 182
- поиска медианы 103
- построения школьного расписания
Запись (record) 8, 31, 48
- с вариантами 36 Запись бесскобочная 377
Инфиксная 230
Польская 377
Постфиксная 230
Искусственный интеллект 163 Итерация 9, 99, 154 Карта (индексов) 123, 128 Квантиль 105
Ключ 76, 303
Ключей преобразование 303 Ключи переменной длины 318
Кнут 77, 86, 134, 144, 264
Кольца 19 Конкатенация 51, 52, 54 Константа 17 Конструктор 20
Записи 32
Массива 26
Контекстная зависимость 322 Конфликт 304 Конфликтов разрешение 304 Конъюнкция логическая 23 Координаты 15, 31, 36
Декартовы 15, 36 Корень дерева 220
Коэффициент заполнения 312
- использования памяти 46
Кривая Гильберта 156
Серпинского 158
Кустарники 299
Ландис 248, 249
Магнитная 108
Лист дерева 220
Лорин 77 Лукасевич377 Мак-Вити 179 Мак-Крейт 289
Мантисса 15
Массив 19, 25, 44
Матрица 29 Машина ПЛ/0 373 Медиана 101, 103 Метасимволы 320
Метод деления пополам 28
Пузырька 84
- рассеянных таблиц 307 Множеств объединение 40
Пересечение 40
Разность 40
Сложение 40
- умножение 40 Множество 15, 19, 38 Множество-степень 38
Множеству принадлежность 40
Моррис 306
Нотация 52 Область переполнения 306 Обход дерева 229
Оператор варианта 37
- присоединения 34, 286
Процедуры 190
Условный 190
Цикла 29
С параметром 190
С предисловием 190 Операции булевские 23
Над файлами 54
Отношений 40
- преобразования 20 I/O-операции 62 Операция 17, 18, 19 Описание 17
Опробирование квадратичное 307
Линейное 306
Открытая адресация 306 Очередь 198 Ошибки наведенные 373
Память для программы 373
Оперативная 295
Паскаль 8, 11, 16, 19, 62
Переменная буферная 55 Переменные 17, 23 Переупорядочение списка 209 Пирамида 91
ПЛ/0 331, 349 ПЛ/1 20
Поддерево 223 Поиск бинарный 28 -- в списке 202
Медианы 103
- по дереву с включением 233
- по списку самоорганизующийся
Поле 48 Поле признака 36
Порядок Б-дерева 282
Частичный 211
- числа 15 Последовательность 16, 19, 52 Потомок 220 Поэтапное уточнение 11, 67, 344 Правила подстановки 320
Порождающие 320
Построения графа 329 | Фиктивные 132 |
Правило «не поднимай панику» 363 | Серпинский 158 |
Предложения 319 | Символ 23, 40, 319 |
Преобразование (типов) 24 | Начальным 320 |
Ключей 303 | Пустой 24 |
Приоритеты операций 40 | Символы внешние 363 |
Присваивание 19, 21, 189 | Возобновления 363 |
Проблема пустой строки 326 | Нетерминальные 320 |
Программа рабочая 373 | Терминальные 320 |
Таблично-управляемая 328 | Управляющие 393 |
Просеивание 92 | Сканер 40, 341 |
Просмотр на один символ вперед без | Слияние 109 |
возврата 323 | Двухфазное 115 |
Проход 109 | Естественное 115 |
По списку 201 | Каскадное 149 |
Процедура 190 | Многопутевое 122 |
Путь внешний 222 | Однофазное 110 |
Внутренний 220 | Простое 109 |
Разряд 15, 44 | Сбалансированное 110, 122 |
Расписание школьное 41 | Трехленточное 109 |
Распознавание предложений 322 | Слова размер 44 |
Распределение горизонтальное 134 | Словарь частотный 203 |
Памяти динамическое 51, 193 | Слово памяти 44 |
Расстановка 303 | Случайный доступ 25 |
Повторная 318 | Смещение 48, 374 |
Реализация 47, 50 | Сопрограммы 144 |
Регистр адреса команды 374 | Сортировка 9, 74, 77 |
Команды 374 | Быстрая 96 |
Вершины стека 374 | Включениями 77 |
Редактирование 67 | Бинарными 80 |
Рекурсия 9, 99, 150 | Простыми 78 |
Косвенная 151 | Внешняя 75 |
Прямая 151 | Внутренняя 75 |
СББ-дерево 298 | Выбором 77 |
Связка динамическая 374 | Простым 81 |
Сегмент 57 | Массивов 75 |
Логический 58 | Методом пузырька 84 |
Физический 58 | Обменом 83 |
Простым 83 |
|
Селектор 20, 37 | Пирамидальная 91 |
Записи 32 | Слиянием 109 |
Массива 26 Серии 115 | Многофазная 128 |
Максимальные 115 | Простым 109 |
Фиктивные 132 | С помощью дерева 89 |
Топологическая 211 | Упаковка 47, 49 |
Устойчивая 79 | Уровень 220 |
Файлов 75 | Файл 14, 19, 53 |
Шелла88 | Индексированный 58 |
i -сортировка 88 | Многоуровневый 57 |
Список 10, 198 | Персональный 14 |
Двунаправленный 315 | С прямым доступом 58 |
Циклический 314 | Фиктивный элемент 79 |
Сравнение 19 | Флойд 92 |
Методов сортировки массивов 105 | Фибоначчи деревья 249 |
Числа 131 |
|
Стек 99, 374 | Фиксация 378 |
Строка разрядов 49 | Форма бэкус-наурова 320 |
Текущая 69 | Инфиксная 377 |
Структуры данных динамические 10 | Постфиксная 377 |
Усложненные 8, 51 | Формула Эйлера 247 |
Фундаментальные 8 | Функция 17 |
Древовидные 219 | Аккермана188 |
Структурирования методы 19 | Преобразования 24 |
Схемы программ 56 | Расстановки 304 |
Таблица рассеянная 307 | Упорядочения 75 |
Расстановки 305 | Факториал 150 |
Таблично-управляемые программы | Характеристическая 49 |
Ханойские башни 186 |
|
Таккер 266 | Хоор 7, 8, 12, 96, 103 |
Ху 266 |
|
Тип базовый 18 | Центроид 267 |
Данных 17 | Цепочка 115 |
Регулярный 26 | |
Скалярный 19 | Цифры арабские 15, 24 |
Составной 30 | Двоичные!5 |
Стандартный 19 | Римские 15 |
Индексов 26 | Числа вещественные 15 |
Рекурсивный 314 | Комплексные 31 |
Транслятор 10, 17, 40, 319 | Натуральные 150 |
Трансляция 40 | С плавающей запятой 15 |
Удаление из дерева 241 | Факториальные 153 |
Из списка 200 | Цели с 15 |
Узел дерева внутренний 220 | Число гармоническое 83 |
Специальный 222 | Кардинальное 18, 20, 39, 49, 50 |
Уилсон 179 | Читаемый вход 59 |
Уильямс 91 | |
Указатели 10 | Шенкер-сортировка 85 |
Уолкер 263 | Эвристика 267 Эйлер |
Никлаус Вирт... Это имя в России известно многим. Три с лишним десятилетия назад профессор Вирт создал в далекой Швейцарии язык программирования Паскаль. Казалось бы, одного этого было достаточно, чтобы навечно вписать его имя в летопись компьютерных наук. Но в жизни нередко бывает так, что признание и известность получают далеко не самые лучшие и не самые совершенные творения. Вот и в случае с Паскалем мы видим лишь вершину айсберга, а большая часть творчества Вирта до сих пор для многих остается неизвестной.
Никлаус Вирт родился 70 лет назад - 15 февраля 1934 г. - в небольшом городке Винтертуре в предместье Цюриха. Родился Никлаус в семье Уолтера и Хедвиг Вирт. Они жили неподалеку от школы, где преподавал его отец. В их доме была хорошая библиотека, где Вирт находил немало интересных книг, рассказывавших про железные дороги, турбины и телеграф.
Небольшой городок Винтертур имеет многовековую историю и славится своим машиностроением: там выпускаются локомотивы и дизельные двигатели. С детских лет Вирт увлекался техникой, особенно авиамоделированием. Он буквально грезил небом. Но для запуска ракет нужно было топливо, и потому он занялся химией. Юный Вирт оборудовал в подвале школы «секретную» лабораторию. Ничто не могло его остановить: однажды сделанная им модель отклонилась от заданной траектории и угодила под ноги директору школы. Однако Вирт все равно продолжал упорно идти к намеченной цели.
Спустя несколько десятилетий Никлаусу Вирту, как и Кену Томпсону, автору UNIX, довелось полетать на МИГе с военного аэродрома в Кубинке, что находится под Москвой. Сбылась его заветная мечта. Лучше всего мотивацию профессионального творчества Вирта раскрыл его коллега по Стэнфордскому университету (США), профессор Дональд Кнут: «Вирт всегда хотел создавать аэропланы, и ему нужен был самый лучший инструментарий. Вот почему он проектировал много компьютерных языков и микрокомпьютеров...»
От строительства моделей Никлаус довольно быстро перешел к разработке дистанционного управления для них. Когда ему исполнилось 18 лет, он с еще двумя цюрихскими авиамоделистами получили из Англии желанную радиоаппаратуру. Это предопределило его дальнейшую судьбу - в 1954 г. Вирт поступил на факультет электроники в цюрихский ETH (Eidgenoessische Technische Hochschule, Швейцарский федеральный технологический институт). После четырех лет обучения Вирт получил степень бакалавра в области электротехники. А затем начинается славное десятилетнее заокеанское научное «турне» будущего «отца Паскаля» и «короля компиляторов» по маршруту Швейцария - Канада - США - Швейцария.
Свое обучение Вирт продолжил в Лавальском университете г. Квебека (Канада), где в 1960 г. получил степень магистра. Затем его пригласили в университет Калифорнии в Беркли (США) - будущую жемчужину Кремниевой долины. Там под руководством профессора Хаски в 1963 г. Никлаус Вирт защитил диссертацию, посвященную развитию Алгола средствами Лиспа (язык Euler). Эта работа в буквальном смысле дала ему путевку в жизнь: Вирта приметили мэтры программирования и пригласили в Комитет IFIP по стандартизации Алгола. Та школа не прошла даром: на всю жизнь Вирт запомнил, что доказывать свою правоту нужно делом, особенно когда тебя не хотят слышать. В разработке языков он навсегда отказался от абстрактно-научного подхода в пользу математически-инженерного. По его словам, лучше сначала реализовать язык и лишь потом следует о нем писать.
С 1963 по 1967 г. Вирт работал доцентом (assistant professor) в Стэнфордском университете и в 1967 г. вернулся в этом звании в университет Цюриха. А в 1968 г. он получил в ETH звание профессора компьютерных наук и начал возводить на родине свой «швейцарский» Стэнфорд. Двадцатилетие с 1969 по 1989 г. было, пожалуй, самым плодотворным периодом в жизни Вирта (табл. 1 ). Он продолжал строить свою школу, уделяя немало времени организационной деятельности. C 1982 по 1984 г. (а потом и с 1988 по 1990 г.) Вирт возглавлял в ETH факультет компьютерных наук, а с 1990 г. руководил Институтом компьютерных систем (Institute of Computer Systems) при ETH. На пенсию профессор Вирт ушел 1 апреля 1999 г. по достижении 65-летнего возраста.
Романтические 1960-е годы положили начало дружбе трех патриархов структурного программирования - голландца Эдсгера Дейкстры, англичанина Энтони Хоара и швейцарца Никлауса Вирта. Этих «нобелевских» лауреатов (премия Тьюринга, присуждаемая ассоциацией ACM, вручается раз в жизни и приравнивается в компьютерных науках к Нобелевской) сблизили не столько абстракции компьютерных наук, сколько четкая профессиональная позиция.
Самым известным достижением профессора Вирта считается язык Паскаль. Безусловно, многие об этом языке слышали и знают его. Паскаль сыграл огромную роль в формировании мировоззрения нескольких поколений программистов. Но этот язык далеко не идеальный. В свое время Брайан Керниган, известный популяризатор языка Си, соавтор классического руководства по Си (K&R), написал критическую статью «Почему Паскаль не является моим любимым языком программирования». Если с ней внимательно ознакомиться, то можно решить, что Никлаус Вирт сделал из нее правильные выводы и в языке Modula-2 под воздействием статьи устранил многие изъяны канонического Паскаля. Однако следует иметь в виду одно немаловажное обстоятельство. Наделавшая шума работа Кернигана была написана 2 апреля 1981 г., т.е. через два года (!) после реализации группой Вирта в ETH первого компилятора Modula-2 и через год после выпуска аппаратной реализации Modula-2 - персонального компьютера Lilith. В апреле 1993 г. на Конференции ACM по истории языков программирования Вирт в ответ на вопрос одного из своих коллег поставил языку Modula-2 оценку «6 баллов» (наивысшая оценка в школах Швейцарии).
Компьютерная индустрия отставала от работ Вирта как минимум на 5-7 лет. В том же 1979 г. намного уступавший Lilith легендарный компьютер Apple II только-только обрел компилятор Apple Pascal, ориентированный на UCSD-реализацию Паскаля. До появления первого скромного Turbo Pascal Андерса Хейльсберга оставалось целых четыре года! Впоследствии Вирт с грустью говорил о том, что с проектом Lilith швейцарская промышленность упустила свой уникальный шанс.
Подлинной жемчужиной творчества Вирта стал проект Oberon. Созданная почти два десятилетия назад система Oberon (Oberon System, http://www.oberon.ethz.ch ) играет в наши дни приблизительно ту же роль, что в начале 1980-х годов играли проекты Alto и Xerox Star знаменитого центра Xerox PARC, откуда взяли начало современные персональные компьютеры и текстовые редакторы. Для таких корпораций, как Microsoft, IBM и Sun Microsystems, проект Oberon стал источником плодотворных идей, среди которых можно выделить документо-ориентированный интерфейс, браузеры, промышленные языки разработки ПО (Java и C#), машинно-независимый мобильный код (JVM и.NET CLR), аплеты, компонентное ПО, динамическую компиляцию (JIT, AOC, DAC), смарт-теги, веб-службы и др.
Мы живем в эпоху торжества безумной технологической гонки и надуманной сложности. Всю свою жизнь Никлаус Вирт посвятил борьбе с этими пагубными явлениями, но его не слышат или не хотят слышать. «Крайнюю степень ума, - писал Блез Паскаль, - обвиняют в безумии точно так же, как полное отсутствие ума. Хороша только посредственность».
Вирт был и остается последователем европейской инженерной культуры. Американские достижения давали ему богатую пищу для размышлений: многие идеи он пропускал через себя и выкристаллизовывал самое ценное. Все три ключевых языка (Паскаль, Modula-2 и Oberon) были созданы Виртом буквально два-три года спустя после возвращения из-за океана. (В 1967 г. Вирт завершал работы по компилятору Algol-W в Стэнфорде, а в 1976 г. и 1984 г. на год уезжал в лаборатории Xerox PARC.) Работы Вирта создавались не в ваккуме. Его окружали единомышленники - коллеги и ученики, среди которых можно выделить Юрга Гуткнехта (соавтора по проекту Oberon), Ханспетера Мессенбока (соавтора языка Oberon-2), Ричарда Орана (соавтора при создании Lilith), Куно Пфистера (основателя Oberon microsystems и идеолога инструментария BlackBox), Клеменса Шиперски (идеолога компонентной архитектуры в Oberon System) и Михаэля Франца (автора концепции динамической кодогенерации, прообраза JIT-компиляции Java).
Большую роль в популяризации в нашей стране языков и систем Никлауса Вирта в 1980-1990-х годах сыграла рабочая группа по Modula-2, бессменным руководителем и вдохновителем которой был Д. М. Сагателян из Института общей физики АН СССР. Нельзя не вспомнить и работы группы профессора И. В. Поттосина из Сибирского отделения АН СССР (НГУ и Институт систем информатики им. А. П. Ершова). Создание инструментария для бортового ПО отечественных спутников (проект СОКРАТ), семейство компьютеров KRONOS (Дмитрий Кузнецов, Алексей Недоря, Евгений Тарасов, Владимир Васекин и др.), XDS-семейство компиляторов Modula-2/Oberon-2 - вот, пожалуй, самые яркие страницы отечественной истории, связанные с именем Вирта. Нарастающая волна интереса к Oberon, вершине творчества патриарха надежного программирования, в связи с острой потребностью в высококачественном программном обеспечении, в частности, в физике, привела к возникновению проекта «Информатика-21» (http://www.inr.ac.ru/~info21/ ), к которому с огромным интересом относится Вирт. Более того, в марте этого года в швейцарском Центре ядерных исследований (CERN), где 15 лет назад взяла свое начало сеть World Wide Web, специально для физиков проводился Oberon Day (http://cern.ch/oberon.day ).
Никлаус Вирт заложил традицию присвоения языкам программирования имен математиков прошлого. В 1963 г. он дал имя Леонарда Эйлера, великого швейцарского математика, много лет проработавшего в России, своему первому творению - языку Euler. А в 1970 г. Блез Паскаль, великий французский математик и философ, творчеством которого восхищались Н. Г. Чернышевский и Л. Н. Толстой, был увековечен Виртом в языке Паскаль. Интересные параллели: 11 мая 1994 г., выступая в С.-Петербургском университете, Дональд Кнут подчеркнул, что для него особенно приятен тот факт, что звание почетного доктора информатики ему присуждает университет, в котором преподавал еще великий Эйлер. Никлаус Вирт 27 июня 1996 г. надел почетную докторскую мантию в Новосибирском Академгородке, созданном М. А. Лаврентьевым и С. Л. Соболевым по образу и подобию того самого Стэнфорда, который Вирт взял за основу строительства своей европейской школы в ETH. Вклад Вирта в развитие компьютерных наук и программной инженерии был оценен по достоинству. Он не только стал членом трех академий (Swiss Academy of Engineering, U.S. Academy of Engineering, Berlin-Brandenburg Academy), но и лауреатом самых престижных наград (табл. 2 ).
Жизненное кредо Никлауса Вирта лучше всего, пожалуй, передают слова великого Блеза Паскаля, написавшего три с лишним столетия назад: «Все наше достоинство заключено в мысли. Не пространство и не время, которых мы не можем заполнить, возвышают нас, а именно она, наша мысль. Будем же учиться хорошо мыслить...
Руслан Богатырев - научный редактор «Мира ПК», главный редактор «Мир ПК - диска», [email protected] .
Полную версию статьи см. в электронном альманахе «Искусство программирования», опубликованном в мартовском приложении «Мир ПК-диска» (№ 3/04).
Мы живем в сложном мире и стараемся решать сложные по своей сути проблемы, которые зачастую для своего решения требуют сложных устройств. Однако это не значит, что мы не должны найти элегантные решения, убеждающие своей ясностью и эффективностью. Простые элегантные решения более эффективны, но найти их труднее, чем сложные, и для этого требуется больше времени.
Никлаус Вирт (Швейцария, Швейцарский федеральный технологический институт).
Из речи при вручении премии Тьюринга (Сан-Франциско, США, октябрь 1984 г.).
Когда компьютеров еще не было, то программирование не составляло никакой проблемы. Когда у нас появилось несколько маломощных компьютеров, то программирование стало проблемой средней сложности. Теперь же, когда мы располагаем гигантскими компьютерами, то и программирование превращается в гигантскую проблему.
Эдсгер Дейкстра (Нидерланды, Эйндховенский технологический университет).
Почти все в программном обеспечении может быть реализовано, продано и даже использовано, если проявить достаточную настойчивость... Но существует одно качество, которое нельзя купить, - это надежность. Цена надежности - погоня за крайней простотой. Это цена, которую очень богатому труднее всего заплатить.
Энтони Хоар (Великобритания, Оксфордский университет).
15 февраля исполняется 80 лет выдающемуся швейцарскому учёному и инженеру - Никлаусу Вирту (Niklaus Wirth), лауреату премии Тьюринга - самой престижной премии в компьютерных науках, аналога Нобелевки.
Знаменитый профессор Высшей политехнической школы ETH из Цюриха, где учились Альберт Эйнштейн (1896) и Джон фон Нейман (1923).
Его знают как автора классического Паскаля (1970), но многие даже понятия не имеют, что было десятилетиями позже. Что его разработки во многом инициировали создание Java и C#. Что нынешние космические спутники, новейшие беспилотники и безупречные по качеству швейцарские железные дороги работают благодаря его блестящей инженерной мысли.
Именно он всей своей жизнью показал путь борьбы с надуманной сложностью, которая не только окружает нас повсеместно, но и стала уже смертельно опасной болезнью нынешней цивилизации.
Наша эпоха - время диктатуры воинствующих дилетантов. И в программировании классика тоже уступает арену коммерчески изуродованной индустриальной «попсе».
Истинное величие И.С.Баха человечество благодаря Феликсу Мендельсону оценило спустя почти сто лет после его смерти. Надеюсь, мудрого профессора Никлауса Вирта - компьютерного Баха - люди оценят по достоинству всё же немного раньше.
Юбилей Никлауса Вирта - очень хорошая проверка на компетентность не только российских СМИ, но и мировых.
Руслан Богатырёв . 15.02.2014, Москва
Профессор Никлаус Вирт (Niklaus K. Wirth), автор языка Паскаль, закончил Швейцарский федеральный технологический институт ETH (Eidgenoessische Technische Hochschule) в родном Цюрихе (1958). В Лавальском университете в Квебеке (Канада) он получил степень магистра (1960). В 1963 г. в Университете Калифорнии в Беркли (США) Вирт под руководством профессора Гарри Хаски реализовал расширение Алгола-60 (язык Euler) и защитил диссертацию. В 1963–1967 гг. Вирт преподавал в Стенфордском университете (США). В это же время он был приглашен в международную экспертную группу IFIP Working Group 2.1, занимавшуюся проектированием языка Алгол-68.
В 1967 г. Вирт вернулся на родину и стал доцентом Университета Цюриха. В 1968 г. он перешел в ETH Zurich, где занялся разработкой языка Паскаль. В 1970 г. был завершен первый компилятор Паскаля. В период 1978–1981 гг. Вирт возглавлял проект, в результате которого был разработан язык Модула-2, ориентированный на него 16-разрядный персональный компьютер Лилит (Lilith) и ОС Medos. Все ПО, включая системное, было полностью реализовано на Модуле-2. В 1984 г. Никлаус Вирт за большой вклад в развитие языков программирования и за создание персонального компьютера Лилит был удостоен премии Алана Тьюринга (The ACM A.M.Turing Award) – самой престижной и почётной в компьютерном мире, которая по своему значению стоит в одном ряду с Нобелевской премией.
В период 1986–1989 гг. Вирт вёл проект по созданию нового языка Oberon, расширяемой объектно-ориентированной ОС Oberon и 32-разрядной рабочей станции Ceres. Многие идеи того проекта были положены сотрудниками Sun Labs в основу языка и технологии Java.
С 1990 г. профессор Вирт руководил Институтом компьютерных систем при ETH Zurich. В 1999 г. он ушёл на заслуженный отдых и стал почётным профессором родного ETH Zurich.
Рекомендуемые материалы
1. (PDF, 2004)
2. Никлаус Вирт в Академгородке (2009)
3. Преподавание информатики: потерянная дорога (2002)
4. Kronos (история одного проекта) (2005-2014)
5. Проект Oberon2005 (Большое турне Вирта по России) (2005)
6. Легендарный профессор Вирт на полигоне НПКЦ «Новик-XXI век» (2005)
7. Хорошие идеи: взгляд из Зазеркалья (2006)
8. Никлаус Вирт: путь к истине (2014)
9. Держаться корней (к 80-летию Никлауса Вирта) (2014)
Видеоинтервью
1. Niklaus Wirth on Teaching Computer Science. IEEE Computer Society, 2012.
2. Google Tech Talk, 2009.
3. Interview with Niklaus Wirth, 2010. Часть 1/3
4. Interview with Niklaus Wirth, 2010. Часть 2/3
5. Interview with Niklaus Wirth, 2010. Часть 3/3