Есть ли хороший модуль CPAN для реализации конечных автоматов при разборе текста? - PullRequest
Новая
       15

Есть ли хороший модуль CPAN для реализации конечных автоматов при разборе текста?

7 голосов
/ 20 февраля 2012

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

Существует ли модуль CPAN, который считается «наилучшей практикой» и хорошо подходит для реализации состояниямашинная логика, подобная этой, в простой и элегантной форме?

Я бы предпочел решения, менее сложные, чем Parse::RecDescent, но если их не существует и Parse::RecDescent гораздо проще применить к этой проблеме, чем я думал, я 'я очень хочу рассмотреть это вместо того, чтобы кататься по своим собственным словам, как я был до сих пор.

Пример общего кода синтаксического анализа: 

my $state = 1;
while (my $token = get_next_token()) { # Usually next line
    if ($state == 1) {
        do_state1_processing();
        if (token_matches_transition_1_to_2($token)) {
            do_state_1_to_2_transition_processing();
            $state == 2;
            next;
        } elsif (token_matches_transition_1_to_4($token)) {
            do_state_1_to_4_transition_processing();
            $state == 4;
            next;
        } else {
             do_state1_continuation();
             next;
        }
    } elsif ($state == 5) {
        do_state5_processing();
        if (token_matches_transition_5_to_6($token)) {
            do_state_5_to_6_transition_processing();
            $state == 6;
            next;
        } elsif (token_matches_transition_5_to_4($token)) {
            do_state_5_to_4_transition_processing();
            $state == 4;
            next;
        } else {
             do_state5_continuation();
             next;
        }
    } else {

    }

}

Ответы [ 4 ]

3 голосов
/ 20 февраля 2012

Я бы порекомендовал взглянуть на Марпа и Марпа :: XS .

Просто посмотрите на этот простой калькулятор . 

my $grammar = Marpa::XS::Grammar->new(
    {   start   => 'Expression',
        actions => 'My_Actions',
        default_action => 'first_arg',
        rules   => [
            { lhs => 'Expression', rhs => [qw'Term'] },
            { lhs => 'Term', rhs => [qw'Factor'] },
            { lhs => 'Factor', rhs => [qw'Number'] },
            { lhs => 'Term', rhs => [qw'Term Add Term'], action => 'do_add' },
            {   lhs    => 'Factor',
                rhs    => [qw'Factor Multiply Factor'],
                action => 'do_multiply'
            },
        ],
    }
);

Вы должны будете самостоятельно внедрить токенизатор.

2 голосов
/ 20 февраля 2012

Вы можете использовать Class :: StateMachine : 

package Foo;
use parent 'Class::StateMachine';

sub new {
    my $class = shift;
    Class::StateMachine::bless {}, $class, 'state_1';
}

sub do_state_processing :OnState('state_1') {
  my $self = shift;
  if    (...) { $self->event_1 }
  elsif (...) { $self->event_2 }
  ...
}

sub do_state_processing :OnState('state_2') {
  ...
}

sub event_1 :OnState('state_1') {
  my $self = shift;
  $self->state('state_2');
}

sub event_2 :OnState('state_2') {
  my $self = shift;
  $self->state('state_3');
}

sub enter_state :OnState('state_1') {
  print "entering state 1";
  ...
}

sub enter_state :OnState('state_2') {
  ...
}

package main;

my $sm = Foo->new;
...
while (my $token = get_next_token()) {
  $sm->do_state_processing;
}

Хотя модуль, специфичный для обработки текста, вероятно, больше подойдет для вашего конкретного случая

1 голос
/ 20 февраля 2012

(С помощью) Несколько лет назад я написал нечто, называемое Perl Formal Language Toolkit , так что это может послужить некоторой основой, однако я думаю, что вы действительно хотите этотакой инструмент, как Ragel Finite State Machine Compiler .К сожалению, он не выводится на Perl, и мне очень важно реализовать цель Perl для Ragel , а также предоставить аналогичные (но более ориентированные на Perl) функции для моего модуля с бит-гниением.

0 голосов
/ 27 февраля 2012

Я написал Parser::MGC главным образом потому, что мне было трудно заставить Parse::RecDescent правильно составлять отчеты об ошибках, и мне не нравилась его причудливая пользовательская встроенная грамматика в строковых кавычках, которые содержат код perl наряду с другим кодом perl.Программа P::MGC - это просто Perl-код;но написано как рекурсивный спуск на структуру грамматики, похожую на P::RD.

...