[Ruby] Re: [Ruby] Re: [Ruby] призыв ;-)

[Alexander Bokovoy]

On Wed, Oct 09, 2002 at 05:52:11PM +0300, Olonichev Sergei wrote:
> > > По моему Libero к библиотеке FST имеет отдаленное отношение, или я
> что-то не
> > > понял?
> > Тогда я не понял. В письме Юры идет речь о конечных автоматах. Libero
> > представляет собой среду, позволяющую по описанию FSM генерировать код,
> > реализующий описанный конечный автомат на конкретном языке.
> 
> Это хорошо будет работать только в случае небольших диаграмм (автоматов).
> Но как например, будет реализован поиск дуги по которой нужно осуществить
> переход, при помощи оператора case, линейно или логарифмически или еще как?
> А сколько при этом автомат будет занимать в памяти?
 Libero генерирует таблицу переходов между состояниями (и последовательность 
вызовов функций внутри состояния). То есть, исполнение автомата заключается
в итерировании этой таблицы переходов. Вот типичный код на C (заранее прошу
прощения у тех, кто незаинтересован), здесь реальный код машины начинается с 
_LR_state = 0:

int lr_calculate (char *p_expr, long *p_result, int *p_offset)
{
    ASSERT (p_expr   != NULL);
    ASSERT (p_result != NULL);
    ASSERT (p_offset != NULL);

    result   = p_result;                /*  Address parameters to function   */
    expr     = p_expr;
    offset   = p_offset;
    feedback = 0;                       /*  Assume no errors                 */

/* *Стандартный обработчик FSM начинается здесь* */

    _LR_state = 0;                      /*  First state is always 0          */
    initialise_the_program ();
    while (the_next_event != terminate_event)
      {
        _LR_event = the_next_event;
        if (_LR_event >= 9 || _LR_event < 0)
          {
            printf ("State %d - event %d is out of range\n",
                     _LR_state, _LR_event);
            break;
          }
        _LR_savest = _LR_state;
        _LR_index  = _LR_action [_LR_state][_LR_event];
        /*  If no action for this event, try the defaults state              */
        if (_LR_index == 0)
          {
            _LR_state = _LR_defaults_state;
            _LR_index = _LR_action [_LR_state][_LR_event];
          }
        if (_LR_index == 0)
          {
            printf ("State %d - event %d is not accepted\n",
                     _LR_state, _LR_event);
            break;
          }
        the_next_event          = _LR_NULL_EVENT;
        the_exception_event     = _LR_NULL_EVENT;
        exception_raised        = FALSE;
        _LR_vecptr = _LR_vector [_LR_index];

        for (;;)
          {
            if ((*_LR_vecptr == _LR_STOP)
            || (exception_raised))
                break;
            (*_LR_module [*_LR_vecptr++]) ();
          }
        if (exception_raised)
          {
            if (the_exception_event != _LR_NULL_EVENT)
                _LR_event = the_exception_event;
            the_next_event = _LR_event;
          }
        else
            _LR_state = _LR_nextst [_LR_state][_LR_event];

        if (_LR_state == _LR_defaults_state)
            _LR_state = _LR_savest;
        if (the_next_event == _LR_NULL_EVENT)
          {
            get_external_event ();
            if (the_next_event == _LR_NULL_EVENT)
              {
                printf ("No event set after event %d in state %d\n",
                         _LR_event, _LR_state);
                break;
              }
          }
      }

/* *Стандартный обработчик FSM заканчивается здесь* */
    return (feedback);
}

/*- Standard dialog routines ------------------------------------------------*/

local raise_exception (event_t event)
{
    exception_raised = TRUE;
    if (event >= 0)
        the_exception_event = event;
}


_LR_nextst -- массив переходов состояний (новое состояние = [текущее состояние][событие]),
_LR_action -- массив действий (выполняемое действие = [текущее состояние][событие])

На самом деле "действие" = вектор вызываемых функций, хранимых в массиве
_LR_vector.

_LR_module -- массив всех вызываемых функций

Затраты на хранение:
_LR_nextst = количество состояний * количество событий 
_LR_action = тоже самое
_LR_vector = количество состояний * (длина состояния в функциях + 1)
_LR_module = количество всех функций * sizeof((void(*)(*)))

Размер элементов (где неуказано) -- в базовой конфигурации для генератора на язык С
используется unsigned short (1 байт). Естественно, это очень условное
ограничение -- все зависит от используемой схемы трансляции. Например, в
схемах, реализующих трансляцию в Perl, awk, shell, PHP, Rex, SQL, для
хранения переходов состояний и действий используются строки.

> По-моему языки программирования не предназначены для представления
> больших графов, с точки зрения обработки значительно выгоднее автоматы
> (трансдьюсеры и др.) представлять в виде графов и дальше уже их
> обрабатывать на Ruby, С или любом другом языке.
Так в Libero и реализовано. Посмотри.

-- 
/ Alexander Bokovoy
---
Most seminars have a happy ending.  Everyone's glad when they're over.