Студопедия

КАТЕГОРИИ:

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

Синтаксический анализ для LR(1)-грамматики

⇐ ПредыдущаяСтр 2 из 2

Алгоритм синтаксического анализа на основе LR(k)-грамматики относится к классу алгоритмов восходящего разбора.

Строкам управляющей таблицы М (LR-таблицы разбора) /2/ ставятся в соответствие состояния, в которых может находиться анализатор, столбцам - элементы множества VUTU$.

Каждая запись рабочего стека представляет собой пару: (символ, номер состояния). Перед началом работы алгоритма в рабочий стек заносится пара ($,1).

Возможные значения элементов таблицы и их интерпретация алгоритмом разбора приведены в таблице 5.1.

 

Таблица 5.1

N п/п Значение элемента таблицы Интерпретация алгоритмом разбора
1 Номер i порождающего правила грамматики Удаление из рабочего стека n записей (n - количество символов в правой части правила номер i); имитация считывания в качестве следующего входно­го символа нетерминала левой части правила номер i.
2 ("Сдвиг", номер j состояния) Запись текущего входного символа в выходной стек и в паре с номером j - в рабочий стек; если этот символ нетерминал, установка указателей на него в ближайших к нему n записях выходного стека с пустыми указателями.
3 “допуск” конец работы
4 "ошибка" Вывод сообщения об ошибке; Конец работы.

 

Для построения управляющей таблицы М может быть выполнена разметка порождающих правил грамматики номерами состояний анализатора. Номера состояний устанавливаются в правой части каждого правила: перед первым символом, между любыми двумя символами и после последнего символа. При этом номер состояния, непосредственно справа от которого находится нетерминал, следует распространить на позиции перед первыми символами всех правых частей правил для данного нетерминала (и т. д. рекурсивно). А если непосредственно слева от одного и того же символа в каких-либо правилах установлены одинаковые множества меток, то и непосредственно справа от этого символа в этих правилах следует поставить одну и ту же метку. После разметки грамматики выполняется построение таблицы М по следующему алгоритму /2/.

1. Если символ А в правой части правила имеет непосредственно слева от себя метку k, а непосредственно справа от себя - метку j, то

M(k,A) = ("сдвиг",j).

2. Если метка j размещается за последним символом правой части правила номер i (если правая часть правила - "lambda", j совпадает с

меткой состояния, непосредственно справа от которого находится нетерминал левой части правила i), то определяется множество Q символов, которые в какой-либо сентенциальной форме могут следовать за нетерминалом левой части правила номер i, и M(j,q)=i для всех q, принадле­жащих Q.

3. M(1,<S>)="допуск".

4. Оставшиеся незаполненными элементы таблицы M получают значение "ошибка".

 

 

Пример

Разметим грамматику G(V,T,P,S):

1) <S>::=<E>

1 2

2) <E>::=<T> + <E>

1,4 3 4 5

3) <E>::=<T>

1,43

4) <T>::=  <F> * <T>

1,4,7 6 7 8

5) <T>::=  <F>

1,4,7 6

6) <F>::=   i

1,4,7 9

 

Управляющая таблица М будет представлена таблицей 5.2.

 

Таблица 5.2

 

  <S> <E> <F> <T> i + * $
1 2 3 4 5 6 7 8 9 “допуск”     сдв,5 сдв,2     сдв,6     сдв,6 сдв,6     сдв,3     сдв,8   сдв,9     сдв,9         сдв,4     5   4 6   сдв,7     6   1 3   2 5   4 6

 

Незаполненные элементы таблицы имеют значение "ошибка".

 

Проанализируем входную цепочку i*i c помощью алгоритма

LR(1) - анализатора. Последовательность изменения состояний стека представлена таблицей 5.3.

 

Таблица 5.3

Рабочий стек Вх.символ M(A,a)
$,1 i M(1,i)=сдв,9
i,9 $,1 * M(9,*)=6
$,1 <F> M(1,<F>)=сдв,6
<F>,6 $,1 * M(6,*)=сдв,7
*,7 <F>,6 $,1 i M(7,i)=сдв,9
i,9 *,7 <F>,6 $,1 $ M(9,$)=6
*,7 <F>,6 $,1 <F> M(7,<F>)=сдв,6
<F>,6 *,7 <F>,6 $,1 $ M(6,$)=5
*,7 <F>,6 $,1 <T> M(7,<T>)=сдв,8
<T>,8 *,7 <F>,6 $,1 $ M(8,$)=4
$,1 <T> M(1,<T>)=сдв,3
<T>,3 $,1 $ M(3,$)=3
$,1 <E> M(1,<E>)=сдв,2
<E>,2 $,1 $ M(2,$)=1
$,1 <S> M(1,<S>)=допуск

 

 

В результате анализа получено синтаксическое дерево разбора (рис.5.1).

<S>
<E>
<T>
<F>
<T>
*
i
<F>
i

Рис.5.1 Синтаксическое дерево разбора

 

В выходном стеке это дерево представляется таблицей 5.4.

 

 

Таблица 5.4

 

9

<S>,0
8

<E>,9
7

<T>,8
6

<T>,7
5

<F>,6
4

i,5
3 *,7  
2

<F>,7
1

i,2

 

 




⇐ Предыдущая12






Последнее изменение этой страницы: 2018-05-31; просмотров: 184.

stydopedya.ru не претендует на авторское право материалов, которые вылажены, но предоставляет бесплатный доступ к ним. В случае нарушения авторского права или персональных данных напишите сюда...