Главная страница
Навигация по странице:

  • 1 Теория конечных автоматов и теория синтаксического анализа 1.1 Теория конечных автоматов

  • 1.2 Теория синтаксического анализа.

  • 1.3 Постановка задачи и применение конечного автомата для еѐ решения

  • Начало (поиск раздели- теля) Поиск const Поиск double, float или int Поиск

  • Другие раздели- тели поиск раздели- теляConst начало Поиск double, float или int поиск разделителяInt, double float

  • Идент. (буква)

  • Цифра (число) поиск разделителяПоиск конеч. разделителя поиск раздели- теля= Поиск - поиск разделителя

  • Отчёт. Практики


    Скачать 341.6 Kb.
    НазваниеПрактики
    АнкорОтчёт
    Дата28.08.2022
    Размер341.6 Kb.
    Формат файлаpdf
    Имя файлаOtchyot_Krokhina_S_1_k_6_gr.pdf
    ТипРеферат
    #654778

    МИНОБРНАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
    ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ
    ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ
    «
    ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
    »
    Факультет прикладной математики, информатики и механики
    Кафедра Математического обеспечения ЭВМ
    Направление 01.03.02 – прикладная математика и информатика
    Отчѐт по учебной практике студентки 1 курса 6 группы факультета прикладной математики, информатики и механики
    Крохиной Софьи Петровны
    Место прохождения практики
    ВГУ
    Сроки прохождения практики
    06.07.2021-19.07.2021
    Тема практики
    Применение конечных автоматов для решения задачи синтаксического анализа
    Выполнила
    Крохина С. П.
    Руководитель практики от кафедры
    Кузнецова И. Ю.
    Воронеж 2021

    Содержание
    Введение ................................................................................................................... 3 1 Теория конечных автоматов и теория синтаксического анализа .................... 4 1.1 Теория конечных автоматов ........................................................................ 4 1.2 Теория синтаксического анализа ................................................................. 7 1.3 Постановка задачи и применение конечного автомата для еѐ решения . 9 2 Реализация решения задачи .............................................................................. 11 3 Тестирование ...................................................................................................... 16
    Заключение ............................................................................................................ 17
    Приложение ........................................................................................................... 18

    3
    Введение
    Конечные автоматы – это технологии, призванные облегчать разработ- ку других алгоритмов. Они служат средством достижения конечной цели - реализации алгоритма. Тем не менее, они обладают рядом интересных осо- бенностей. В основном будут рассматриваться конечные автоматы, реали- зующие алгоритмы синтаксического анализа (parsing algorithm). Синтаксиче- ский анализ означает считывание строки (или текстового файла) и разбиение последовательностей символов на отдельные лексемы. Конечный автомат, который выполняет синтаксический анализ, обычно называют синтаксиче- ским анализатором (parser).
    Цели учебной практики: изучить теорию конечных автоматов, теорию синтаксического анализа, решить задачу синтаксического анализа с помощью применения конечных автоматов:
    Пусть в файле хранятся строки, представляющие собой исходный код программы на языке Паскаль (С++). Вывести синтаксически правильные описания единичных числовых констант. Список зарезервированных слов задать в отдельном файле.

    4
    1 Теория конечных автоматов и теория синтаксического анализа
    1.1 Теория конечных автоматов
    Теория автоматов – это раздел дискретной математики, посвященный автоматным моделям реальных устройств, предназначенных для обработки дискретной информации с помощью заданного алгоритма, без учета их фи- зических и технических характеристик.
    Конечный автомат – это система, имеющая входные, выходные сигна- лы и конечное число внутренних состояний, а также функции переходов ме- жду состояниями.
    1) Входные сигналы (S) представляют собой воздействия, генерируемые внешней средой и влияющие на поведение исследуемой системы.
    2) Выходные сигналы (R) - результат обработки этой информации.
    3) Состояние автомата (K) - cодержимое памяти в настоящее время называет- ся. Состояния – это величины, которые не являются ни входными, ни выход- ными сигналами (еще их называют промежуточными переменными).
    В любой момент времени автомат находится только в одном состоянии.
    Переход состояний – это изменение текущего состояния, вызванное входным сигналом. В ответ на поступившее событие автомат может перейти в новое состояние или остаться в прежнем. То, в какое состояние перейдет автомат, зависит и от текущего состояния, и от события. Выходной сигнал зависит от входного сигнала и от состояния автомата в настоящий момент времени.
    На множествах K, S, R задают 2 логических оператора:
    1) Функция переходов g – определяющая переход автомата из одного состоя- ния в другое под действием входных сигналов (т. е. имеется состояние, пода-
    ѐтся входной сигнал и автомат переходит в другое состояние).
    2) Функция выходов p – определяющая зависимость выходного сигнала ав- томата от состояния автомата и входного сигнала.
    Состояние автомата используется для описания систем, выходные сиг- налы, которые зависят не только от входных сигналов в данный момент вре- мени, но и от некоторой предыстории, т.е. сигналов, которые поступали на

    5 входы системы ранее. Следовательно, конечные автоматы относятся к после- довательным схемам, которые обладают памятью. Конечность множества со- стояний говорит о том, что автомат обладает ограниченной памятью.
    Если перефразировать, то конечный автомат – система с конечным входным алфавитом S, конечным выходным алфавитом R, конечным множе- ством состояний K и двумя характеристическими функциями g и p.
    Классы конечных автоматов
    1) Автомат Мура: выходные сигналы зависят только от текущего состояния т. е. все действия привязаны к состояниям.
    2) Автомат Мили: выходные сигналы зависят как от текущего состояния, так и от текущих значений входных сигналов т. е. все действия привязаны к пе- реходам.
    В реальных ситуациях модель обычно представляет собой комбинацию машин Мура и Мили.
    Способы задания конечных автоматов
    1) Таблица переходов состояний – табличное представление конеч. автомата.
    2) Диаграмма перехода состояний – представление конечного автомата в ви- де графа, вершины которого соответствуют состояниям, а ориентированные дуги – переходам между ними.
    Для задания конечного автомата необходимо описать все элементы множества M = {S, R, K, g, p}. После того, как установлены входной алфавит, выходной алфавит и множество состояний, описание системы может быть формализовано при помощи таблицы, графа переходов. Такое представление необходимо для проведения любого точного анализа или синтеза конечного автомата.
    Чтобы задать автомат табличным способом, нужно заполнить его таб- лицу выходов и переходов, исходя из функции выходов р и функции перехо- дов g. Строки этих таблиц соответствуют входным сигналам, а столбцы – со-

    6 стояниям. На пересечении строки и столбца в таблице переходов ставится состояние, в которое автомат перейдет под воздействием входного сигнала, а в таблице выходов – соответствующий этому переходу выходной сигнал.
    Удобнее составлять совмещенную таблицу переходов и выходов.
    Если строится граф, то дуга проводится из вершины 1 в вершину 2 то- гда, когда в данном автомате возможен переход из состояния 1 в состояние 2 по некоторому входному сигналу. Стрелка указывает направление перехода.
    Над началом дуги указывается входной сигнал, а над стрелкой – выходной сигнал (Мура). Либо граф Мили, где сигналы указываются посередине дуги.
    Такие спецификации конечного автомата зачастую более точны и по- нятны, чем словесное описание.

    7
    1.2 Теория синтаксического анализа.
    В процессе компиляции на этапе анализа можно выделить лексический анализ, синтаксический разбор и семантический разбор. Нам понадобятся только первые два.
    Лексический анализ (сканер) – это часть компилятора, которая читает литеры программы на исходном языке и строит из них слова – лексемы ис- ходного языка. На вход лексического анализатора поступает текст исходной программы, выходная информация передаѐтся для дальнейшей обработки на этап синтаксического разбора (Лексический анализ не является обязатель- ным, но есть причины, по которым он присутствует практически во всех компиляторах).
    Синтаксический разбор – это основная часть компилятора на этапе анализа. Она выполняет выделение синтаксических конструкций в тексте ис- ходной программы и проверяет синтаксическую правильность программы.
    Форма Бэкуса-Наура (сокр. БНФ, Бэкус-Наурова форма) — формальная система описания синтаксиса, в которой одни синтаксические категории по- следовательно определяются через другие категории. БНФ используется для описания контекстно-свободных формальных грамматик.
    Терминальные символы — это минимальные элементы грамматики, не имеющие собственной грамматической структуры. В РБНФ (расширенная
    БНФ) терминальные символы — это либо предопределѐнные идентификато- ры (имена, считающиеся заданными для данного описания грамматики), либо цепочки — последовательности символов в кавычках или апострофах.
    Нетерминальные символы — это элементы грамматики, имеющие соб- ственные имена и структуру. Каждый нетерминальный символ состоит из одного или более терминальных и/или нетерминальных символов, сочетание которых определяется правилами грамматики. В РБНФ каждый нетерми- нальный символ имеет имя, которое представляет собой строку символов.
    Для БНФ используется:
    1) Символ «::=» читается: «определяется как
    ».

    8 2) Нетерминалы обозначаются произвольной символьной строкой, заклю- чѐнной в скобки «<» и «>».
    3) Терминалы – символы, используемые в описываемом языке.
    4) Символ «|» – означает «или».
    Примеры:
    1) <цифра>::=0|1|2|3|4|5|6|7|8|9. 2) <буква>::=a|b|c|…|Y|Z.
    Для РБНФ:
    1) «[» и «]» – условное вхождение (заключѐнная в скобках синтаксическая конструкция может отсутствовать).
    2) «{» и «}» – повторение заключѐнной в скобках синтаксической конструк- ции 0 или более раз.
    3) «(» и «)» – ограничение альтернативных конструкций. Применяется для группировки элементов при формировании сложных выражений.
    Примеры:
    1) A={B} – либо пусто, либо В, либо ВВ, либо ВВВ и т. д.
    2) A= B{B} – либо В, либо ВВ, либо ВВВ и т. д.
    3) A= (B|C)D – либо ВD, либо ВС.
    Вернемся к вопросу о конечных состояниях. Смысл конечного состоя- ния заключается в определении условия завершения работы автомата.Работа автомата может быть завершена при попадании его в одно из заключитель- ных состояний (такие состояния назовем поглощающими). Однако условие завершения может быть более сложным: работа автомата заканчивается то- гда, когда входная последовательность исчерпана и при этом автомат нахо- дится в одном из терминальных состояний.
    Итак, чтобы построить обобщѐнный алгоритм анализатора нужно:
    1) Задать множество состояний, множество переходов и матрицу переходов.
    2) Задать переменные текущего символа, номера состояния и т. д.
    3) Задать цикл, в котором считывается символ и относится к одной из катего- рий автомата (буква, цифра и т. д.), затем выполняется переход к следующе- му состоянию, обрабатываются промежуточные значения и в конце проверя- ется достижение выходного состояния.

    9
    1.3 Постановка задачи и применение конечного автомата для еѐ решения
    Условие задачи:
    Пусть в файле хранятся строки, представляющие собой исходный код программы на языке Паскаль (С++). Вывести синтаксически правильные описания единичных числовых констант. Список зарезервированных слов задать в отдельном файле.
    Задача будет решаться для C++ на C++. Для решения задачи построим РБНФ:
    <буква> ::= a|b|c|…|x|y|z|A|B|C|…|X|Y|Z (Все строчные и прописные буквы английского алфавита).
    <цифра> ::= 0|1|2|3|4|5|6|7|8|9. <число>::=<цифра>{<цифра>}.
    <идентификатор> ::= <буква>{<буква>|<цифра>}.
    <ключевое слово> ::= const|int|float|double|char|bool|auto|… (список ключевых слов представлен в приложении списком 1).
    <разделитель> ::= { | } | ; | = | - | ( | ) |(пробел) (остальные разделители можно отнести к другим символам т. к. они не понадобятся).
    <другие символы> ::= *|^|’|!|… (Все остальные символы, не относящиеся ни к буквам, ни к цифрам)
    Тогда числовая константа описывается как:
    A ::= ( ; | { | } | ( | ) ) const (int|double|float) <идентификатор> = [-]<число>;
    На основе РБНФ зададим конечный автомат:
    1) Множество состояний:
    1. Начало (поиск разделителя)
    2. Поиск const
    3. Поиск int, float, double
    4. Поиск буквы (для идентификатора)
    5. Поиск =
    6. Поиск -
    7. Поиск числа (цифры)
    8. Поиск конечного разделителя
    9. Конец

    10 2) Множество переходов:
    1. Разделитель - «;»
    2. Другие разделители – «{», «}», «)» ,«(».
    3. Ключ. слово - const
    4. double, float, int
    5. Буква (идентификатор)
    6. Цифра (число)
    7. Разделитель - «=»
    8. Разделитель - «-» (минус)
    9. Пробел
    10. Другие ключ. слова и символы
    «;» выделяем отдельно так как в конце описания константы обязатель- но должен быть символ «;», а в начале, перед описанием может быть любой из разделителей «{», «}», «)» ,«(», «;».
    3) Зададим таблицу переходов состояний.
    Начало
    (поиск
    раздели-
    теля)
    Поиск
    const
    Поиск
    double,
    float или
    int
    Поиск
    буквы
    (идент.)
    Поиск = Поиск -
    Поиск
    цифр
    (числа)
    Поиск
    ко-
    неч.разде
    лителя
    «;»
    Поиск const конец
    Другие
    раздели-
    тели
    поиск раздели- теля
    Const
    начало
    Поиск double, float или int поиск разделителя
    Int,
    double
    float
    поиск раздели- теля
    Поиск буквы поиск разделителя
    Идент.
    (буква)
    поиск разделителя
    Поиск = поиск раздели- теля поиск разделителя
    Цифра
    (число)
    поиск разделителя
    Поиск конеч. разделителя поиск раздели- теля
    =
    Поиск - поиск разделителя
    -
    поиск разделителя
    Поиск цифр поиск разделителя
    пробел
    Поиск const
    Поиск double, float или int
    Поиск буквы
    (идент.)
    Поиск = Поиск -
    Поиск цифр
    Поиск ко- неч.разде лителя
    Другой
    символ и
    ключ.
    слова
    поиск разделителя

    11
    2 Реализация решения задачи
    Общий принцип работы программы: 1. Создаѐтся переменная с правильным описанием числовой константы, открывается файл и читается построчно. 2.
    Каждая строка читается посимвольно 3. Определяется тип символа/слова, за- тем это(т) символ/слово добавляется к правильному описанию константы , затем стирается чтобы дальше было удобнее обрабатывать строку (она уко- рачивается, и так пока не станет пустой). Выполняется переход между со- стояниями и идѐт проверка: если после нескольких состояний мы не достиг- ли конечного состояния, а пришли к начальному то строка с правильным описанием очишается, если же мы дошли до конца то выводим на экран эту строку, увеличиваем счѐтчик и возвращаемся к начальному состоянию. Когда будет достигнут конец файла, то, если счѐтчик =0 то правильных описаний констант не нашлось.
    1) подключим основные библиотеки:
    #include

    #include

    //для использования строк
    #include

    //для работы с файлами
    #include

    //для функции isalpha – определяет является ли символ буквой
    #include

    //для использования динамических массивов
    2) Зададим множество состояний и множество переходов с помощью enum: enum sost
    { nach
    , scon
    , sdfi
    , siden
    , srav
    , sminu
    , schis
    , send
    , kone
    }; enum typelex
    { tz
    , razdel
    , con
    , dfi
    , iden
    , chislo
    , ravno
    , minu
    , prob
    , drugoe
    , pusto
    }; sost - состояния typelex – тип символа/слова nach-начало tz - «;». scon- поиск const razdel - «{», «}», «)» ,«(» sdfi – поиск double, float, int con - const siden – поиск буквы (идент.) dfi – double, float, int srav- поиск = iden – буква (идент.) sminu- поиск - chislo - число schis – поиск цифры (числа) minu - минус send – поиск конечного разделителя prob - пробел kone - конец drugoe - другое pusto – нач. состояние для обработки

    12 3) Зададим матрицу переходов с помощью двумерного массива типа sost. sost massost[10][8] =
    {{
    scon
    ,
    scon
    ,
    scon
    ,
    scon
    ,
    scon
    ,
    scon
    ,
    scon
    ,
    kone
    },
    {
    scon
    ,
    scon
    ,
    scon
    ,
    scon
    ,
    scon
    ,
    scon
    ,
    scon
    ,
    nach
    },
    {
    nach
    ,
    sdfi
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    },
    {
    nach
    ,
    nach
    ,
    siden
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    },
    {
    nach
    ,
    nach
    ,
    nach
    ,
    srav
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    },
    {
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    send
    ,
    send
    ,
    nach
    },
    {
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    sminu
    ,
    nach
    ,
    nach
    ,
    nach
    },
    {
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    schis
    ,
    nach
    ,
    nach
    },
    {
    nach
    ,
    scon
    ,
    sdfi
    ,
    siden
    ,
    srav
    ,
    sminu
    ,
    schis
    ,
    send
    },
    {
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    }};
    4) Введѐм функцию которая отделяет первое слово от строки, чтобы удобнее было определять тип слова/символа. На вход подаѐтся строка файла и воз- вращается первое слово (все символы до первого пробела) string slovv(
    string sl
    )
    { string t; for
    (
    int i = 0; i < sl
    .length(); i++)
    { if
    (
    sl
    [
    i
    ]
    ==
    ' '
    ) break
    ; t
    +=
    sl
    [
    i
    ]
    ;
    } return t;
    }
    5) Введем функцию которая определяет тип слова «идентификатор». На вход подаѐтся слово. Мы проверяем чтобы это слово состояло только из букв, цифр и нижнего подчѐркивания, если это так то возвращается iden, иначе возвращается drugoe. typelex identi(
    string slovo
    )
    { typelex tip = iden
    ; for
    (
    int i = 0; i < slovo
    .length(); i++)
    { if
    ((
    slovo
    [
    i
    ]
    ==
    '_'
    )||(isalpha(
    slovo
    [
    i
    ]
    )) || ((
    slovo
    [
    i
    ]
    >=
    '0'
    ) && (
    slovo
    [
    i
    ]
    <=
    '9'
    ))) tip = iden
    ; else
    { tip = drugoe
    ; break
    ;
    }
    } return tip;
    }
    6) Введем функцию которая определяет слово как идентификатор, const, double, float или int. На вход подаѐтся строка файла, массив ключевых слов, его размер, по ссылке передаѐтся тип слова и строка с правильным описани- ем числовой константы, чтобы их можно было изменять. Функция возвраща-

    13 ет целое число – длину слова, чтобы потом очистить строку на это количест- во символов. Вначале берѐтся первое слово в строке, может быть так, что идентификатор, «=», число и «;» написаны без пробелов, поэтому идентифи- катор (слово) надо отделить. Потом уже проверяется тип полученного слова
    (идентификатор не может быть ключ. словом). int wor(
    string tex
    , vector
    <
    string
    > keywo
    , int k
    , typelex
    & tip
    , string
    & poluch
    )
    { string vsp=slovv(
    tex
    ), strok;
    //выдел. первое слово (все симв. до первого пробела)
    tip
    = iden
    ; for
    (
    int i = 0; i < vsp.length(); i++)
    //отделяем слово от разделителей или от =
    { if
    ((vsp
    [
    i
    ]
    ==
    ';'
    )||(vsp
    [
    i
    ]
    ==
    '{'
    )||(vsp
    [
    i
    ]
    ==
    '}'
    )||(vsp
    [
    i
    ]
    ==
    '('
    )||(vsp
    [
    i
    ]
    ==
    ')'
    ) || (vsp
    [
    i
    ]
    ==
    '='
    )) break
    ; strok
    +=
    vsp
    [
    i
    ]
    ;
    } if
    (strok
    ==
    "const"
    )
    { tip
    = con
    ; poluch
    +=
    "const"
    ; return
    5;
    } for
    (
    int j = 0; j < k
    ; j++) if
    (strok
    ==
    keywo
    [
    j
    ]
    )
    { if
    ((strok
    ==
    "double"
    ) || (strok
    ==
    "float"
    ) || (strok
    ==
    "int"
    )) tip
    = dfi
    ; else tip
    = drugoe
    ; poluch
    +=
    keywo
    [
    j
    ]
    ; return keywo
    [
    j
    ]
    .length();
    } tip
    = identi(strok); poluch
    +=
    strok; return
    (strok.length());
    }
    7) Введем функцию определяющую число. На вход подаѐтся строка файла, по ссылке строка с правильным описанием числовой констаны, чтобы еѐ можно было изменять. Работает аналогочно с предыдущей функцией, только для чисел. Возвращает длину числа. int chisla(
    string tex
    , string
    & poluch
    )
    { string vsp = slovv(
    tex
    ), strok; for
    (
    int i = 0; i < vsp.length(); i++)
    { if
    ((vsp
    [
    i
    ]
    <
    '0'
    ) || (vsp
    [
    i
    ]
    >
    '9'
    )) break
    ; strok
    +=
    vsp
    [
    i
    ]
    ;
    } poluch
    +=
    strok; return
    (strok.length());
    }

    14 8) Введем функцию определяющую к какому типу отнести символ/слово. На вход по ссылке подаѐтся строка файла, чтобы стереть из неѐ обработанные символы/слова, и строка с правильным описанием числовой константы. Так- же передаѐтся массив зарезервированных слов, его размер и состояние. Воз- вращается тип слова/символа. typelex lexx(
    string
    & text
    , vector
    <
    string
    > keywo
    , int k
    , string
    & poluch
    , sost q
    )
    { typelex p(
    pusto
    ); switch
    (
    text
    [
    0
    ]
    )
    { case
    '{'
    : case
    '}'
    : case
    ')'
    : case
    '('
    : poluch
    +=
    text
    [
    0
    ]
    ; text
    .erase(0, 1); return
    (p = razdel
    ); break
    ;
    //разделитель case
    ';'
    : poluch
    +=
    text
    [
    0
    ]
    ; if
    (
    q
    != send
    )
    //может быть так что идут 2 подряд описания константы, поэто- му ; межу ними не стирается text
    .erase(0, 1); return
    (p = tz
    ); break
    ; case
    '-'
    : poluch
    +=
    text
    [
    0
    ]
    ; text
    .erase(0, 1); return
    (p = minu
    ); break
    ;
    //минус case
    '='
    : poluch
    +=
    text
    [
    0
    ]
    ; text
    .erase(0, 1); return
    (p = ravno
    ); break
    ;
    //равно
    } if
    ((isalpha(
    text
    [
    0
    ]
    ))||(
    text
    [
    0
    ]
    ==
    '_'
    ))
    { int r = wor(
    text
    , keywo
    , k
    , p, poluch
    );
    //ищем длину и тип слова text
    .erase(0, r); return
    (p);
    //идент., const, double, float, int или другое ключ. слово
    } if
    ((
    text
    [
    0
    ]
    >=
    '0'
    ) && (
    text
    [
    0
    ]
    <=
    '9'
    ))
    { int h = chisla(
    text
    , poluch
    );
    //ищем длину числа text
    .erase(0, h); return
    (p = chislo
    );
    //число
    } if
    (
    text
    [
    0
    ]
    ==
    ' '
    )
    { poluch
    +=
    text
    [
    0
    ]
    ; text
    .erase(0, 1); return
    (p = prob
    );
    //пробел
    } poluch
    +=
    text
    [
    0
    ]
    ; text
    .erase(0, 1); return
    (p = drugoe
    );
    //другие символы и ключ. слова
    }

    15 9) Основная часть программы int main()
    { setlocale(
    LC_ALL
    ,
    "Russian"
    ); sost massost[10][8] = … (матрица переходов); ifstream prog(
    "D:/papka/Prakt.txt"
    );
    //файл с текстом исходной программы ifstream rezerv(
    "D:/papka/zarwzerv.txt"
    );
    //ключ. слова if
    ((
    !
    prog) || (
    !
    rezerv))
    //проверяем открытие файлов cout
    <<
    "Error"
    ; else
    { cout
    <<
    "Files is open\n\n"
    ; vector
    <
    string
    > keyww; int n = 0;
    //создание массива ключевых слов while
    (rezerv)
    { string taxt; getline(rezerv, taxt); if
    (taxt.length() > 0)
    { keyww.push_back(taxt); n++;
    }
    } sost q(
    nach
    ); int y = 0; string poluch =
    ""
    ;
    //строка для правильного описа- ния числовой константы и кол-во этих описаний while
    (prog)
    { string text; getline(prog, text);
    //считали строку while
    (text.length() > 0)
    { typelex top = lexx(text, keyww, n, poluch, q); q = massost[top][q];
    //выполнение перехода по матрице if
    ((q == nach
    )|| ((q == scon
    ) && ((top == tz
    ) || (top == raz- del
    ))))
    //очищаем строку от лишних слов/символов poluch
    =
    ""
    ; if
    (q == kone
    )
    //если найдено одно прав. опис. то выводим стро- ку, очищаем её и переходим в нач. сост. для поиска других правильных описаний
    { y++; cout
    <<
    poluch
    <<
    endl; q = nach
    ; poluch
    =
    ""
    ;
    }
    }
    } if
    (y == 0)
    //если нет правильных описаний cout
    <<
    "Нет правильного описания единичной числовой константы((("
    <<
    endl; rezerv.close(); prog.close();
    }
    }

    16
    3 Тестирование
    1) { const double 5 = 5; - программа выведет что правильных описаний нет т. к. идентификатор не может быть цифрой.
    2) (const char t=5; - правильных описаний нет т. к. константа должна быть чи- словой а не char.
    3) ;const int for = 5; - правильных описаний нет т. к. идентификатор не может быть ключевым словом.
    4) ;const float t = 5a; - правильных описаний нет т. к. в числе не должно быть букв.
    5) int z const int t=5; - правильных описаний нет т. к. нет разделителя между z и const.
    6) const int t = - 3 5; - правильных описаний нет т. к. в числе пробела между цифрами быть не может (или между 3 и 5 должен быть разделитель - ;).
    7) {const int t=6} - правильных описаний нет т. к. после числа должен быть разделитель - ;.
    8) } int k=9; const int t =
    -5; - даже с учѐтом новой строки будет выведена строка - const int t = -5;
    9) ; const float t = 5; - даже с учѐтом пробелов будет выведена эта же строка, но без ; в начале.

    17
    Заключение
    В результате прохождения учебной практики цель была достигнута, ба- за теории конечных автоматов и теории синтаксического анализа, необходи- мая для решения задачи, была изучена, задача синтаксического анализа была решена с помощью конечного автомата в полном объѐме.
    Я научилась применять на практике конечные автоматы, призванные облегчать разработку других алгоритмов и служащие средством достижения конечной цели - реализации алгоритма.

    18
    Приложение
    1. Программа
    #include

    #include

    #include

    #include

    //isalpha
    #include

    using namespace std; enum sost
    { nach
    , scon
    , sdfi
    , siden
    , srav
    , sminu
    , schis
    , send
    , kone
    }; enum typelex
    { tz
    , razdel
    , con
    , dfi
    , iden
    , chislo
    , ravno
    , minu
    , prob
    , drugoe
    , pusto
    }; string slovv(
    string sl
    )
    { string t; for
    (
    int i = 0; i < sl
    .length(); i++)
    { if
    (
    sl
    [
    i
    ]
    ==
    ' '
    ) break
    ; t
    +=
    sl
    [
    i
    ]
    ;
    } return t;
    }
    typelex identi(
    string slovo
    )
    { typelex tip = iden
    ; for
    (
    int i = 0; i < slovo
    .length(); i++)
    { if
    ((
    slovo
    [
    i
    ]
    ==
    '_'
    ) || (isalpha(
    slovo
    [
    i
    ]
    )) || ((
    slovo
    [
    i
    ]
    >=
    '0'
    ) && (
    slo- vo
    [
    i
    ]
    <=
    '9'
    ))) tip = iden
    ; else
    { tip = drugoe
    ; break
    ;
    }
    } return tip;
    } int wor(
    string tex
    , vector
    <
    string
    > keywo
    , int k
    , typelex
    & tip
    , string
    & poluch
    )
    //ищем const, другие ключ. слова, идент. и их длину
    { string vsp=slovv(
    tex
    ), strok; tip
    = iden
    ; for
    (
    int i = 0; i < vsp.length(); i++)
    { if
    ((vsp
    [
    i
    ]
    ==
    ';'
    )||(vsp
    [
    i
    ]
    ==
    '{'
    )||(vsp
    [
    i
    ]
    ==
    '}'
    )||(vsp
    [
    i
    ]
    ==
    '('
    )||(vsp
    [
    i
    ]
    ==
    ')'
    ) || (vsp
    [
    i
    ]
    ==
    '='
    )) break
    ; strok
    +=
    vsp
    [
    i
    ]
    ;
    } if
    (strok
    ==
    "const"
    )
    { tip
    = con
    ; poluch
    +=
    "const"
    ; return
    5;
    } for
    (
    int j = 0; j < k
    ; j++) if
    (strok
    ==
    keywo
    [
    j
    ]
    )
    { if
    ((strok
    ==
    "double"
    ) || (strok
    ==
    "float"
    ) || (strok
    ==
    "int"
    )) tip
    = dfi
    ; else tip
    = drugoe
    ;

    19 poluch
    +=
    keywo
    [
    j
    ]
    ; return keywo
    [
    j
    ]
    .length();
    } tip
    = identi(strok); poluch
    +=
    strok; return
    (strok.length());
    } int chisla(
    string tex
    , string
    & poluch
    )
    { string vsp = slovv(
    tex
    ), strok; for
    (
    int i = 0; i < vsp.length(); i++)
    { if
    ((vsp
    [
    i
    ]
    <
    '0'
    ) || (vsp
    [
    i
    ]
    >
    '9'
    )) break
    ; strok
    +=
    vsp
    [
    i
    ]
    ;
    } poluch
    +=
    strok; return
    (strok.length());
    } typelex lexx(
    string
    & text
    , vector
    <
    string
    > keywo
    , int k
    , string
    & poluch
    , sost q
    )
    { typelex p(
    pusto
    ); switch
    (
    text
    [
    0
    ]
    )
    { case
    '{'
    : case
    '}'
    : case
    ')'
    : case
    '('
    : poluch
    +=
    text
    [
    0
    ]
    ; text
    .erase(0, 1); return
    (p = razdel
    ); break
    ;
    //разделитель case
    ';'
    : poluch
    +=
    text
    [
    0
    ]
    ; if
    (
    q
    != send
    ) text
    .erase(0, 1); return
    (p = tz
    ); break
    ;
    //разделитель ;
    case
    '-'
    : poluch
    +=
    text
    [
    0
    ]
    ; text
    .erase(0, 1); return
    (p = minu
    ); break
    ;
    //минус case
    '='
    : poluch
    +=
    text
    [
    0
    ]
    ; text
    .erase(0, 1); return
    (p = ravno
    ); break
    ;
    //равно
    } if
    ((isalpha(
    text
    [
    0
    ]
    ))||(
    text
    [
    0
    ]
    ==
    '_'
    ))
    { int r = wor(
    text
    , keywo
    , k
    , p, poluch
    ); text
    .erase(0, r); return
    (p);
    //идентификатор const или другое ключ. слово
    } if
    ((
    text
    [
    0
    ]
    >=
    '0'
    ) && (
    text
    [
    0
    ]
    <=
    '9'
    ))
    { int h = chisla(
    text
    , poluch
    ); text
    .erase(0, h); return
    (p = chislo
    );
    //число
    } if
    (
    text
    [
    0
    ]
    ==
    ' '
    )
    { poluch
    +=
    text
    [
    0
    ]
    ; text
    .erase(0, 1); return
    (p = prob
    );
    //пробел
    } poluch
    +=
    text
    [
    0
    ]
    ; text
    .erase(0, 1); return
    (p = drugoe
    );
    //другие символы или ключ. слова
    }

    20 int main()
    { setlocale(
    LC_ALL
    ,
    "Russian"
    ); sost massost[10][8] =
    {{
    scon
    ,
    scon
    ,
    scon
    ,
    scon
    ,
    scon
    ,
    scon
    ,
    scon
    ,
    kone
    },
    {
    scon
    ,
    scon
    ,
    scon
    ,
    scon
    ,
    scon
    ,
    scon
    ,
    scon
    ,
    nach
    },
    {
    nach
    ,
    sdfi
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    },
    {
    nach
    ,
    nach
    ,
    siden
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    },
    {
    nach
    ,
    nach
    ,
    nach
    ,
    srav
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    },
    {
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    send
    ,
    send
    ,
    nach
    },
    {
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    sminu
    ,
    nach
    ,
    nach
    ,
    nach
    },
    {
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    schis
    ,
    nach
    ,
    nach
    },
    {
    nach
    ,
    scon
    ,
    sdfi
    ,
    siden
    ,
    srav
    ,
    sminu
    ,
    schis
    ,
    send
    },
    {
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    ,
    nach
    }}; ifstream prog(
    "D:/papka/Prakt.txt"
    );
    //откуда считывать ifstream rezerv(
    "D:/papka/zarwzerv.txt"
    );
    //ключ. слова if
    ((
    !
    prog) || (
    !
    rezerv)) cout
    <<
    "Error"
    ; else
    { cout
    <<
    "Files is open\n\n"
    ; vector
    <
    string
    > keyww; int n = 0;
    //массив ключевых слов и его размер while
    (rezerv)
    { string taxt; getline(rezerv, taxt); if
    (taxt.length() > 0)
    { keyww.push_back(taxt); n++;
    }
    } sost q(
    nach
    ); int y = 0; string poluch =
    ""
    ;
    //строка для правильного описа- ния и кол-во прав. опис.
    while
    (prog)
    { string text; getline(prog, text);
    //считали строку while
    (text.length() > 0)
    { typelex top = lexx(text, keyww, n, poluch, q); q = massost[top][q]; if
    ((q == nach
    )|| ((q == scon
    ) && ((top == tz
    ) || (top == raz- del
    )))) poluch
    =
    ""
    ; if
    (q == kone
    )
    { y++; cout
    <<
    poluch
    <<
    endl; q = nach
    ; poluch
    =
    ""
    ;
    }
    }
    } if
    (y == 0) cout
    <<
    "Нет правильного описания единичной числовой константы((("
    <<
    endl; rezerv.close(); prog.close();
    }
    }

    21 2. Список 1 (Ключевые слова) alignas alignof and and_eq asm auto bitand bitor bool break case catch char char16_t char32_t class compl const constexpr const_cast continue decltype default delete do double dynamic_cast else enum explicit export extern false float for friend goto if inline int long mutable namespace new noexcept not not_eq nullptr operator or or_eq private protected public register reinterpret_cast return short signed sizeof static static_assert static_cast final struct switch template this thread_local throw true try typedef typeid typename union unsigned using virtual void volatile wchar_t while xor xor_eq override


    написать администратору сайта