Студопедия

КАТЕГОРИИ:

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


Нисходящий анализ.




Метод рекурсивного спуска.

Предиктивный разбор.

Рассмотрим на примере нисходящий анализ в общем виде, а именно анализ методом рекурсивного спуска, который может использовать откаты (возвраты), т. е. производить повторное сканирование входного потока.

Пример:

Рассмотрим грамматику с правилами

и входной строкой: ω = cad.

Сначала создаём дерево, состоящее из одного узла, помеченного как S. Теперь воспользуемся первой продукцией для S, получим дерево 1)

 

           
   
S
 
S
   
S
 
 

 


d
A
c
d
A
c

                       
 
c
 
A
 
d
           
 

 


1)
3)
2)

 

Крайний слева лист, c, соответствует первому символу строки ω. В противном случае мы должны перейти ко второй продукции для S. Если её нет, то строка не соответствует правилам грамматики. Переместим указатель входа на второй символ в строке ω и рассмотрим следующий лист в строке – это нетерменал A. Применим к A первую продукцию и получим 2). ca соответствует ω, передвигаем и видим, что d не соответствует листу дерева b, а значит мы должны вернуться к A и попробовать следующую продукцию.

Возвращаясь к A, мы должны вернуть указатель входа на вторую позицию, т. е. на ту позицию, в которой он был, когда мы впервые пришли к разложению A. При рассмотрении второй альтернативы для A мы получаем дерево 3).

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

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

Для построения предиктивного СА правильная альтернатива должна точно определяться по первому ее символу. В противном случае может получиться неоднозначность.

 


Поделиться:

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





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