Синтаксический разбор строк и конечные автоматы
От: Аноним Андрей Боровский  
Дата: 12.06.03 03:17
Оценка: 286 (4)
Статья :
Синтаксический разбор строк и конечные автоматы

Авторы :
Андрей Боровский
re
От: Аноним  
Дата: 05.11.02 06:31
Оценка:
С одной стороны, интересно. А с другой — выдумывать новые текстовые форматы сегодня просто неграмотно, ведь есть XML. Да и для того же HTML есть парсеры, выполненные в виде COM-объектов.
Re: XML - не панацея
От: Аноним  
Дата: 05.11.02 18:30
Оценка: +1
XML — не панацея, поскольку внутри XML-тэгов может быть все что угодно — любой язык, который надо "допарсивать". Взять, к примеру SVG (http://www.w3.org/TR/SVG11/). Да, это XML. Но внутри его полно такого:

<path d="M300,200 h-150 a150,150 0 1,0 150,-150 z" . . . />

Так что статья полезная и, главное — популярная. Люблю такие статьи. И в общем-то она действительно не о текстовых парсерах, как уже было отмечено. Парсеры — это просто наиболее очевидная и простая область применения.
Re: re
От: Аноним  
Дата: 05.11.02 13:23
Оценка:
Ничего ты не понял :(
Это только маленький кусочек из теории автоматов. Наиболее простой вопрос — конечные автоматы.
Есть много других автоматов. Это применяется для обработки любых данных — бинарных, видео, графика, звук и тд и тд.
Теория автоматов дает тебе возможность вместо изобретения алгоритма эвристически синтезировать его !
Re: re
От: Михаил  
Дата: 17.06.03 21:59
Оценка:
Здравствуйте, Аноним, Вы писали:

А>... выдумывать новые текстовые форматы сегодня просто неграмотно, ведь есть XML.



Сильно!
...А отсюда наливаем, когда рецепт написан совсем неразборчиво...
Re[2]: re
От: Аноним  
Дата: 18.06.03 09:06
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Ничего ты не понял

А>Это только маленький кусочек из теории автоматов. Наиболее простой вопрос — конечные автоматы.
А>Есть много других автоматов. Это применяется для обработки любых данных — бинарных, видео, графика, звук и тд и тд.
А>Теория автоматов дает тебе возможность вместо изобретения алгоритма эвристически синтезировать его !

А какие еще есть полезные на практике автоматы, кроме конечных? В любом случае современный компьютер теоретически всего лишь сложный конечный автомат, даже не машина Тьюринга.
Но изучать теорию автоматов, конечно полезно. Только ничего синтезировать автоматически не получится, разбор грамматики это весьма специфический алгоритм.
Re[3]: Пошто компьютер-то обидели...
От: fAX Израиль  
Дата: 19.06.03 19:14
Оценка:
Здравствуйте, Аноним, Вы писали:

[ХЪ]
А> ...В любом случае современный компьютер теоретически всего лишь сложный конечный автомат, даже не машина Тьюринга.
Извините, Вы не правы. Компьютер — это больше, чем автомат, если Вы, конечно не имеете в виду, что число образов памяти конечно... Да и в таком случае можно предположить, что вычисления останавливаются, добавляется память (эмуляция бесконечной памяти) — в итоге получаем модель RAM, которая, как известно, эквивалентна МТ.
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Re[3]: re
От: Mikhail_T  
Дата: 19.06.03 21:39
Оценка:
Здравствуйте, Аноним, Вы писали:


А>А какие еще есть полезные на практике автоматы, кроме конечных? В любом случае современный компьютер теоретически всего лишь сложный конечный автомат, даже не машина Тьюринга.


Сделайти тогда вот такой автомат. Он работает с алфавитом из 2 букв 0,1 и принимает все слова вот такого типа 01 0011 000111 все остальные слова он не принимает, удачи.

А>Но изучать теорию автоматов, конечно полезно. Только ничего синтезировать автоматически не получится, разбор грамматики это весьма специфический алгоритм.


Разбор граматики это всеволиш другой подвид автоматов.
Re[4]: re
От: fAX Израиль  
Дата: 19.06.03 22:08
Оценка:
Здравствуйте, Mikhail_T, Вы писали:

А>>А какие еще есть полезные на практике автоматы, кроме конечных? В любом случае современный компьютер теоретически всего лишь сложный конечный автомат, даже не машина Тьюринга.


M_T>Сделайти тогда вот такой автомат. Он работает с алфавитом из 2 букв 0,1 и принимает все слова вот такого типа 01 0011 000111 все остальные слова он не принимает, удачи.


Похоже, имелось в виду: допустим, образ памяти компьютера — это его состояние, а все возможные состояния вводов — это алфавит... Таким образом, и компьютер на определённом вводе "зашкалит". Но всё равно — мысль крамольная...
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Re[4]: re
От: Аноним  
Дата: 20.06.03 09:17
Оценка:
Здравствуйте, Mikhail_T, Вы писали:

M_T>Сделайти тогда вот такой автомат. Он работает с алфавитом из 2 букв 0,1 и принимает все слова вот такого типа 01 0011 000111 все остальные слова он не принимает, удачи.


Это неправильная постановка вопроса. Естественно, такого автомата нет, но и никакой современный компьютер (да и вообще никакой скорее всего) не способен решить эту задачу в такой формулировке. Потому что память у них конечная.
Надеюсь, вы не будете спорить, что компьютер по своим возможностям не может превосходить машину Тьюринга? Теперь ограничим
у нее размер ленты (поскольку бесконечной памяти нет) и что получим? Получим конечный автомат с числом состояний M*A*Q, M —
количество ячеек памяти, A — объем ячейки памяти, Q — количество сотояний программы для МТ эмулирующей работу других
программ (я точно не помню формулировку соответствующей теоремы, поэтому не указываю конкретный размер ни алфавита, ни
количество состояний).
Да о чем вообще спор? Обидно, что компьютер такая примитивная вещь с теоретической точки зрения? Ну и что, на заре
автоматостроения, один из создателей этой теории доказал, что можно построить автомат (при некоторых допущениях), который будет
вести себя неотличимо от любого отдельно взятого человека. В математике сплошь и рядом сложнейшая практическая проблема может
иметь простое теоретическое решение, которое невозможно реализовать на практике.

M_T>Разбор граматики это всеволиш другой подвид автоматов.

Я это и имел ввиду.
Re[4]: Пошто компьютер-то обидели...
От: Аноним  
Дата: 20.06.03 09:18
Оценка:
Здравствуйте, fAX, Вы писали:

fAX>Здравствуйте, Аноним, Вы писали:


fAX>[ХЪ]

А>> ...В любом случае современный компьютер теоретически всего лишь сложный конечный автомат, даже не машина Тьюринга.
fAX>Извините, Вы не правы. Компьютер — это больше, чем автомат, если Вы, конечно не имеете в виду, что число образов памяти конечно... Да и в таком случае можно предположить, что вычисления останавливаются, добавляется память (эмуляция бесконечной памяти) — в итоге получаем модель RAM, которая, как известно, эквивалентна МТ.

Да нету покамест бесконечной памяти в природе, а с конечной компьютер как был так и будет автоматом.