[cdev] исправление find
Grigoriy A. Sitkarev
sitkarev на komitex.ru
Чт Апр 1 05:24:00 MSK 2010
Вернёмся к find.
Подход к решению задачи в find очень правильный. Заранее неизвестно, по
каким комбинациям параметров пользователю захочется вести поиск, поэтому
даём ему возможность задавать любые комбинации, а для этого нужен некий
очень простой язык. Этот язык стандартизован и мы пользуемся
спецификацией Open Group.
В find у нас есть несколько выражений, перечислю их в порядке убывания
приоритетов, из primaries можно составлять комбинации:
(expr) - выражение в скобках
!expr - отрицание выражения
expr -a expr - логическое AND
expr -o expr - логическое OR
Можно записать в формальном синтаксисе:
primary_or_expr = primary | '(' or_expr ')'
neg_or_expr = '!' neg_or_expr | primary_or_expr
and_expr = and_expr '-a' neg_or_expr | neg_or_expr
or_expr = or_expr '-o' and_expr | and_expr
cmd = NULL | or_expr
Стартовый символ грамматики тогда будет cmd.
Можно объяснить всё несколько проще, например так. У нас есть два
оператора логических, OR и AND. Приоритет у AND выше поэтому:
aaa -a bbb -a ccc -o xxx -a yyy -a zzz -o ppp -a qqq -a rrr
Иначе можно написать (используя операторы Си) как:
(aaa && bbb && ccc) || (xxx && yyy && zzz) || (ppp -a -qqq -a rrr)
Т.е. пока нам после выражения встречается оператор AND (-a) - все эти
выражения относятся к одной группе выражений и их надо вычислять, одно
за другим, пока хотя бы одно не станет ложным или они все не будут
вычислены. Если хотя бы одно стало ложным, значит результат вычисления
этой группы - ложь и дальше его уже можно и не вычислять.
Тогда получается что оператор OR собирает группы.
Выполнить группу 1 ИЛИ если результат вычисления группы 1 ложь,
выполнить группу 2 ИЛИ если разультат вычисления группы 2 ложь,
выполнить группу 3 ИЛИ ...
У нас есть ещё выражение в скобках, приоритет у которого выше чем у
операторов AND и OR. Но мы можем воспользоваться рекурсией здесь, и
сказать что если мы увидели выражение в скобках, то мы выполняем нашу
процедуру для групп рекурсивно для всего выражения в скобках. Если там
ещё раз встретятся скобки, мы ещё раз рекурсивно в них "зайдём" и т.д.
Только надо убедиться, что закрывающие скобки для нашего уровня рекурсии
всегда есть и мы их видим в выражении. Также заметим, что мы можем
сказать что в принципе OR у нас всегда присутствует, но в нём может быть
только одна группа (т.е. присутствует только левый операнд).
Что касается выражения отрицания, то нам достаточно хранить просто один
флаг, каждый раз когда мы встречаем оператор '!', изменять его значение
на противоположное. Потом этот флаг будет сохраняться в описании команды.
Как всё это представить в виде структур данных?
Я думаю что было бы хорошо всё выражение, которое надо "посчитать",
представить в виде групп команд и собственно команд. Каждая группа
команд это часть выражения OR (или левая сторона или правая) а команда
часть выражения AND (или левая или правая сторона).
Общее представление структуры команды - в ней три поля, ссылка на
следующую команду в группе, указатель на функцию-обработчик и поле
отрицания результата команды (оно или истина или ложь). Далее для
каждого primary у нас есть структура, которая включает в себя поля
команды и добавляет туда ещё свои специфичные. Так как у нас
функция-обработчик ждёт указатель на struct command а у нас во всех
структурах *_primary поле cmd идёт первым, мы можем передавать ей
указатель на структуру *_primary - у них один и тот же адрес с cmd. Поле
cmd первое в структуре поэтому адреса одинаковые. Чтобы Си не ругался,
сделаем преобразование явное.
int
find_command(struct command *cmd)
{
int res = 0;
struct find_primary *prm;
prm = (struct find_primary *) cmd;
...
return res;
}
/* Command group */
struct cgroup {
/* pointer to next group in OR list */
struct cgroup *next;
/* struct command *grp[ncmds] */
struct command **grp;
/* number of commands in the group */
size_t ncmds;
/* number of pointers in grp */
size_t nalloc;
};
struct command {
/* pointer to next command in the group */
struct command *next;
/* pointer to command */
int (fn)(struct command *cmd);
/* shoud we negate the command? */
int negate;
};
struct name_primary {
struct command cmd;
char *pattern;
};
struct perm_primary {
struct command cmd;
mode_t mode;
int exact_match;
};
struct type_primary {
struct command cmd;
enum {
F_CHAR = 'c',
F_BLOCK = 'b',
F_DIR = 'd',
F_LINK = 'l',
F_FIFO = 'f',
F_SOCK = 's'
} type;
};
struct size_primary {
struct command cmd;
/* 0, 1, or -1 is no flag, '+' or '-' respectively */
int sign;
/* file size */
size_t size;
};
Для скобочного выражения нам надо делать рекурсию, тогда получается что
выражение в скобках это тоже команда, но у неё будет свой список из
групп команд а те в свою очередь тоже могут быть скобочными выражениями
и могут иметь свои такие же и т.д.
struct type_quoted {
/* command data */
struct command cmd;
/* list of command groups */
struct cgroup *list;
};
Для вычисления выражения пишем функцию, которая будет возвращать целое
(истина/ложь) и получает всего один аргумент, это список из групп команд.
int eval_expr(struct cgroup *grp);
На первый взгляд так. Все алгоритмы дальше встают на свои места.
В теории, можно было бы и группы команд сделать в массиве указателей а
не списком, можно было и команды сделать не в массиве указаталей а
списком, всё это вариации "на тему" но сути не меняет (меняется скорость
при большом количестве выражений).
Дальше можно "усилить" задачу, и делать некоторую оптимизацию, потому
что некоторые primaries вычисляются быстрее, некоторые медленнее и т.д.
Простор для творчества большой.
Т.к. уже 4 утра и очень хочется спать, ищите у меня ошибки.
--
Г.А.
Лена Довжко пишет:
> Здравствуйте.
> Вы хотели рассказать как реализовывать интерпретатор для find ?(тока без кода)
> И куда лучше все записывать, чтобы потом проверять удобно было.( а то ведь от порядка скобок и смысл выражения зависит и много их может быть)
> Может структуру какую, где будут указтель на функциию обработчик и параметры? А потом их вызывать в определенном порядке.
> (Личное письмо, было отправлено случайно, использовался браузер, а не почтовый клиент, и в поле кому был не тот адрес)
>
> _______________________________________________
> cdev mailing list
> cdev на wiki.syktsu.ru
> http://wiki.syktsu.ru/cgi-bin/mailman/listinfo/cdev
Подробная информация о списке рассылки cdev