Краткие
теоретические сведения
Лексический анализатор (или сканер)
- это часть компилятора, которая читает
литеры программы на исходном языке и
строит из них слова (лексемы) исходного
языка. На вход лексического анализатора
поступает текст исходной программы, а
выходная информация передается для дальнейшей
обработки компилятором на этапе синтаксического
анализа и разбора.
В большинстве компиляторов лексический
и синтаксический анализаторы - это взаимосвязанные
части. Лексический разбор исходного текста
в таком варианте выполняется поэтапно
так, что синтаксический анализатор, выполнив
разбор очередной конструкции языка, обращается
к сканеру за следующей лексемой. При этом
он может сообщить информацию о том, какую
лексему следует ожидать. В процессе разбора
может даже происходить “откат назад”,
чтобы выполнить анализ текста на другой
основе. В дальнейшем будем исходить из
предположения, что все лексемы могут
быть однозначно выделены сканером на
этапе лексического разбора
Работу синтаксического и лексического
анализаторов можно изобразить в виде
схемы на рис. 2
Рис.
2. Взаимодействие синтаксического и лексического
анализаторов.
Лексема |
Тип лексемы |
Значение |
begin |
Ключевое слово |
X1 |
for |
Ключевое слово |
X2 |
i |
Идентификатор |
i : 1 |
:= |
Знак присваивания |
|
1 |
Целочисленная константа |
1 |
to |
Ключевое слово |
X3 |
N |
Идентификатор |
N : 2 |
do |
Ключевое слово |
X4 |
fg |
Идентификатор |
fg : 3 |
:= |
Знак присваивания |
|
fg |
Идентификатор |
fg : 3 |
* |
Знак арифметической операции |
|
0.5 |
Вещественная константа |
0.5 |
Вот пример фрагмента текста программы
на языке Паскаль и соответствующей ему
таблицы лексем (табл. 1):
Вот пример фрагмента текста программы
на языке Паскаль и соответствующей ему
таблицы лексем (табл. 1):
...
begin
for i:=1 to N do
fg := fg * 0.5
...
Таблица 1
Таблица лексем программы
Вид представления информации после
выполнения лексического анализа целиком
зависит конструкции компилятора. Но в
общем виде ее можно представить как таблицу
лексем, которая в каждой строчке должна
содержать информацию о виде лексемы,
ее типе и, возможно, значении. Обычно такая
таблица имеет два столбца: первый - строка
лексемы, второй - указатель на информацию
о лексеме, может быть включен и третий
столбец - тип лексем.
ПРИНЦИП РАБОТЫ
Лексический анализатор имеет дело с
константами и идентификаторами . Язык
констант и идентификаторов в большинстве
случаев является регулярным - то есть,
может быть описан с помощью регулярных
(праволинейных или леволинейных) грамматик
. Распознавателями для регулярных языков
являются конечные автоматы.
Недетерминированный конечный автомат
задается пятеркой:
M=(Q,S,d,q0,F),
где:
Q - конечное множество состояний автомата;
S - конечное множество допустимых входных
символов;
d - заданное отображение множества Q*S во множество подмножеств P(Q) d: Q*S®P(Q) (иногда d называют функцией переходов автомата);
q0ÎQ - начальное состояние автомата;
FÍQ - множество заключительных состояний
автомата.
Работа
автомата выполняется по тактам. На каждом
очередном такте i автомат, находясь в
некотором состоянии qiÎQ, считывает очередной символ wÎS из входной цепочки символов и изменяет
свое состояние на qi+1=d(qi,w), после чего
указатель в цепочке входных символов
передвигается на следующий символ и начинается
такт i+1. Так продолжается до тех пор, пока
цепочка входных символов не закончится.
Конец цепочки символов часто помечают
особым символом ^. Считается также, что перед тактом 1
автомат находится в начальном состоянии
q0.
Говорят, что автомат допускает цепочку aÎS*, если в результате выполнения всех тактов
работы над этой цепочкой он окажется
в состоянии qÎF. Язык, определяемый автоматом, является
множеством всех цепочек, допускаемых
автоматом. Для анализа цепочки с помощью
конечного автомата достаточно подать
ее на вход автомата, выполнить все такты
его работы и определить, перешел ли автомат
в результате работы в одно из заданных
конечных состояний.
Графически автомат отображается нагруженным
однонаправленным графом, в котором вершины
представляют состояния, дуги отображают
переходы из одного состояния в другое,
а символы нагрузки (пометки) дуг соответствуют
функции перехода.
Недетерминированный автомат неудобен
для анализа цепочек, так как в нем могут
встречаться состояния, допускающие неоднозначность,
т.е. такие, из которых выходит две или
более дуги, помеченных одним и тем же
символом. Очевидно, что программирование
работы такого автомата - нетривиальная
задача.
Доказано, что
любой недетерминированный автомат может
быть преобразован в детерминированный
так, чтобы их языки совпадали (говорят,
что автоматы эквивалентны).
Детерминированный конечный автомат
задается пятеркой:
M’=(Q’,S,d’,q0’,F’),
где:
Q’ - конечное множество состояний автомата;
S - конечное множество допустимых входных
символов автомата;
q0’ÎQ’ - начальное состояние автомата;
d’ - заданное отображение множества Q’*S во множество Q’ d: Q’*S®Q’;
FÍQ’ - множество заключительных состояний
автомата.
После построения конечный детерминированный
автомат может быть минимизирован, т.е.
для него может быть построен эквивалентный
ему автомат с минимальным числом состояний.
Можно написать функцию, отражающую функционирование
любого детерминированного конечного
автомата. Чтобы запрограммировать такую
функцию, достаточно иметь переменную,
которая бы отображала текущее состояние
автомата, а переходы автомата из одного
состояния в другое на основе символов
входной цепочки могут быть построены
с помощью операторов выбора. Работа функции
должна продолжаться до тех пор, пока не
будет достигнут конец входной цепочки.
Для вычисления результата функции необходимо
по ее завершению проанализировать состояние
автомата. Если это одно из конечных состояний,
то функция выполнена успешно, и входная
цепочка принимается, если нет - то входная
цепочка не принадлежит заданному языку
ПРОГРАММНАЯ
РЕАЛИЗАЦИЯ ЛЕКСИЧЕСКОГО АНАЛИЗАТОРА
Рассмотрим пример анализа лексем, представляющих
собой целочисленные константы без знака
в формате языка Си. В соответствии с требованиями
языка, такие константы могут быть десятичными,
восьмеричными, либо шестнадцатеричными.
Восьмеричной константой считается
число, начинающееся с 0 и содержащее цифры
от 0 до 7; шестнадцатеричная константа
должна начинаться с последовательности
символов 0x и может содержать цифры и буквы
от A до F (будем рассматривать только прописные
буквы). Остальные числа считаются десятичными
(правила их записи напоминать, наверное,
не стоит). Будем считать, что всякое число
завершается символом конца строки ^.
Рис. 3. Граф конечного
детерминированного автомата, распознающего
грамматику целых чисел языка Си.
Рассмотренные выше правила могут быть
записаны в форме Бэкуса-Наура в грамматике
целочисленных констант без знака языка
Си (для избежания путаницы терминальные
символы грамматики выделены жирным шрифтом).
G({S,G,X,H,Q,Z},{0...9,A...F, ^},P,S)
P: S® G^|Z^|H^|Q^
G® 1|2|3|4|5|6|7|8|9|G0|G1|G2|G3|G4|G5|G6|G7|G8|G9|Z8|Z9|Q8|Q9
H® X0|X1|X2|X3|X4|X5|X6|X7|X8|X9|XA|XB|XC|XD|XE|XF|
H0|H1|H2|H3|H4|H5|H6|H7|H8|H9|HA|HB|HC|HD|HE|HF
X® Zx
Q® Z0|Z1|Z2|Z3|Z4|Z5|Z6|Z7|Q0|Q1|Q2|Q3|Q4|Q5|Q6|Q7
Z® 0
Хорошо
видно, что данная грамматика является
регулярной грамматикой (леволинейной).
Конечный детерминированный автомат M’({N,Z,X,H,Q,G,S,ER},{0...9,A...F,^},d,N,{S}), который распознает язык, заданный
этой грамматикой, изображен на рис. 3.
Начальным состоянием автомата является
состояние N. В автомат дополнительно
введено особое состояние ER, обозначающее ошибку
в распознавании цепочки символов. На
графе автомата дуги, идущие в это состояние,
не нагружены символами. По принятому
соглашению они обозначают функцию перехода
по любому символу, кроме тех символов,
которыми уже помечены другие дуги, выходящие
из той же вершины графа. Такое соглашение
принято, чтобы не загромождать обозначениями
граф автомата (на рис. 3 такие дуги и состояние ER выделены пунктиром).
Можно написать программу, моделирующую
работу указанного автомата. Ниже приводится
текст функции на языке Паскаль, его реализующей.
Результат функции истинный (True), если входная цепочка
символов принадлежит входному языку
автомата. Границей цепочки считается
символ с кодом 0 (#0), в функции он искусственно
добавляется в конец цепочки.
В программе переменная iState отображает
текущее состояние автомата, переменная
i является счетчиком символов входной
строки. Конечно, рассмотренная программа
может быть оптимизирована (например,
можно сразу же прекращать разбор по обнаружению
ошибки), но в данном примере оптимизация
не выполнялась, чтобы можно было четко
отследить соответствие между программой
и построенным автоматом.
type
TAutoState = ( AUTO_N, AUTO_Z, AUTO_X,
AUTO_Q, AUTO_H, AUTO_G,
AUTO_ER, AUTO_S );
function RunAuto (sInput: string): Boolean;
var
iState : TAutoState;
i : integer;
begin
sInput := sInput + #0;
iState := AUTO_N;
i := 0;
repeat
i := i + 1;
case iState of
AUTO_N:
case sInput[i] of
‘0’: iState := AUTO_Z;
‘1’..’9’: iState := AUTO_G;
else iState := AUTO_ER;
end;
AUTO_Z:
case sInput[i] of
‘0’..’7’: iState := AUTO_Q;
‘8’,’9’: iState := AUTO_G;
‘x’: iState := AUTO_X;
#0: iState := AUTO_S;
else iState := AUTO_ER;
end;
AUTO_X:
case sInput[i] of
‘0’..’9’: iState := AUTO_H;
‘A’..’F’: iState := AUTO_H;
else iState := AUTO_ER;
end;
AUTO_Q:
case sInput[i] of
‘0’..’7’: iState := AUTO_Q;
‘8’,’9’: iState := AUTO_G;
#0: iState := AUTO_S;
else iState := AUTO_ER;
end;
AUTO_H:
case sInput[i] of
‘0’..’9’: iState := AUTO_H;
‘A’..’F’: iState := AUTO_H;
#0: iState := AUTO_S;
else iState := AUTO_ER;
end;
AUTO_G:
case sInput[i] of
‘0’..’9’: iState := AUTO_G;
#0: iState := AUTO_S;
else iState := AUTO_ER;
end;
AUTO_ER: iState := AUTO_ER;
end {case};
until (sInput[i] = #0);
RunAuto := (iState = AUTO_S);
end; { RunAuto }
var s:string;
begin
writeln('vvedite posledovatelnost');
readln(s);
if RunAuto(s) then writeln(That's true);