Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Топ:
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Установка замедленного коксования: Чем выше температура и ниже давление, тем место разрыва углеродной цепи всё больше смещается к её концу и значительно возрастает...
Интересное:
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Дисциплины:
2020-04-01 | 204 |
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!