Грамматики предшествования

Ещё один распространенный класс КС-грамматик, для которых возможно построить восходящий распознаватель без возвратов, представляют грамматики предшествования. Распознаватель для них строится также на основе алгоритма «сдвиг-свёртка».

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

Таким образом, задача состоит в том, чтобы определить отношения предшествования между символами грамматики. В случае удачи грамматика может быть отнесена к одному из классов грамматик предшествования.

Существует несколько видов грамматик предшествования. Они различаются по тому, какие отношения предшествования в них определены и между какими типами символов (терминальными или нетерминальными) эти отношения могут быть установлены.

Выделяют следующие типы грамматик предшествования:

§ простого предшествования;

§ расширенного предшествования;

§ слабого предшествования;

§ операторного предшествования.

Наиболее распространены первый и последний типы грамматик.

Для примера рассмотрим грамматики операторного предшествования.

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

Пусть так же, как и в предыдущем разделе, кроме терминального алфавита V_T имеются специальные символы {^_н, ^_к} (или {├, ┤}), которые ограничивают цепочку слева и справа соответственно.

Будем использовать следующие обозначения цепочек: bÎV_NÈ{e} (т.е. нетерминал или пусто), a, g, dÎV^* (V=V_TÈV_N). Определим отношения предшествования { @̇, <×, ×> } на множестве V_T È{^_к, ^_н}:

1. a @ b (a имеет такое же старшинство, как b), если A ® aabbg;

2. a <× b (a имеет меньшее старшинство, чем b), если A ® aaBg, B Þ⁺ bb d;

Схематичное представление данного правила показано на первом рисунке.

3. a ×> b (a имеет большее старшинство, чем b), если A ® aBbg, B Þ⁺ dab;

Схематичное представление правила показано на втором рисунке.

4. ^_н <× a, если S Þ⁺ bad;

5. a ×> ^_к, если S Þ⁺ dab.

Если между любыми двумя операторами из V_T È{^_к, ^_н} возможно не более одного такого отношения, то соответствующая операторная грамматика называется грамматикой операторного предшествования.

Пример.

Дана грамматика построения АВ с операциями сложения и умножения и скобками: G({x,+,*,(,)}, {S,T,R}, P, S), где правила P: S ® S+T ₍₁₎|T ₍₂₎, T®T*R ₍₃₎|R ₍₄₎, R®(S) ₍₅₎|x ₍₆₎. Здесь вместо символа x может быть использовано любое целое число.

В соответствии с приведенными выше правилами определения отношений предшествования построим таблицу, в которую занесём отношения между всеми операторами данной грамматики:

	+	*	(	)	x	^к
^н	<×	<×	<×		<×
+	×>	<×	<×	×>	<×	×>
*	×>	×>	<×	×>	<×	×>
(	<×	<×	<×	=̇	<×
)	×>	×>		×>		×>
x	×>	×>		×>		×>

Рассмотрим работу алгоритма разбора на базе грамматик ОП.

Цепочка a считается принятой, если за конечное число шагов произошел переход от начальной конфигурации к заключительной:
(^_н a ^_к, e,e)├─*(^_к, ^_н S,m) Þ stop(+).

Алгоритм:

1) Считывающая головка устанавливается на первый символ цепочки a₁, в стек заносится ^_н, i=1.

2) Верхний символ стека (или ближний к верху стека терминальный символ) сравнивается с a_i.

3) Если отношение <× или = ̇, то выполняется сдвиг, i++, возврат на шаг 2.

4) Если отношение ×>, то выполняется свёртка. При этом если нет подходящего правила, то алгоритм заканчивается с ошибкой, иначе основа (символы, связанные отношением = ̇) удаляется из стека и сворачивается по найденному правилу. Далее возврат на шаг 2.

5) Если на шаге 2 отношение не найдено Þ завершение с ошибкой.

6) Если получена заключительная конфигурация – цепочка разобрана.

Дополнительные требования к правилам грамматики: (1) среди них не должно быть пустых правил; (2) не должно быть правил с одинаковыми правыми частями.

Вернёмся к примеру. S ® S+T | T, T®T*R | R, R® (S) | x.

Сначала устраним цепные правила. Получим: S ® S+T | T*R |(S) | x, T®T*R | (S) | x, R® (S) | x. Можно избавиться от лишних нетерминалов и оставить только один нетерминальный символ S. Правила примут вид:

S ® S+S ₍₁₎| S*S ₍₂₎| (S) ₍₃₎ | x ₍₄₎. Разбирается цепочка ^_н x*(x+x) ^_к.

[x*(x+x) ^_к, ^_н, e] ├─ { ^_н <× x Þ сдвиг} [*(x+x) ^_к, ^_н x, e] ├─ {x ×> * Þ свёртка} [*(x+x) ^_к, ^_н S, 4e] ├─ { ^_н <× * Þ сдвиг} [(x+x) ^_к, ^_н S*, 4] ├─ {* <× (Þ сдвиг} [x+x) ^_к, ^_н S*(, 4] ├─ {(<× x Þ сдвиг} [+x) ^_к, ^_н S*(x, 4] ├─ {x ×> + Þ свёртка} [+x) ^_к, ^_н S*(S, 44] ├─ {(<×+ Þ сдвиг} [x) ^_к, ^_н S*(S+, 44] ├─ {+ <× x Þ сдвиг} [) ^_к, ^_н S*(S+x, 44] ├─ {x ×>) Þ свёртка} [) ^_к, ^_н S*(S+S, 444] ├─ {+ ×>) Þ свёртка} [) ^_к, ^_н S*(S, 1444] ├─ {(= ̇,) Þ сдвиг} [ ^_к, ^_н S*(S), 1444] ├─ {) ×>^_к Þ свёртка} [ ^_к, ^_н S*S, 21444] ├─ {* ×>^_к Þ свёртка} [ ^_к, ^_н S, 231444] ├─ stop (+).

Рассмотрим другой способ разбора. При вычислении значения выражения сначала выполняются операции с большим приоритетом.

В той же цепочке ^_н x*(x+x) ^_к подставим вместо символов x конкретные числа: ^_н 3*(2+7) ^_к – и запишем под ней знаки отношений:

^н

*

(

+

)

^к

<×

×>

<×

<×

×>

<×

×>

×>

Рассмотрим процесс выполнения действий. Сначала будет выбрано из цепочки число 3 и сохранено в стеке. В результате останется:

^н

*

(

+

)

^к

<×

<×

<×

×>

<×

×>

×>

Теперь следует выбрать число 2 и сохранить его в стеке; останется:

^н

*

(

+

)

^к

<×

<×

<×

<×

×>

×>

Теперь так же выбирается число 7 и сохраняется в стеке:

^н	*	(	+	)	^к
	<×	<×	<×	×>	×>

^н	*	(	)	^к
	<×	<×	=̇	×>

Старшей операцией осталось сложение; его нужно применить к двум верхним элементам стека, результат остается в стеке, а символ операции «+» удаляем из цепочки. В итоге получится:

^н	*	^к
	<×	×>

Скобки имеют одинаковое старшинство и просто отбрасываются:

^н

^к

Производится умножение двух верхних элементов стека, результат остается там же, а знак операции удаляется:

Отношения предшествования между оставшимися символами отсутствуют, поэтому происходит остановка. Поскольку вся цепочка разобрана, результат её выполнения находится в стеке.

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

Контрольные вопросы

1. Какие существуют возможности сделать работу алгоритма нисходящего разбора с возвратами более эффективной?

2. Какие ограничения накладываются на правила грамматики для применимости метода рекурсивного спуска? Может ли в этих правилах использоваться левая или правая рекурсия? Почему?

3. Какими действиями можно привести правила грамматики к виду, необходимому для метода рекурсивного спуска?

4. В чём состоит основной недостаток метода рекурсивного спуска?

5. Какая грамматика обладает свойством LL(k)? Что означает это название? Может ли быть k=0?

6. В чём отличие вида правил грамматик класса LL(k) от грамматик, допускающих разбор по методу рекурсивного спуска?

7. Какой из видов рекурсии и почему запрещён в правилах LL-грамматик?

8. Какие дополнительные множества строятся для грамматик класса LL(k) и каково их назначение?

9. Как можно формально проверить, относится ли некоторая грамматика к классу LL(1)?

10. Для чего строится таблица в алгоритме нисходящего разбора для LL(1)-грамматики? Что заносится в эту таблицу? Может ли разбор выполняться без использования таблицы?

11. Что позволяет избежать возвратов в алгоритме восходящего разбора?

12. Какая грамматика обладает свойством LR(k)? Что означает это название? Может ли быть k=0?

13. Для чего нужна управляющая таблица в алгоритме разбора для LR-грамматик? Что заносится в эту таблицу? Может ли разбор входной цепочки выполняться без использования таблицы?

14. Для каких значений k обычно применяются на практике грамматики класса LR(k) и почему?

15. К какому классу распознавателей – восходящим или нисходящим – относятся распознаватели на базе грамматик предшествования?

16. Чем различаются грамматики предшествования?

17. Отношения между какими парами символов строятся в грамматиках операторного предшествования?

18. Какова трудоёмкость распознавателей на базе грамматик предшествования?

Дата добавления: 2015-07-12