Лекция № 5 демонстрационный язык программирования dpl

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

В истории программирования можно найти много идей, которые могут служить источниками для создания своего языка. Остановимся на тех из них, которые были предложены Дейкстрой в его книге «Дисциплина программирования» [10]. В ней излагаются концепции безошибочного программирования и предлагаются языковые конструкции, поддерживающие такой подход. Этот язык также описан в книге Гриса [15], посвященной изучению разработке правильных программ и методов доказательства правильности программ.

Назовем разрабатываемый язык DPL (Demonstration Programming Language). Учитывая, что разработка языка носит учебный характер, в первоисточник будет внесен ряд изменений, позволяющих изучить необходимые методы разработки трансляторов.

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

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

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

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

– мы имеем в своем распоряжении набор базовых «кирпичиков», опираясь на которые, легче изучать более сложные понятия;

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

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

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

$ буква = A|B|C|D|E|F|G|H| I|J|K|L|M|N| O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z.

$ цифра = 0|1|2|3|4|5|6|7|8|9.

$ идентификатор = ( буква | _ ) { буква | цифра | _ }.

$ число = целое | действительное.

$ целое = двоичное | восьмиричное | десятичное |

шестнадцатиричное.

$ двоичное = {2} {/ 0 | 1 /}.

$ восьмиричное = {8}{ 0|1|2|3|4|5|6|7 }.

$ десятичное = [{10}] {/ цифра /}.

$ шестнадцатиричное = {16} {/ цифра |A|B|C|D|E|F|

a|b|c|d|e|f /}.

$ действительное = числовая_строка порядок | числовая_строка

. [числовая_строка] [порядок] | . числовая_строка [порядок].

$ числовая_строка = {/ цифра /}.

$ порядок = (E|e)[+|-] числовая_строка.

$ пробельный_символ = {/ пробел | табуляция | перевод_строки |

комментарий /}.

$ комментарий = /* { символ } */.

$ строка ={ символ | } .

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

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

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

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

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

or | read | skip | space | tab | var | write |.

$ разделитель = ( | ) | [ | ] | , | ; | : | := | * | / | % |

+ | — | — | | = | !=.

Статьи к прочтению:

Лекция 5: Языки логического программирования Пролог и Mercury

Похожие статьи: