САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ имени академика С.П. КОРОЛЕВА Кафедра информационных систем и технологий
    ПОЯСНИТЕЛЬНАЯ ЗАПИСКА к курсовому проекту по курсу "Информационные технологии" на тему "Построение функции предшествования по заданной КС-грамматике" Выполнил: студент группы 634 Абраров А.М. Руководитель проекта: Шамашов М.А. Дата сдачи: Оценка:
    Самара 2001 г.
    
    РЕФЕРАТ
    Курсовой проект
    Пояснительная записка: 30 с., 5 рис., 3 схем программ и алгоритмов, 3 библиографического источника.
    ТЕРМИНАЛ, НЕТЕРМИНАЛ, ГРАММАТИКА, ФУНКЦИЯ ПРЕДШЕСТВОВАНИ, ГРАФ, ЛИНЕАРИЗАЦИЯ.
    В курсовом проекте разработан алгоритм и соответствующая ему программа, позволяющая по введённой пользователем КС-грамматике построить функцию предшествования, используя граф линеаризации и алгоритм пересчета с визуализацией шагов построения графа. Грамматика может быть введена как в самой программе, так и из текстового файла. Также существует возможность сохранения результата. Программа написана на языке Pascal 7.0. СОДЕРЖАНИЕ
    СОДЕРЖАНИЕ 3
    1. ПОСТАНОВКА ЗАДАЧИ 4
    2. ОПИСАНИЕ СТРУКТУРЫ ДАННЫХ 5
    3. ГРАММАТИКИ ПРЕДШЕСТВОВАНИЯ 6
    3.1 ГРАММАТИКИ ПРОСТОГО ПРЕДШЕСТВОВАНИЯ 6
    3.2 ГРАММАТИКИ ОПЕРАТОРНОГО ПРЕДШЕСТВОВАНИЯ 8
    3.3 ПРИМЕР ПОСТРОЕНИЯ МАТРИЦЫ ПРЕДШЕСТВОВАНИЯ 10
    3.4 ЛИНЕАРИЗАЦИЯ МАТРИЦЫ ПРЕДШЕСТВОВАНИЯ 13
    4. РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ 13
    5. ТЕКСТ ПРОГРАММЫ 15
    6. СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 30
     1. Постановка задачи
    
    По заданной КС-грамматике построить отношение простого или операторного предшествования и функцию предшествования, используя граф линеаризации и алгоритм пересчета с визуализацией шагов построения графа.
     2. Описание структуры данных Типы: Для хранения терминалов и терминалов используется тип: notTerm=^List; List=Record{список терминалов и нетерминалов}
    Name:Str10;{терминал или нетерминал}
    Next:notTerm;
    End; Для хранения грамматики (текста) используется: strBuf=array [1..800] of Char; Матрица предшествования: matrixPr=array [1..20,1..20] of 0..4; Функция предшествования: FuncPr=array [1..2,1..20] of Byte; Процедуры и функции (основные): Ввод грамматики осуществляется функцией: Function InputText:Boolean; Для синтаксического анализа КС-грамматики используется процедура: Procedure Check; Для нахождения "левых" и "правых" используется процедура: Procedure SearchLR; Построение матрицы предшествования выполняет процедура: Procedure Matrix; Построение функции предшествования осуществляется процедурой: Procedure FuncPrecede;
     3. Грамматики предшествования КС-языки делятся на классы в соответствии со структурой правил их грамматик. В каждом из классов налагаются дополнительные ограничения на допустимые правила грамматики. Одним из таких классов является класс грамматик предшествования. Они используются для синтаксического разбора цепочек с помощью алгоритма "сдвиг-свертка". Выделяют следующие типы грамматик предшествования: * простого предшествования; * расширенного предшествования; * слабого предшествования; * смешанной стратегии предшествования; * операторного предшествования. ............