Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


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




Основной метод восходящего синтаксического анализа – перенос-свертка (ПС-анализ). Самый широкий класс грамматик, для которых успешно применяется ПС-анализаторы – это LR-грамматики. Достаточно удобный ПС-анализатора состоит в использовании стека для хранения символов грамматики и входного буфера для хранения анализируемой строки. Изначально стек пуст. Входной буфер содержит строку w. СА работает путем переноса нулей или нескольких символов в стек, до тех пор пока на вершине стека не окажется основа β, затем он свертывает β к левой части соответствующей продукции. Повторяет этот цикл пока не будет обнаружена ошибка или он не придет в конфигурацию, когда в стеке находится только стартовый символ, а буфер пуст, тогда сообщает об успешном разборе.

 

Пример:

Имеется цепочка: id1+id2*id3

E→E+E

E→E*E

E→(E)

E→id

СТЕК ВХОД ДЕЙСТВИЕ
id1+id2*id3 перенос
⊥id1 +id2*id3 свертка E→id
⊥E +id2*id3 перенос
⊥E+ id2*id3 перенос
⊥E+id2 *id3 свертка E→id
⊥E+E *id3 перенос
........... .......... ...........
⊥E Допуск

 

Существуют КС-грамматики, для которых ПС-анализ не применим, т.к. можно достичь , в которой нельзя определить какая из возможных сверток должна применяться, поэтому данный метод используется для LR-грамматик, в которых данная ситуация не врзникает.

 

LR(k)-анализатор

L – сканирование входного потока слева направо

R – построение обращенных правых разборов, т.е. от листа в корень

k – число входных символов, которые могут быть просмотрены для принятия решения о способе проведения разбора. Если k=1 опущено, то считается, что k=1.

 

Алгоритм разбора для LR(0)-грамматики

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

Грамматическое вхождение – это символы полного словаря грамматики, снабженные двумя индексами (1 – правило грамматики, в правую часть которого входит данный символ; 2 – номер позиции в этой правой части).

Управляющая программа LR-анализатора функционирует так: она определяет Sm – текущее состояние на вершине стека (магазина) и ai – текущий входной символ, затем обращается к функции action(Sm., ai) ячейки таблицы управления, которя может иметь одно из 4 значений:

1) Перенос S (перенос Si-значение пренос в i состояние);

2) Свертка в соответствие с продукцией;

3) Допуск (acc)ж

4) Ошибка (в таблице пустая клетка).

Кроме функции action в таблице используется функция go to – она получает в качестве аргумента состояние и символ грамматики и возвращает новое состояние, т.е. она представляет собой функцию переходов детерминированного конечного автомата, распознающего активные префиксы грамматики G.

Следующий шаг определяет текущий входной символ ai и состояние Sm в соответствии с их значениями в таблице.

Пример:

Имеется грамматика:

1) E→E+T

2) E→T

3) T→T*P

4) T→P

5) P→(E)

6) P→id


 


Поделиться:

Дата добавления: 2015-01-29; просмотров: 97; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты