| Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум на Исходниках.RU > Все языки: Статьи, заготовки в FAQ > Aнализ и выделение информации из текста |
| Автор: mikv 03.01.05, 11:30 |
| Наверное, многие сталкивались с задачами на анализ и выделение информации из текста. У многих начинающих программистов это вызывает серьезные проблемы. Однако существуют методы, которые позволяют решать задачи такого рода легко и быстро. Это автоматное программирование(или 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_COLLAPSE_OFF}><{CODE_WRAP_OFF}> Состояние Символ Новое состояние код { комментарий комментарий } код Начальное состояние: code. Вот код программы. <{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}> 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. Теперь усложним задачу. Ведь у нас есть директивы компилятору. Наша первоначальная версия программы их также считает комментариями и удаляет. Модифицируем автомат, чтобы он оставлял в тексте программы директивы компилятора. <{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}> Состояние Символ Новое состояние код { промежуточное комментарий } код промежуточное $ код промежуточное прочие симв. комментарий Состояние 'промежуточное' вводятся специально, чтобы обслуживать директивы компилятору. Обратите внимание, что на этот раз в программы мы явно не вводим состояние 'промежуточное'. Но тем не менее, оно там присутствует. Код программы меняется совсем не сильно: <{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}> 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. Эта тема была разделена из темы "Неотёсанные топики" Сообщения были разделены в тему "Русские буквы в тексте" |