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

Федеральное Агентство  по Образованию

Государственное образовательное  учреждение высшего профессионального  образования

Санкт-Петербургский  Государственный Электротехнический Университет «ЛЭТИ» им. В.И.Ульянова (Ленина)

(СПБГЭТУ)

 

 

Кафедра МОЭВМ

 

 

 

 

 

 

 

Пояснительная записка

к курсовой работе по дисциплине

«Теория языков программирования»

 

Вариант № 3

 

 

 

Выполнили:       Воробьев А.В.

Швецов М.Н.

Группа:                         4305

Проверил:   Самойленко В.П.

 

 

 

 

 

 

 

 

 

 

 

 

 

Санкт-Петербург

2007 год

 

Содержание

 

1. Задание на курсовую работу

 

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

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

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

Язык должен допускать использование  логических выражений, в состав которых  могут входить отношения, круглые  скобки и знаки логических операций:  И, ИЛИ, НЕ и, в случае наличия в  языке логического типа, константы  и переменные этого типа. Приоритет операций обычный.

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

Состав операторов языка:

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

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

Программа на входном языке может  содержать комментарии, вид которых предусмотрен базовым языком.

 

Исходная  постановка задачи

 

Базовый язык – Паскаль.

Базовые типы: целый, символьный, ограниченный.

Структурированный тип: символьная строка.

Операции над строками: определение длины строки, конкатенация строк, замена подстроки в строке, поиск подстроки в строке, доступ к элементу строки по индексу, доступ к подстроке.

Оператор цикла – с постусловием.

Перегрузка операций – не разрешается.

Эквивалентность типов – именная.

Класс грамматик – грамматики простого предшествования.

Промежуточный язык – тетрады.

 

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

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

 

Разработка языка программирования начинается с определения его  синтаксиса. Естественный язык мало пригоден для этой цели, поэтому для точного  описания синтаксиса языка программирования нужен некоторый вспомогательный язык. Язык, предназначенный для описания другого языка, называется метаязыком.

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

Для описания синтаксиса языков программирования наибольшее распространение  получила форма Бэкуса-Наура и ее различные модификации

 

Форма Бэкуса-Наура

 

Форма Бэкуса-Наура (БНФ) представляет собой очень естественный способ описания синтаксиса. В БНФ каждое определяемое понятие — это металингвистическая переменная. Значением металингвистической переменной может быть любая конструкция из некоторого фиксированного для этого понятия набора конструкций. Каждая металингвистическая форма определяет одну металингвистическую переменную и состоит из двух частей: левой и правой. В левой части записывается определяемая металингвистическая переменная, которая заключается в угловые скобки '<' и '>' (предполагается, что эти скобки являются метасимволами и не принадлежат алфавиту определяемого языка), например: <двоичное число>, <метка>, <арифметическое выраже-ние>. В правой части формы записываются все варианты определения конструкции, задаваемой этой формой. Каждый вариант представляет собой цепочку основных символов определяемого языка и металингвистических переменных. Варианты разделяются металингвистической связкой '|',  имеющей  смысл "или". Левая  и  правая  части  формы разделяются метасимволом '::=', означающим "по определению есть".

На практике для описания синтаксиса  языков программирования часто используют расширения БНФ, позволяющие более  естественно представлять альтернативные, необязательные и повторяющиеся  части металингвистических формул. Так, одно из расширений БНФ (РБНФ) разрешает использовать следующие упрощения:

1. необязательные элементы синтаксической конструкции заключаются в квадратные скобки '[' и ']';
2. альтернативные варианты могут в случае необходимости заключаться в квадратные скобки для образования многовариантного выбора;
3. элементы синтаксической конструкции, повторяющиеся нуль и более раз, заключаются в фигурные скобки '{' и '}'.

 

Форма Бэкуса-Наура для задания

 

<программа>::=[program <идентификатор>]{<описание объектов программы>;}<раздел операторов>.

 

<описание  объектов программы>::=<раздел  меток>|<раздел описания типов>|<раздел  описания переменных>|<раздел  описания констант>

 

<раздел  меток>::= label <метка> {,<метка>}

<метка>::=<идентификатор>|<целое без знака>

 

<раздел  описания типов> ::= type <определение типа> {;<определение типа>}

<определение  типа>::=<имя типа>=<тип>

<имя типа>::= <идентификатор> 

<тип>::=<простой  тип>|<составной тип>|<имя типа>

<простой тип>::=integer|char|<диапазонный тип>

<составной тип>::=<строка>

<строка>::=string

<диапазонный  тип>::=<константа>..<константа>

 

<раздел описания констант>::= const <определение константы> {;<определение константы>}

<определение константы>::=<имя  константы>=<простое выражение>

<имя константы>::=<идентификатор>

<константа>::=<целое число>|<имя константы>

 

<раздел описания переменных>::= var <описание переменных>{;<описание переменных>}

<описание  переменных>::= <перечень имен> : <тип>

<перечень  имен>::=<идентификатор> {,<идентификатор>}

 

<раздел  операторов>::=<составной оператор>

<составной  оператор>::= begin <последовательность операторов> end

<последовательность  операторов>::=<оператор>{;<оператор>}

<оператор>::= [метка :] <непомеченный оператор>

<непомеченный  оператор>::= <оператор присваивания>|<оператор ввода>|<оператор вывода>|<составной оператор>|<оператор безусловного перехода>|<условный оператор>|<цикл с постусловием>|<операции над строками>

 

<оператор  присваивания>::=<переменная>:=<простое выражение>

<оператор  ввода>::= read(<перечень имен>)

<оператор  вывода>::= write(<перечень выражений>)

<перечень  выражений >::=<простое выражение>{,<простое выражение>}

 

<оператор безусловного перехода>::= goto <метка>

<условный оператор>::=if <условие> then <оператор> [else <оператор>]

<цикл  с постусловием>::= repeat <последовательность операторов> until <условие>

<условие>::=<логическое  выражение>

 

<операции  над строками>::=<определение длины строки> |<конкатенация строк>|<замена подстроки в строке>|<поиск подстроки в строке>|<доступ к элементу строки по индексу>|<доступ к подстроке>|<равенство строк>

<определение длины строки>::=length(<строка>)

<конкатенация  строк>::=concat(<строка>,<строка>)

<замена подстроки в строке>::=replace(<строка>,<подстрока>,<новая строка>)

<поиск подстроки в строке>::=pos(<строка>,<подстрока>)

<доступ к элементу строки по индексу>::=StrChar(<строка>,<целое без знака>)

<доступ к подстроке>::= copy(<строка>,<целое без знака>,<целое без знака>)

<равенство строк>::= Same(<строка>,<строка>)

 

<подстрока>::=<строка>

<новая строка>::=<строка>

 

<простое выражение>::= <терм 1><остаток  суммы>

<остаток суммы>::=ε|+<терм 1><остаток  суммы>|-<терм 1><остаток суммы>

<терм 1>::=<терм 2><остаток произведения>

<остаток произведения>::=ε|*<терм 2><остаток произведения>|/<терм 2><остаток произведения>

<терм 2>::=<переменная>|<константа>|(< простое выражение>)|<оператор преобразования типов>

<оператор преобразования типов>::=<тип>(<простое выражение>)

 

 

<Логическое выражение>::= <Лог_терм 1><остаток Лог_суммы>

<остаток Лог_суммы>::=ε| or <Лог_терм 1><остаток суммы>

<Лог_терм 1>::=<Лог_терм 2><остаток Лог_произведения>

<остаток Лог_произведения>::=ε|and <Лог_терм 2><остаток Лог_произведения>

<Лог_терм 2>::=<выражение сравнения>|(<Логическое выражение>)|<вызов функции>|not <Лог_терм 2>

 

<выражение сравнения>::=<простое  выражение><знак сравнения><простое  выражение>

<знак сравнения>::=<|>|<=|>=|<>|=

 

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

 

Представление данных различных типов  в оперативной памяти.

 

Тип	Размер, байт	Диапазон значений
Integer	2	-32768..32767
Char	1	-128…127

 

Входной язык также поддерживает ограниченный тип.

- Ограниченный тип описывает  множество чисел, находящихся между двумя значениями заданных константных выражений. Это множество должно быть перечислимым, следовательно, значения константных выражений должны быть целыми числами. Все результирующие и промежуточные (полученные на каком-то шаге вычисления) значения константных выражений должны соответствовать ограничениям, накладываемым на встроенный тип Integer. В случае несоответствия компилятор вернет ошибку компиляции.

 

Операции входного языка  и их приоритет

 

Операции перечислены в порядке  убывания приоритета. Операции выполняются без учета переполнения.

 

Знак операции	Порядок выполнения и особенности исполь-зования	Семантический смысл
–	Слева направо, Унарный	Унарный минус, определен для числовых переменных, возвращает переменную такого же типа, что и получает. Меняет знак числа на противоположный.
*	Слева направо, Бинарный	Умножение, определено для числовых переменных. Результат вычисляется в наибольшем типе среди указанных операндов
/	Слева направо, Бинарный	Деление с отбрасыванием  дробной части, определено для числовых переменных. Результат вычисляется в наибольшем типе среди указанных операндов
+	Слева направо, Бинарный	Сложение, определено для числовых переменных. Результат вычисляется в наибольшем типе среди указанных операндов
-	Слева направо, Бинарный	Вычитание, определено для числовых переменных. Результат вычисляется в наибольшем типе среди указанных операндов
=, <>, <, >, <=, >=	Слева направо, Бинарный	Операции сравнения, определены для числовых переменных. Необходимы только для формирования условия
not	Слева направо, Унарный	Логическое  НЕ, определено для операций сравнения. Необходимо только для формирования условия
and	Слева направо, Бинарный	Логическое И, определено для операций сравнения. Необходимо только для формирования условия
or	Слева направо, Бинарный	Логическое ИЛИ, определено для операций сравнения. Необходимо только для формирования условия