Регулярные выражения
Функция grep сканирует один файл, вызывая match для каждой его строки:
Если открыть файл не удается, то программа не прекращает работу. Такое поведение было выбрано для того, чтобы при вызове:
% grep herpolhode *.*
Даже если какой-то файл в каталоге не может быть открыт, grep уведомляла об этом и продолжала работу; если бы на этом она останавливалась, пользователю пришлось бы вручную набивать список всех файлов в каталоге, кроме недоступного. Обратите внимание и на то, что grep выводит имя файла и строку, соответствующую шаблону, однако имя файла не выводится, если чтение происходит из стандартного потока ввода или из одного файла. Может быть, такое поведение покажется кому-то старомодным, однако оно отражает идиоматический стиль, в основе которого лежит опыт. Когда задан только один источник ввода, миссия grep состоит, как правило, в выборе соответствующих строк, и имя файла никого не интересует. А. вот если поиск происходит в нескольких файлах, то, как правило, задачей является найти все совпадения с какой-то строкой, и здесь имя файла будет весьма информативно. Сравните:
% strings markov.exe | grep 'DOS mode'
И:
% grep grammer chapter*.txt
Продуманность нюансов – одна из тех черт, что сделали grep столь популярным инструментом; здесь мы видим, что для создания хороших программ нотация обязательно должна учитывать человеческую психологию.
В нашей реализации match завершает работу сразу же, как только найдено соответствие. Для grep это вполне подходит в качестве поведения по умолчанию, но для реализации оператора подстановки (найти и заменить) в текстовом редакторе больше подошел поиск крайне левого самого длинного совпадения (leftmost longest). Например, если нам задан текст "ааааа", то шаблону а * соответствует, в частности, и пустая строка в начале текста, однако более естественным было бы включить в совпадение все пять а. Для того чтобы match искала крайне левую и самую длинную строку, matchstar надо переписать так, чтобы добиться жадного (greedy) поведения алгоритма: вместо того чтобы просматривать каждый символ текста слева направо, он должен каждый раз пытаться пройти до конца самой длинной строки, соответствующей оператору-звездочке, и откатываться назад, если оставшаяся часть обрабатываемого текста не соответствует оставшейся части шаблона. Другими словами, она должна выполняться справа налево.
Вот как выглядит версия matchstar, осуществляющая поиск крайне левого максимального совпадения:
