Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Топ:
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов...
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Интересное:
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Дисциплины:
2020-04-01 | 201 |
5.00
из
|
Заказать работу |
|
|
Распознаватель лексем языка для данной грамматики задан конечным детерминированным автоматом, схема которого представлена на рисунках 3, 4 и 5.
Рисунок 3 - Схема распознавателя 1
Рисунок 4 - Схема распознавателя 2
Рисунок 5 - Схема распознавателя 3
Легенда:
V - любой определенный алфавитно-цифровой символ (буквы латинского алфавита, знак «_», десятичные цифры);
V(*) - любой символ кроме перечисленных в скобках;- буквы латинского алфавита и знак «_»;(*) - любая буква кроме перечисленных в скобках;
Р - пробел, табуляция, перенос строки;
D - недопустимые символы (все кроме перечисленных);- сохранение (ID - в таблице идентификаторов; L -в таблице лексем);
e - ошибка;- имя лексемы;
Состояния соответствуют:
Н - начальное состояние;
К - конечное состояние;
P1, P2, P3, P4 - состояния, соответствующие ключевому слову “prog”;
En1, En2 - состояния, соответствующие ключевому слову “end”;
I1, I2 - состояния, соответствующие ключевому слову “if”;
E1, E2, E3, E4 - состояния, соответствующие слову “else”;
T1, T2, T3, T4 - состояния, соответствующие слову “then”;
W1, W2, W3, W4, W5 - состояния, соответствующие ключевому слову “while”;
D1, D2 - состояния, соответствующие ключевому слову “do”;
S1, S2, S3 - состояния, соответствующие символьное константе:
A1, A2 - состояния, соответствующие оператору присваивания “:=”;
С1, С2 - комментарий;
Программа, реализованная на основе данного автомата, выполняет лексический анализ текста программы на заданном языке.
Результат выполнения программы
Результат разбора входных выражений на лексемы представлен на рисунке 6.
Рисунок 6 - Результат работы лексического анализатора (таблица лексем)
Спроектированный лексический анализатор выполняет лексический анализ входного текста в соответствии с заданной грамматикой и порождает таблицу лексем с указанием их типов. Программа выводит также сообщения о наличие во входном тексте ошибок. Этот алгоритм послужит в дальнейшем базой для построения дерева вывода в 3 части курсовой работы.
|
4. ПОСТРОЕНИЕ СИТАКСИЧЕСКОГО АНАЛИЗАТОРА
Дерево вывода
Лексический анализатор выделяет в тексте лексемы языка. Полученная после лексического анализа цепочка во второй части программы рассматриваться в соответствии с алгоритмом разбора. После построения цепочки вывода на ее основе строится дерево разбора.
Программа выполняет лексический анализ входного языка, порождает таблицу лексем и выполняет синтаксический разбор текста по заданной грамматике с построением дерева разбора. Текст на входном языке задается в виде символьного (текстового) файла. Программа должна выдавать сообщения о наличие во входном тексте ошибок.
Длину идентификаторов и строковых констант считать ограниченной 32 символами.
Синтаксический анализатор
Перед синтаксическим анализатором стоят две основные задачи: проверить правильность конструкций программы, которая представляется в виде уже выделенных слов входного языка, и преобразовать ее в вид, удобный для дальнейшей семантической (смысловой) обработки и генерации кода. Одним из таких способов представления является дерево синтаксического разбора.
Программирование работы недетерминированного МП-автомата - это сложная задача. Разработанный алгоритм, позволяет для произвольной КС-грамматики определить, принадлежит ли ей заданная входная цепочка (алгоритм Кока-Янгера-Касами).
Доказано, что время работы этого алгоритма пропорционально n 3, где n - длина входной цепочки. Для однозначной КС-грамматики при использовании другого алгоритма (алгоритм Эрли) это время пропорционально n 2. Подобная зависимость делает эти алгоритмы требовательными к вычислительным ресурсам. На практике и не требуется анализ цепочки произвольного КС-языка - большинство конструкций языков программирования может быть отнесено в один из классов КС-языков, для которых разработаны алгоритмы разбора, линейно зависящие от длины входной цепочки.
|
КС-языки делятся на классы в соответствии со структурой правил их грамматик. В каждом из классов налагаются дополнительные ограничения на допустимые правила грамматики.
Одним из таких классов является класс грамматик предшествования. Они используются для синтаксического разбора цепочек с помощью алгоритма “сдвиг-свертка”. Выделяют следующие типы грамматик предшествования:
- простого предшествования;
- расширенного предшествования;
- слабого предшествования;
- смешанной стратегии предшествования;
- операторного предшествования.
Алгоритм построения синтаксического анализатора включает следующие этапы:
) составление правил грамматики языка;
) выявление множества крайних правых и кайних левых терминальных и нетерминальных символов;
) построение матрицы предшествования.
Рассмотрим эти этапы более подробно.
4.3 Таблицы предшествования
Множество правил грамматики имеет вид:
<буква>→” A ” |….| ” Z ” |….| ” a ” |….| ” z ” |”_”
<арифм.опер.>→”+” | ”-” | ”*” |”/”
<цифра>→”0”|”1”|”2”|”3”|”4”|”5”|”6”|”7”|”8”|”9”
< ID >→<буква>
|< ID ><буква>
|< ID ><цифра>
<симв.конст.> →’<буква>’
|’<цифра>’
<операнд>→< ID >
|< симв.конст.>
<арифм.выр.>→ <операнд><арифм.оп.><операнд>
|<арифм.выр><арифм.оп.><операнд>
|<операнд><арифм.оп.>< арифм.выр >
<оператор>→<оп.цикла>
|< оп.присв>
|<услов.оп>
<оп.присв.>→< ID >”:=”<операнд>”;”
|< ID >”:=”<арифм.выр.>”;”
<блок опер.> →<оператор> ”;” <оператор>
|<блок>”;”<оператор>
<тело>→”{“<блок опер>”;}”
<оп.цикла>→ “ do ”<тело>“ while ” ”(” <арифм.выр.>”)” ”;”
|“ do ””{“ <оператор> ”}” “ while ””(” <арифм.выр.>”)””;”
<услов.оп>→ if “(”<арифм.выр>“)”” then ”<тело>” else ”<тело>
| if “(” <арифм.выр>“)”” then ”<тело>
| if “(”<арифм.выр>“)” then ”<оператор>” else ”<оператор>
| if “(” <арифм.выр>“)”” then ”<оператор>
|
| if “(”<арифм.выр>“)”” then ”<оператор>” else ”<тело>
| if “(”<арифм.выр>“)”” then ”<тело>” else ”<оператор>
<прогр.>→ “ prog ”<тело> “ end ”
|“ prog ”<оператор> “ end ”
Грамматика является грамматикой операторного предшествования, так как она не содержит l-правил и правые части правил не содержат смежных нетерминальных символов. Построим множества крайних левых и крайних правых символов L (U), R (U) относительно всех нетерминальных символов грамматики.
Таблица 3.1 - Множества крайних правых и крайних левых символов
Символ (U) | Начало построения | |
L(U) | R(U) | |
<элемент> | <число>,ID, <элемент> | <число>,ID |
<лев.выр> | <элемент>,<лев.выр> | <элемент>,<число> |
<выр> | <лев.выр> | ”;” |
<сис.уравн> | <сис.уравн>,<выр> | <выр> |
На основе полученных множеств построим множества крайних левых и крайних правых терминальных символов Lt (U), Rt (U) относительно всех нетерминальных символов грамматики.
Таблица 3.2 - Множества крайних правых и крайних левых терминальных символов
Символ (U) | Начало построения | |
L(U) | R(U) | |
<элемент> | <число>,ID | <число>,ID |
<лев.выр> | <число>,ID | <число>,ID |
<выр> | <число>,ID | ”;” |
<сис.уравн> | <число>,ID | ”;” |
На основе этих множеств и правил грамматики G построим матрицу предшествования грамматики:
Таблица 3.3 - Матрица предшествования исходной грамматики
константа | переменная. | ; | = | - | + | * | / | |
Константа | - | - | < | < | < | < | < | - |
Переменная | - | - | - | < | < | < | < | < |
; | < | < | - | - | - | - | - | - |
= | < | - | - | - | - | - | - | - |
- | < | < | - | - | - | - | - | - |
+ | < | < | - | - | - | - | - | - |
* | < | < | - | - | - | - | - | - |
/ | < | < | - | - | - | - | - | - |
|
|
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!