Разделы На главную История денег и экономики История экономических знаний Формы безналичных денег Международные финансы Экономические концепции Экономические теории Экономика в реальной жизни Экономический анализ и интеграция Макроэкономика Экономика и социальное общество Социальная экономика Социология Кризисная экономика Инфляция в экономике Экономика зарубежных стран Иностранные деньги Государственное регулирование Бюджетная система Политическая экономия Политология Законы денег Налогообложение Аудит Банкротство Теория рынка Конкуренция Международная торговля Товарная биржа Нефть и газ на бирже Логистика Банки - услуги и операции Банки в России Банковский кредит Недвижимость Ипотека в банке Инвестирование Стратегии инвестирования Инвестиционные фонды Ценные бумаги Акции Вексель Облигации Опционы Фьючерсы Биржевая торговля Биржа Forex Фондовый рынок Фондовый рынок России Волны Эллиотта Теория фракталов Торговая теория Ганна Фибоначчи на бирже Графический анализ на бирже Паттерны Биржевой анализ "Крестики-нолики" Японские свечи Технический анализ Математика на бирже Фундаментальный анализ Биржевая торговля Стратегии торговли Механические торговые системы Программирование МТС Управление торговым капиталом Управление портфелем Управление риском Страхование Профессия трейдер Практический трейдинг Технологии инфосистем Информационный рынок Безопасность информации Криптология и криптография Реклама PR - Public Relations Маркетинг Финансовая система Начало бизнеса Предпринимательство Малый бизнес Микроэкономика Торговля Ценообразование Работа в Интернете Сайты, софт, дизайн Управление качеством Управление предприятием Производство продукции Стратегический менеджмент Учебники по менеджменту Системы и организации Теория систем Планирование Статистика финансов Управление персоналом Трудовые отношения Бухгалтерия «1С:Бухгалтерия» Управленческий учет Делопроизводство и офис Автоматизация делопроизводства Рынок труда Карьера Менеджер Лидерство и бизнес карьера Лидерство и карьера Общение и переговоры Общение в бизнесе Бизнес переговоры Инновации в моделировании Экономическое моделирование Нейронные сети Нейролингвистика Логика нейросетей Программирование Пакет Excel Технологии программирования Языки программирования Практическая психология Психологические тренинги Психология в медицине Возрастная психология Ваши скрытые резервы Здоровье и долголетие Работа с эмоциями Пикап Управление временем Гипнотерапия Подсознание Трансовые техники Магия Здоровье советы Спорт для здоровья Йога Религии Эзотерика Мистицизм

Построение восходящих преобразователей

Пред.СтраницаСлед.СтраницаРаздел Содержание

  4.3.7  Построение восходящих преобразователей.

Построение восходящих преобразователей,  так же как в  рассмотренном выше случае, выполняется на основе распознавателя путем модификации команд за счет выполнения операции передачи  выходных символов.  Одно из отличий построения восходящих преобразователей заключается в том, что для их построения должна быть использована транслирующая грамматика в постфиксной форме.
 

     Это определение  говорит  о  том,  что  правила  постфиксной транслирующей грамматики должны иметь вид:

     <A> ®

a{ z },

где  a О( VT  И  VА) *  и z О VTвых

.
     Любая транслирующая грамматика может  быть  преобразована  в постфиксную  форму путем разбиения правил грамматики и добавления новых нетерминальных символов.  Например, для преобразования правила

     <A>  ® a{ z }<B>{ w },

введем дополнительный нетерминал   и разобьем исходное правило на две части. В результате получаем правило в постфиксной форме:



     <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 шаге.

Пред.Страница  След.Страница Раздел  Содержание






---