Считывание '"';переход в состояние А;слово = '"'
Считывание 'S';сохранение состояния В; слово = "'S'
и. т.д.
Однако, блок-схема конечного автомата, показанная на рис. 10.1, обладает еще одной особенностью, о которой еще ничего не было сказано. Состояния А и С обозначены двойными окружностями, в то время как состояние В - одинарной. По соглашению в диаграммах конечных автоматов двойные окружности используются для обозначения конечного состояния (называемого также состоянием останова (halt state) или поглощающим состоянием (accepting state)). Когда входная строка полностью считана, конечный автомат оказывается в особом состоянии (применительно к приведенному выше примеру строки заключительное состояние конечного автомата - состояние А). Если заключительное состояние является конечным, говорят что конечный автомат поглощает входную строку. Независимо от того, какие символы (или, точнее, лексемы (tokens)) были найдены во входной строке и какие при этом были осуществлены переходы, конечный автомат "понимает" строку. С другой стороны, если бы конечный автомат прекратил работу в незавершенном состоянии, строка не была бы принята (поглощена) и конечный автомат не понял бы ее.
В данном случае состояние В не является поглощающим состоянием. Что это означает на практике? Если в момент, когда входная строка исчерпана, конечный автомат находится в состоянии В, это означает, что был считан первый символ двойной кавычки, но не второй. Т.е. конечный автомат считывает строку, содержащую текст с непарным символом двойной кавычки. В зависимости от строгости алгоритма, эта ситуация может считаться ошибкой либо просто игнорироваться. В алгоритме, изображенном на рис. 10.1, она считается ошибкой.
Если говорить об ошибках, хотя в данном конкретном примере эта ситуация не отражена, возможно состояние, когда переход к конкретному символу или лексеме невозможен. Это немедленно привело бы к ошибке. В дальнейшем будет показано, как это свойство можно встроить в сам конечный автомат.
Вычертив блок-схему, теперь ее необходимо реализовать. Для простоты понимания мы немного изменим ее, чтобы считывание входной строки управляло конечным автоматом, а не чтобы каждое состояние приводило к считыванию следующего символа из входной строки. Это облегчит понимание процесса выхода из конечного автомата.
Код реализации конечного автомата, показанного на рис. 10.1, приведен в листинге 10.1 (полный исходный код можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDStates.pas). Обратите внимание, что было решено назвать состояния не абстрактно А, В и С, как на рисунке, а с использованием описательных имен ScanNormal, ScanQuoted и ScanPunctuation (соответственно, СчитываниеОбычныхСимволов, СчитываниеКавычек и СчитываниеЗнаковПрепинания).
Листинг 10.1. Извлечение слов из строки
procedure TDExtractWords(const S : string; aList : TStrings);
type
TStates = (ScanNormal, ScanQuoted, ScanPunctuation);
const
WordDelim= ' !<>[]{}(),./?;:-+=*&';
var
State : TStates;
Inx : integer;
Ch : char;
CurWord : string;
begin
{инициализация путем очистки списка строк и начало работы в состоянии ScanNormal с пустым словом}
Assert(aList <> nil, 'TDExtractWords: list is nil');
aList.Clear;
State := ScanNormal;
CurWord := '';
{считывание всех символов строки}
for Inx := 1 to length(S) do
begin
{get the next character}
Ch := S[Inx];
{обработка в зависимости от состояния}
case State of
ScanNormal : begin
if (Ch = '"') then begin
if (CurWord <> '') then
aList.Add(CurWord);
CurWord := '';
State := ScanQuoted;
end
else
if (TDPosCh(Ch, WordDelim) <> 0) then begin
if (CurWord <> '') then begin
aList.Add(CurWord);
CurWord := '''';
end;
State := ScanPunctuation;
end else
CurWord := CurWord + Ch;
end;