- •Введение
- •Общие требования к курсовой работе
- •Этапы выполнения курсовой работы
- •2.2.2. Определение синтаксиса лексем
- •2.2.3. Построение диаграммы лексического анализатора
- •2.2.4. Тестирование лексического анализатора
- •2.3. Описание этапа синтаксического анализа
- •2.3.1. Построение кс-грамматики входного языка
- •2.4.8. Построение атрибутного дмп-процессора
- •2.4.9. Тестирование атрибутного дмп-процессора
- •3. Задания на курсовую работу
- •Задание 1
3. Задания на курсовую работу
В процессе выполнения курсовой работы необходимо разработать язык программирования, являющийся подмножеством заданного языка, и транслятор с этого языка в промежуточный язык, тип которого определяется вариантом индивидуального задания. Метод синтаксического анализа также определяется заданием.
Язык должен обеспечивать операции над переменными и константами заданных базовых типов, а также над переменными и компонентами производного типа, которые определяются вариантом задания. Состав операций должен включать как предусмотренные базовым языком, так и перечисленные в варианте задания. В языке должна быть определена операция преобразования типов при структурной или именной эквивалентности типов. В языке должна быть предусмотрена возможность создания пользовательских типов.
Язык должен допускать использование арифметических выражений, в состав которых могут входить константы и простые переменные базовых типов, компоненты структурированного типа, круглые скобки и знаки операций: сложение, вычитание, умножение, деление. Приоритет операций - обычный.
Язык должен допускать использование логических выражений, в состав которых могут входить отношения, круглые скобки и знаки логических операций: И, ИЛИ, НЕ и, в случае наличия в языке логического типа, константы и переменные этого типа. Приоритет операций - обычный.
Операции над переменными структурированного типа определяется вариантом задания.
Состав операторов языка:
оператор присваивания;
оператор ввода;
оператор вывода;
составной оператор;
оператор безусловного перехода;
условный оператор, условие в котором задается логическим выражением;
оператор цикла, условие в котором задается логическим выражением.
Конкретный вид операторов определяется вариантом задания.
Программа на входном языке может содержать комментарии.
Задание 1
Базовый язык – Паскаль.
Базовые типы: целый, вещественный, комплексный, ограниченный.
Структурированный тип – вектор с комплексными компонентами.
Операции над векторами: определение длины вектора, сумма и разность векторов, скалярное произведение векторов, умножение вектора на число.
Операции над комплексными числами: доступ к вещественной и мнимой частям, определение модуля числа.
Оператор цикла – с предусловием.
Перегрузка операций – разрешается.
Эквивалентность типов – именная.
Класс грамматик – грамматики простого предшествования.
Промежуточный язык – тетрады.
Задание 2
Базовый язык – Паскаль.
Базовые типы: целый, булевский, ограниченный.
Структурированный тип – булевская матрица.
Операции над булевскими матрицами: определение размеров матрицы, конъюнкция и дизъюнкция матриц, инверсия матрицы.
Оператор цикла – с постусловием.
Перегрузка операций – не разрешается.
Эквивалентность типов – структурная.
Класс грамматик – SLR(1) - грамматики.
Промежуточный язык – триады.
Задание 3
Базовый язык – Паскаль.
Базовые типы: целый, символьный, ограниченный.
Структурированный тип – символьная строка.
Операции над строками: определение длины строки, конкатенация строк, замена подстроки в строке, поиск подстроки в строке, доступ к элементу строки по индексу, доступ к подстроке.
Оператор цикла – с постусловием.
Перегрузка операций – не разрешается.
Эквивалентность типов – именная.
Класс грамматик – грамматики простого предшествования.
Промежуточный язык – тетрады.
Задание 4
Базовый язык – Паскаль.
Базовые типы: целый, рациональный, ограниченный, перечислимый.
Структурированный тип – массив.
Операции над рациональными числами: обращение к числителю и знаменателю, выделение целой и дробной части, приведение к неправильной дроби, нахождение общего знаменателя двух рациональных чисел, приведение к простой дроби.
Оператор цикла – с параметром.
Перегрузка операций – разрешается.
Эквивалентность типов – именная.
Класс грамматик – LL(1) - грамматики.
Промежуточный язык – польская инверсная запись.
Задание 5
Базовый язык – Паскаль.
Базовые типы: целый, вещественный, булевский, ограниченный, перечислимый.
Структурированные типы: запись, список.
Операции над списком: определение количества элементов в списке, конкатенация списков, поиск элемента в списке, получение элемента списка с заданным номером, удаление элемента с заданным номером.
Оператор цикла – с предусловием.
Перегрузка операций – не разрешается.
Эквивалентность типов – именная.
Класс грамматик – грамматики слабого предшествования.
Промежуточный язык – триады.
Задание 6
Базовый язык – Паскаль.
Базовые типы: целый, вещественный, булевский, символьный, ограниченный, перечислимый.
Структурированные типы: символьная строка, стек.
Операции над строками: определение длины строки, конкатенация строк, замена подстроки в строке, поиск подстроки в строке, доступ к элементу строки по индексу, доступ к подстроке.
Операции над стеком: определение количества элементов в стеке, вталкивание элемента в стек, выталкивание элемента из стека, чтение верхушки стека.
Оператор цикла – с параметром.
Перегрузка операций – не разрешается.
Эквивалентность типов – структурная.
Класс грамматик – SLR(1) - грамматики.
Промежуточный язык – тетрады.
Задание 7
Базовый язык – Паскаль.
Базовые типы: целый, вещественный, ограниченный, перечислимый.
Структурированные типы: запись, массив, массив записей.
Оператор цикла – с параметром.
Перегрузка операций – не разрешается.
Эквивалентность типов – именная.
Класс грамматик – грамматики операторного предшествования.
Промежуточный язык – польская инверсная запись.
Задание 8
Базовый язык – Visual Basic.
Базовые типы: целый, вещественный, комплексный.
Структурированный тип – массив.
Операции над комплексными числами: доступ к вещественной и мнимой частям, определение модуля числа.
Оператор цикла – DO … LOOP.
Перегрузка операций – не разрешается.
Эквивалентность типов – структурная.
Класс грамматик – LL(1) - грамматики.
Промежуточный язык – триады.
Задание 9
Базовый язык – Паскаль.
Базовые типы: целый, булевский, символьный, ограниченный, перечислимый.
Структурированный тип – множество.
Операции над множествами: проверка принадлежности элемента множеству (in), объединение, пересечение, дополнение множеств.
Оператор цикла – с предусловием.
Перегрузка операций – разрешается.
Эквивалентность типов – именная.
Класс грамматик – грамматики операторного предшествования.
Промежуточный язык – польская инверсная запись.
Задание 10
Базовый язык – Паскаль.
Базовые типы: целый, вещественный, комплексный, булевский.
Структурированные типы: запись, указатель.
Операции над указателями: присваивание, разыменование (@ и ^), сравнение (на равенство и неравенство).
Дополнительные требования: операторы new и dispose.
Операции над комплексными числами: доступ к вещественной и мнимой частям, определение модуля числа.
Оператор цикла – с постусловием.
Перегрузка операций – не разрешается.
Эквивалентность типов – именная.
Класс грамматик – грамматики слабого предшествования.
Промежуточный язык – тетрады.
Задание 11
Базовый язык – Си.
Базовые типы: целый, вещественный, булевский.
Структурированный тип – вектор с вещественными компонентами.
Операции над векторами: определение длины вектора, сумма и разность векторов, скалярное произведение векторов, умножение вектора на число.
Дополнительные требования: операции ++, --, условный оператор присваивания, операторы присваивания +=, *=, -=, /=.
Оператор цикла – с параметром.
Перегрузка операций – разрешается.
Эквивалентность типов – структурная.
Класс грамматик – LL(1)-грамматики.
Промежуточный язык – тетрады.
Задание 12
Базовый язык – Си.
Базовые типы: целый, вещественный, комплексный.
Структурированные типы: структура, очередь.
Операции над очередью: определение количества элементов в очереди, добавление элемента в очередь, изъятие элемента из очереди, чтение первого и последнего элемента очереди.
Операции над комплексными числами: доступ к вещественной и мнимой частям, определение модуля числа.
Дополнительные требования: операторы присваивания +=, *=, -=, /=.
Оператор цикла – с предусловием.
Перегрузка операций – не разрешается.
Эквивалентность типов – именная.
Класс грамматик – грамматики слабого предшествования.
Промежуточный язык – триады.
Задание 13
Базовый язык – Си++.
Базовые типы: целый, вещественный, булевский, перечислимый.
Структурированные типы: структура, указатель.
Операции над указателями: присваивание, разыменование (*. и ->), сравнение (на равенство и неравенство).
Дополнительные требования: операторы new и delete, условный оператор присваивания, операторы присваивания +=, *=, -=, /=.
Оператор цикла – с постусловием.
Перегрузка операций – разрешается.
Эквивалентность типов – структурная.
Класс грамматик – SLR(1)-грамматики.
Промежуточный язык – тетрады.
Задание 14
Базовый язык – Си++.
Базовые типы: целый, вещественный, перечислимый.
Структурированные типы: массив, указатель.
Операции над указателями: присваивание, разыменование (*. и ->), сравнение (на равенство и неравенство).
Дополнительные требования: операторы new и delete, операции ++, --, условный оператор присваивания, операторы присваивания +=, *=, -=, /=, функции.
Оператор цикла – с параметром.
Перегрузка операций – разрешается.
Эквивалентность типов – структурная.
Класс грамматик – грамматики простого предшествования.
Промежуточный язык – польская инверсная запись.
Задание 15
Базовый язык – Си.
Базовые типы: целый, вещественный, перечислимый.
Структурированный тип: матрицы с вещественными компонентами.
Операции над матрицами: определение размеров матрицы, сумма и разность матриц, произведение матриц, транспонирование матрицы.
Дополнительные требования: операции ++, --, условный оператор присваивания, операторы присваивания +=, *=, -=, /=.
Оператор цикла – с постусловием.
Перегрузка операций – не разрешается.
Эквивалентность типов – именная.
Класс грамматик – грамматики операторного предшествования.
Промежуточный язык – тетрады.
Задание 16
Базовый язык – Си++.
Базовые типы: целый, вещественный, рациональный.
Структурированные типы: массив, указатель.
Операции над указателями: присваивание, разыменование, сравнение (на равенство и неравенство).
Операции над рациональными числами: обращение к числителю и знаменателю, выделение целой и дробной части, приведение к неправильной дроби, нахождение общего знаменателя двух рациональных чисел, приведение к простой дроби.
Дополнительные требования: операторы new и delete, операции ++, --, условный оператор присваивания, операторы присваивания +=, *=, -=, /=.
Оператор цикла – с параметром.
Перегрузка операций – разрешается.
Эквивалентность типов – структурная.
Класс грамматик – грамматики простого предшествования.
Промежуточный язык – триады.
Задание 17
Базовый язык – Си.
Базовые типы: целый, вещественный, символьный.
Структурированный тип: массив.
Операции над массивами символьного типа: определение длины строки, конкатенация строк, замена подстроки в строке, поиск подстроки в строке, доступ к подстроке.
Дополнительные требования: операции ++, --, условный оператор присваивания, операторы присваивания +=, *=, -=, /=.
Оператор цикла – с параметром.
Перегрузка операций – разрешается.
Эквивалентность типов – структурная.
Класс грамматик – LL(1)-грамматики.
Промежуточный язык – польская инверсная запись.
Задание 18
Базовый язык – Си.
Базовые типы: целый, вещественный, символьный, перечислимый.
Структурированный тип: битовая строка.
Операции над битовыми строками: сложение, вычитание, умножение, деление битовых строк (как двоичных чисел), доступ к элементу строки по индексу, доступ к подстроке, конкатенация строк, преобразование битовой строки к целому числу и обратно.
Оператор цикла – с предусловием.
Перегрузка операций – разрешается.
Эквивалентность типов – именная.
Класс грамматик – SLR(1)-грамматики.
Промежуточный язык – тетрады.
Задание 19
Базовый язык – Java.
Базовые типы: целый, вещественный, символьный.
Структурированный тип: символьная строка.
Операции над строками: определение длины строки, конкатенация строк, замена подстроки в строке, поиск подстроки в строке, доступ к подстроке.
Дополнительные требования: функции, оператор new, операции ++, --, условный оператор присваивания.
Оператор цикла – с предусловием.
Перегрузка операций – разрешается.
Эквивалентность типов – структурная.
Класс грамматик – грамматики операторного предшествования.
Промежуточный язык – триады.
Задание 20
Базовый язык – Java.
Базовые типы: целый, вещественный, комплексный.
Структурированный тип – матрицы с комплексными компонентами.
Операции над матрицами: определение размеров матрицы, сумма и разность матриц, произведение матриц, транспонирование матрицы.
Операции над комплексными числами: доступ к вещественной и мнимой частям, определение модуля числа.
Дополнительные требования: функции, оператор new, операции ++, --.
Оператор цикла – с постусловием.
Перегрузка операций – не разрешается.
Эквивалентность типов – структурная.
Класс грамматик – грамматики слабого предшествования.
Промежуточный язык – тетрады.
Задание 21
Базовый язык – Java.
Базовые типы: целый, вещественный, рациональный, булевский.
Структурированный тип – вектор с рациональными компонентами.
Вектор с рациональными компонентами: определение длины вектора, сумма и разность векторов, скалярное произведение векторов, умножение вектора на число.
Операции над рациональными числами: обращение к числителю и знаменателю, выделение целой и дробной части, приведение к неправильной дроби, нахождение общего знаменателя двух рациональных чисел, приведение к простой дроби.
Дополнительные требования: функции, оператор new, операции ++, --.
Оператор цикла – с постусловием.
Перегрузка операций – не разрешается.
Эквивалентность типов – структурная.
Класс грамматик – LL(1) - грамматики.
Промежуточный язык – польская инверсная запись.
Задание 22
Базовый язык – Java.
Базовые типы: целый, вещественный, булевский, комплексный.
Структурированный тип – массив.
Операции над комплексными числами: доступ к вещественной и мнимой частям, определение модуля числа.
Дополнительные требования: функции, оператор new, операции ++, --, условный оператор присваивания.
Оператор цикла – с параметром.
Перегрузка операций – разрешается.
Эквивалентность типов – структурная.
Класс грамматик – SLR(1)-грамматики.
Промежуточный язык – польская инверсная запись.
Задание 23
Базовый язык – Java.
Базовые типы: целый, вещественный, булевский.
Структурированный тип – очередь с приоритетом.
Операции над очередью: определение количества элементов в очереди, добавление элемента в очередь, изъятие элемента из очереди, чтение первого элемента очереди.
Дополнительные требования: функции, оператор new, операции ++, --, условный оператор присваивания.
Оператор цикла – с предусловием.
Перегрузка операций – не разрешается.
Эквивалентность типов – именная.
Класс грамматик – грамматики слабого предшествования.
Промежуточный язык – триады.
Задание 24
Базовый язык – Java.
Базовые типы: целый, вещественный, булевский.
Структурированный тип – булевская матрица.
Операции над матрицами: определение размеров матрицы, конъюнкция и дизъюнкция матриц, инверсия матрицы, транспонирование матрицы.
Дополнительные требования: функции, оператор new, операции ++, --.
Оператор цикла – с параметром.
Перегрузка операций – не разрешается.
Эквивалентность типов – структурная.
Класс грамматик – LL(1) - грамматики.
Промежуточный язык – тетрады.
Задание 25
Базовый язык – Visual Basic.
Базовые типы: целый, булевский, дата.
Структурированный тип: символьная строка.
Операции над строками: определение длины строки, конкатенация строк, замена подстроки в строке, поиск подстроки в строке, доступ к элементу строки по индексу, доступ к подстроке.
Операции над датами: определение текущей даты, чтение из даты числа, месяца и года.
Оператор цикла – .FOR … NEXT.
Перегрузка операций – не разрешается.
Эквивалентность типов – структурная.
Класс грамматик – грамматики операторного предшествования.
Задание 26
Базовый язык – Visual Basic.
Базовые типы: целый, вещественный, дата.
Структурированный тип – массив.
Операции над датами: определение текущей даты, чтение из даты числа, месяца и года.
Оператор цикла – . DO…LOOP.
Перегрузка операций – не разрешается.
Эквивалентность типов – структурная.
Класс грамматик – LL(1) - грамматики.
Промежуточный язык – триады.
Список литературы
Опалева Э.А., Самойленко В.П., Семенова О.Н. Формальные методы описания перевода: Учеб. пособие /СПбГЭТУ. СПб., 2000.
Опалева Э.А., Самойленко В.П., Семенова О.Н. Методы синтаксического анализа: Метод. указания к лабораторным работам/ СПбГЭТУ. СПб., 1995.
Опалева Э.А., Самойленко В.П. Формальные грамматики и распознающие автоматы: Учеб. пособие /ЛЭТИ. Л., 1991.
Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов /Пер. с англ. М.: Мир, 1979.
Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции: В 2 т. Т. 1/ Пер. с англ. М.: Мир, 1978.
Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты /Пер. с англ. М.: Изд. дом «Вильямс», 2001.
Эллис М., Строуструп В. Справочное руководство по языку программирования С++ с комментариями. Проект стандарта ANSI /Пер. с англ. М.:Мир, 1992.
Шмидт В. Visual Basic 5.0 / М.: «АБФ», 1997.
Ноутон П., Шилдт Г. JavaTM2/Пер. с англ. СПб.: «БХВ-Петербург», 2001.