Контроль знаний. Поиск основы в грамматиках простого предшествования

Пример

Поиск основы в грамматиках простого предшествования

Лабораторная работа №7

Краткие сведения из теории

При использовании метода «Простого предшествования» в текущей сентенциальной форме осуществляется поиск основы, которая в соответствии с правилами этой грамматики приводится к нетерминальному символу, стоящему в левой части. Будем искать основу сентенциальной формы, двигаясь слева направо и рассматривать одновременно два соседних символа. Пусть имеется цепочка … RS …. _­­­­­­Здесь возможны ситуации:

1) оба символа принадлежат основе (правой части правила)(U: = …RS…)

R≐S (одновременно)

U

… R S …

2) R принадлежит основе, а S – нет (U:=…WS…; W=>+…R)

R⋗S (R раньше S) U

W

… R S

3) S принадлежит основе, а R – нет (U: = …RW…; W=>+S…)

R⋖S (R позже S) U

W

R S …

Имеется грамматика G(Z).

Z: = bMb;

M: = (L|a;

L: = Ma).

Z

b M b

(L

M a)

a

Если между какой-либо парой символов определено более чем одно отношение, использование матрицы невозможно. Если отношение единственно, то можно утверждать, что основой сентенциальной формы S₁…S_n является подцепочка S_i…S_j, для которой выполнено условие:

…S_i-1⋖ S_i ≐ S_i+1 ≐ … ≐ S_j-1 ≐ S_j ⋗ S_j+1…

Для принятия решения о том, действительно ли рассматриваемая часть сентенциальной формы является основой, используют по одному символу слева и справа от неё. Если S­₁ – начальный символ основы и вместе с тем первый символ рассматриваемого предложения (сентенциальной формы), то символа S₀ не существует. Для фиксации этого факта, заключают предложение между некоторыми символами, не являющимися символами грамматики: S_j ⋗ # или # ⋖ S_j.

Алгоритм

Если грамматика является грамматикой простого предшествования, то

для поиска основы каждой ее сентенции надо просматривать элементы сентенции слева направо и найти самую левую пару символов xj и xj +1, такую что xj. >xj +1.

Окончанием основы сентенции будет xj.

Далее просматривать элементы сентенции справа налево, начиная с символа xj до тех пор, пока не будет найдена самая правая пара символов xi -1 и xi, такая что xi -1 <. xi.

Заголовком основы будет символ xi. Таким образом, будет найдена основа сентенции, имеющая вид xi xi +1 …xj -1 xj.

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

На основе отношений предшествования строят матрицу предшествования грамматики. Строки и столбцы матрицы предшествования помечаются символами грамматики. Пустые клетки матрицы указывают на то, что данные символы не связаны отношением предшествования.

Вопросы:

К теме 3.1.

1. Дайте определения следующим понятиям: язык, алфавит, грамматика, терминальный символ, нетерминальный символ, начальный символ, цепочка.

2. Для чего нужен начальный символ?

3. Что такое формальный и неформальный языки? Для чего нужно формализовать язык?

4. Что называют сентенциальной формой?

5. Что такое фраза и простая фраза?

6. Что называется произведением отношений и транзитивным замыканием?

7. Какие требования предъявляются к грамматикам?

8. Что такое синтаксическое дерево? Приведите пример.

9. Что означает неоднозначность грамматики? Как она проявляется?

10. Какие алгоритмы разбора синтаксических деревьев вы знаете? В чем они заключаются?

11. Какие 4 основных класса языков выделил Хомский?

К теме 3.2.

1. Что такое сканер и синтаксический анализатор?

2. Что включают в себя символы исходного языка?

3. Что такое диаграмма состояний и как она строится?

4. В чем заключается алгоритм распознавания на основе диаграммы состояний?

5. Что значит детерминированный конечный автомат?

6. Что значит недетерминированный конечный автомат?

К темам 3.3 - 3.5.

1. Что такое основа и для чего она нужна?

2. Какие виды простых предшествований вам известны?

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

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

5. Что такое первичные фразы и для чего их используют?

6. Какие существуют способы представления грамматики в оперативной памяти?

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

8. Определите основную суть работы по алгоритму 1:1 ограниченного контекстного преобразователя.

9. Какие элементы входят в таблицу, используемую при разборе цепочек по алгоритму 1:1 ограниченного контекстного преобразователя.

10. Что используется при составлении таблицы для 1:1 ограниченного контекстного преобразователя.

11. Какая цепочка считается правильной?

12. Укажите основное отличие алгоритма 1:1 ограниченного контекстного преобразователя от m:n контекстного преобразователя.

13. Что такое стратификация?

14. Что называется основой сентенциальной формы в грамматике предшествования более высокого порядка.

15. Что такое грамматика n:m предшествования?

16. Опишите алгоритм разбора по грамматике n:m предшествования.

17. Дайте определение левой свертки.

18. В чем заключается работа восходящего распознавателя?

19. Какой автомат называется детерминированным (недетерминированным)?

20. При каких условиях конфигурация автомата называется зацикливающейся?

21.LL(k)-грамматики. Предсказывающие алгоритмы разбора.