2014-02-09
381
Способ представления грамматики в ОП
Предшествование m,n
Предшествование более высокого порядка
E
E + T
T * F
(E)
E + T
Для этого дерева: +≐T и +⋖T; (≐E и (⋖E.
Чтобы решить проблему, введём новые правила:
E: = E1;
E1: = E1+T1|T1;
T1: = T.
Учитывая эти правила, можно нарисовать дерево:
E
|
E1
E1 + T1
|
T
T * F
|
(E)
|
E1
E1 + T1
Для этого дерева имеем следующие отношения: +≐T1 и +⋖T; (≐E и (⋖E1. Этот путь решения проблемы называется стратификация.
R, S, TÎ VN∪VT.
RS>∘ T – S является хвостом основы.(2.1 предшествование).
RS =>∘ T – T принадлежит основе. (2.1 предшествование).
R∘< ST – S является головой основы. (1.2 предшествование).
R∘<= ST – R принадлежит основе. (1.2 предшествование).
1) RS>∘ T тогда и только тогда, когда Z=>+…[R]UTx… =>+…RSTx….
Чтобы получился этот вывод, нужно: U=>+…S или U=>+…RS.
2) RS =>∘ T тогда и только тогда, когда Z=>+…yUx => yRSTx.
Чтобы получился этот вывод, нужно: U: = RST.
3) R∘< ST тогда и только тогда, когда Z=>+…RUx =>+…RSTx….
|
|
|
Чтобы получился этот вывод, нужно: U: = ST.
4) R∘<= ST тогда и только тогда, когда Z=>+…yUx =>…yRSTx….
Чтобы получился этот вывод, нужно: U: = RST.
Если # S1 S2 … Si Sj … Sn # – сентенциальная форма, то основа этой сентенциальной формы будет цепочка Si … Sj, если для неё выполняется условие: Si-1∘< Si Si+1= >∘ Si+2 … Sj-1Sj >∘ Sj+1.
W = xy |x| = m; |y| = n.
x ∘<y, если первый символ цепочки y является головой основы.
x >∘ y, если последний символ цепочки x является хвостом основы.
x ≗ y,, если последний символ цепочки x и первый символ цепочки y принадлежат основе.
Грамматика m,n предшествования это такая грамматика, которая удовлетворяет условиям:
1. Все правые части правил единственны.
2. Для любой пары цепочек xy таких, что |x| = m; |y| = n, выполняется не более одного из трех рассмотренных выше отношений.
EE+T|T$TT*F|F$F(E)|а#, где
$ – символ, не принадлежащий грамматике, - разделитель между правилами;
# – конец массива;
| – промежуточный мета-символ.
Построение легкое, но работать с ним неудобно.
Имеет более удобную структуру двумерный массив.
Каждая вершина – это символ из правой части и содержит 4 компоненты:
1. Имя в некоторой внутренней форме.
2. Определение: 0, если терминал; в противном случае указывает на первый символ правой части первого правила. Предположение, что рассматриваемый находится в левой.
3. Альтернатива: указывает на первый символ правой части правила, который может быть использован вместо правила, где стоит рассматриваемый символ; 0 в противном случае.
4. Приемник: указывает на символ, который следует непосредственно за рассматриваемым, а если такового нет, то 0. Рассматриваются все символы для правой части.
|
|
|
| Е | ||
| Определение | Альтернатива | Приёмник |
E:=E<АОП>T|T;
T:=T<МОП>F|F;
F:=(E)|а;
АОП - аддитивный оператор: <АОП>:=+|-;
МОП - мультипликативный оператор: <МОП>:=*|/.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Этим графом пользуется машина.
В итеративной форме: E:=T{+T}.
В НФБ: E:=E+T|E-T, в итеративной форме: E:=T{+T}.
Каждый нетерминальный выглядит как Е:
1) имя в некоторой внутренней форме;
2)
| Для правой части |
3) альтернатива Т;
4) приёмник F;
5) каждому нетерминальному символу ставится в соответствие вершина графа, указывая на (первый символ), правую часть правила.
|
|
|
E:={<АОП>T}.
Для повторения АОП введём символ *- начало, **- конец цепочки.
G(z).
E:=E+T|T.
T:=T*F|F.
F:=(E)|а.
| E | |
| T | |
| F | |
| (E) | |
| E+T |
| E |
| T |
| T |
| F |
| * |
| 1) |
| E |
| 2) |
3.3.7. Предшествование более высокого порядка
Рассмотрим следующее дерево:
| E |
| T |
| F |
| (E) |
| * |
| E |
| T |
| + |
| E+T |
Для этого дерева существует следующие неоднозначности: +≐T и +⋖T; (≐E и (⋖E.
Для простого предшествования это не пригодно, поэтому для нашего случая необходимо ввести символ, чтобы Т не совпадали, то есть введем стратификацию.
Для решения проблемы введём новые правила:
1. E: = E1;
2. E1: = E1+T1|T1;
3. T1: = T.
Теперь, учитывая эти новые правила, можно нарисовать следующее дерево:
| E1 |
| F |
| * |
| Т |
| T |
| + |
| T1 |
| E |
| (E) |
| E1 |
| E1+T |
В итоге для этого дерева имеем следующие отношения:
+≐T1 и +⋖T;
(≐E и (⋖E1.
Для первого дерева без замены Т и ввода новых правил получим
E+T*F;
+⋖T*;
(⋖E+.
Для того чтобы отличать предшествование 2.1 от операторного, внесём символ «∘» за знак <. Пусть у нас есть три символа R, S, T, которые принадлежат словарю алфавита.
Этот путь решения проблемы называется стратификация.
RS>∘ T – S является хвостом основы.(2.1 предшествование).
RS =>∘ T – T принадлежит основе. (2.1 предшествование).
R∘<ST – S является головой основы. (1.2 предшествование).
R∘<= ST – R принадлежит основе. (1.2 предшествование).
R, S, TÎ VN∪VT.
Выводы к определениям:
1) RS>∘T тогда и только тогда, когда имеется вывод Z=>+…[R]UTx…=> =>+…RSTx…
Для этого необходимы следующие выводы: U=>+…S или U=>+…RS.
2) RS =>∘T тогда и только тогда, когда Z=>+…[R]Ux =>...RSTx.
Чтобы получился этот вывод, нужно: U: = ST.
3) R∘< ST тогда и только тогда, когда Z=>+…RUТx =>+…RSTx….
Чтобы получился этот вывод, нужно: U: = S.
4) R∘<= ST тогда и только тогда, когда Z=>+…UТx =>…RSTx….
Чтобы получился этот вывод, нужно: U: = RS.
Если цепочка # S1 S2 … Si Sj … Sn # – сентенциальная форма, то основа этой сентенциальной формы будет цепочка Si … Sj, если для неё выполняется условие
Si-1∘< Si Si+1=>∘ Si+2 … Sj-1Sj >∘ Sj+1.
=>∘ этот символ означает, что мы ищем хвост основы.
∘<= этот символ означает, что ищем голову основы.
Si … Sj –основа.
# ∘<S # -условие, когда заканчивается поиск.
Может быть ситуация:
# Sj >∘ Sj+1 #;
# ∘<SiSj #;
# ∘<S #.
Если найден хвост, то можно просмотреть правила и сравнить правые части.
