Тема 3. Демонстрационный язык программирования

[ содержание | предыдущая тема | следующая тема ]

Содержание темы

Источники вдохновения для создания демонстрационного языка. Синтаксис и семантика DPL. Примеры программ. Описание пользовательского синтаксиса с использованием диаграмм Вирта.

Источники вдохновения для создания демонстрационного
языка

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

История программирования полна идеями, которые могут служить источниками для создания своего языка. Мы же остановимся на тех из них, которые были предложены Дейкстрой в его книге "Дисциплина программирования" [Дейкстра78]. В ней излагаются концепции безошибочного программирования и предлагаются языковые конструкции, поддерживающие такой подход. Этот язык также описан в книге Гриса [Грис84], посвященной изучению разработке правильных программ и методов доказательства правильности программ. Назовем разрабатываемый язык DPL (Dejkstra Programming Language). Учитывая, что разработка языка носит учебный характер, внесем в него ряд изменений, противоречащих позициям автора, но позволяющих изучить необходимые методы разработки трансляторов.

Синтаксис и семантика DPL

DPL содержит основные операторы обработки данных и управления, которые позволяют строить простые программы. Вместе с тем, в нем отсутствуют конструкции, широко применяемые в развитых языках. В частности, нет процедур и функций, блочной структуры, типов данных, классов. Это не мешает изучению основных принципов разработки трансляторов, которые можно с успехом использовать и при разработке более сложных языков программирования. Описание языка построим по традиционному принципу. В начале рассмотрим элементарные конструкции, а затем структуру программы. Для описания синтаксиса DPL будем использовать РБНФ.

Элементарные конструкции

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

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

К элементарным относятся такие понятия, как идентификатор, числа (целые, действительные, двоичные, десятичные), комментарии, метки, знаки операций, разделители, строки символов. Список можно продолжить и дальше. Эти понятия уточняются и конкретизируются при описании семантики языка. Например, идентификатор может служить в качестве имени переменной, процедуры, функции или типа. Элементарные конструкции обычно описываются с позиции, удобной для их изучения пользователем. Они могут распознаваться как во время лексического, так и синтаксического анализа, хотя большая их часть обычно распознается сканером.

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

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

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

Дополнительным описанием следует также снабдить понятия комментария и строки. Комментарий может задаваться в любом месте программы, где можно поставить пробел или разделитель. Он начинается парой символов "/*" и заканчивается другой парой "*/". Между ними могут быть любые печатаемые символы, включая отдельные группы звездочек и наклонных линий, не образующих завершающую комбинацию, а также символы табуляции, перевода строки. Строка может содержать только видимые символы, заключенные между двумя кавычками. Если в строке необходимо поставить кавычку, то она дублируется при написании:

"Строка, в которой следующее ""слово"" взято в кавычки".

Ключевые слова и разделители используются для формирования выражений, описаний и операторов. В DPL они определяются следующим образом:

Составные конструкции. Организация программы

К составным конструкциям относятся понятия, определяющие структуру программы, ее операторов, описаний и выражений.

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

Краткое описание семантики языка.

Оператор присваивания имеет нетрадиционную форму и, в общем случае, обеспечивает одновременное присваивание нескольким переменным, расположенным слева от знака ":=" значений предварительно вычисленных выражений, расположенных в правой части. Каждой переменной соответствует свое выражение. Присваивания начинаются только после вычисления всех выражений, результаты которых временно сохраняются. Это позволяет произвести обмен значений переменных с использованием только одного оператора присваивания:

В обычных языках программирования необходимо написать три отдельных оператора:

Выражения задаются в традиционной инфиксной форме. Порядок выполнения операций определяется их приоритетом и скобками. В начале выполняются выражения в скобках. Наивысший приоритет имеет унарный минус "-", далее следуют мультипликативные операции "*", "/", "%" (вычисление остатка), затем аддитивные "+", "-" и, наконец операции отношения "<", "=", ">", "<=", ">=", "!=".

Для представления пустого оператора Дейкстра намеренно использовал специальное ключевое слово skip (что мотивировал соответствующим текстом), хотя в большинстве языков программирования пустой оператор - это пустое место:

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

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

В соответствии с концепциями безошибочного программирования, разработанными Дейкстрой, определены условный оператор и оператор цикла. Их тела содержат наборы операторов, выполнение которых возможно только при истинности условий, задаваемых предваряющими их охраняющими выражениями. Выражения отделяются от охраняемых ими операторов стрелками "->" и, начиная с первого, последовательно анализируются до тех пор, пока не встретится "истинное". Истинным считается ненулевое значение выражения. Предполагается, что в рассматриваемой версии языка операции отношения возвращают в качестве результата целое число, равное 1, при выполнении условия и, равное 0, если условие не выполняется. Если в условном операторе все охраняющие выражения дают ложь, то он выполняется как оператор ошибки (abort). Оператор цикла в данной ситуации эквивалентен пустому оператору (skip). Возникновение такой ситуации обеспечивает выход из цикла. При наличии истинного охраняющего выражения происходит выполнения охраняемых операторов и повторное выполнение оператора цикла. Оператор abort также эквивалентен конструкции case end (пустое тело в условном операторе), а оператор skip - оператору loop end.

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

И, наконец, прокомментирую акт вандализма, осуществленный мною по отношению к Дейкстре: включение в язык оператора перехода goto. И это после того, как он воздвиг фундамент структурного программирования и написал целый ряд обличительных статей о вреде данного рудимента и атавизма одновременно! Однако использование данного оператора в учебном языке осуществляется только для того, чтобы продемонстрировать ряд особенностей, связанных с построением транслятора. Поэтому, после нескольких лет сомнений и метаний (когда goto отсутствовал), я решился на столь тяжкий грех (хорошо, что Дейкстра не видел моих исходных текстов синтаксического анализатора, а не то гореть мне в аду).

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

Ниже приведены примеры программ, раскрывающие особенности использования языка.

Пример 1. Алгоритм Евклида (нахождение наибольшего общего делителя).

begin
    var x, y: int; /* описание переменных */
    read x, y; /* ввод операндов */
    /* выполнять до равенства аргументов */
    loop x != y ->
        case
             x > y -> x := x - y
        or
             y > x -> y := y - x
        end
    end;
    write x /* полученный НОД */
end

Пример 2. Одновременное нахождение наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК).

begin
    var x, y, u, v: int; /* описание переменных */
    read x, y; /* ввод операндов */
    u, v := y, x;
    /* выполнять до равенства аргументов */
    loop	
        x > y -> x, v := x - y, v + u
    or
        y > x -> y, u := y - x, u + v
    end;
    write "НОД = ", x; /* НОД */
    write skip, "НОК = ", (u + v) / 2 /* НОК */
end

Пример 3. Суммирование n элементов из входного потока.

begin
    var a, i, s, n: int;
    i,s := 0,0;
    read n;
    loop
        i < n -> read a; s,i := s+a,i+1
    end;
    write s
end

Пример 4. Сортировка элементов вектора.

begin
    var A[100], i, n: int;
    i := 0;
    read n; /* чтение числа элементов */
    /* ввод вектора */
    loop 
        i < n -> read A[ i ];
        i := i +1
    end;
    i := 0;
    /* сортировка методом пузырька */
    loop i < n-1 ->
        case
            A[ i ] > A[ i+1 ] ->
                A[ i ], A[ i+1 ],i := A[ i + 1], A[ i ], 0
        or 
            A[ i ] <= A[ i+1 ] ->
                 i := i + 1

        end
    end;
    /* вывод вектора */
    i := 0;
    loop
        i < n ->
        write A[ i ], skip;
        i := i + 1
    end
end

Описание пользовательского синтаксиса с использованием диаграмм Вирта

Разработка транслятора, рассматриваемая в последующих разделах, опирается на описание синтаксиса DPL с использованием диаграмм Вирта. Поэтому, необходимо осуществить перевод с одного метаязыка на другой. Сам синтаксис пока по-прежнему остается пользовательским, а его изменение будет осуществляться в дальнейшем по мере надобности. Окончательное представление синтаксиса DPL с применением диаграмм Вирта приведено на рис. 3.1 без каких либо дополнительных комментариев.

Рис. 3.1. Описание синтаксиса DPL с использованием диаграмм Вирта.

Контрольные вопросы и задания

1. Завершить лабораторную работу, написав аналогичные примеры программ для языка программирования , заданного вариантом.

[ содержание | предыдущая тема | следующая тема ]