Языки программирования
"Хотели бы вы pазpаботать собственный язык пpогpаммиpования? Если вы -
типичный пpогpаммист, вам, веpоятнее всего, этого хотелось бы. Идея постpоить,
[pазpаботать,] pасшиpить и модифициpовать собственный язык пpогpаммиpования,
над котоpым вы будете обладать полным контpолем, пpивлекает многих пpогpаммистов.
Немногие, однако, понимают пpи этом, насколько пpоцесс создания собственного
языка может быть пpост и пpиятен". Так начинается глава из книги Геpбеpта Шилдта
"Теоpия и пpактика C++" (BHV-Санкт-Петеpбуpг,1996), в котоpой пpиведен пpимеp
интеpпpетатоpа BASIC-подобного языка. Впеpвые этот матеpиал ко мне в 1990 году
в виде сделаной на ЕС ЭВМ pаспечатки, называлась она "Язык C для пpофессионалов".
Тогда главу я пpопустил. В 1992 году в существовавшем тогда жуpнале "Монитоp"
(##4,5) появилась небольшая статья М.Чеpкашина "Компилятоp пишется так ...".
Автоp с помощью очень небольшой пpогpаммы, пеpеводящей текст с пpидуманного им
языка на Pascal хотел показать, как устpоен компилятоp. Хотя пpимеp пеpевода с
одного языка высокого уровня на другой (к тому же, гораздо более мощный) - это
совсем не то же, что перевод в машинный код, но статья меня заинтересовала -
неужели действительно так пpосто? В результате я тоже решил написать компилятор.
И вот что получилось...
Машинный код и язык ассемблера
Учебники по программированию обычно начинаются с описания простейших программ
на языке Pascal (или Basic). Но почему бы не посмотреть сначала на код, в который
эти программы превращаются? Традиционная программа, печатающая приветствие
"Hello, world!" очень проста и может быть написана не только на ассемблере, но и
непосредственно в машинном коде. В этой главе приводятся минимальные сведения
о системе команд микропроцессора i8086 и о языке ассемблера. i8086 - очень старый
процессор, так что не следует тратить много времени на его изучение, но некоторое
время потратить стоит. Дальше
Языки высокого уровня
Краткое описание базовых элементов языков программирования. Здесь же находится
важное для дальнейшего изложения описание придуманного мной языка Context.
Почему не C? Не только и не столько из-за моих личных предпочтений. Целью
изложения является показать, как создать язык и транслятор с нуля, поэтому
важно не использовать готовые инструменты, а собственного транслятора языка C
у меня нет. Дальше
Простой ассемблер
Представленный здесь ассемблер написан с единственной целью - получить машинный
код компилятора языка Context. Кроме того, ассемблер - пример не очень сложной,
но содержательной программы. Дальше.
Рекурсивные функции
Идея рекурсии - одна из важнейших идей программирования, может быть самая
важная. Но в учебниках она занимает немного места, предполагается, что это
нечто очевидное, но для меня оно не было очевидным. В этой главе приведены
несколько важных для понимания дальнейшего примеров. Хотелось бы дополнить
их программой, играющей в крестики-нолики, но та что я смог написать играет
довольно плохо и очень медленно. Так что привести здесь хороший алгоритм я
пока не могу и буду благодарен, если кто-нибудь мне поможет.
Дальше
Простой компилятор
Чтобы создать компилятор, нужно понять, как решаются следующие задачи
Сортировка и поиск
Задача поиска в наборе данных встречается очень часто и решается она разными
способами. В некоторых случаях возможен прямой перебор. Если набор данных
упорядочен, поиск может быть значительно ускорен путем применения метода
половинного деления (пример - любой словарь), но в этом случае вставка новых
данных и удаление имеющихся невозможна (словарь) или требует много времени
(файл на диске, массив в памяти) - ведь требуется поддержание порядка. Разумеется,
быстый поиск возможен только после выполнения сортировки набора данных,
для чего применяются различные методы сортировки массивов
и файлов. Если набор данных должен обновляться или
если требуется несколько различных порядков, используются индексы. Пример
индекса - картотека в библиотеке, алфавитный указатель в книге - тоже индекс, но
необновляемый (как и сама книга). Существует несколько различных видов индексов,
в первую очередь это древовидные индексы, но также надо
упомяуть хэш-таблицы, обеспечивающие при соблюдении некоторых условий гораздо
более высокую скорость поиска (в лучшем случае поиск требует единственного сравнения).
Сжатие данных
Сжатие данных позволяет лучше использовать емкость запоминающих устройств
и пропускную способность кналов связи. Степень сжатия и сама возможность его
зависят и от вида данных и от применяемого алгоритма.
Первый (?) алгоритм сжатия появился в 1952 году. D.A.Huffman предложил метод кодирования данных, основаный на анализе частот входящих в них символов и замене этих символов кодами переменной длины. Но начать лучше не с него, а с метода LZSS (Lempel-Ziv-Storer-Szymanski). Этот алгоритм обеспечивает довольно высокую степень сжатия, и при этом он исключительно прост. Дальше.