Государственное образовательное учреждение
высшего профессионального образования
Кубанский государственный технологический университет
(КубГТУ)
Армавирский механико-технологический институт
Кафедра внутризаводского электрооборудования и автоматики
к курсовому проекту
по дисциплине: Теория языков программирования
на тему: «Лексический и синтаксический анализатор языка высокого уровня»
Государственное образовательное учреждение
высшего профессионального образования
Кубанский государственный технологический университет
(КубГТУ)
Армавирский механико-технологический институт
Кафедра внутризаводского электрооборудования и автоматики
Утверждаю
Заведующий кафедрой ВЭА
Проф. ____________ В.И. Куроедов
на курсовой проект
Студенту группы____________курса__________________
специальности 230105(2204) «Программное обеспечение вычислительной техники и автоматизированных систем»
Тема проекта: «Лексический и синтаксический анализатор языка высокого уровня»
Содержание задания: Спроектировать и построить лексический и синтаксический анализаторы для заданного формального языка программирования. Построить и реализовать в лексическом анализаторе распознаватель лексем с заданной структурой: нагруженное дерево (один элемент дерева хранит один символ (букву входного алфавита) лексемы).
Учебный язык включает директиву using, функцию main(), описание переменных, констант, цикла for, операторов присваивания, арифметические операции. За основу лексики, синтаксиса и семантики учебного языка принять стандарты языка программирования С#.
Объем работы:
Пояснительная записка 35 – 40 листов
Графическая часть 2-3 листа формата А3
Рекомендуемая литература:
1. Ключко В.И. Теория вычислительных процессов и структур. Учебное пособие, - КубГТУ, 1998;
2. Соколов А.П. Системы программирования: теория, методы, алгоритмы: Учеб. Пособие, - М.:
Финансы и статистика, 2004. – 320 с.: ил.
3. Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение. - СПб.: Питер, 2001. - 736 с.
Срок выполнения проекта:
с «___»____________ «___»_____________20___ г.
Срок защиты «___»____________ 20___ г.
Дата выдачи задания «___»_____________20___ г.
Дата сдача проекта на кафедру «___»_____________20___ г.
Руководитель канд. техн. наук, доцент _____________________
Задание принял студент______________________________
Нормативные ссылки
ГОСТ Р ИСО 9001-2001 Системы менеджмента качества. Требования.
ГОСТ 7.1-2003 СИБИД. Библиографическая запись. Библиографическое описание. Общие требования и правила составления.
ГОСТ 19.101-77 ЕСПД. Виды программ и программных документов.
ГОСТ 19.102-77 ЕСПД. Стадии разработки.
ГОСТ 19.103-77 ЕСПД. Обозначение программ и программных документов.
ГОСТ 19.105-78 ЕСПД. Общие требования к программным документам
ГОСТ 19.202-78 ЕСПД. Спецификация. Требования к содержанию и оформлению.
ГОСТ 19.404-79 ЕСПД. Пояснительная записка Требования к содержанию и оформлению.
ГОСТ 19.701-90 ЕСПД. Схемы алгоритмов, программ, данных и систем. Обозначения условные и правила выполнения.
Реферат
Пояснительная записка к курсовому проекту содержит 37 листов, 8 рисунков, 3 таблицы, 9 литературных источников, 2 приложения. К пояснительной записке прилагается 1 диск с готовой программой и материалами к ней, а также графическая часть, состоящая из трех листов.
СИНТАКСИС, ЛЕКСЕМА, КОНСТАНТА, АВТОМАТ – РАСПОЗНАВАТЕЛЬ, РЕГУЛЯРНОЕ МНОЖЕСТВО, ФОРМАЛЬНАЯ ГРАМАТИКА, ТЕРМИНАЛ, НЕТЕРМИНАЛ, АВТОМАТ С МАГАЗИННОЙ ПАМЯТЬЮ
Объект: лексический и синтаксический анализатор.
Цель: практическое применение теории формальных грамматик и теории автоматов для проектирования трансляторов.
Рассмотрен синтаксис заданного языка программирования, разработана грамматика регулярных множеств. Спроектированы автоматы для лексического анализа и распознавания лексем. Разработана формальная LL(1) грамматика для заданного языка программирования, спроектирован автомат с магазинной памятью для нисходящего анализа программы. Написана программа на языке высокого уровня Microsoft Visual C++ для лексического и синтаксического анализа текста на учебном языке программирования.
Содержание
1 Синтез лексического анализатора (сканера)
1.1 Описание синтаксиса формального языка программирования
1.2 Система регулярных выражений
1.3 Распознаватели констант и служебных слов
1.4 Управляющая таблица конечного автомата лексического анализа
2 Синтез синтаксического анализатора
2.1 Описание формальной грамматики
2.2 Построение множества ВЫБОР(n)
2.3 Построение управляющей таблицы
Список используемой литературы
Приложение А. Листинг лексического анализатора
Приложение Б. Листинг синтаксического анализатора
Целью данного проекта является: практическое применение теории формальных грамматик и теории автоматов для проектирования трансляторов.
Задачи: написать транслирующую грамматику для учебного языка программирования; спроектировать и построить лексический анализатор; спроектировать и построить синтаксический анализатор.
Входной информацией является файл, содержащий текст программы, написанной на учебном языке.
Выходной информацией являются таблицы лексем и имен, а также подтверждение того, что код соответствует синтаксису.
Результатом курсового проекта должна быть программа-анализатор, состоящая из двух частей: лексического анализатора, разбивающего исходный текст программы на лексемы и заполняющего таблицу имен; синтаксического анализатора, проверяющего соответствие текста заданной грамматике.
1 Синтез лексического анализатора (сканера)
1.1 Описание синтаксиса формального языка программирования
Директива using позволяет в текущем пространстве имен использовать типы данных, определенные в другом пространстве имен. Синтаксис:
using System.Text;
В данном случае лексема using является ключевым словом.
С помощью ключевого слова class определяются классы. Например:
public class TestClass
{
// Определение полей и методов класса
}
Ключевое слово public определяет уровень доступности класса.
Поля класса определяются как переменные:
public class TestClass
{
public uint a, b = 35, i;
public bool c, d;
public const long int e = 9L;
}
Для каждого поля прописывается модификатор доступа (public) и тип поля (double, int или decimal).
Методы класса определяются так же, как и обычные функции:
public class TestClass
{
public int Main(Param1, Param2)
{ }
}
Как и для полей класса, для методов задается модификатор доступа и тип возвращаемого значения метода.
Тело метода класса согласно учебному языку может содержать:
–определение цикла со счетчиком:
for (<выражение>; <условие>; <выражение>)
{ <блок операторов> }
–вызовы процедур:
write (<список параметров>);
read (<список параметров>);
–операторы присваивания:
a = <выражение>;
d *= <выражение>;
f /= <выражение>;
–арифметические выражения, содержащие бинарные операции:
a = b - (c + d);
Так же в тексте программы могут содержаться многострочные комментарии:
/* многострочный
комментарий */
Для записи идентификаторов используются буквы английского языка и цифры. Идентификаторы начинаются с буквы. Целые константы записываются арабскими цифрами.
1.2 Система регулярных выражений
Для записи грамматики лексем языка применим форму Бэкуса-Наура.
Для записи идентификаторов используются буквы английского языка и цифры. Идентификаторы начинаются с буквы. Синтаксис идентификаторов определяется праволинейной регулярной грамматикой:
<S> -> L <I>( 1)
<I> -> L <I>( 2)
<I> -> D <I>( 3)
<I> -> е( 4)
где L - буква множества (A..Z), D - цифра множества (0..9), е - пустая цепочка или символ окончания лексемы.
Целые константы записываются арабскими цифрами.
Праволинейная грамматика целого числа:
<ЦЧ> → +<Ц>|-<Ц>
<Ц> → н<Ц>
1.3 Распознаватели констант и служебных слов
Заданная грамматика может бать реализована автоматом со следующими состояниями:
S - состояние ожидания первого символа лексемы;
I - состояние ожидания символов идентификаторов: буквы, цифры;
С - состояние ожидания символов целой части числа;
E -состояние ошибки;
R - состояние допуска лексемы.
Автомат переходит в допустимое состояние R из состояния I для идентификаторов и из состояния C для чисел.
Регулярная грамматика для заданных условий записи лексем задается следующими множествами:
Р: [P1, P2, … ,P4] – множество правил;
G: [S, I, C, E, R] – множество состояний, где S – начальный символ;
[0..9, A..Z, «–», «#», «(», «)», «*», «,», «.», «/», «:», «;», «{«, «}», «+», «=»] – множество входных символов, из них разделительные символы и уникальные лексемы [«–», «#», «(», «)», «*», «,», «/», «:», «;», «{«, «}», «+», «=»].
Символы пробел и табуляции означают конец лексемы. Эти символы не является лексемой и требуют выполнения операции «СДВИГ» над входной строкой. По символу пробел автомат допускает лексему и переходит в начальное состояние анализа следующего символа входной строки автомата.