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

UptoLike

ВУЗ: 

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

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

Рубрика: 

39
Если грамматика является грамматикой простого предшествования, то
для поиска основы каждой ее сентенции надо просматривать элементы сентен-
ции слева направо и найти самую левую пару символов x
j
и x
j+1
, такую что
x
j
⋅
>x
j+1
. Окончанием основы сентенции будет x
j
. Далее просматривать элементы
сентенции справа налево, начиная с символа x
j
до тех пор, пока не будет найде-
на самая правая пара символов x
i-1
и x
i
, такая что x
i-1
<⋅ x
i
. Заголовком основы
будет символ x
i
. Таким образом, будет найдена основа сентенции, имеющая вид
x
i
x
i+1
…x
j-1
x
j
. Схема поиска основы сентенции грамматики представлена на ри-
сунке 7.1.
x
1
x
2
…
x
i
x
i+1
x
i+2
… x
j-2
x
j-1
x
j
…
x
n
<⋅ … <⋅ =
⋅
… =
⋅
⋅
> …
⋅
>
Рисунок 7.1 – Схема поиска основы сентенции грамматики
На основе отношений предшествования строят матрицу предшествования
грамматики. Строки и столбцы матрицы предшествования помечаются симво-
лами грамматики. Пустые клетки матрицы указывают на то, что данные симво-
лы не связаны отношением предшествования.
Определение 7.3. Построение матрицы предшествования основано на
двух вспомогательных множествах, определяемых следующим образом:
- L(A) = {X | ∃ A⇒*Xz}, A∈V
N
, X∈V, z∈V
*
- множество крайних левых
символов относительно нетерминального символа А;
-
R(A) = {X | ∃ A⇒*zX}, A∈V
N
, X∈V, z∈V
*
- множество крайних правых
символов относительно нетерминального символа А.
Определение 7.4. Отношения предшествования можно определить с по-
мощью введенных множеств следующим образом:
- B
i
=⋅ B
j
(∀ B
i
, B
j
∈ V), если и только если существует правило
A→xB
i
B
j
y ∈P, где A∈V
N
, x, y ∈V
*
;
- B
i
<⋅ B
j
(∀ B
i
, B
j
∈ V), если и только если существует правило
A→xB
i
Dy∈P и B
j
∈ L(D), где A, D ∈ V
N
, x, y ∈ V
*
;
- B
i
⋅
> B
j
(∀ B
i
, B
j
∈ V), если и только если существует правило A→xCB
j
y
и B
i
∈ R(C) или существует правило A→xCDy ∈ P и B
i
∈ R(C), B
j
∈L(D),
где A, C, D ∈ V
N
, x, y ∈ V
*
.
Матрицу предшествования дополняют символами ⊥
н
и ⊥
к
(начало и конец
цепочки). Для них определены следующие отношения предшествования:
- ⊥
н
<⋅ X, ∀ X ∈ V, если X ∈ L(S);
-
⊥
к
⋅> X, ∀ X ∈ V, если X ∈ R(S).
Основа сентенции 
       Если грамматика является грамматикой простого предшествования, то
для поиска основы каждой ее сентенции надо просматривать элементы сентен-
ции слева направо и найти самую левую пару символов xj и xj+1, такую что
xj⋅>xj+1. Окончанием основы сентенции будет xj. Далее просматривать элементы
сентенции справа налево, начиная с символа xj до тех пор, пока не будет найде-
на самая правая пара символов xi-1 и xi, такая что xi-1 <⋅ xi. Заголовком основы
будет символ xi. Таким образом, будет найдена основа сентенции, имеющая вид
xi xi+1…xj-1 xj. Схема поиска основы сентенции грамматики представлена на ри-
сунке 7.1.
                                 Основа сентенции

 x1        x2   …     xi        xi+1        xi+2   …   xj-2        xj-1        xj   …    xn
      <⋅        …          <⋅          =⋅          …          =⋅          ⋅>        … ⋅>

                Рисунок 7.1 – Схема поиска основы сентенции грамматики
      На основе отношений предшествования строят матрицу предшествования
грамматики. Строки и столбцы матрицы предшествования помечаются симво-
лами грамматики. Пустые клетки матрицы указывают на то, что данные симво-
лы не связаны отношением предшествования.
      Определение 7.3. Построение матрицы предшествования основано на
двух вспомогательных множествах, определяемых следующим образом:
      - L(A) = {X | ∃ A⇒*Xz}, A∈VN, X∈V, z∈V* - множество крайних левых
        символов относительно нетерминального символа А;
      - R(A) = {X | ∃ A⇒*zX}, A∈VN, X∈V, z∈V* - множество крайних правых
        символов относительно нетерминального символа А.
    Определение 7.4. Отношения предшествования можно определить с по-
мощью введенных множеств следующим образом:
      - Bi =⋅ Bj (∀ Bi, Bj ∈ V), если и только если существует правило
        A→xBiBjy ∈P, где A∈VN, x, y ∈V*;
      - Bi <⋅ Bj (∀ Bi, Bj ∈ V), если и только если существует правило
        A→xBiDy∈P и Bj ∈ L(D), где A, D ∈ VN, x, y ∈ V*;
      - Bi ⋅> Bj (∀ Bi, Bj ∈ V), если и только если существует правило A→xCBjy
        и Bi ∈ R(C) или существует правило A→xCDy ∈ P и Bi ∈ R(C), Bj∈L(D),
        где A, C, D ∈ VN, x, y ∈ V*.
     Матрицу предшествования дополняют символами ⊥н и ⊥к (начало и конец
цепочки). Для них определены следующие отношения предшествования:
      - ⊥н <⋅ X, ∀ X ∈ V, если X ∈ L(S);
      - ⊥к ⋅> X, ∀ X ∈ V, если X ∈ R(S).

                                                                                          39

Страницы