Пред.Страница
След.Страница
Раздел
Содержание
4.3.5. Пример построения
преобразователя.
Применение правил построения
команд преобразователя рассмотрим на примере транслирующей грамматики Г,
которая описывает перевод инфиксных выражений, состоящих из идентификаторов
и знаков + и *, в постфиксные польские выражения. Эта грамматика имеет
следующую схему:
Г 4.
1 : R =
{<E> Ю +<E><E>{+},
<E> Ю x<E><E>{x},
<E> Ю a{a}}
Используя правило построения команд
преобразователя (1) для правил грамматики, начинающихся входным терминальным
символом, получаем команды преобразователя Мп1:
q(s0,
+, <E>) = (s0,
{+}<E><E>,
$),
q(s0,
*, <E>) = (s0,
{*}<E><E>,
$),
q(s0,
a, <E>) = (s0,
{a}, $)
Правила построения команд вида (2),(3),(4)
к заданной грамматике неприменимы, поэтому с помощью правил вида (5) построим
команды, обеспечивающие передачу выходных символов на выход. Эти команды
имеют вид:
q*(s0,
+, {+}) = (s0,
$, +), q*(s0,
*, {+}) = (s0,
$, +),
q*(s0,
a, {+}) = (s0,
$, +), q*(s0,
$', {+}) = (s0,
$, +),
q*(s0,
*, {*}) = (s0,
$, *), q*(s0,
+, {*}) = (s0,
$, *),
q*(s0,
*, {a})
= (s0, $,
*), q*(s0,
$', {*})
= (s0, $,
*),
q*(s0,
a, {a})
= (s0, $,
a), q*(s0,
+{a}) = (s0,
$, a),
q*(s0,
*, {a})
= (s0, $,
a), q*(s0,
$', {a}) = (s0,
$, a)
Для перехода в заключительное
состояние s1
в соответствии с правилом (6) построим команду:
q(s0,
$', h0)
= (s1, $,
$)
Чтобы посмотреть как работает
построенный преобразователь, рассмотрим построение выходной цепочки для
входа +a*aa. Последовательность конфигураций, получаемых с помощью команд
преобразователя имеет вид:
(s0, +a*aa,
h0E, $)
|-- (s0, a*aah0{+}EE,
$) |--
(s0, *aa,
h0{+}T{a},
$) |--
(s0, *aa,
h0{+}E,
a) |--
(s0, aa,
h0{+}{*}T{a},
a) |--
(s0, a,
h0{+}{*}E,
aa) |--
(s0, $,
h0{+}{*}{a},
aa) |--
(s0, $,
h0{+}{*},
aaa) |--
(s0, $,
h0{+},
aaa*) |--
(s0, $,
h0, aaa*+)
|--
(s0, $,
$, aaa*+).
Результатом работы преобразователя
является выходная цепочка aaa*+,
представляющая постфиксную запись заданной входной цепочки.
Пред.Страница
След.Страница
Раздел
Содержание