Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
япмт шпоры.docx
Скачиваний:
0
Добавлен:
01.05.2025
Размер:
74 Кб
Скачать
☆

15. Нисходящий синтаксический анализ.

Задача нисходящего анализа, как правило, сводится к нахождению левого порождения. Процесс нисходящего анализа начинается с символа предложения с последующей генерацией предложения языка. Рассмотрим в качестве примера язык вида {x m y n |m, n > 0}, определяемый следующими продукциями: S -> XY X -> xX X -> x Y - >yY Y -> y

После генерации знак предложения подчеркивается во входной строке.

Каждому этапу синтаксического анализа соответствуют три позиции таблицы: входная строка с подчеркнутыми символами, текущая продукция, а также текущее состояние сентенциальной формы. В конце синтаксического анализа все знаки входной строки подчеркнуты, а сентенциальная форма полностью совпадает с заданной строкой.

На каждом этапе первый неподчеркнутый символ определяется как входной символ и используется для разбора. Если в сентенциальной форме генерируется терминал, появляется еще один подчеркнутый символ. Принятие решений при нисходящем синтаксическом разборе обычно основывается на символе или последовательности символов предпросмотра. Под символом предпросмотра здесь имеется в виду либо текущий входной символ, либо символ, обозначающий признак конца строки. Существуют грамматики, поддерживающие методы нисходящего синтаксического анализа с одним символом предосмотра. Это -так - называемые LL(1) -грамматики. Термин LL(1) означает следующее :первая буква L определяет направление чтения слева

( Left ) направо,вторая буква L определяет использование левых ( Leftmost) порождений, цифра 1- один символ предосмотра. Соответственно LL(1) - язык определяется как язык, генерируемый посредством LL(1) -грамматики.

16.Восходящий синтаксический анализ.

Задача восходящего анализа, как правило, сводится к нахождению правого порождения. Рассмотрим в качестве примера рассмотренный в предыдущих разделах язык {x m y n |m, n > 0}, определяемый следующими продукциями: S -> XY X -> xX X -> x Y - >yY Y -> y

В отличие от нисходящего, при восходящем синтаксическом анализе этапы порождения определяются в противоположном порядке, то есть:xxxyy=> xxX yy=> xXyy=> Xyy=> XyY=> XY=> S. Применение продукции грамматики на каждом этапе предусматривает

замену правой части продукции ее левой частью, состоящей из одного символа.

При восходящем синтаксическом анализе правые части продукции

не распознаются до тех пор, пока не будут полностью считаны. В связи с этим требуется хранение частично распознанных правых частей продукций до замены их соответствующими левыми частями. Для этой цели используется стек. Таким образом, основные этапы процесса восходящего синтаксического анализа выражаются с помощью двух типов действий.

Занесение последнего считанного символа в стек - действие

переноса (SA-shift action) .

Замена строки наверху стека посредством применения продукции грамматики - действие свертки (RA - reduce action)

Вершина стека расположена справа, а в последнем столбце показан применяемый тип операций (SA | RA) . Действие переноса выполняет удаление символа и занесение его в стек. Действие свертки предусматривает изменения в вершине стека и в сентенциальной форме посредством применения продукции. В начальном состоянии синтаксического разбора стек пустой, а сентенциальная форма совпадает с анализируемым предложением (xxxyy) . В финальном состоянии сентенциальная форма совпадает с начальным символом грамматики (S), стек содержит также начальный символ грамматики, строка полностью прочитана.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]