Лексический анализатор

Лексический анализ текста состоит в выделении фрагментов текста, называемых лексемами. Лексемы могут рассматриваться при синтаксическом анализе как терминальные символы грамматики, порождающей этот текст. Выделение фазы лексического анализа сильно упрощает грамматику языка. Возможны два способа реализации лексического анализа: либо как отдельного просмотра текста и переработки его в цепочку лексем, синтаксический анализ которой ведется на втором просмотре, либо как процедуры, к которой синтаксический анализатор обращается, когда ему понадобится очередная лексема. Мы будем рассматривать второй вариант, как более распространенный и гибкий, хотя между ними нет принципиальной разницы. Лексический анализатор часто называют сканером.

В языках программирования обычно выделяются такие лексемы, как идентификаторы (id), константы - числа (intnumb, realnumb), строки и др., ключевые слова (for,...), разделители (;, :=,...) и т.д. Выдавая некоторые лексемы, сканер должен выдать и их значение, воспринятое из текста, например, лексему id и ее значение 'ABC' или лексему realnumb и ее значение 0.56.

Как правило, множество лексем образует регулярный язык и может анализироваться конечным автоматом, При реализации такого автомата следует учитывать, что об окончание лексемы автомат узнаёт, когда, находясь в заключительном состоянии, он не может продолжать анализ (например, когда встречается пробел после ключевого слова или символ конец-файла). Поскольку в тексте лексемы могут быть разделены произвольным количеством несущественных символов (так называемые пробельные символы и комментарии), то с них следует начинать регулярное выражение лексемы:

лексема = несущественный-символ ^* собственно-лексема
собственно-лексема = идентификатор | число |...

Рассмотренная выше формальная модель конечного автомата должна быть расширена средствами вычисления значений лексем.

С каждым правилом автомата будем связывать символ s, называемый трансдуктором: (q, a) ® (q ', s). Каждый такой трансдуктор соответствует некоторой программе на каком-нибудь языке, обрабатывающей символ a для получения значения лексемы. Трансдуктор и определённая выделенная лексема lex связывается с каждым заключительным состоянием автомата: q ® (s, lex).

Пример 4.6. Для выделения идентификатора (см. пример 4.1) можно использовать расширенный автомат с правилами

(q ₀, a) ® (q ₁, s ₁),..., (q ₀, z) ® (q ₁, s ₁),
(q ₁, a) ® (q ₁, s ₂),..., (q ₁,z) ® (q ₁, s ₂),
(q ₁,0) ® (q ₁, s ₂),..., (q ₁,9) ® (q ₁, s ₂),
q ₁ ® (s ₃, id)

и программами трансдукторов, написанными на Паскале. Эти программы используют специальные переменные:

Ident: array[1..30] of char; N,K: integer

и общую для всех правил переменную C:char, хранящую прочитанный символ. Они накапливают первые 30 символов идентификатора, игнорируя остальные:

procedure s1; begin for K:=1 to 30 do Ident[K]:=' '; Ident[1]:=C; N:=2 end;procedure s2: begin if N<31 then begin Ident[N]:=C; N:=N+1 end end;procedure s3: begin end;

Первый символ текста читается до первого обращения к сканеру, а следующие - сканером. Следовательно, при каждом входе в сканер он получает первый символ очередной лексемы (возможно, несущественный или специальный символ конец-файла).

Реализация сканера по такому расширенному автомату может иметь вид программы на Паскале:

...type Lex=(id,...); {имена всех лексем}var Ident:array[1..30] of char; N,K:integer; {переменные трансдукторов}...C:char; Lexema:Lex; {общие переменные}...procedure Scanner;var S:integer; {номер состояния} begin S:=0; {начальное состояние}100: case S of {для правил вида (q_i,a)®(q_j,s)}... i: begin if C='a' then begin s; S:=j end else if C=... else {следующее правило для q_i}... error {для незаключительного q_i, завершение работы} end;... j: begin if C=... else {правила для q_j}... goto 101 {для заключительного q_j} end;... end; {case1}if not eof then read(C) else C:='конец файла';goto 100; 101: {конец лексемы} case S of {для правил вида q_j®(s,lx)}... j: begin s; Lexema:=lx end;... end {case2}end {Scanner};

Полученную таким образом программу сканера можно сделать более эффективной, учитывая особенности конкретного языка. Наиболее часто используемые улучшения следующие:

1. Так как q ₀ обычно имеет больше всего правил (практически для всех символов машинного алфавита), для него используется какой-нибудь из самых быстрых способов разветвления по значениям переменной C (лучше всего использовать массив меток, если это поддерживает язык реализации).

2. Часто используется проверка текстового символа на попадание в интервал (например, 'a'-'z' и '0'-'9').

3. Для распознавания ключевых слов, начинающихся с буквы, удобно использовать автомат, распознающий идентификаторы. Накопив слово, нужно затем проверить, не попадает ли оно в список ключевых слов. Если попадает, выдать соответствующее ключевое слово, если нет, выдать идентификатор. В автомате из примера 4.6 переделать нужно только процедуру s 3. Поиск символа в таблице ключевых слов лучше всего делать или с помощью хеш-функции, или двоичным поиском.

Построение по расширенному автомату программы сканера, подобной описанной выше, может быть автоматизировано, хотя инженерная проблема автоматического построения наиболее эффективного сканера еще не решена до конца.

Дата добавления: 2014-01-07