Информатика и выч. техника \ Теория языков программирования и методы трансляции

Контекстно-свободные языки. Свойства и распознаватели КС-языков. Преобразование КС-грамматик. КС-грамматики в нормальной форме, страница 22

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 (1)| S*S (2)| (S) (3) | x (4). Разбирается цепочка  ^н x*(x+x)^к.

[x*(x+x)^к, ^н, l] ├─ {^н <× x Þ сдвиг} [*(x+x)^к, ^нx, l] ├─ {x ×>* Þ свёртка} [*(x+x)^к, ^нS, 4l] ├─ {^н <× * Þ сдвиг} [(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

)

^к
 

<×

×>

<×

<×

×>

<×

×>

×>

  

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

^н

*

(

2

+

7

)

^к
 

<×

<×

<×

×>

<×

×>

×>

  

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

^н

*

(

+

7

)

^к
 

<×

<×

<×

<×

×>

×>

  

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

^н

*

(

+

)

^к
 

<×

<×

<×

×>

×>

  

^н

*

(

)

^к
 

<×

<×

=̇

×>

  

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

^н

*

^к
 

<×

×>

  

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

^н

^к

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

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

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

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

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.  Какова трудоёмкость распознавателей на базе грамматик предшествования?

Скачать файл