[Perl] Машина Тьюринга

Ни у кого не завалялась?
 
+
-
edit
 

Gudleifr

втянувшийся

Ни у кого не завалялась реализация на Perl Машины Тьюринга (или другого достаточно сложного конечного автомата)? Не "гольф". Скорее, нужна красивая учебно-демонстрационная. Чтобы "входными символами" могли быть сложные регулярные выражения, и было бы куда цеплять функции-триггеры, отслеживающие переход из состояния в состояние. А то у меня получается еще менее красиво, чем на голом Си.
 38.038.0
+
-
edit
 

Mishka

модератор
★★☆
Gudleifr> Ни у кого не завалялась реализация на Perl Машины Тьюринга (или другого достаточно сложного конечного автомата)?

Это как? МТ и конечный автомат — это две очень разные вещи. Вот регулярные выражения и конечные автоматы — одно и то же по мощности выражения.
 37.037.0
+
-
edit
 

Gudleifr

втянувшийся

Mishka> Это как? МТ и конечный автомат — это две очень разные вещи. Вот регулярные выражения и конечные автоматы — одно и то же по мощности выражения.
Меня не интересует вычислительная мощность. Меня интересует красивая запись состояний и переходов между ними. Плюс, возможность вынесения "за скобки" общей части. Моей Perl-изобретательности хватило только на следующее (там варьируются только ф-ии фывода - массив p - чтение и разбор происходят одинаково):
code text
  1. #!/usr/bin/perl
  2.  
  3. # МАШИНА: СОСТОЯНИЕ => [[СИМВОЛ, СОСТОЯНИЕ, СДВИГ], ...]
  4. %stats = (Garbage => [["^\\\", "Path", 0], ["^\$", 0, 1],
  5.                 [0, 0, 1]],
  6.         Path => [ "Param", 1], ["^. ", "Param", 0],
  7.                 ["^\\\", 0, 1], ["^ТЕКСТ", "Text", 1],
  8.                 ["^ТАБЛИЦА", "Header", 1], ["^ЗАПИСИ", "Header", 1],
  9.                 [0, "Garbage", 0]],
  10.         Header => [["^\$", "Text", 1], [0, 0, 1]],
  11.         Text => [["^\$", "Param", 1], [0, 0, 1]],
  12.         Param => [["^. ", 0, 1], ["^\\\", "Path", 0],
  13.                 ["^\$", "Garbage", 1], [0, "Garbage", 0]]);
  14.  
  15. # СЧИТЫВАНИЕ СИМВОЛА, ЕСЛИ ОН ЕЩЕ НЕ БЫЛ СЧИТАН
  16. sub ready {
  17.         $reading = <FI> unless $reading;
  18.         return 0 unless $reading;
  19.         $reading =~ s/\s*\r?\n//;
  20.         return 1
  21. }
  22.  
  23. # ОДИН ТАКТ РАБОТЫ
  24. sub step {
  25.         foreach (@{$stats{$state}}) { # СОСТОЯНИЕ
  26.                 my $s = $_->[0]; # СИМВОЛ
  27.                 if (!$s or $reading =~ /$s/) {
  28.                         $p->{$state . $s}() if exists $p->{$state . $s}; # ВЫВОД
  29.                         $state = $_->[1] if $_->[1]; # НОВОЕ СОСТОЯНИЕ
  30.                         $reading = 0 if $_->[2]; # СДВИГ
  31.                         return
  32.                 }
  33.         }
  34. }
  35.  
  36. # СЧИТЫВАЕМ ЛЕНТУ (ФАЙЛ)
  37.  
  38. sub machine {
  39.         $p = shift;
  40.         $reading = 0;
  41.         $state = "Garbage";
  42.         step() while ready();
  43. }
  44.  
  45. # ПРИМЕР ПРОГРАММЫ
  46.  
  47. # ФУНКЦИИ ВЫВОДА: СОСТОЯНИЕ.СИМВОЛ
  48. $p1 = {"Garbage^\\\", sub {
  49.                 print "Garbage-Path:", $reading, "\n"
  50.         },
  51.         "Garbage^\$", sub {
  52.                 print "Garbage:", $reading, "\n"
  53.         },
  54.         "Garbage0", sub {
  55.                 print "Garbage:", $reading, "\n"
  56.  
  57.         "Param^\\\", sub {
  58.                 print "Param-Path:", $reading, "\n"
  59.         },      }};
  60.  
  61. $s = shift @ARGV;
  62. $s .= ".txt";
  63. open FI, $s;
  64. machine($p1);
  65. close FI

Другие варианты, например с представлением состояний в виде ф-ий выглядели еще страшнее. Но, думаю, бывалый Perl-овец напишет гораздо красивее.
 38.038.0
Это сообщение редактировалось 09.10.2015 в 09:51
+
-
edit
 

Mishka

модератор
★★☆
Gudleifr> Меня не интересует вычислительная мощность. Меня интересует красивая запись состояний и переходов между ними. Плюс, возможность вынесения "за скобки" общей части. Моей Perl-изобретательности хватило только на следующее (там варьируются только ф-ии фывода - массив p - чтение и разбор происходят одинаково):

Реализация МТ и конечного автомата — две очень разные вещи. Просто это надо понимать. Если тебе нужен автомат, то могу рассказать, как сделано у нас. На С++, но идея от этого не меняется. Если ты хочешь именно МТ (а там и лента, и состояния, и алфавит, и действия совершенно другие)


Gudleifr> Другие варианты, например с представлением состояний в виде ф-ий выглядели еще страшнее. Но, думаю, бывалый Perl-овец напишет гораздо красивее.

База — символ алфавита и указатель на ф-цию, которая должна быть вызвана, а так же указатель на состояние, на которое надо перейти. Само состояние имеет символ состояний и список баз. Это принимаемые символы. При попадании в определённое состояние ожидается входной символ. После этого происходит поиск по списку. Найдено — значит перешли в новое состояние, не найдено — автомат переходит в запрещённое состояние и полностью останавливается. Выделение общих частей происходит простым способом. Кодируется автомат первого уровня, а, когда общая часть отработана, то в ф-ции, которая отрабатывается при переходе, вызывается автомат второго уровня. При некоторой сноровке, автомамт легко программируется так, что его начальное и конечное состояние (и запрещённое) становятся текущими для "интерпретатора автоматов", а автомат, вызвавший подавтомат просто сидит на стеке и ждёт завершения подавтомата. Если применять объекты, то ещё проще, т.к. подавтомат всегда объект со своей программой и памятью, поэтому на остальную часть свои проблемы не проецирует. Программка автомата, как правило ручное заполнение массива объектов.
 37.037.0
+
-
edit
 

Gudleifr

втянувшийся

Mishka> Реализация МТ и конечного автомата — две очень разные вещи. Просто это надо понимать...
Спасибо, но понимать не надо. Надо написать 10 красивых строк на Perl.
 38.038.0
+
-
edit
 

Mishka

модератор
★★☆
Gudleifr> Спасибо, но понимать не надо. Надо написать 10 красивых строк на Perl.
Для реализации МТ — мне не надо.
 37.037.0
+
-
edit
 

Gudleifr

втянувшийся

Mishka> мне не надо.
Возникла вторая проблема.
Пока ф-ии вывода просты, текст (приведенного выше решения) более или менее очевиден.
Но, как только, возникает проблема в разделении на подсостояния (встраивание машин друг в друга), получается типический быдлокод (как на C++ каком-нибудь).
Кто-нибудь видел красивое Perl-решение
1. описания встроенных машин;
либо
2. расширяемой машины?
 41.041.0

в начало страницы | новое
 
Поиск
Настройки
Твиттер сайта
Статистика
Рейтинг@Mail.ru