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


4.3.3.  Перевод определяемый преобразователем.
 
Определение.  
                      Цепочку d назовем выходом для цепочки c, если существует последовательность  
                      конфигураций, первой из которых является начальная конфигурация с заданной   
                      входной цепочкой c, а последней – заключительная конфигурация с выходной  
                      цепочкой d                                   (s0, c, h0I, $) |--* (s', $', $, d). Определение.  
                          Переводом, определяемым преобразователем с магазинной памятью Мп,  
                          назовем множество пар, состоящих из входных и соответствующих им  
                          выходных цепочек.     D(Mп) = {(x, y) | (s0, c, h0, $) |--* (s', $', $, y) & s' О F}
   Используя последнее определение, можно определить возможность построения преобразователя, реализующего заданный перевод в виде следующего утверждения.
 
Утверждение.   
                        Для каждой простой СУ-схемы перевода Т = {Va, Vтвх, Vтвых, Q, I} можно  
                        построить такой Мп магазинный преобразователь, что D(Т) = D(Мп). 
    Приведенное утверждение говорит о возможности построения преобразователя, но не гарантирует получение детерминированного преобразователя, который может быть получен при выполнении следующих условий:  
 
Утверждение.  
                            Для каждой простой СУ - схемы перевода Т, входная грамматика которой  
                            принадлежит классу LL(1) - грамматик, можно построить такой  
                            детерминированный магазинный  преобразователь Мп, что перевод, 
                            определяемый преобразователем, совпадает  с переводом, задаваемым 
                            СУ - схемой Т. 


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