Модельный учебный компилятор,
разработанный с помощью утилит Lex и Yacc

Содержание

• Описание входного языка
  • Типы данных и переменные
  • Выражения
  • Предложения языка
  • Структурные операторы
  • Операторы ввода / вывода
  • Динамические массивы
  • Функции
  • Стандартные функции
  • Примеры программ
• Примеры программ
• Сборка и использование компилятора
• Структура компилятора

Для учебных целей разработан модельный компилятор delta, реализованный с помощью утилит Lex и Yacc (вернее, их свободных версий flex и bison). В исходном языке специально опущены некоторые существенные возможности (логические переменные, циклы for, классы и др.) — они оставлены в качестве задач для самостоятельного решения различной степени сложности.

Описание входного языка

Входной язык представляет собой минимальное подмножество языка C, дополненниое некоторыми конструкциями языка Python. Существенное отличие от языка C состоит в отсутствии фигурных скобок для указания границ блоков. Также для определения блоков формально не используются отступы в стиле языка Python (хотя, конечно же, отступ в 4 пробела для всех строчек вложенного блока — это правило хорошего тона в программах на любых языках!). Вместо этого каждая конструкция имеет строку-заголовок и строку-конец (аналог закрывающей фигурной скобки в C). Например, цикл while, который в C можно записать как

    while (условие) {
        тело цикла
    }

    while (условие)
        тело цикла
    endwhile

Кроме того, в число управляющих конструкций учебного языка добавлен оператор выбора, отсутствующий в C:
     if (условие1) ... elseif (условие2) ... elseif (условие3) ... else ... endif
Например, следующий фрагмент вычисляет функцию signum — знак числа x:

    if (x > 0.)
        sgn = 1;
    elseif (x < 0.)
        sgn = -1;
    else
        sgn = 0;
    endif

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

Типы данных и переменные

Типы данных ограничиваются базовыми типами и динамическими массивами. Базовых типов всего 3: целое число int, вещественное число double и текстовая строка string. Delta — язык с динамической типизацией (как Python), переменные в нем не имеют типов. Операторы описания типов переменных в языке отсутствуют, как и в Python'е. Типы выражений и значений переменных определяются только в процессе работы программы.

Для конструирования типов можно использовать динамические массивы, которые эквивалентны спискам в языке Python:

    a = [1, 2, 3];          # Массив длины 3
    b = [[1, 2], [3, 4]];   # Матрица 2x2

Выражения

В выражениях можно использовать 4 обычные арифметические операции, операцию возведения в степень ^ или ** и операцию взятия остатка от деления % (как и в C). Присваивание, как и в C/C++, также является операцией. Реализованы также математические стандартные функции sqrt, sin, cos, exp, atan, atan2, rand и т.д. Числовые константы записываются так же, как и в языке C (правда, целочисленные восьмеричные и шестнадцатеричные константы не реализованы). В текущей реализации целые значения представляют собой знаковые 64-разрядные числа. Строковые константы записываются в двойных апострофах: "abc", "x=" и т.п. Типа символ в стиле типа char или wchar языка C в языке нет. Вместо этого из строк можно извлекать подстроки с помощью функций left, right, mid, substr:

    s = "e2-e4; c7-c5";
    t = left(s, 5);         # t == "e2-e4"
    h = substr(s, 7, 2);    # h == "c7"
    r = substr(s, 1, 1);    # r == "2"

Предложения языка

Язык состоит из операторов и функций. Оператор может состоять из выражения, после которого ставится точка с запятой. Чаще всего это оператор присваивания:

    переменная = выражение;

    x = 5;
    y = 2*x + 1;
    x = y = z = 1000;
    f(x, y, z);
    d = gcd(17, 43);
    a = [1, 2, 3] + [4, 5]; # a == [1, 2, 3, 4, 5]
    append(a, 6);           # a == [1, 2, 3, 4, 5, 6]
    append(a, [7, 8, 9]);   # a == [1, 2, 3, 4, 5, 6, [7, 8, 9]]

В языке для базовых типов имеются операции приведения типа.

    x = double("6.125"); # вычислется число по его текстовому
                         # представлению
    s = string(x + 1);   # s == "7.125"

Структурные операторы

Структурных операторов всего 2 типа: оператор цикла while и условный оператор if. Условный оператор может иметь 3 формы:
— оператор "если" if... endif
— оператор "если-иначе" if... else... endif
— оператор выбора "если - иначе если - иначе если -... иначе":
     if... elseif... elseif... else... endif

Структурные операторы имеют строку-заголовок и строку-окончание. В окончании к ключевому слову, с которого начинается строка-заголовок, добавляется префикс "end": if-endif, while-endwhile. Фигурные скобки или ключевые слова begin-end для указания границ структурных операторов становятся ненужными, а программа более ясной; кроме того, это позволяет избежать неоднозначностей в грамматике языка и конфликтов при разборе, которые присутствуют, например, в языке C при разборе конструкции

    if (условие1) if (условие2) оператор1; else оператор2;

Примеры использования структурных операторов.
1. Суммирование массива:

    s = 0.; i = 0;
    while (i < 100)
        s = s + a[i];
        i = i + 1;
    endwhile

    numBalls = "";
    . . .
    numBalls = numBalls+n; // число n преобразуется
             // к текстовому виду и добавляется в конец строки
    numBalls = numBalls + " мяч";
    if (n == 0 || n >= 5)
        numBalls = numBalls + "ей";
    elseif (n >= 2)
        numBalls = numBalls + "а";
    endif

Для выхода из цикла while можно, как и в C, использовать оператор break;
для перехода к следующей итерации цикла — оператор continue;

В условиях можно использовать операции сравнения и логические операции, записываемые так же, как и в языке C. Например,

    if (y > 0. && x / y > 10.)
        x = 10. * y;
    endif

    x = 100;
    . . .
    if (x)
        y = 1;
    endif

    if (x != 0)
        y = 1;
    endif

Реализация логического типа bool и логических переменных оставлена в качестве задачи для самостоятельного решения.

Операторы ввода / вывода

В программах можно использовать встроенные операторы ввода и вывода, вводящие значения переменных с клавиатуры (стандартного входа) или выводящие значения в стандартный поток вывода: input, output, outputln. Но лучше вместо встроенных операторов пользоваться стандартными функциями scan, print и println, которые также реализованы в языке. Функция scan, так же как и оператор input, всегда вводит целиком строку до символа перевода строки '\n' (не включая этого символа). Пример:

    s = scan();
    println("s = ", s);
    x = int(s);
    y = double(s);
    println("x = ", x, " y = ", y);

    6.5

    s = 6.5
    x = 6 y = 6.5

Динамические массивы

Динамические массивы похожи на списки в Python'е. Элементы массива могут иметь различные типы.

    a = [1, 2, "abc", [3, 4, 5]];

    a = [];
    append(a, [1, 2, 3]);
    append(a, [4, 5, 6]);
    # a -- матрица [[1, 2, 3], [4, 5, 6]]

    a = [1, 2];
    append(a, 3);         # a == [1, 2, 3]
    append(a, [4, 5]);    # a == [1, 2, 3, [4, 5]]
    extend(a, [6, 7, 8]); # a == [1, 2, 3, [4, 5], 6, 7, 8]
    b = a + [9, 10]; # b == [1, 2, 3, [4, 5], 6, 7, 8, 9, 10]

    a = [0, 1, 2, 3, 4, 5];
    b = left(a, 3);             # b == [0, 1, 2]
    c = right(a, 2);            # c == [4, 5]
    d = mid(a, 1, 3);           # d == [1, 2, 3]
    e = mid(a, 2);              # e == [2, 3, 4, 5]

    s = "012345";
    b = left(a, 3);             # b == "012"
    c = right(a, 2);            # c == "45"
    d = mid(a, 1, 3);           # d == "123"
    e = mid(a, 2);              # e == "2345"

Функции

Заголовок функции состоит из ключевого слова func (или function), за которым следует имя функции и список параметров. За заголовком следует тело функции. Заканчивается описание функции ключевым словом endfunc (или endfunction). Функция может возвращать значение value с помощью оператора "return value;". Пример функции gcd(a, b), вычисляющей наибольший общий делитель целых чисел a, b:

    func gcd(a, b)
        while (b != 0)
            r = a%b;
            a = b; b = r;
        endwhile
        return a;
    endfunc

Функции могут вкладываться друг в друга, тогда параметры и локальные переменные объемлющей функции доступны во вложенных функциях и являются для них нелокальными объектами. Пример: пусть мы имеем функцию gauss(a), приводящую матрицу a к ступенчатому виду. Матрица a является входным параметром функции gauss, ее результатом будет ступенчатая матрица b. Тогда внутри функции gauss можно описать функцию swapRows(i, j), которая меняет местами две строки матрицы a с индексами i, j. При этом матрица a, а также число ее столбцов n не передаются функции swapRows как параметры, а являются для нее нелокальными объектами:

    func gauss(a)
        func swapRows(i, j)
            k = 0;
            while (k < n)
                tmp = a[i][k];
                a[i][k] = a[j][k]; a[j][k] = tmp;
                k = k + 1;
            endwhile
        endfunc

        m = len(a);     # number of rows of matrix
        n = len(a[0]);  # number of columns
        . . .
        swapRows(i, j);
        . . .
    endfunc

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

    func bubbleSort(ref a)
        func swap(i, j)
            tmp = a[i]; a[i] = a[j]; a[j] = tmp;
        endfunc

        wasInversions = 1; pass = 1;
        while (wasInversions != 0)
            wasInversions = 0;
            i = 0;
            while (i < len(a) - pass)
                if (a[i] > a[i+1])
                    swap(i, i+1);
                    wasInversions = 1;
                endif
                i = i + 1;
            endwhile
            pass = pass + 1;
        endwhile
    endfunc

Одна и та же функция может возвращать значения разных типов в зависимости от типов фактических параметров или вовсе не возвращать значения. Набор значений можно возвращать как массив. Например, в Расширенном алгоритме Евклида функция extEucl(m, n) вычисляет наибольший общий делитель d целых чисел m, n и его выражение через исходные числа:

    d = u*m + v*n.

    # Extended Euclid Algorithm:
    # For integers m, n compute d = gcd(m, n)
    #     and u, v such that d = u*m + v*n
    func extEucl(m, n)
        a = m; b = n;
        u1 = 1; v1 = 0;
        u2 = 0; v2 = 1;
        while (b != 0)
            # Invariant: a == u1*m + v1*n
            #            b == u2*m + v2*n
            #            gcd(a, b) == gcd(m, n)
            q = a/b; r = a%b;
            a = b; b = r;
            tmp = u1; u1 = u2; u2 = tmp - q*u2;
            tmp = v1; v1 = v2; v2 = tmp - q*v2;
        endwhile
        return [a, u1, v1];
    endfunc

Функции можно запоминать в переменных и передавать как параметры другим функциям Например, следующая функция simpson(f, a, b, n) вычисляет интеграл по формуле Симпсона от произвольной функции f(x) на отрезке [a, b]; функция f является ее параметром.

    function simpson(f, a, b, n)
        k = 2*n;
        h = (b - a)/k;
        s = f(a);
        x = a;
        while (0 == 0)
            x = x + h;
            s = s + 4.*f(x);
            x = x + h;
            if (x >= b - h/2.)
                break;
            endif
            s = s + 2.*f(x);
        endwhile
        s = s + f(b);
        return s*h/3.;
    endfunc

Пример "functional.d" иллюстрирует элементы функционального программирования. В нем реализованы популярные в этой области функции map(f, list) и reduce(g, list), работающие со списками. Функция map к каждому элементу списка применяет функцию f, заменяющую его на образ под действием f. Функция reduce "сворачивает" список (например, вычисляет произведение его элементов), используя функцию g как бинарную операцию над его элементами.

Стандартные функции

Список стандартных функций, реализованный в настоящее время в языке:

Примеры программ

1. Печать квадратов первых 20 натуральных чисел — файл "square20.d":

    n = 1;
    while (n <= 20)
        println(n, " ", n*n);
        n = n+1;
    endwhile
    end

    1 1
    2 4
    3 9
    4 16
    5 25
    6 36
    7 49
    8 64
    9 81
    10 100
    11 121
    12 144
    13 169
    14 196
    15 225
    16 256
    17 289
    18 324
    19 361
    20 400

2. Печать n первых простых чисел — файл "nprimes.d":

    # Input an integer number n and print first n prime numbers
    print("Number of primes: ");
    s = scan();
    n = int(s);

    k = 0;
    p = 2;
    while (k < n)
        if (p == 2)
            print(" ", p);
            k = k+1;
            p = p+1;
        else
            prime = 1;
            d = 3;
            while (prime == 1 && d*d <= p)
                if (p % d == 0)
                    prime = 0;
                    break;
                endif
                d = d+2;
            endwhile
            if (prime == 1)
                print(" ", p);
                k = k+1;
                if (k % 10 == 0)
                    println();
                endif
            endif
            p = p+2;
        endif
    endwhile

    println();

    Number of primes:
    50
     2 3 5 7 11 13 17 19 23 29
     31 37 41 43 47 53 59 61 67 71
     73 79 83 89 97 101 103 107 109 113
     127 131 137 139 149 151 157 163 167 173
     179 181 191 193 197 199 211 223 227 229

3. Приближенное вычисление квадратного корня вещественного числа — файл "sqrt.d":

    #
    # Compute a square root of a number
    # and compare the result with standard sqrt(x) function
    #
    func main()
        while (0 == 0)      # Infinite loop
            print("Input a number (0 for the end): ");
            x = double(scan());
            if (x == 0.)
                break;
            endif
            y = squareRoot(x);
            println("squareRoot(x) = ", y);
            println("standard sqrt(x) = ", sqrt(x));
        endwhile
    endfunc

    # Compute a square root using Newton iterations
    func squareRoot(a)
        println("    in squareRoot: a = ", a);
        if (a < 0.)
            println("    Incorrect argument");
            return 0.;
        endif

        EPS = 0.0000001;
        x = a;
        if (x < 1.)
            x = 1.;
        endif
        xPrev = x + 1e100;
        while (fabs(xPrev - x) > EPS)
            xPrev = x;
            x = (x + a/x) / 2.;
            println("    ", x);
        endwhile
        println("    in squareRoot: result = ", x);
        return x;
    endfunc

    # Starter
    main();

    Input a number (0 for the end): 2
        in squareRoot: a = 2
        1.5
        1.41667
        1.41422
        1.41421
        1.41421
        in squareRoot: result = 1.41421
    squareRoot(x) = 1.41421
    standard sqrt(x) = 1.41421
    Input a number (0 for the end): 10
        in squareRoot: a = 10
        5.5
        3.65909
        3.19601
        3.16246
        3.16228
        3.16228
        in squareRoot: result = 3.16228
    squareRoot(x) = 3.16228
    standard sqrt(x) = 3.16228

Пример "gcd.d" иллюстрирует возможность возвращения списка (динамического массива) в качестве результата функции. В данном случае функция extEucl(m, n) возвращает список из трех значений:

    func main()
        while (0 == 0)      # Infinite loop
            println("Input 2 integer numbers (two zeroes for the end):");
            print("m = ");
            m = int(scan());
            print("n = ");
            n = int(scan());
            if (m == 0 && n == 0)
                break;
            endif
            d = gcd(m, n);
            println("gcd(m, n) = ", d);
            println("Extended Euclid algoritm:");
            res = extEucl(m, n);
            println("d = ", res[0], ", u = ", res[1], ", v = ", res[2]);
            println("d == gcd(m, n) == u*m + v*n\n");
        endwhile
    endfunc

    # Recursive implementation of gcd
    func gcd(a, b)
        if (b == 0)
            return a;
        else
            return gcd(b, a%b);
        endif
    endfunc

    # Extended Euclid Algorithm:
    # For integers m, n compute d = gcd(m, n)
    #     and u, v such that d = u*m + v*n
    func extEucl(m, n)
        a = m; b = n;
        u1 = 1; v1 = 0;
        u2 = 0; v2 = 1;
        while (b != 0)
            # Invariant: a == u1*m + v1*n
            #            b == u2*m + v2*n
            #            gcd(a, b) == gcd(m, n)
            q = a/b; r = a%b;
            a = b; b = r;
            tmp = u1; u1 = u2; u2 = tmp - q*u2;
            tmp = v1; v1 = v2; v2 = tmp - q*v2;
        endwhile
        return [a, u1, v1];
    endfunc

    main();

    Input 2 integer numbers (two zeroes for the end):
    m = 19
    n = 43
    gcd(m, n) = 1
    Extended Euclid algoritm:
    d = 1, u = -9, v = 4
    d == gcd(m, n) == u*m + v*n

Пример "gauss.d" иллюстрирует работу с матрицами. В программе вводится квадратная матрица и методом Гаусса приводится к ступенчатому виду. Печатается ступенчатая форма матрицы и ее определитель.

Алгоритмы сортировки иллюстрируют использование вложенных функций и нелокальных переменных:
"qsort.d" — сортировка QuickSort;
"heapsort.d" — сортировка HeapSort.

Примеры "simpson.d" и "functional.d" иллюстрируют работу с переменными, значениями которых являются функции (вернее, указатели на функции, если придерживаться терминологии языка C). В файле "simpson.d" реализована функция

    function simpson(f, a, b, n)

Программа в файле "functional.d" иллюстрирует элементы функционального программирования. В ней реализованы стандартные в этой области функции map(f, list) и reduce(g, list), работающие со списками. Функция map к каждому элементу списка применяет функцию f, заменяющую его на образ под действием f. Функция reduce "сворачивает" список (например, вычисляет произведение его элементов), используя функцию g как бинарную операцию над его элементами (в языке Hakell эта функция называется foldl).

Сборка и использование компилятора

Исходные текста проекта (архивы в tar-gzip формате и в zip-формате):
"Delta.tgz" или "Delta.zip".

Для компиляции проекта следует выполнить команду

    make

Для запуска готового компилятора и выполнения программы "filename.d" следует выполнить команду

    ./delta filename.d

    delta filename.d

    delta -std_input

    end

Также есть и другие возможности: распечатать промежуточный код программы, распечатывать таблицы символов и т.п. Полный текст подсказки показывается по команде "delta" без аргументов:

    Delta Compiler + Interpreter.
    Usage:
        delta [-show_icode] [-show_nametable]
              [-std_input] [-debug] [source_file]
    where
    -show_icode        Print intermediate code
    -show_nametable    Print global nametable
    -std_input         Read program from standard input
    -show_debug        Print a lot of debugging information
    source_file        File with a source program

Структура компилятора

Компилятор состоит из следующих модулей и файлов:

• сканер — файлы "scan.l", "parser.h" и "lextypes.h";
• парсер — файл "comp.y" (файлы "parser.h" и "lextypes.h" используются для связи между сканером, парсером и другими частями проекта);
• деревья выражений (expression Trees) — файлы "tree.h" и "tree.cpp";
• промежуточный сод (Intermediate Code) — файлы "icode.h" и "icode.cpp";
• таблица имен (Name Table) — файлы "nt.h" и "nt.cpp";
• таблица меток переходов (Label Table) — файлы "lt.h" и "lt.cpp";
• интерпретатор — файлы "interpret.h" и "interpret.cpp";
• значения (Values) в стеке интерпретатора — файлы "value.h" и "value.cpp";
• стандартные фунции — файлы "stfunc.h" и "stfunc.cpp";
• файл для сборки проекта — "Makefile"
• Примеры программ — файлы
  "square20.d" (печать квадратов первых 20-ти натуральных чисел),
  "nprimes.d" (печать n первых простых чисел),
  "sqrt.d" (вычисление квадратного корня),
  "gcd.d" (вычисление наибольшего общего делителя и алгоритм Евклида),
  "gauss.d" (работа с матрицами, метод Гаусса),
  "bubblesort.d" (примитивная пузырьковая сортировка),
  "qsort.d" (сортировка QuickSort),
  "heapsort.d" (самая быстрая сортировка HeapSort),
  "simpson.d" (вычисление интерала от произвольной функции),
  "functional.d" (элементы функционального программирования: map, reduce).
• описание проекта (текст, который вы читаете) — файл "delta.html".