Синтаксичний розбір рядків і кінцеві автомати
Андрій Боровський
У цій статті мова піде про те, як
аналізувати інформацію, передану у вигляді послідовності символів (рядок)
і виділяти з неї значущі елементи. Ми розглянемо порівняно прості
ситуації, з якими програмістам доводиться стикатися при рішенні самих
різних завдань: розбір виразів з простою синтаксичною структурою, але з
досить вільними правилами запису.
Припустимо, у програмі, яку ви пишете, потрібен
модуль, що аналізує текст HTML-сторінки. Ми напишемо функцію, яка, отримавши
рядок, що містить тег, отримувала б з цього рядка всі атрибути тега та їх
значення. Структуру тега можна схематично представити наступним чином:
<ТЕГ атрібут1 = "значення" атрібут2 = "значення" ...>
На перший погляд завдання здається дуже простою, однак ситуація ускладнюється
через досить м'яких правил мови HTML. Між ім'ям атрибута, знаком
рівності і значенням може стояти будь-яке число розділових символів
(прогалин, символів табуляції і навіть символів переходу на нову строку), або ж
розділові символи можуть взагалі бути відсутнім. Значення атрибутів можуть
бути або у лапках, або ні, при цьому значення, укладене в
подвійні лапки, може містити символи одинарних лапок, і навпаки. Крім
того, не всім атрибутів тегів присвоюються значення.
Для вирішення зазначеної проблеми ми напишемо функцію
ParseTag, що аналізує переданий їй тег й створює списки атрибутів тега і
їх значень. Функція ParseTag діє за принципом кінцевого автомата.
Кінцеві автомати та подібні їм структури широко застосовуються при обробці
рядків. Сфери найбільш частого застосування кінцевих автоматів входить пошук
підрядка по заданому зразком, обробку регулярних виразів (regular
expressions), лексичний та синтаксичний аналіз. Кінцеві автомати широко
застосовуються в трансляторах і інтерпретатора (не кажучи вже про такі завдання,
як проектування логічних пристроїв).
Суворе визначення кінцевих автоматів можна знайти в
будь-якому підручнику з теорії алгоритмів, ми ж тут обмежимося інтуїтивним
визначенням. У кожен даний момент часу кінцевий автомат може перебувати
в одному з можливих станів (число станів, у яких може знаходитися
кінцевий автомат - звичайно). Автомат послідовно зчитує символи вхідного
тексту (рядки). Кожен лічений символ або переводить автомат в нове
стан, або залишає його в колишньому стані. Формально автомат можна описати
за допомогою функції переходів. Аргументами цієї функції є попереднє
стан автомата і черговий лічений символ, а значенням - новий стан
автомата.
Безліч станів для нашого автомата включає:
ReadTag - читає ім'я тега;
WaitAttr - очікує ім'я атрибута;
WaitAttrOrEq - очікує ім'я атрибута або символ '=';
ReadAttr - читає ім'я атрибута;
WaitValue - очікує значення ознаки;
ReadValue - читає значення атрибуту без лапок;
ReadValueSQ - читає значення атрибута в одинарних лапках;
ReadValueDQ - читає значення атрибута в подвійних
лапках.
Дотримуючись термінології кінцевих автоматів, ми можемо
назвати стану WaitAttr, WaitAttrOrEq, ReadAttr і ReadValue допускають.
Це означає, що якщо після обробки переданої рядка автомат знаходиться в
будь-якому іншому стані, отже, тег містить помилку (автомат не перевіряє,
завершується чи рядок символом '>', це - завдання блоку, що викликає функцію
ParseTag).
Процес програмної реалізації автомата можна
спростити, побудувавши для нього діаграму переходів. Далі наводиться діаграма
переходів для нашого автомата. Цифри на діаграмі відповідають номерам
станів, перерахованих вище.
Малюнок 1
Пояснення до діаграми:
a - символ-розділювач
b - будь-який символ окрім роздільник
c - символ "="
d - будь-який символ окрім роздільник або символ
"="
e - за будь-символ крім роздільник і лапок
f - символ одинарних лапок
g - символ подвійних лапок
Нижче наводиться текст функції ParseTag і
допоміжної функції GetSubString. У функції ParseTag є чотири параметри:
рядок, що містить тег, укладений у '<' і '>', рядок, у якому
повертається ім'я тега, і об'єкти типу TStringList, що містять імена і значення
атрибутів відповідно. Якщо цього атрибуту не зіставляючи ніяке
значення, в списку значень назви ознаки відповідає порожній рядок. У
разі успішного виконання функція повертає значення 0, інакше --
1.
Автомат реалізований в тілі циклу функції ParseTag.
Додавання нового елемента в список здійснюється в момент переходу з
стану ReadXXX в який-небудь інший стан. Крім цього в цикл добавлена
перевірка помилок синтаксису, наприклад, двох символів '=', наступних підряд.
Після завершення циклу ми аналізуємо стану автомата. Якщо автомат
знаходиться в одному з станів ReadXXX, відбувається додавання останнього
елемента у відповідний список. Якщо автомат не знаходиться ні в одному з допускають
станів, функція повертає повідомлення про синтаксичну помилку.
function GetSubString (const S: String; Start, Stop: Integer):
String;
begin
SetLength (Result, Stop-Start);
Move (S [Start], Result [1],
Stop-Start);
end;
function ParseTag (const Tag: String; var TagName: String;
Attrs, Values: TStringList):
Integer;
type
// Можливі стану
TState = (ReadTag, WaitAttr,
WaitAttrOrEq, ReadAttr, WaitValue,
ReadValue, ReadValueSQ,
ReadValueDQ);
const
// Значення, що повертаються функцією GetLink
resOK = 0;// розбір пройшов успішно
resBadSyntax = -1;// синтаксична помилка
// Набір можливих розділових символів
Delimeters = [ '', # 9, # 13, # 10];
var
State: TState;
StartPos, i: Integer;
begin
Result: = resOK;
// очищаємо список елементів
Attrs.Clear;
Values.Clear;
State: = ReadTag;// вхідна стан автомата
i: = 2;// пропускаємо символ'<'
while (Tag [i ]<>'>')
and (i
begin
case State of
ReadTag:
if Tag [i] in Delimeters
then
begin
// читання імені тега закінчено
TagName: =
GetSubString (Tag, StartPos, i);
State: = WaitAttr;
end;
WaitAttr:
if (Tag [i] in Delimeters)
= False then
begin
if Tag [i] = '=' then
begin
Result: =
resBadSyntax;
Exit;
end;
StartPos: = i;
State: = ReadAttr;
end;
ReadAttr:
if (Tag [i] in Delimeters)
or (Tag [i] = '=') then
begin
// читання імені атрибута закінчено,
додаємо ім'я атрибута до списку
Attrs.Add (GetSubString (Tag,
StartPos, i ));
if Tag [i] = '=' then
State: = WaitValue
else State: =
WaitAttrOrEq;
end;
WaitAttrOrEq:
if (Tag [i] in Delimeters)
= False then
begin
if Tag [i] = '=' then
State: = WaitValue else
begin
// починається читання назви ознаки
// попереднього атрибути не
присвоєно ніяких значень,
// додаємо пустий рядок в список
Values
Values.Add ('');
State: = ReadAttr;
StartPos: = i;
end;
end;
WaitValue:
if (Tag [i] in Delimeters)
= False then
begin
if Tag [i] = '=' then
begin
// два символи '=' поспіль
Result: = resBadSyntax;
Exit;
end;
if Tag [i] = ' "'
then
begin
// читання значення почнеться з
наступного символу після лапок:
StartPos: = i + 1;
State: = ReadValueDQ;
end else
if Tag [i] =''''then
begin
// читання значення почнеться з наступного символу
після лапок:
StartPos: = i + 1;
State: = ReadValueSQ;
end else
begin
// читання значення без лапок
StartPos: = i;
State: = ReadValue;
end;
end;
ReadValue:
if Tag [i] in Delimeters
then
begin
// читання значення закінчено
Values.Add (GetSubString (Tag, StartPos, i ));
State: = WaitAttr;
end;
ReadValueDQ:
if Tag [i] = ' "' then
begin
// читання значення в подвійних лапках
закінчено
Values.Add (GetSubString (Tag,
StartPos, i ));
State: = WaitAttr;
end;
ReadValueSQ:
if Tag [i] =''''then
begin
// читання значення в одинарних
лапках закінчено
Values.Add (GetSubString (Tag,
StartPos, i ));
State: = WaitAttr;
end;
end;// case State of
Inc (i);
end;// while
(Body [i ]<>'>') and (i
// перевіряємо стан автомата після обробки рядка
// останнім символом рядка повинен бути
'>'
case State of
ReadValue:
Values.Add (GetSubString (Tag, StartPos, i));
ReadAttr: Attrs.Add (GetSubString (Tag,
StartPos, i ));
ReadTag: TagName: =
GetSubString (Tag, StartPos, i);
WaitAttr, WaitAttrOrEq:;//
нічого не робимо
else Result: = resBadSyntax;// інші стани неприпустимі
end;
end;
Однією з важливих особливостей такого підходу до розбору
строк є те, що аналіз виконується в міру зчитування символів, з
використанням інформації про поточний символі і символів, прочитаних раніше. Це
дозволяє вести обробку даних, що передаються по деякому послідовному
каналу, безпосередньо в процесі їх надходження.
Фактично представлена функція виконує дві
операції: виділяє в переданої рядку синтаксичні елементи (tokens) і
визначає, що являє собою цей елемент (ім'я тега, ім'я атрибуту,
значення атрибута). Рішення про те, чим є наступний елемент, що приймається
заздалегідь, на підставі даних про попередньому елементі і простих правил: за ім'ям
тега слід ім'я атрибута; за ім'ям атрибута слід або ім'я атрибута, або
символ '='; за символом '=' слід значення атрибута.
Процедури, засновані на кінцевих автоматах, широко
застосовуються для перевірки синтаксису. В якості прикладу розглянемо функцію
CheckMath, яка виконує синтаксичний аналіз математичного вирази:
function CheckMath (const S: String): Integer;
type
TState = (Start, InDigit,
AfterDigit, InOp, InLPrnt, InRPrnt);
const
resLPrntMissing = -1;
resRPrntMissing = -2;
var
State: TState;
i, ParCount: Integer;
begin
Result: = 0;
ParCount: = 0;// лічильник дужок
State: = Start;
for i: = 1 to Length (S) do
case State of
Start:// вхідна стан
case S [i] of
'':;// стан не змінюється
'0 '.. '9': State: = InDigit;
'-': State: = InOp;// символ '-'
перед числом або дужкою
'(':
begin
Inc (ParCount);
State: = InLPrnt;
end;
else
begin
// Синтаксична помилка
Result: = i;
Exit;
end;
end;
InDigit:
case S [i] of
'0 '.. '9':;// стан не змінюється
'+', '-', '*', '/':
State: = InOp;
')':
begin
Dec (ParCount);
State: = InRPrnt;
end;
'': State: =
AfterDigit;
else
begin
Result: = i;
Exit;
end;
end;
AfterDigit:
case S [i] of
'':;
'+', '-', '*', '/':
State: = InOp;
')':
begin
Dec (ParCount);
State: = InRPrnt;
end;
else
begin
Result: = i;
Exit;
end;
end;
InOp:
case S [i] of
'':;
'0 '.. '9': State: =
InDigit;
'(':
begin
Inc (ParCount);
State: = InLPrnt;
end;
else
begin
Result: = i;
Exit;
end;
end;
InLPrnt:
case S [i] of
'0 '.. '9': State: =
InDigit;
'-': State: = InOp;
'(': Inc (ParCount);
'':;
else
begin
Result: = i;
Exit;
end;
end;
InRPrnt:
case S [i] of
'+', '-', '*', '/':
State: = InOp;
')': Dec (ParCount);
'':;
else
begin
Result: = i;
Exit;
end;
end;
end;// case State of
if State in [InLPrnt, InOp]
then// Неприпустимі стану
Result: = Length (S);
if ParCount> 0 then Result
: = ResRPrntMissing else
if ParCount <0 then Result
: = ResLPrntMissing;
end;
Вхідна математичний вираз може містити
цілочисельні константи, символи арифметичних операцій і дужки. Між
символами операцій, дужками і числами допустимо будь-яку кількість пробілів.
Функція CheckMath повертає значення 0, якщо передане їй вираз не містить
помилок. Якщо вираз містить помилку, функція повертає позитивне число,
відповідне позиції символу, в якій було виявлено помилку. Якщо число
відкритих дужок не дорівнює числу закритих, функція повертає або -1, або -2, в
залежно від того, яких дужок не вистачає.
У даній функції задіяні наступні стани:
Start - початковий стан;
InDigit - прочитана цифра;
AfterDigit - прочитаний роздільник після цифри;
InOp - прочитаний символ арифметичної операції;
InLPrnt - прочитана відкриває дужка;
InRPrnt - прочитана закриває дужка.
Символи пробілу не змінюють попереднього стану, за
винятком стану InDigit. Остання зроблено для того, щоб не допустити
появи прогалин між символами, що становлять чисельну константу.
Список літератури
Для підготовки даної роботи були використані
матеріали з сайту http://www.rsdn.ru/
