Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi
- Название:Фундаментальные алгоритмы и структуры данных в Delphi
- Автор:
- Жанр:
- Издательство:ДиаСофтЮП
- Год:2003
- ISBN:ISBN 5-93772-087-3
- Рейтинг:
- Избранное:Добавить в избранное
-
Отзывы:
-
Ваша оценка:
Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi краткое содержание
Книга "Фундаментальные алгоритмы и структуры данных в Delphi" представляет собой уникальное учебное и справочное пособие по наиболее распространенным алгоритмам манипулирования данными, которые зарекомендовали себя как надежные и проверенные многими поколениями программистов. По данным журнала "Delphi Informant" за 2002 год, эта книга была признана сообществом разработчиков прикладных приложений на Delphi как «самая лучшая книга по практическому применению всех версий Delphi».
В книге подробно рассматриваются базовые понятия алгоритмов и основополагающие структуры данных, алгоритмы сортировки, поиска, хеширования, синтаксического разбора, сжатия данных, а также многие другие темы, тесно связанные с прикладным программированием. Изобилие тщательно проверенных примеров кода существенно ускоряет не только освоение фундаментальных алгоритмов, но также и способствует более квалифицированному подходу к повседневному программированию.
Несмотря на то что книга рассчитана в первую очередь на профессиональных разработчиков приложений на Delphi, она окажет несомненную пользу и начинающим программистам, демонстрируя им приемы и трюки, которые столь популярны у истинных «профи». Все коды примеров, упомянутые в книге, доступны для выгрузки на Web-сайте издательства.
Фундаментальные алгоритмы и структуры данных в Delphi - читать онлайн бесплатно полную версию (весь текст целиком)
Интервал:
Закладка:
Листинг 10.5. Программа синтаксического анализа регулярных выражений type
TtdRegexParser = class private
FRegexStr : string;
{$IFDEF Delphi1}
FRegexStrZ: PAnsiChar;
{$ENDIF}
FPosn : PAnsiChar;
protected
procedure rpParseAtom;
procedure rpParseCCChar;
procedure rpParseChar;
procedure rpParseCharClass;
procedure rpParseCharRange;
procedure rpParseExpr;
procedure rpParseFactor;
procedure rpParseTerm;
public
constructor Create(const aRegexStr : string);
destructor Destroy; override;
function Parse(var aErrorPos : integer): boolean;
end;
constructor TtdRegexParser.Create(const aRegexStr : string);
begin
inherited Create;
FRegexStr := aRegexStr;
{$IFDEF Delphi1}
FRegexStrZ := StrAlloc(succ( length (aRegexStr)));
StrPCopy(FRegexStrZ, aRegexStr);
{$ENDIF}
end;
destructor TtdRegexParser.Destroy;
begin
{$IFDEF Delphi1}
StrDispose(FRegexStrZ);
{$ENDIF}
inherited Destroy;
end;
function TtdRegexParser.Parse(var aErrorPos : integer): boolean;
begin
Result := true;
aErrorPos := 0;
{$IFDEF Delphi1}
FPosn := FRegexStrZ;
{$ELSE}
FPosn := PAnsiChar (FRegexStr);
{$ENDIF}
try
rpParseExpr;
if (FPosn^ <> #0) then begin
Result := false;
{$IFDEF Delphi1}
aErrorPos := FPosn - FRegexStrZ + 1;
{$ELSE}
aErrorPos := FPosn - PAnsiChar(FRegexStr) + 1;
{$ENDIF}
end;
except on E: Exception do
begin
Result false;
{$IFDEF Delphi1}
aErrorPos := FPosn - FRegexStrZ + 1;
{$ELSE}
aErrorPos := FPosn - PAnsiChar (FRegexStr) + 1;
{$ENDIF}
end;
end;
end;
procedure TtdRegexParser.rpParseAtom;
begin
case FPosn^ of
'(' : begin
inc(FPosn);
writeln (' Open paren');
rpParseExpr;
if (FPosn^ <> ')') then
raise Exception.Create('Regex error: expecting a closing parenthesis');
inc(FPosn);
writeln (' close paren');
end;
'[' : begin
inc(FPosn);
if (FPosn^ = 'A') then begin
inc(FPosn);
writeln('negated char class');
rpParseCharClass;
end
else begin
writeln('normal char class');
rpParseCharClass;
end;
inc(FPosn);
end;
'.' : begin
inc(FPosn);
writeln (' any character');
end;
else
rpParseChar;
end; {case}
end;
procedure TtdRegexParser.rpParseCCChar;
begin
if (FPosn^ = #0) then
raise Exception.Create('Regex error: expecting a normal character, found null terminator');
if FPosn^ in [']', '-'] then
raise Exception.Create('Regex error: expecting a normal character, found a metacharacter');
if (FPosn^ = '\') then begin
inc(FPosn);
writeln(' escaped ccchar ', FPosn^ );
inc(FPosn);
end
else begin
writeln('ccchar ', FPosn^ );
inc(FPosn);
end;
end;
procedure TtdRegexParser.rpParseChar;
begin
if (FPosn^ = #0) then
raise Exception.Create(
'Regex error: expecting a normal character, found null terminator');
if FPosn^ in Metacharacters then
raise Exception.Create(
'Regex error: expecting a normal character, found a metacharacter' );
if (FPosn^ = '\') then begin
inc(FPosn);
writeln (' escaped char ', FPosn^ );
inc(FPosn);
end
else begin
writeln('char ', FPosn^ );
inc(FPosn);
end;
end;
procedure TtdRegexParser.rpParseCharClass;
begin
rpParseCharRange;
if (FPosn^ <> ']') then
rpParseCharClass;
end;
procedure TtdRegexParser.rpParseCharRange;
begin
rpParseCCChar;
if (FPosn^ = '-') then begin
inc(FPosn);
writeln ('-—range to—-');
rpParseCCChar;
end;
end;
procedure TtdRegexParser.rpParseExpr;
begin
rpParseTerm;
if (FPosn^ = '|' ) then begin
inc(FPosn);
writeln('alternation');
rpParseExpr;
end;
end;
procedure TtdRegexParser.rpParseFactor;
begin
rpParseAtom;
case FPosn^ of
'?' : begin
inc(FPosn);
writeln(' zero or one');
end;
'*' : begin
inc(FPosn);
writeln(' zero or more');
end;
'+' : begin
inc(FPosn);
writeln(' one or more');
end;
end; {case}
end;
Полный исходный код класса TtdRegexParser можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDRegex.pas;
Если вы просмотрите листинг 10.5, то увидите, что эта программа синтаксического анализа всего лишь выводит текущий грамматический элемент на экран монитора и генерирует исключение в ситуации, когда можно констатировать, что регулярное выражение неверно. Естественно, ни одно из этих действий не будет выполняться в реальной рабочей среде. Первое не будет выполняться потому, что нашей целью является компиляция регулярного выражения в код NFA-автомата, а второе - потому, что исключения не следует использовать для проверки, поскольку это слишком неэффективно. Тем не менее, этот код может служить иллюстрацией общей структуры упрощенного нисходящего синтаксического анализатора: вначале выполняется разработка грамматических правил, а затем достаточно простым образом они преобразуются в код.
Нам осталось только рассмотреть реализацию метода ParseTerm. По сравнению с уже реализованными методами эта реализация несколько сложнее. Проблема состоит в том, что согласно формулировке продукции, <���член> является либо <���коэффициентом>, либо <���коэффициентом>, за которым следует еще один <���член> (т.е. имеет место конкатенация). Не существует никакой операции, типа знака плюса или чего-то подобного, которая бы связывала два элемента. Если бы такая операция существовала, метод ParseTerm можно было бы реализовать так же, как были реализованы остальные методы ParseХхххх. Однако, поскольку никакого метасимвола выполнения конкатенации не существует, приходится прибегнуть к другому средству.
Рассмотрим проблему более внимательно. Предположим, что мы выполняем синтаксический анализ регулярного выражения "ab". Его нужно было бы проанализировать в качестве <���выражения>, что означает анализ в качестве <���члена>, затем <���коэффициента>, затем <���элемента>, а затем <���символа>. В результате была бы выполнена обработка фрагмента "а". Затем грамматический разбор был бы продолжен, пока снова не было бы достигнуто определение <���члена>, в котором говорится, что за первым <���коэффициентом> может следовать еще один <���член>. Продолжая анализ продукции, мы идентифицируем фрагмент "b" как <���символ>, и на этом выполнение задачи завершается.
Все сказанное звучит достаточно просто. Так в чем же трудность? Выполним эти же действия для выражения "(а)". На этот раз синтаксический анализ продукций выполняется до тех пор, пока не будет достигнуто определение, согласно которому <���элемент> может состоять из "(и, за которой следует <���выражение>, а за ним ")". Таким образом, обработка "С завершается и снова начинается с синтаксического анализа верхней грамматической конструкции - < выражения>. Снова выполним нисходящий анализ: <���выражение>, затем <���член>, затем <���коэффициент>, затем <���элемент> и, наконец, <���символ>. В результате выполняется обработка фрагмента "а". Снова возвращаясь к началу, мы встречаем альтернативное определение продукции <���член>. Так почему бы на этот раз нам не обратиться к альтернативной ветви и не попытаться выполнить синтаксический анализ конкатенации?
Очевидно, что подобное делать нельзя, поскольку на этот раз текущим символом является ")". В первом примере мы решили выполнить синтаксический анализ конкатенации, поскольку текущим символом был "b", но на сей раз им является ")". Прежде чем решить, выполнять ли синтаксический анализ еще одного сцепленного <���члена>, необходимо быстро проанализировать текущий символ. Если его можно считать началом еще одного <���элемента>, то мы продолжаем обработку и анализируем его в качестве такового. Если же нет, мы считаем, что что-то другое (а именно вызывающий метод) выполнит с ним какие-либо действия, и что конкатенация отсутствует.
Этот процесс называют разрывом грамматического правша (breaking the grammar). Мы должны предположить, что если в данном случае конкатенация имеет место, текущий символ будет служить начальным символом элементах. Иначе говоря, если текущий символ - ".", "(" "[", или обычный символ, мы должны выполнить синтаксический анализ еще одного <���члена>. Если же нет - мы считаем, что конкатенация отсутствует, и осуществляем выход из метода ParseTerm. Для определения того, что нужно делать с продукцией <���член> (продукцией "более высокого" уровня), мы используем информацию продукции <���элемент> (продукции "более низкого" уровня). Излишне повторять, что необходимость в таком подходе возникает только по причине отсутствия метасимвола конкатенации.
Читать дальшеИнтервал:
Закладка:
