Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=80084&view=findpost&p=563793 Mon, 03 Jan 2005 11:30:02 +0000 Aнализ и выделение информации из текста https://forum.sources.ru/index.php?showtopic=80084&view=findpost&p=563793 такого рода легко и быстро. Это автоматное программирование(или switch-технология).

Сама теория автоматов, лежащая в основе этой технологии зародилась задолго до первых компьютеров. Еще в далекие 30-ые Алан Тьюринг исследовал абстрактную машину, которая являлась автоматом. Рассмотрим самый простой вариант - детерминированный конечный автомат(ДКА).

Строгое определение(которое дается в умных книжках) выглядит примерно так:
Конечным автоматом называется реализация алгебраической структуры (S, A, m, s0, F), где
S - непустое множество состояний;
A - конечное множество входных символов (алфавит);
m - отображение S*A-->S, или функция переходов, которая каждой паре (символ, состояние) ставит в соответствие состояние из множества S;
s0 - состояние из S, известное как начальное (стартовое);
F - множество заключительных (допускающих) состояний, F S или просто соответствует окончанию просмотра текста.

Если сказать тоже самое попроще:
КА представляет собой набор состояний и переходов между ними, зависящих от входных данных.

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

Рассмотрим решение задачи с применением автоматов. Самый простой вариант:
"Дан текст программы на Pascal в файле input.txt. Следует удалить из него все комментарии и поместить преобразованный код в файл output.txt. Размер текста может превышать 1000 килобайт."

Прежде всего, вспомним, что комментариями в языке Паскаль являются символы, заключенные между '{' и '}'.
Построим автомат для решения задачи. У него будет 3 состояния: 'код' и 'комментарий'. Запишем все состояния и переходы между ними в табличку:
    Состояние            Символ          Новое состояние
    код                  {               комментарий
    комментарий          }               код



Начальное состояние: code.

Вот код программы.
    type
       automat = (code,comment);
    var
       x        : automat;
       ch       : Char;
       inp,outp : File Of Char;
    begin
       x := code;
       Assign(inp,'input.txt');
       Reset(inp);
       Assign(outp,'output.txt');
       Rewrite(outp);
       while not(eof(inp)) do
       begin
          read(inp,ch);
          case ch of
            '{':
               if x = code then x := comment;
            '}':
               if x = comment then
               begin
              x := code;
                  Continue; {Здесь мы делаем переход на заголовок цикла}
                  {иначе символ '{' будет выведен в выходной файл - ведь }
                  {автомат уже сменил состояние}
               end;
          end;
          if x=code then write(outp,ch);
       end;
       Close(outp);
       Close(inp);
    end.


Теперь усложним задачу. Ведь у нас есть директивы компилятору.
Наша первоначальная версия программы их также считает комментариями и удаляет. Модифицируем автомат, чтобы
он оставлял в тексте программы директивы компилятора.

    Состояние            Символ          Новое состояние
    код                  {               промежуточное
    комментарий          }               код
    промежуточное        $               код
    промежуточное        прочие симв.    комментарий


Состояние 'промежуточное' вводятся специально, чтобы обслуживать директивы компилятору. Обратите внимание,
что на этот раз в программы мы явно не вводим состояние 'промежуточное'. Но тем не менее, оно там присутствует.
Код программы меняется совсем не сильно:

    type
       automat = (code,comment);
    var
       x        : automat;
       ch, Tmp  : Char;
       inp,outp : File Of Char;
    begin
       x := code;
       Assign(inp,'input.txt');
       Reset(inp);
       Assign(outp,'output.txt');
       Rewrite(outp);
       while not(eof(inp)) do
       begin
          read(inp,ch);
          case ch of
            '{':
               if x = code then
               begin
                  read(inp,Tmp);
                  if Tmp = '$' then
                  begin
                     write(outp,ch);
                     write(outp,Tmp);
                     Continue;
                  end else x := comment;
               end;
     
            '}':
               if x = comment then
               begin
              x := code;
                  Continue;
               end;
          end;
          if x=code then write(outp,ch);
       end;
       Close(outp);
       Close(inp);
    end.


Эта тема была разделена из темы "Неотёсанные топики"

Сообщения были разделены в тему "Русские буквы в тексте"]]> mikv Все языки: Статьи, заготовки в FAQ