Программирование на основе автоматов

Программирование на основе автоматов — это парадигма программирования , в которой программа или ее часть мыслится как модель конечного автомата (автомата) или любого другого (часто более сложного) формального автомата (см. Теорию автоматов ). Иногда вводится потенциально бесконечное множество возможных состояний, и такое множество может иметь сложную структуру, а не просто перечисление.

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

Следующие свойства являются ключевыми индикаторами автоматного программирования:

Временной период выполнения программы четко разделен до шагов автомата . Каждый шаг фактически представляет собой выполнение раздела кода (одинакового для всех шагов), который имеет одну точку входа. Этот раздел можно разделить на подразделы, которые будут выполняться в зависимости от разных состояний, хотя это не обязательно.
Любая связь между шагами автомата возможна только через явно отмеченный набор переменных, называемый состоянием автомата . Между любыми двумя шагами программа не может иметь неявных компонентов своего состояния, таких как значения локальных переменных, адреса возврата, текущий указатель инструкции и т. д. То есть состояние всей программы, взятое в любые два момента входа в шаг автомата, может отличаться только значениями переменных, рассматриваемых как состояние автомата.

Все выполнение автоматного кода представляет собой цикл шагов автомата.

Другая причина использования понятия автоматного программирования состоит в том, что стиль мышления программиста о программе в этом методе очень похож на стиль мышления, используемый для решения математических задач с использованием машин Тьюринга , алгоритмов Маркова и т. д.

Пример [ править ]

Задача [ править ]

чтения текста из стандартного ввода Рассмотрим задачу построчного и записи первого слова каждой строки в стандартный вывод . Сначала мы пропускаем все ведущие пробельные символы, если они есть. Затем печатаем все символы первого слова. Наконец, мы пропускаем все конечные символы, пока новой строки не встретим символ . Всякий раз, когда последовательность символов новой строки встречается не в начале потока, мы печатаем только первый и пропускаем остальные; в противном случае мы пропускаем все. Затем мы перезапускаем процесс со следующей строки. При обнаружении условия конца файла (независимо от этапа) мы останавливаемся.

Традиционная программа [ править ]

Традиционная программа на языке C , выполняющая указанную выше задачу, может выглядеть так:

#include   <ctype.h> 
 #include   <stdio.h> 


 int   main  (  void  )   { 
   int   c  ; 

    делать   { 
     делать   { 
       c   =   getchar  (); 
      }   while   (  isspace  (  c  )); 

      while   (  !  isspace  (  c  )   &&   c   !=   EOF  )   { 
       putchar  (  c  ); 
        с   =   получитьсимвол  (); 
      } 
    
     while   (  c   !=   '\n'   &&   c   !=   EOF  )   { 
       c   =   getchar  (); 
      } 
    
     if   (  c   ==   '\n'  )   { 
       putchar  (  c  ); 
      } 
   }   while   (  c   !=   EOF  ); 

    вернуть   0  ; 
  }

Например, компиляция и запуск вышеуказанной программы на этом входе:

$  clang   program.c   &&   (  printf   "\t\v\f\r \n\n\t\v\f\r foo bar baz\n\n\t\v\f\r qux quux corge"   |   . /а.аут  )

дает:

фу 
 кукс

Программа на основе автоматов [ править ]

Процедурный [ править ]

Ту же задачу можно решить, думая в терминах конечных автоматов . Анализ строки состоит из трех этапов: пропуск начальных пробелов, печать символов первого слова и пропуск конечных символов. Назовем эти состояния автомата BEFORE, INSIDE и AFTER. Автоматная версия программы может выглядеть так:

#include   <ctype.h> 
 #include   <stdio.h> 

 enum   State   {  BEFORE  ,   INSIDE  ,   AFTER  }; 


  int   main  (  void  )   { 
   int   c  ; 
   перечисления    состояние   s   =   BEFORE  ; 

    while   ((  c   =   getchar  ())   !=   EOF  )   { 
     switch   (  s  )   { 
       case   BEFORE  : 
         if   (  !  isspace  (  c  ))   { 
           putchar  (  c  ); 
            с   =   ВНУТРИ  ; 
          } 
        
         перерыв  ; 
        случай   ВНУТРИ  : 
         if   (  c   ==   '\n'  )   { 
           putchar  (  c  ); 
            с   =   ДО  ; 
          }   Еще,   если   (  isspace  (  c  ))   { 
           s   =   ПОСЛЕ  ; 
          }   Еще   { 
           putchar  (  с  ); 
          } 
          
         перерыв  ; 
        случай   ПОСЛЕ  : 
         if   (  c   ==   '\n'  )   { 
           putchar  (  c  ); 
            с   =   ДО  ; 
          } 
        
         перерыв  ; 
      } 
   } 

   вернуть   0  ; 
  }

Хотя программа теперь выглядит длиннее, у нее есть по крайней мере одно существенное преимущество: существует только одно чтение (то есть вызов метода getcharфункция) инструкция. Кроме того, здесь всего одна петля вместо четырех, как в традиционной версии. Тело whileцикл — это шаг автомата , а сам цикл — это цикл шага автомата. Программа реализует работу конечного автомата, показанного на диаграмме состояний.

Важнейшим свойством программы является то, что участок кода шагов автомата четко локализован. С явной функцией step на этапе автоматизации программа лучше демонстрирует это свойство:

#include   <ctype.h> 
 #include   <stdio.h> 

 enum   State   {  BEFORE  ,   INSIDE  ,   AFTER  }; 


  void   шаг  (  enum   State  *   const   s  ,   int   const   c  )   { 
   переключатель   (  *  s  )   { 
     case   BEFORE  : 
       if   (  !  isspace  (  c  ))   { 
         putchar  (  c  ); 
          *  s   =   ВНУТРИ  ; 
        } 
      
       перерыв  ; 
      случай   ВНУТРИ  : 
       if   (  c   ==   '\n'  )   { 
         putchar  (  c  ); 
          *  с   =   ДО  ; 
        }   Еще   если   (  isspace  (  c  ))   { 
         *  s   =   ПОСЛЕ  ; 
        }   Еще   { 
         putchar  (  с  ); 
        } 
        
       перерыв  ; 
      случай   ПОСЛЕ  : 
       if   (  c   ==   '\n'  )   { 
         putchar  (  c  ); 
          *  с   =   ДО  ; 
        } 
      
       перерыв  ; 
    } 
 } 


 Int   Main  (  void  )   { 
   int   c  ; 
   перечисления    состояние   s   =   BEFORE  ; 

    while   ((  c   =   getchar  ())   !=   EOF  )   { 
     шаг  (  &  s  ,   c  ); 
    } 

   вернуть   0  ; 
  }

Теперь программа наглядно демонстрирует основные свойства автоматного кода:

периоды времени выполнения шагов автомата не могут перекрываться;
единственная информация, передаваемая с предыдущего шага на следующий, — это явно заданное состояние автомата .

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

Таблица перехода состояний
Вход Текущее состояние	новая линия	пробелы	другой
до	до	до	внутри/распечатать
внутри	до/распечатать	после	внутри/распечатать
после	до/распечатать	после	после

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

Вообще говоря, программа, основанная на автоматах, естественным образом может использовать этот подход. С явным двумерным массивом transitions для таблицы перехода состояний программа использует такой подход:

#include   <ctype.h> 
 #include   <stdio.h> 

 enum   State   {  BEFORE  ,   INSIDE  ,   AFTER  }; 


  void   nop  (  int   const   c  )   {} 


 void   print  (  int   const   c  )   { 
   putchar  (  c  ); 
  } 


 struct   Branch   { 
   enum   State   const   next_state  ; 
    пустота   (  *  действие  ) (  INT  ); 
  }; 


  struct   Branch   const   переходы  [  3  ][  3  ]   =   { 
   // пробелы новой строки другие входы/состояния 
   {{  BEFORE  ,     &  nop  },   {  BEFORE  ,   &  nop  },   {  INSIDE  ,   &  print  }},    // before 
   {{  BEFORE  ,   &  print  },   {  AFTER  ,    &  nop  },   {  INSIDE  ,   &  print  }},    // внутри 
   {{  BEFORE  ,   &  print  },   {  AFTER  ,    &  nop  },   {  AFTER  ,      &  nop  }}     // after 
 }; 


  void   шаг  (  enum   State  *   const   s  ,   int   const   c  )   { 
   int   const   row   =   (  *  s   ==   BEFORE  )   ?    0   :   (  *  s   ==   ВНУТРИ  )   ?    1   :   2  ; 
    int   const   столбец   =   (  c   ==   '\n'  )   ?    0   :   isspace  (  с  )   ?    1   :   2  ; 
    struct   Branch   const  *   const   b   =   &  переходы  [  строка  ][  столбец  ]; 
    *  s   =   b  ->  next_state  ; 
    б  ->  действие  (  с  ); 
  } 


 Int   Main  (  void  )   { 
   INT   C  ; 
   перечисления    состояние   s   =   BEFORE  ; 

    while   ((  c   =   getchar  ())   !=   EOF  )   { 
     шаг  (  &  s  ,   c  ); 
    } 

   вернуть   0  ; 
  }

Объектно-ориентированный [ править ]

Если язык реализации поддерживает объектно-ориентированное программирование , простой рефакторинг программы заключается в инкапсуляции автомата в объект, скрывая таким образом детали его реализации. Программа на C++, использующая объектно-ориентированный стиль, могла бы выглядеть так:

#include   <ctype.h> 
 #include   <stdio.h> 

 enum   State   {  BEFORE  ,   INSIDE  ,   AFTER  }; 


  struct   Branch   { 
   enum   State   const   next_state  ; 
    пустота   (  *  действие  ) (  INT  ); 
  }; 


  класс   StateMachine   { 
   общественный  : 
     StateMachine  (); 
      недействительный   фидChar  (  INT  ); 

    защищено  : 
     static   void   nop  (  int  ); 
      статическая   пустота   печати  (  int  ); 

    частный  : 
     перечисление   State   _state  ; 
      статическая   структура   Branch   const   _transitions  [  3  ][  3  ]; 
  }; 


  StateMachine  ::  StateMachine  ()  :   _state  (  BEFORE  )   {} 


 void   StateMachine  ::  feedChar  (  int   const   c  )   { 
   int   const   row   =   (  _state   ==   BEFORE  )   ?    0   :   (  _state   ==   ВНУТРИ  )   ?    1   :   2  ; 
    int   const   столбец   =   (  c   ==   '\n'  )   ?    0   :   isspace  (  с  )   ?    1   :   2  ; 
    struct   Branch   const  *   const   b   =   &  _transitions  [  строка  ][  столбец  ]; 
    _state   =   b  ->  next_state  ; 
    б  ->  действие  (  с  ); 
  } 


 void   StateMachine  ::  nop  (  int   const   c  )   {} 


 void   StateMachine  ::  print  (  int   const   c  )   { 
   putchar  (  c  ); 
  } 


 struct   Branch   const   StateMachine  ::  _transitions  [  3  ][  3  ]   =   { 
   // пробелы новой строки другие входы/состояния 
   {{  BEFORE  ,     &  nop  },   {  BEFORE  ,   &  nop  },   {  INSIDE  ,   &  print  }},    // before 
   {{  BEFORE  ,   &  print  },   {  AFTER  ,    &  nop  },   {  INSIDE  ,   &  print  }},    // внутри 
   {{  BEFORE  ,   &  print  },   {  AFTER  ,    &  nop  },   {  AFTER  ,      &  nop  }}     // после 
 }; 


  int   main  ()   { 
   int   c  ; 
    Государственная машина   м  ; 

    while   ((  c   =   getchar  ())   !=   EOF  )   { 
     m  .   фидЧар  (  с  ); 
    } 

  вернуть   0  ; 
  }

Для минимизации изменений, не связанных напрямую с тематикой статьи, ввод/вывод getchar и putchar функции из стандартной библиотеки C. используются

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

#include   <ctype.h> 
 #include   <stdio.h> 

 class   StateMachine  ; 


 класса    состояние   { 
   общественное  : 
     виртуальный   недействительный   фидChar  (  StateMachine  *  ,   int  )   const   =   0  ; 
  }; 


  класс   До  :   общественное   состояние   { 
   общественное  : 
     статическое   состояние   const  *   экземпляр  (); 
      виртуальная   пустота   FeedChar  (  StateMachine  *  ,   int  )   const   переопределение  ; 

    защищено  : 
     До  ()   =   по умолчанию  ; 

    частный  : 
     статическое   состояние   const  *   _instance  ; 
  }; 


  класс   Внутри  :   общественное   состояние   { 
   общественное  : 
     статическое   состояние   const  *   экземпляр  (); 
      виртуальная   пустота   FeedChar  (  StateMachine  *  ,   int  )   const   переопределение  ; 

    защищено  : 
     Внутри  ()   =   по умолчанию  ; 

    частный  : 
     статическое   состояние   const  *   _instance  ; 
  }; 


  класс   После  :   общественное   состояние   { 
   общественное  : 
     статическое   состояние   const  *   экземпляр  (); 
      виртуальная   пустота   FeedChar  (  StateMachine  *  ,   int  )   const   переопределение  ; 

    защищено  : 
     После  ()   =   по умолчанию  ; 

    частный  : 
     статическое   состояние   const  *   _instance  ; 
  }; 


  класс   StateMachine   { 
   общественный  : 
     StateMachine  (); 
      недействительный   фидChar  (  INT  ); 

    protected  : 
     void   setState  (  State   const  *  ); 

    частный  : 
     Состояние   const  *   _state  ; 
     друга    класс   До  ; 
     друга    класс   Внутри  ; 
     друга    класс   После  ; 
  }; 


  State   const  *   Before  ::  инстанцирование  ()   { 
   if   (  !  _instance  )   { 
     _instance   =   new   Before  ; 
    } 

   Вернуть   _экземпляр  ; 
  } 


 void   Before  ::  feedChar  (  StateMachine  *   const   m  ,   int   const   c  )   const   { 
   if   (  !  isspace  (  c  ))   { 
     putchar  (  c  ); 
      м  ->  setState (  Внутри  ::  экземпляр  ()); 
    } 
 } 


 Состояние   const  *   До  ::  _instance   =   nullptr  ; 


  Состояние   const  *   Внутри  ::  экземпляр  ()   { 
   if   (  !  _instance  )   { 
     _instance   =   new   Inside  ; 
    } 

   Вернуть   _экземпляр  ; 
  } 


 void   Inside  ::  feedChar  (  StateMachine  *   const   m  ,   int   const   c  )   const   { 
   if   (  c   ==   '\n'  )   { 
     putchar  (  c  ); 
      m  ->  setState  (  Before  ::  instantiate  ()); 
    }   else   if   (  isspace  (  c  ))   { 
     m  ->  setState  (  After  ::  экземпляр  ()); 
    }   Еще   { 
     putchar  (  с  ); 
    } 
 } 


 Состояние   const  *   Внутри  ::  _instance   =   nullptr  ; 


  Состояние   const  *   After  ::  экземпляр  ()   { 
   if   (  !  _instance  )   { 
     _instance   =   new   After  ; 
    } 

   Вернуть   _экземпляр  ; 
  } 


 void   After  ::  feedChar  (  StateMachine  *   const   m  ,   int   const   c  )   const   { 
   if   (  c   ==   '\n'  )   { 
     putchar  (  c  ); 
      m  ->  setState  (  Before  ::  instantiate  ()); 
    } 
 } 


 State   const  *   After  ::  _instance   =   nullptr  ; 


  StateMachine  ::  StateMachine  ()  :   _state  (  Before  ::  instance  ()))   {} 


 void   StateMachine  ::  feedChar  (  int   const   c  )   { 
   _state  ->  feedChar  (  this  ,   c  ); 
  } 


 void   StateMachine  ::  setState  (  State   const  *   const   s  )   { 
   _state   =   s  ; 
  } 


 int   main  ()   { 
   int   c  ; 
    Государственная машина   м  ; 

    while   ((  c   =   getchar  ())   !=   EOF  )   { 
     m  .   фидЧар  (  с  ); 
    } 

   вернуть   0  ; 
  }

Автоматика и автоматы [ править ]

Программирование на основе автоматов действительно близко соответствует потребностям программирования, возникающим в области автоматизации .

Производственный цикл обычно моделируется как:

последовательность шагов шага по входным данным (от захватчиков);
набор действий, выполняемых в зависимости от текущего этапа.

Различные специализированные языки программирования позволяют выразить такую модель более или менее сложными способами.

Программа автоматизации [ править ]

Представленный выше пример может быть выражен в соответствии с этим представлением, как в следующем псевдокоде («set» активирует логическую переменную, «reset» деактивирует логическую переменную, «:» присваивает переменную, а «=» проверяет равенство) :

новая строка: '\n'
 пробел: ('\t', '\n', '\v', '\f', '\r', '')
 утверждает: (до, внутри, после)


 setState(с) {
   если раньше и (c != новая строка и c не в пробелах), то устанавливается внутри
   если внутри, то (если c в пробеле, то устанавливается после else, если c = новая строка, то устанавливается до)
   если после и c = новая строка, то установите перед
 }


 doAction(c) {
   если раньше и (c != новая строка и c не в пробелах), то write(c)
   если внутри и c не в пробелах, то напишите (c)
   если после и c = новая строка, то напишите(c)
 }


 цикл {
   установить раньше

   цикл до тех пор, пока (c: readCharacter) = EOL {
     setState (с)
     сделатьДействие(с)
   }
 }

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

События [ править ]

В области автоматизации переход от шага к шагу зависит от входных данных, поступающих от самой машины. В программе это представлено чтением символов из текста. На самом деле эти данные сообщают о положении, скорости, температуре и т. д. критических элементов машины.

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

s:стадия c:состояние
   
    с1
    |
    |-c2
    |
    с2
    |
    ----------
    |  |
    |-c31 |-c32
    |  |
   s31 s32
    |  |
    |-c41 |-c42
    |  |
    ----------
    |
    s4

Приложения [ править ]

Автоматное программирование широко используется в лексическом и синтаксическом анализе . ^[1]

Кроме того, мышление в терминах автоматов (то есть разбиение процесса выполнения на шаги автомата и передача информации от шага к шагу через явное состояние автомата ) необходимо для событийно-ориентированного программирования как единственной альтернативы использованию параллельных процессов или потоков. .

Понятия состояний и конечных автоматов часто используются в области формальной спецификации . Например, UML при разработке архитектуры программного обеспечения на основе используются диаграммы состояний для определения поведения программы. Также различные протоколы связи часто указываются с использованием явного понятия состояния (например, RFC 793 ).

Мышление в терминах автоматов (шагов и состояний) также можно использовать для описания семантики некоторых языков программирования . Например, выполнение программы, написанной на языке Рефал , описывается как последовательность шагов так называемой абстрактной машины Рефал; состояние машины — это представление (произвольное выражение Refal без переменных).

Продолжения на языке Scheme требуют мышления в терминах шагов и состояний, хотя сама Scheme никоим образом не связана с автоматами (она рекурсивна). Чтобы функция call/cc работала, реализация должна иметь возможность фиксировать полное состояние исполняемой программы, что возможно только в том случае, если в состоянии нет неявной части. Такое пойманное состояние и есть то, что называется продолжением , и его можно рассматривать как состояние (относительно сложного) автомата. Шаг автомата – это вывод очередного продолжения из предыдущего, а процесс выполнения – цикл таких шагов.

Александр Оллонгрен в своей книге ^[2] объясняет так называемый венский метод описания семантики языков программирования, полностью основанный на формальных автоматах.

Система STAT [1] является хорошим примером использования автоматного подхода; эта система, помимо других функций, включает встроенный язык STATL , который ориентирован исключительно на автоматы.

История [ править ]

Методы, основанные на автоматах, широко использовались в областях, где существуют алгоритмы, основанные на теории автоматов, таких как анализ формального языка. ^[1]

Одна из первых работ по этому вопросу принадлежит Johnson et al., 1968. ^[3]

Одно из первых упоминаний об автоматном программировании как об общей методике можно найти в статье Питера Наура , 1963 год. ^[4]Автор называет эту технику подходом машины Тьюринга , однако реальной машины Тьюринга в статье не приводится ; вместо этого описывается техника, основанная на шагах и состояниях.

Сравнение с императивным и процедурным программированием [ править ]

Понятие состояния не является исключительной собственностью автоматного программирования. ^[5]Вообще говоря, состояние (или состояние программы ) появляется во время выполнения любой компьютерной программы , как совокупность всей информации, которая может измениться в ходе выполнения. Например, состояние традиционной императивной программы состоит из

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

Их можно разделить на явную часть (например, значения, хранящиеся в переменных) и неявную часть (адреса возврата и указатель инструкции).

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

Отношения объектно-ориентированного программирования [ править ]

В теории объектно-ориентированного программирования , что объект говорят имеет внутреннее состояние и способен получать сообщения , отвечать на них, отправлять сообщения другим объектам и изменять свое внутреннее состояние во время обработки сообщений. В более практической терминологии вызов метода объекта считается тем же, что и отправка сообщения объекту .

Таким образом, с одной стороны, объекты объектно-ориентированного программирования можно рассматривать как автоматы (или модели автоматов), состояние считается один или несколько методов которых представляет собой комбинацию частных полей, а шагом . Такие методы не должны вызывать друг друга и самих себя ни прямо, ни косвенно, иначе объект нельзя будет считать реализованным автоматным способом.

С другой стороны, объект хорош для реализации модели автомата. Когда автоматный подход используется в объектно-ориентированном языке, модель автомата обычно реализуется классом, состояние представляется частными полями класса, а шаг реализуется как метод; такой метод обычно является единственным непостоянным общедоступным методом класса (помимо конструкторов и деструкторов). Другие общедоступные методы могут запрашивать состояние, но не изменять его. Все вторичные методы (например, определенные обработчики состояний) обычно скрыты в приватной части класса.

См. также [ править ]

Клеточный автомат
Недетерминированное программирование
Образец состояния
Esterel — язык, основанный на автоматах.
Umple — инструмент для добавления автоматов в Java и C++.

Ссылки [ править ]

^ Перейти обратно: ^а ^б Ахо, Альфред В.; Уллман, Джеффри Д. (1973). Теория синтаксического анализа, трансляции и компиляции . Том. 1. Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. ISBN 0-13-914564-8 .
^ Оллонгрен, Александр (1974). Определение языков программирования путем интерпретации автоматов . Лондон: Академическая пресса. ISBN 0-12-525750-3 .
^ Джонсон, WL; Портер, Дж. Х.; Экли, С.И.; Росс, DT (1968). «Автоматическая генерация эффективных лексических процессоров с использованием методов конечных состояний» . Связь АКМ . 11 (12): 805–813. дои : 10.1145/364175.364185 . S2CID 17253809 .
^ Наур, Питер (сентябрь 1963 г.). «Проект компилятора GIER ALGOL, часть II». БИТ Численная математика . 3 (3): 145–166. дои : 10.1007/BF01939983 . S2CID 189785656 .
^ «Автоматное программирование» (PDF) . Научно-технический журнал информационных технологий, механики и оптики (53). 2008.

Внешние ссылки [ править ]

СП Нобл. «Конечные автоматы на Форте» — автоматное программирование на Форте.
Харель, Дэвид (1987). «Диаграммы состояний: визуальный формализм для сложных систем» (PDF) . наук. Вычислить. Программирование . 8 (3): 231–274. дои : 10.1016/0167-6423(87)90035-9 .
Харель, Дэвид; Друсинский, Д. (1989). «Использование диаграмм состояний для описания и синтеза оборудования». Транзакции IEEE по автоматизированному проектированию интегральных схем и систем . 8 (7): 798–807. дои : 10.1109/43.31537 . S2CID 8754800 .
Polikarpova N. I., Shalyto A. A. Automata-based programming SPb.: Piter. 2009 (rus)
Университет ИТМО, кафедра «Технологии программирования»

[gram-1] Перейти обратно: ^а ^б Ахо, Альфред В.; Уллман, Джеффри Д. (1973). Теория синтаксического анализа, трансляции и компиляции . Том. 1. Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. ISBN 0-13-914564-8 .

[2] Оллонгрен, Александр (1974). Определение языков программирования путем интерпретации автоматов . Лондон: Академическая пресса. ISBN 0-12-525750-3 .

[3] Джонсон, WL; Портер, Дж. Х.; Экли, С.И.; Росс, DT (1968). «Автоматическая генерация эффективных лексических процессоров с использованием методов конечных состояний» . Связь АКМ . 11 (12): 805–813. дои : 10.1145/364175.364185 . S2CID 17253809 .

[4] Наур, Питер (сентябрь 1963 г.). «Проект компилятора GIER ALGOL, часть II». БИТ Численная математика . 3 (3): 145–166. дои : 10.1007/BF01939983 . S2CID 189785656 .

[5] «Автоматное программирование» (PDF) . Научно-технический журнал информационных технологий, механики и оптики (53). 2008.

[1]

[2]

[3]

[4]

[5]