Теория формальных языков, грамматик и автоматов. Ишакова Е.Н. - 38 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

Составители: 

Рубрика: 

38
7 Лабораторная работа № 7. Моделирование функциониро-
вания распознавателя для грамматик простого предшествования
Цель: - закрепить понятие «грамматика простого предшествования»; -
сформировать умения и навыки построения множеств L(A) и R(A), матрицы
предшествования символов грамматики и распознавателя для грамматик про-
стого предшествования методом «сдвиг-свертка».
Основы теории
Определение 7.1. Приведенная КС-грамматика G (V
N
, V
T
, P, S) называет-
ся грамматикой простого предшествования, если выполняются следующие ус-
ловия.
1) Для каждой упорядоченной пары терминальных и нетерминальных
символов выполняется не более чем одно из трех отношений предшествования:
а) B
i
=⋅ B
j
(∀ B
i
, B
j
∈ V), если и только если существует правило
A→xB
i
B
j
y ∈P, где x, y ∈V
*
;
б) B
i
<⋅ B
j
(∀ B
i
, B
j
∈ V), если и только если существует правило
A→xB
i
Dy ∈P и вывод D⇒*B
j
z, где A, D ∈ V
N
, x, y, z ∈ V
*
;
в) B
i
⋅> B
j
(∀ B
i
, B
j
∈ V), если и только если существует правило
A→xCB
j
y и вывод С⇒*zB
i
или существует правило A→xCDy ∈ P и вывод
С⇒*zB
i
и D⇒*B
j
w, где A, C, D ∈ V
N
, x, y, z, w ∈ V
*
.
2) Различные правила в грамматике имеют разные правые части.
Определение 7.2. Отношения =⋅, <⋅, ⋅> называют отношениями простого
предшествования для символов грамматики.
В основе распознавателя для грамматик простого предшествования лежит
правосторонний разбор строки языка. Исходной сентенциальной формой явля-
ется заданная строка языка, а целевой – начальный символ грамматики. На ка-
ждом шаге разбора в исходной цепочке символов пытаются выделить подце-
почку, совпадающую с правой частью некоторого правила вывода грамматики,
и заменить ее нетерминалом, стоящим в левой части этого правила. Данная
операция называется сверткой к нетерминалу, а заменяемая подстрока – осно-
вой сентенции. Описанный процесс разбора соответствует построению дерева
вывода цепочки снизу вверх (от листьев к корню).
Метод предшествования основан на том факте, что отношения между
двумя соседними символами распознаваемой строки соответствуют трем сле-
дующим вариантам:
- B
i
=
⋅
B
i+1
, если символы B
i
и B
i+1
принадлежат основе;
-
B
i
<
⋅
B
i+1
, если B
i+1
– крайний левый символ некоторой основы;
-
B
i
⋅> B
i+1
, если B
i
– крайний правый символ некоторой основы.
Алгоритм 7.1. Поиск основы сентенции грамматики 
    7 Лабораторная работа № 7. Моделирование функциониро-
вания распознавателя для грамматик простого предшествования

      Цель: - закрепить понятие «грамматика простого предшествования»; -
сформировать умения и навыки построения множеств L(A) и R(A), матрицы
предшествования символов грамматики и распознавателя для грамматик про-
стого предшествования методом «сдвиг-свертка».
                               Основы теории
      Определение 7.1. Приведенная КС-грамматика G (VN, VT, P, S) называет-
ся грамматикой простого предшествования, если выполняются следующие ус-
ловия.
      1) Для каждой упорядоченной пары терминальных и нетерминальных
символов выполняется не более чем одно из трех отношений предшествования:
            а) Bi =⋅ Bj (∀ Bi, Bj ∈ V), если и только если существует правило
      A→xBiBjy ∈P, где x, y ∈V*;
            б) Bi <⋅ Bj (∀ Bi, Bj ∈ V), если и только если существует правило
      A→xBiDy ∈P и вывод D⇒*Bjz, где A, D ∈ VN, x, y, z ∈ V*;
            в) Bi ⋅> Bj (∀ Bi, Bj ∈ V), если и только если существует правило
      A→xCBjy и вывод С⇒*zBi или существует правило A→xCDy ∈ P и вывод
      С⇒*zBi и D⇒*Bjw, где A, C, D ∈ VN, x, y, z, w ∈ V*.
      2) Различные правила в грамматике имеют разные правые части.
      Определение 7.2. Отношения =⋅, <⋅, ⋅> называют отношениями простого
предшествования для символов грамматики.
      В основе распознавателя для грамматик простого предшествования лежит
правосторонний разбор строки языка. Исходной сентенциальной формой явля-
ется заданная строка языка, а целевой – начальный символ грамматики. На ка-
ждом шаге разбора в исходной цепочке символов пытаются выделить подце-
почку, совпадающую с правой частью некоторого правила вывода грамматики,
и заменить ее нетерминалом, стоящим в левой части этого правила. Данная
операция называется сверткой к нетерминалу, а заменяемая подстрока – осно-
вой сентенции. Описанный процесс разбора соответствует построению дерева
вывода цепочки снизу вверх (от листьев к корню).
      Метод предшествования основан на том факте, что отношения между
двумя соседними символами распознаваемой строки соответствуют трем сле-
дующим вариантам:
     - Bi =⋅ Bi+1, если символы Bi и Bi+1 принадлежат основе;
     - Bi <⋅ Bi+1, если Bi+1 – крайний левый символ некоторой основы;
     - Bi ⋅> Bi+1, если Bi – крайний правый символ некоторой основы.
               Алгоритм 7.1. Поиск основы сентенции грамматики



38

Страницы