Пред.Страница
След.Страница
Раздел
Содержание
4.3.7 Построение
восходящих преобразователей.
Построение восходящих преобразователей, так же как в рассмотренном
выше случае, выполняется на основе распознавателя путем модификации команд
за счет выполнения операции передачи выходных символов. Одно
из отличий построения восходящих преобразователей заключается в том, что
для их построения должна быть использована транслирующая грамматика в постфиксной
форме.
Определение. Транслирующая грамматика, записанная
в форме, когда все
символы действия в правых частях распо ложены правее всех
терминальных и нетерминальных символов, называется
постфиксной транслирующей грамматикой.
|
Это определение говорит о том,
что правила постфиксной транслирующей грамматики должны иметь
вид:
где a О(
VT И VА) *
и z О VTвых
.
Любая транслирующая грамматика может
быть преобразована в постфиксную форму путем разбиения
правил грамматики и добавления новых нетерминальных символов. Например,
для преобразования правила
введем дополнительный нетерминал и разобьем исходное правило
на две части. В результате получаем правило в постфиксной форме:
<D> ®
a{ z },
<A> ®
<D><B>{w}.
Воспользуемся этим приемом для преобразования
к постфиксной форме транслирующей грамматики, которая
задает преобразование арифметических выражений без скобок, описываемых
грамматикой 4. 2, в постфиксную форму.
Г 4. 2 :
<I> ® a{a}<R>,
<R> ® +a{a}{+}<R>,
<R>®-a{a}{-}<R>,
<R>® $.
Добавляем три новых нетерминала <P>,
<Q>, <S> и, разбивая правила грамматики, получаем
грамматику в постфиксной форме.
Г 4. 3 : <I> ®
<S><R>,
<S> ® a{a},
<R> ® <P><R>,
<P> ® +a{a}{+},
<R> ® <Q><R>,
<Q> ® -a{a}{-},
<R> ® $.
Напомним, что при построении восходящих распознавателей обработка
каждого правила A
<A> ® ax
с номером k с символом x, занимающим самую правую позицию в правой части
правила, связывалась операция Свертка(k).
В постфиксной транслирующей грамматике самую правую позицию могут
занимать символы действия, поэтому при построении восходящего преобразователя
эти символы можно объединить с операцией свертки в одну операцию,
которую назовем
Свертка - Действие(k) (СД(k)). Учитывая,
что все символы действия постфиксной транслирующей грамматики могут быть
объединены с операциями свертки, приходим к заключению, что
процедура построения восходящего распознавателя может быть применена для
построения восходящего преобразователя при условии, что вместо операции
Cвертка (k) будет использоваться операция
Свертка - Действие(k) для
правил построения постфиксной транслирующей грамматики, содержащая
символы действия.
В качестве иллюстрации последнего утверждения
рассмотрим построение преобразователя для грамматики Г
4. 3. Выполняя последовательно шаги процедуры построения
SLR(1) преобразова-
теля для грамматики с аннулирующими правилами и заменяя операции
Свертка(k) для правил 2, 4 и 6 операциями
Свертка - Действие(k), получаем
таблицы переходов и действий искомого преобразователя в следующем виде.
Таблица 4.1
|
I |
S |
R |
P |
Q |
+ |
- |
a |
I0 |
|
|
|
|
|
|
|
|
S |
|
|
R1 |
P |
Q |
+ |
- |
|
R1 |
|
|
|
|
|
|
|
|
a2 |
|
|
|
|
|
|
|
|
P |
|
|
R3 |
P |
Q |
+ |
- |
|
R3 |
|
|
|
|
|
|
|
|
+ |
|
|
|
|
|
|
|
a4 |
a4 |
|
|
|
|
|
|
|
|
Q |
|
|
R5 |
P |
Q |
+ |
- |
|
R5 |
|
|
|
|
|
|
|
|
- |
|
|
|
|
|
|
|
a6 |
a6 |
|
|
|
|
|
|
|
|
h0 |
I0 |
S |
|
|
|
|
|
a2 |
Таблица 4.2
|
+ |
- |
a |
|-- |
I0 |
|
|
|
D |
S |
П |
П |
|
c7 |
R1 |
|
|
|
c1 |
c1 |
CD2 |
CD2 |
|
CD2 |
P |
П |
П |
|
c7 |
R3 |
|
|
|
c3 |
+ |
|
|
П |
|
a4 |
CD4 |
CD4 |
|
CD4 |
Q |
П |
П |
|
c7 |
R5 |
|
|
|
c5 |
- |
|
|
П |
|
a6 |
CD6 |
|
CD6 |
CD6 |
a4 |
|
|
П |
|
В качестве демонстрации работы преобразователя
построим последовательность конфигураций для входной цепочки а + а - а|--,
дополнив эту последовательность указателем выполняемого действия.
Вход
Магазин Действие
Выход
1. а
+ а - а|-- h0
П -
2. + а - а|-- h0 a2
СД2
a
3. + а - а|-- h0 S
П
a
4. а - а|--
h0 S +
П
a
5. - а|--
h0 S + a4
СД4
aa +
6. - а|--
h0 S P
П
aa +
7. а|--
h0 S P-
П
aa +
8. |--
h0 S P - a6 СД6
aa + a -
9. |--
h0 S P Q С7
aa + a -
10. |--
h0 S P Q R5 С5
aa + a -
11. |--
h0 S PR3
С3 aa
+ a -
12. |--
h0 S R1
С1
aa + a -
13. |--
h0 I0
Д
aa + a -
Приведенная последовательность конфигураций
показывает, что выходная цепочка формируется при выполнении операций
СД2, СД4 и СД6 соответственно на 2, 5 и 8 шаге.
Пред.Страница
След.Страница
Раздел
Содержание