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

Содержание

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

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

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

    while (условие) {
        тело цикла
    }
в учебном языке записывается как
    while (условие)
        тело цикла
    endwhile
(в роли закрывающей фигурной скобки используется оператор 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), переменные в нем не имеют типов. Типы выражений и значений переменных определяются только в процессе работы программы.

Выражения

В выражениях можно использовать 4 обычные арифметические операции, операцию возведения в степень ^ или ** и операцию взятия остатка от деления % (как и в C). Присваивание, как и в C/C++, также является операцией. Реализованы также математические стандартные функции sin, cos, exp и т.д. Числовые константы записываются так же, как и в языке C (правда, целочисленные восьмеричные и шестнадцатеричные константы не реализованы). Строковые константы записываются в двойных апострофах: "abc", "x=" и т.п.

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

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

    переменная = выражение;
где переменная в левой части может быть простой переменной или элементом массива. Оператор заканчивается символом ";" (точка с запятой). Отметим, что присваивание является операцией и может использоваться внутри любого выражения. Операция присваивания выполняется справа налево. Комментарий обозначается как в C++ "//" или как в Python'е "#". Примеры: 
    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"
После выполнения этого фрагмента строковая переменная 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;
(непонятно, к какому if относится else — в C считается, что к внутреннему; при LR-разборе конфликт сдвиг-свертка в данном случае разрешается в пользу сдвига).

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

    s = 0.; i = 0;
    while (i < 100)
        s = s + a[i];
        i = i + 1;
    endwhile
2. Определение окончания множественного числа в русском языке (0 мячей, 1 мяч, 2 мяча, 3 мяча, 4 мяча, 5 мячей, 6 мячей...): 
    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
В отличие от C, целочисленные выражения нельзя использовать в качестве логических. Например, фрагмент программы 
    x = 100;
    . . .
    if (x)
        y = 1;
    endif
является ошибочным (впрочем, и в C это дурной стиль!). Вместо этого надо писать 
    if (x != 0)
        y = 1;
    endif
(такому стилю хорошо бы следовать и при программировании на C).

Реализация логического типа 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 размера 2x3: 
    a = [];
    append(a, [1, 2, 3]);
    append(a, [4, 5, 6]);
    # a -- матрица [[1, 2, 3], [4, 5, 6]]
Стандартная функция append(a, x) добавляет элемент x в конец массива a, при этом длина массива увеличивается на 1. Функция extend(a, b) дописывает содержимое массива b в конец массива a. Операция + соединяет два массива, ее результатом является новый массив: 
    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]
Стандартные функции left, right, mid извлекают из массива подмассивы в начале, середине и конце соответственно. Вторым аргументом функции mid является индекс начала подмассива, третьим аргументом — длина подмассива. Если третий аргумент отсутствует или отрицательный, то результатом явлется подмассив, начинающийся с указанной позиции и включающий все элементы до конца массива: 
    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]
Функции left, right, mid аналогично работают и со строками: 
    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"

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

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

    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();
    Вывод программы (для n=50): 
        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();
    Вывод программы для чисел 2 и 10 (для заданного числа печатаются последовательность приближений и окончательный результат): 
        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.

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

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

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

        make

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

        ./delta filename.d
    или просто 
        delta filename.d
    если текущая директория находится в пути или файл "delta" находится в одной из директорий, добавленных в путь. Текст программы читается из указанного файла. Можно также читать программу из входного потока: 
        delta -std_input
    для окончания ввода программы следует набрать строку 
        end
    (можно ввести также символ конца файла — Ctrl+D в Unix'е или Ctrl+Z в MS Windows). После этого программа выполняется, ее ввод и вывод происходит в консоли.

    Также есть и другие возможности: распечатать промежуточный код программы, распечатывать таблицы символов и т.п. Полный текст подсказки показывается по команде "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
    -debug             Print a lot of debugging information
    source_file        File with a source program

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

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

    Все файлы запакованы в единый tgz-архив "Delta.tgz" (есть и файл "Delta.zip" для тех, кто предпочитает zip-архивы). При распаковке архива создается поддиректория "Delta" в текущей директории, куда и помещаются все распакованные файлы.