На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Поиск Участники Календарь Избранное RSS
msm.ru
! Друзья, соблюдайте, пожалуйста, правила форума и данного раздела:
• Данный раздел не предназначен для вопросов и обсуждений, он содержит FAQ-заготовки для разных языков программирования. Любой желающий может разместить здесь свою статью. Вопросы же задавайте в тематических разделах!
• Если ваша статья может быть перенесена в FAQ соответствующего раздела, при условии, что она будет оформлена в соответствии с Требованиями к оформлению статей.
• Чтобы остальным было проще понять, указывайте в описании темы (подзаголовке) название языка в [квадратных скобках]!
Модераторы: Модераторы
  
> Aнализ и выделение информации из текста , [Pascal]
Мыкв
Сообщ. #1 ,

    Senior Member
    ****
    Профиль · PM
    Рейтинг (т): 56
    Наверное, многие сталкивались с задачами на анализ и выделение информации из текста. У многих начинающих программистов это вызывает серьезные проблемы. Однако существуют методы, которые позволяют решать задачи
    такого рода легко и быстро. Это автоматное программирование(или 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 состояния: 'код' и 'комментарий'. Запишем все состояния и переходы между ними в табличку:
    ExpandedWrap disabled
      Состояние            Символ          Новое состояние
      код                  {               комментарий
      комментарий          }               код



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

    Вот код программы.
    ExpandedWrap disabled
      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.


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

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


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

    ExpandedWrap disabled
      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.


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

    Сообщения были разделены в тему "Русские буквы в тексте"
    Сообщение отредактировано: Jin X -
    0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
    0 пользователей:


    Рейтинг@Mail.ru
    [ Script execution time: 0,0361 ]   [ 15 queries used ]   [ Generated: 27.04.24, 22:10 GMT ]  
    Powered by Invision Power Board(U) v1.2 © 2003  IPS, Inc.