Приведение КС-грамматики к нормальному виду
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
Филиал ФГБОУ "ДГТУ" в г. Каспийск
Кафедра ПОВТ и АС
Курсовая работа
По дисциплине:
"Теория языков программирования"
на тему:
"Приведение КС-грамматики к нормальному виду"
Выполнила:
студент 4 курса гр. М831
Магомедов К.К.
Приняла: Сулейманова О.Ш.
Каспийск 2011г.
Аннотация
Целью данной курсовой работы является разработка программы, позволяющей осуществить приведение КС-грамматики к нормальному виду, т.е.:
1.Удалить бесплодные символы
2.Удалить недостижимые символы
3.Устранить правила с пустой правой частью
4.Исключить цепные правила
Работа содержит:
_____ страниц машинописного текста
рисунков
3 библиографических источника
Содержание
Введение
Задание
Приведение КС-грамматики к нормальному виду
Преобразования грамматик
Алгоритм удаления недостижимых символов
Исключение цепных правил
Описание процедур
Литература
Приложение
Введение
Формальные грамматики и языки
Формальные грамматики как математический аппарат появились именно по необходимости представления синтаксиса в трансляторах и автоматизации синтаксического анализа. В отличии от лексики и семантики, которые можно реализовать используя содержательные средства, синтаксический анализатор почти не возможно сделать руководствуясь здравым смыслом. Здесь необходимо иметь промежуточный уровень между синтаксисом языка и программируемой системой, таким уровнем являются формальные грамматики.
Формальные грамматики являются не только синтаксисом, но и основным инструментом для синтаксического анализатора. Самая общая схема синтаксического анализатора, построенная на основе формальных методов:
.Описание синтаксиса языка дается исключительно средствами формальных грамматик.
2.Формальный метод синтаксического анализа устанавливает свойства формальных грамматик, которые определяются исходя из правил, составляющих формальные грамматики.
.Правила, множества различных символов и отношения представляются табличными данными, на основе которых функционирует распознаватель.
.Распознаватель представляет собой алгоритм (управляющий автомат), который наряду с входной строкой, в качестве элемента использует стек.
.Распознаватель, используя данные извлеченные из формальной грамматики, выполняет действия, которые соответствуют синтаксической структуре самого текста.
Стековая структура является процессом определенного набора действий, соответствующих синтаксическому анализу. Полученные формальным методом табличные данные являются программой его работы.
Описание синтаксиса в виде формальных грамматик является ее исходным текстом.
Взаимосвязь синтаксиса и формальных грамматик
После предварительного анализа свойств формальных грамматик нужно отметить, что они в целом играют роль синтаксиса. Синтаксис языка программирования, представленный в виде конкретной формальной грамматики своеобразный аналог исходного текста программы.
Одна и та же программа может быть написана разными способами, т.е. идея воплощенная и реализованная на формальном языке можно реализовать множеством способов. Программа пишется содержательно, не существует формальных методов разработки программ. Не возможно определить формальными методами - эквивалентны ли две программы с точки зрения результата программы. Один и тот же синтаксис можно реализовать в виде множества формальных грамматик. Синтаксис преобразуется в формальную грамматику содержательно. Общим недостатком формальных языков является отрыв формальных грамматик от синтаксиса. Обычно формальная грамматика изучается как некоторая данность, а не результат программирования определенного синтаксиса.
Из всех классов формальных грамматик только КС грамматики продуктивно используются в синтаксическом анализе. Они дают дополнительный смысл понятию нетерминальный смысл.
Нетерминальный символ - обозначение элемента синтаксиса и место его вхождения в другие элементы синтаксиса. Кроме нетерминалов, явно обозначающих синтаксические единицы, для многих элементов синтаксиса используются вспомогательные нетерминалы.
Основные понятия и определения.
Алфавит - это конечное множество символов.
Например, алфавит A = {a, b, c, +,! } содержит 5 букв, а алфавит B = {00, 01, 10, 11} содержит 4 буквы, каждая из которых состоит из двух символов.
Цепочкой символов в алфавите V называется любая конечная последовательность символов этого алфавита.
Цепочка, которая не содержит ни одного символа, называется пустой цепочкой. Для ее обозначения будем использовать символ l.
Более формально цепочка символов в алфавите V определяется следующим образом:
) l - цепочка в алфавите V;
) если ? - цепочка в алфавите V и a - символ этого алфавита, то ?a или аa - цепочка в алфавите V;
) ? - цепочка в алфавите V тогда и только тогда, когда она является таковой в силу (1) и (2).
Если ? и ? - цепочки, то цепочка ?? называется конкатенацией (или сцеплением) цепочек ? и ?.
Например, если ? = ab и ? = cd, то ?? = abcd.
Для любой цепочки ? всегда ?l = l? = ?.
Обращением (или реверсом) це