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