Поиск образцов в тексте

РВ являются основным средством приложений для поиска образцов, шаблонов в тексте. Они задают «схему» образца поиска. С помощью РВ можно не прилагая больших усилий, описывать такие образцы и быстро менять такие описания, если результат не устраивает.

РВ компилируются в ДКА или НКА, которые затем моделируются для получения программы распознавания образов в тексте.

Пример 1.

Зададим шаблон (образец) для распознавания названий улиц поисковой системой при просмотре сайтов.

Название улицы может начинаться с «улица», «ул.», «проспект», «пр.», «переулок», «пер.».

улица | ул\. | проспект | пр\. | переулок | пер\.

Затем идет название улицы. Оно начинается с прописной буквы и затем идет несколько строчных.

[А-Я][а-я]*

Название улицы может состоять из нескольких слов с заглавной буквы (например, ул. Карла Маркса)

[А-Я][а-я]*([А-Я][а-я]*)*

Итоговое выражение

(улица| ул\.|проспект|пр\.|переулок|пер\.) [А-Я][а-я]*([А-Я][а-я]*)*

Таким образом, распознавание адресов на web-страницах с помощью компилятора РВ намного проще по сравнению с программой на традиционном языке программирования.

Написать РВ для поиска сотовых и 6-значных городских телефонных номеров.

Распознаватели

Ранее мы рассмотрели задание языков через механизм порождения, с помощью грамматики. Теперь рассмотрим второй основной подход задания языков – через механизм распознавания.

Распознаватель, по сути, является процедурой специального вида, которая по заданной цепочке определяет, принадлежит ли она языку. Если принадлежит, то процедура останавливается с ответом «да», т. е. допускает цепочку; иначе – останавливается с ответом «нет» или зацикливается. Язык, определяемый распознавателем – это множество всех цепочек, которые он допускает.

Определение. Распознавателем языка называется алгоритм или физическое устройство, которое по произвольной цепочке определяет, принадлежит ли она данному языку или нет.

Начнем с распознавателя регулярных языков – конечного автомата.