48546 (597403), страница 3
Текст из файла (страница 3)
Вариант построения синтаксического анализа.
Нисходящий разбор - синтаксическое дерево строится от корня к листьям, его отличительная черта является целенаправленность, так как отправляясь от нетерминального символа языка, мы стремимся найти такую подстановку, которая бы привела к части цепочки терминальных символов. Достигается это путем направленного перебора различных вариантов. В списке правил подстановке отыскивается правило, которые в левой части содержат не терминальные символы, а в правой части символы терминальные анализируемого предложения. Если такое правило есть, то дерево не рассчитывается и правило повторяется. Если правило не найдено, то возвращаемся на один или несколько шагов назад, пытаясь изменить выбор сделанный ранее. Процесс разбора заканчивается в одном из двух случае.
Построенное дерево, все листья которого являются терминальными символами и при чтении с лево на право образуют анализируемое предложение. В этом случаи результат положительный, синтаксически рассматриваемое предложение соответствует грамматике языка.
Распознаватель переработал все возможные варианты, но так и не пришел к дереву, значит анализируемое предложение не принадлежит данному языку или содержит ошибку.
«константа»:: = «КФТ» | «знак» «КФТ»
Шаг 1 константа
Шаг 2 КФТ
Восходящий разбор – дерево строится от листьев к корню, то есть алгоритм отправляется от заданной строки, пытается применить правило подстановки с лева на право и все это привести к начальному символу грамматики. Часть строки, которую можно привести к нетерминальному символу называют фразой. Если приведение осуществляется приведением одного правило подстановки, фраза называется непосредственно приводимой. Самая левая непосредственная фраза называется основой. Алгоритм разбора заключается в следующем: в исходном предложении отыскивается основа и приводится к нетерминальному символу. Эта операция применяется до тех пор, пока не получим единый символ и он должен быть начальным символом грамматики. Либо в цепочке не может быть найдена фраза, в этом случаи делается возврат на один или несколько шагов, выбирается другая основа, если все возможные варианты перебраны, а корень дерева так и не построен, делается вывод об наличии ошибки. Восходящий разбор представляет собой перебор вариантов, но они не целенаправленны.
Нисходящие и восходящие методы требуют большого количества перебора. Поэтому требую только детерминированные методы.
Метод рекурсивного спуска – хорошо известный легко реализуемый и детерминированный метод разбора с верху в низ. С его помощью на основании соответствующей грамматике, можно быстро написать синтаксический анализатор. Основное преимущества – скорость создания анализатора. Другое преимущество заключается в соответствии между грамматикой и анализатором, благодаря тому что увеличивается вероятность того, что анализатор правильный. Основной недостаток - медленность, много вызовов. Вручную грамматику изменим, в ведем два нетерминальных символа. По грамматике пишем программу синтаксического анализатора. Lex – функция, которая выделяет лексему.
Лекция 30.11.07
Ll(1) – грамматика
Контекстно-свободные грамматики традиционно служат основой создания синтаксических анализаторов. Для того чтобы построить де терминированный анализатор работающий по принципу сверху в низ используется Ll(1) грамматика. Первая l означает, что исходная строка разбивается с лево на право, вторая буква – левосторонний разбор, а цифра означает, что варианты порождающих правил выбирается с помощью одного предварительного просматриваемого символа.
Определим S-грамматику.
Правая часть порождающего правила начинается с терминала.
В тех случаях, когда в левой части более одного одинаковых не терминала, то соответствующие правые части начинаются с разных терминалов.
Для того что бы грамматика была, необходимым условием является множеством символам предшественников не должно пересекаться. Грамматику называют Ll(1) если для каждого не терминала появляющегося в левой части более одного раза множества направляющих символов соответствующих правил не пересекаются. Возникает вопрос, все ли грамматики. Существует ли алгоритмы, определяющие свойства. Однако, грамматику, можно преобразовать что бы она стала Ll(1).
Что бы заменить левую рекурсию на правую мы упорядочиваем не терминалы.
Факторизация – во многих ситуациях грамматику не обладающих признаками Ll(1) можно преобразовать в грамматику Ll(1). Процесс факторизации нельзя автоматизировать, распространив его на общий случай.
Лекция 07.12.07
Ll(1) – грамматика
После нахождения грамматики, можно перейти к построению синтаксического разбора. Этот этап аналогичен рекурсивному спуску, только здесь исключается многочисленные вызовы процедур, благодаря представлению грамматики в табличном виде. Представим грамматику в виде схемы, номера соответствующие элементам будут являться номерами строк в таблице разбора.
В таблицу разборов включают по одному элементу на каждое правило грамматики. И на каждый экземпляр терминала и не терминала правой части правильной грамматики. Таблица состоит из шести столбцов.
1 столбец – направляющие символы (терминал)
2 столбец – поле перехода, обычно дает следующий элемент для обработки (номер строки). Если значение поля возврата, не окажется истинной, то адрес следующего элемента берется из стека. Это соответствует концу правила.
3 столбец – направляющие символы, переход
| № | Терминал | Переход | Принимать | стек | возврат | ошибка |
| 1 | Begin | 2 | f | f | f | t |
| 2 | Begin | 3 | t | f | f | t |
| 3 | d | 7 | f | t | f | t |
| 4 | coma | 5 | t | f | f | t |
| 5 | s | 15 | f | t | f | t |
| 6 | end | 0 | t | f | t | t |
| 7 | d | 8 | f | f | f | t |
1 действие - begin считывается и проверяется. Стек пуст, и используется в стек разборах для указания адресов возврата. Переходим на строку 2. Проверяем и принимаем begin.
В таблице каждому шагу разбора соответствует один элемент. В процессе разбора осуществляется:
Считываем и проверяем предварительно просматриваемый символ. С тем, чтобы выяснить не является ли он направляющим для какой либо конкретной правой части порождающего правила. Если этот символ не направляющий, то она проверяется на следующем этапе.
Осуществляется проверка терминала, появляющаяся в правой части порождающего правила.
Проверка не терминала. Она заключается в проверке нахождения предварительно просматриваемого символа, в одном из множеств направляющих символов. Помещения в стек адреса возврата и переходу к первому правилу относящемуся к данному правилу. Если нетерминал появляется в конце правой части, то нет необходимости помещать в стек. Программа содержит цикл процедуры. Тело которое обрабатывает элемент таблицы разбора и определяется следующий элемент для обработки. Если предварительно просматриваемый элемент отсутствует в списке системы и значение поле ошибки окажется ложью, нужно обрабатывать следующий элемент с тем же символом. Ели предварительно просматриваемый символ не содержится в текущем и поле ошибки t, то выдается сообщение о синтаксической ошибке.
Преимущества:
Никогда не требуется преимущества возврата, поскольку этот метод не терминированный.
Имеются хорошие диагностические характеристики, и существует возможность исправления ошибок. Так как синтаксические ошибки распознаются по первому не приемлемому символу, а в таблице разборов есть список возможных символов продолжения.
Таблица разбора меньше чем соответствующие таблицы в других методах, значит скорость выше.
LL1 разбор применяется к широкому классу языков, однако в большинстве случаев требуется ручное преобразование.
LR(1) – снизу в верх, разбираемый детерминированный. К – используется правосторонний разбор, от начального символа.1 - фиксированное число предварительно просматриваемых символов. Первое действие – сдвиг, во время которого считывается и помещается в стек символ, это соответствует продвижению на один пункт вдоль какого либо правила грамматики. Приведение, во время которого множество элементов верхней части стека замещается каким либо не терминалом грамматики.
Лекция 14.12.07
S - > real IDLIST
IDLIST - >IDLIST
IDLIST - > ID
ID - > a b с d
Стек символов
A ID IDLIST
Real real real
ID
IDLIST
Real
Чтобы построить таблицу разбора необходимо найти все состояния грамматики.
Таблица разбора представляет собой матрицу состоящую из столбцов – для каждого терминала и не терминала грамматики + признак окончания, и строк соответствующему каждому состоянию.
| Состояние | S | IDLIST | ID | real | , | A B S D | |
| 1 | HALT | S2 | |||||
| 2 | S5 | S4 | S3 | ||||
| 3 | R4 | R4 | |||||
| 4 | R3 | R3 | |||||
| 5 | S6 | R1 | |||||
| 6 | S7 | S3 | |||||
| 7 | R2 | R2 |
Таблица разбора включает элементы 4 типов. Сдвиг S 2 – 2 означает состояние, поместить в стек символов соответствующие столбцу символ. В стек состояния поместить 2 и перейти в состояние 2. Если входной символ терминал, принять его.
R4 – r означает элемент приведение, 4 означает 4 правило вывода. Выполнить приведения. Удалить элемент.
3 элемент – пробел, соответствует ошибке.
Сравнительный анализ методов
Оба метода детерминированы и могут обнаруживать синтаксические ошибки на самом раннем этапе.2 метод применяется к более широкому классу языков и грамматик и не требует преобразования грамматики. Дд1 требует преобразования, и при наличии хорошего преобразователя не вызывает затруднения.
Экспериментальные данные выполнены с помощью анализатора при сравнении максимального и минимального время разбора предложения пришли к мнению что метод LL быстрее на 50%, то есть метод с верху в низ быстрее на 50%.
После синтаксического анализатора, последним шагом процесса компиляции является генерация кода. Как только распознан фрагмент исходного текста программ соответствующий некоторому правилу грамматики, вызывается семантическая подпрограмма, которая не посредственно генерирует код.
Все реально существующие компиляторы, на этапе разбора входных цепочек, проверяет только синтаксис входного языка не учитывая его семантику. Для проверки необходимо иметь информацию о найденных лексических единицах языка.
Лекция 21.12.07
Генерация кода
С
ложные компиляторах могут компилироваться промежуточные формы представления программ, пригодные для последующего анализа, с целью генерации более эффективного объектного кода.
Промежуточные формы
Последовательность четверок
Последовательность троек
Полиз – позволяет представлять любое математическое выражение без скобок
S->EVP
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
