который выполняет синтаксический анализ, обычно называют синтаксическим анализатором (parser).
Использование конечного автомата: синтаксический анализ
Чтобы лучше понять весь процесс, рассмотрим пример. Предположим, что требуется разработать алгоритм, который должен извлекать отдельные слова из строки текста. Извлекаемые слова будут помещаться в список строк. Более того, желательно, чтобы внутри строки текст, заключенный в кавычки, воспринимался как одно слово. Т.е., если имеется строка:
Не said, 'State machines?'
процедура должна игнорировать знаки препинания и пробелы и возвращать следующее:
Не
said
'State machines?'
Обратите внимание, что пробел и вопросительный знак внутри заключенного в кавычки текста остались без изменений.
Простейший способ реализации этого конкретного алгоритма - использование конечного автомата. Конечный автомат (state machine) - это система (обычно цифровая), которая переходит из одного состояния в другое в соответствии с принимаемыми ею входными данными (сигналами). Смена состояний называется переходом (trAnsition). Конечный автомат можно представить специальной блок-схемой. Блок схема рассматриваемого алгоритма показана на рис. 10.1.
Показанный на рисунке конечный автомат имеет три состояния: А, В и С. Работа блок-схемы начинается с состояния A. В этом состоянии выполняется считывание символа из входной строки. Если этот символ - двойная кавычка, осуществляется переход в состояние В. Если символ является пробелом или знаком препинания, выполняется переход в состояние С. Если это любой другой символ, конечный автомат остается в состоянии А (это показано петлей).
После перехода в состояние В считывание символов продолжается в нем до тех пор, пока не будет считан символ закрывающей двойной кавычки. В этот момент происходит переход обратно в состояние A.
С другой стороны, если был выполнен переход в состояние С, считывание символов продолжается в этом состоянии до тех пор, пока не произойдет одно из двух: либо не будет выполнено считывание символа двойной кавычки, в результате чего произойдет переход в состояние В, либо не будет выполнено считывание символа, который не является ни двойной кавычкой, ни пробелом, ни знаком препинания, в результате чего будет осуществлен переход в состояние A.
Рисунок 10.1. Конечный автомат извлечения слов из строки
Во время перехода может требоваться также выполнение какого-либо действия. Предположим, что мы используем строку для накапливания символов текущего слова. Первоначальный переход в состояние А очистит эту строку. Циклический переход из состояния А в состояние А допишет символ к текущему слову. Переход из состояния А в состояние В вначале добавит текущее слово (если таковое имеется) к списку строк, а затем установит в качестве текущего слова открывающую двойную кавычку. Циклический переход из состояния В в это же состояние допишет символ к текущему слову. Переход из состояния В обратно в состояние А допишет закрывающую двойную кавычку к текущему слову, добавит его в список строк, а затем очистит текущее слово. При переходе из состояния А в состояние С текущее слово добавляется в список строк, а затем очищается. Переход из состояния С в это же состояние не вызывает никаких действий (именно во время этого перехода происходит действительное отбрасывание пробелов и знаков препинания). При переходе из состояния С в состояние А значение текущего слова устанавливается равным считываемому символу. При переходе из состояния С в состояние В текущее слово устанавливается равным открывающей двойной кавычке.
Проанализировав рисунок 10.1, как это описано в предыдущем абзаце, легко убедиться, что конечный автомат прекрасно реализует рассматриваемый алгоритм.
Переход в состояние А; очистка слова
Считывание ' H1; сохранение состояния А; слово = ' H'
Считывание 'e'; сохранение состояния А; слово = ' Не'
Считывание ' '; переход в состояние С; вывод слова 'Не', очистка слова
Считывание 's'; переход в состояние А; слово = ' s'
Считывание 'a'; сохранение состояния А; слово = ' sa'
Считывание 'i'; сохранение состояния А; слово - 'sai'
Считывание 'd';сохранение состояния А; слово = 'said'
Считывание ','; переход в состояние С; вывод слова 'said', очистка слова
Считывание ' '; сохранение состояния С
Считывание ''';переход в состояние А;слово = '''
Считывание 'S';сохранение состояния В; слово = ''S'
и. т.д.
Однако, блок-схема конечного автомата, показанная на рис. 10.1, обладает еще одной особенностью, о которой еще ничего не было сказано. Состояния А и С обозначены двойными окружностями, в то время как состояние В - одинарной. По соглашению в диаграммах конечных автоматов двойные окружности используются для обозначения конечного состояния (называемого также состоянием останова (halt state) или поглощающим состоянием (accepting state)). Когда входная строка полностью считана, конечный автомат оказывается в особом состоянии (применительно к приведенному выше примеру строки заключительное состояние конечного автомата - состояние А). Если заключительное состояние является конечным, говорят что конечный автомат поглощает входную строку. Независимо от того, какие символы (или, точнее, лексемы (tokens)) были найдены во входной строке и какие при этом были осуществлены переходы, конечный автомат 'понимает' строку. С другой стороны, если бы конечный автомат прекратил работу в незавершенном состоянии, строка не была бы принята (поглощена) и конечный автомат не понял бы ее.
В данном случае состояние В не является поглощающим состоянием. Что это означает на практике? Если в момент, когда входная строка исчерпана, конечный автомат находится в состоянии В, это означает, что был считан первый символ двойной кавычки, но не второй. Т.е. конечный автомат считывает строку, содержащую текст с непарным символом двойной кавычки. В зависимости от строгости алгоритма, эта ситуация может считаться ошибкой либо просто игнорироваться. В алгоритме, изображенном на рис. 10.1, она считается ошибкой.
Если говорить об ошибках, хотя в данном конкретном примере эта ситуация не отражена, возможно состояние, когда переход к конкретному символу или лексеме невозможен. Это немедленно привело бы к ошибке. В дальнейшем будет показано, как это свойство можно встроить в сам конечный автомат.
Вычертив блок-схему, теперь ее необходимо реализовать. Для простоты понимания мы немного изменим ее, чтобы считывание входной строки управляло конечным автоматом, а не чтобы каждое состояние приводило к считыванию следующего символа из входной строки. Это облегчит понимание процесса выхода из конечного автомата.
Код реализации конечного автомата, показанного на рис. 10.1, приведен в листинге 10.1 (полный исходный код можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDStates.pas). Обратите внимание, что было решено назвать состояния не абстрактно А, В и С, как на рисунке, а с использованием описательных имен ScanNormal, ScanQuoted и ScanPunctuation (соответственно, СчитываниеОбычныхСимволов, СчитываниеКавычек и
