Пред.СтраницаСлед.Страница
Раздел
Содержание
4.3.5. Пример построения
преобразователя.
Применение правил построения
команд преобразователя рассмотрим на примере транслирующей грамматики Г,
которая описывает перевод инфиксных выражений, состоящих из идентификаторов
и знаков + и *, в постфиксные польские выражения. Эта грамматика имеет
следующую схему:
Г 4.
2 : 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*+, представляющая постфиксную
запись заданной входной цепочки.
Пред.СтраницаСлед.Страница
Раздел
Содержание