Построение функции предшествования по заданной КС-грамматике

    Дисциплина: Программирование
    Тип работы: Курсовая
    Тема: Построение функции предшествования по заданной КС-грамматике

    САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ имени академика С.П. КОРОЛЕВА
    Кафедра информационных систем и технологий
    ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
    к курсовому проекту по курсу
    \"Информационные технологии\" на тему
    \"Построение функции предшествования по заданной КС-грамматике\"
    Выполнил:
    студент группы 634 Абраров А.М.
    Руководитель проекта:
    Шамашов М.А.
    Дата сдачи:
    Оценка:
    Самара 2001 г.
    РЕФЕРАТ
    Курсовой проект
    Пояснительная записка: 30 с., 5 рис., 3 схем программ и алгоритмов, 3 библиографического источника.
    ТЕРМИНАЛ, НЕТЕРМИНАЛ, ГРАММАТИКА, ФУНКЦИЯ ПРЕДШЕСТВОВАНИ, ГРАФ, ЛИНЕАРИЗАЦИЯ.
    В курсовом проекте разработан алгоритм и соответствующая ему программа, позволяющая по введённой пользователем КС-грамматике построить функцию предшествования, используя граф
    линеаризации и алгоритм пересчета с визуализацией шагов построения графа. Грамматика может быть введена как в самой программе, так и из текстового файла. Также
    существует возможность сохранения результата. Программа написана на языке
    Pascal 7.0.
    СОДЕРЖАНИ
    TOC \\o \"1-5\"
    СОДЕРЖАНИЕ
    ......................................................................................................................................................................
    PAGEREF _Toc533955590 \\h
    1. Постановка задачи
    ...............................................................................................................................................
    PAGEREF _Toc533955591 \\h
    2. Описание структуры данных
    .....................................................................................................................
    PAGEREF _Toc533955592 \\h
    3. Грамматики предшествования
    .................................................................................................................
    PAGEREF _Toc533955593 \\h
    3.1 Грамматик
    простого предшествования
    ...................................................................
    PAGEREF _Toc533955594 \\h
    3.2 Грамматик
    операторного предшествования
    ........................................................
    PAGEREF _Toc533955595 \\h
    3.3 Пример построения матрицы предшествования
    .................................................
    PAGEREF _Toc533955596 \\h
    3.4 Линеаризация матрицы предшествования
    ..............................................................
    PAGEREF _Toc533955597 \\h
    4. Руководство пользователя
    .......................................................................................................................
    PAGEREF _Toc533955598 \\h
    5. Текст программы
    .................................................................................................................................................
    PAGEREF _Toc533955599 \\h
    6. Список использованных источников
    .............................................................................................
    PAGEREF _Toc533955600 \\h
    Постановка задачи
    По заданной КС-грамматике построить отношение простого или операторного предшествования и функцию предшествования, используя граф линеаризации и алгоритм пересчета с
    визуализацией шагов построения графа.
    Описание структуры данных
    Типы:
    Для хранения терминалов и терминалов используется тип:
    notTerm=^List;
    List=Record{список терминалов и нетерминалов}
    {терминал или нетерминал}
    Для хранения грамматики (текста) используется:
    Матрица предшествования:
    Функция предшествования:
    Процедуры и функции (основные):
    Ввод грамматики осуществляется функцией:
    Function
    InputText
    :Boolean;
    Для синтаксического анализа КС-грамматики используется процедура:
    Procedure Check;
    Для нахождения «левых» и «правых» используется процедура:
    Procedure SearchLR;
    Построение матрицы предшествования выполняет процедура:
    Procedure Matrix;
    Построение функции предшествования осуществляется процедурой:
    Procedure FuncPrecede;
    3. Грамматики предшествования
    КС-языки делятся на классы в соответствии со структурой правил их грамматик. В каждом из классов налагаются дополнительные ограничения на допустимые правила грамматики.
    Одним из таких классов является класс грамматик предшествования. Они используются для синтаксического разбора цепочек с помощью алгоритма “сдвиг-свертка”. Выделяют следующие
    типы грамматик предшествования:
    простого предшествования;
    расширенного предшествования;
    слабого предшествования;
    смешанной стратегии предшествования;
    операторного предшествования.
    Далее будут рассмотрены ограничения на структуру правил и алгоритмы разбора для двух типов - грамматик простого и операторного предшествования.
    3.1 Грамматик
    простого предшествования
    Грамматикой простого предшествования называют такую КС-грамматику G(VN,VT,P,S), V=VT
    в которой:
    Для каждой упорядоченной пары терминальных и нетерминальных символов выполняется не более чем одно из трех отношений предшествования:
    i = S
    ), если и только если
    правило U
    P, где U
    VN, x,y
    ), если и только если
    правило U
    P и вывод D
    jz, где U,D
    VN, x,y,z
    ) , если и только если
    правило U
    P и вывод C
    i или
    правило U
    xCDy
    P и выводы C
    i и D
    jw, где U,C,D
    VN, x,y,z,w
    Различные порождающие правила имеют разные правые части.
    Отношения =, называют отношениями предшествования для символов. Отношение предшествования единственно для каждой упорядоченной пары символов. При этом между
    какими-либо двумя символами может и не быть отношения предшествования - это значит, что они не могут находиться рядом ни в одном элементе разбора синтаксически правильной цепочки.
    Отношения предшествования зависят от порядка, в котором стоят символы, и в этом смысле их нельзя путать со знаками математических операций - например, если S
    j, то не обязательно, что S
    i (поэтому знаки предшествования иногда помечают специальной точкой: =
    Метод предшествования основан на том факте, что отношения предшествования между двумя соседними символами распознаваемой строки соответствуют трем следующим вариантам:
    i+1, если символ S
    i+1 - крайний левый символ некоторой основы;
    i+1 , если символ S
    i - крайний правый символ некоторой основы;
    i = S
    i+1 , если символы S
    i и S
    i+1 принадлежат одной основе.
    Исходя из этих соотношений выполняется разбор строки для грамматики предшествования.
    На основании отношений предшествования строят матрицу предшествования грамматики. Строки матрицы предшествования помечаются первыми символами, столбцы - вторыми символами
    отношений предшествования, а в клетки матрицы на пересечении соответствующих столбца и строки помещаются знаки отношений. При этом пустые клетки матрицы говорят о том, что между
    данными символами нет ни одного отношения предшествования.
    Матрицу предшествования грамматики можно построить, опираясь непосредственно на определения отношений предшествования, но удобнее воспользоваться двумя дополнительными
    множествами - множеством крайних левых и множеством крайних правых символов относительно нетерминалов грамматики. Эти множества определяются следующим образом:
    (U) = {T |
    *Tz}, U,T
    V, z
    * - множество крайних левых символов относительно нетерминального символа U (цепочка z может б...

    Забрать файл

    Похожие материалы:


ПИШЕМ УНИКАЛЬНЫЕ РАБОТЫ
Заказывайте напрямую у исполнителя!


© 2006-2016 Все права защищены