ТЯП-3 Лексические анализаторы (сканеры)














тип 3 регулярные
леволинейная AB | , где A,BVN , VT*
праволинейная AB | , где A,BVN , VT*.
тип 3 автоматные
леволинейная ABt | t, где A,BVN , tVT
праволинейная AtB | t, где A,BVN , tVT







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

В качестве состояний нового ДКА рассматриваются все состояния исходного автомата, а также всевозможные сочетания этих состояний по два, по три, …, по n, если в исходном автомате было n состояний.
Для всех новых состояний строится функция переходов, в которой для каждого состояния qiqj появляется переход в новое состояние, представляющий собой объединение всех прежних переходов из qi и qj.
Начальное состояние нового автомата остается тем же, а множество конечных состояний нового автомата будут состоять из всех сочетаний, в которых присутствовало qf – конечное состояние исходного автомата.
После построения ДКА из него удаляют все недостижимые состояния (состояния, переход в которые невозможен при любой входной цепочке).
В итоге построен ДКА, эквивалентный заданному НКА. При этом если исходный автомат имел n состояний, то в наихудшем случае построенный ДКА будет иметь (2n–1) состояний.
Рассмотрим на примере построение ДКА, эквивалентного заданному НКА.
p
q
1
r
1
0,1
1. Пусть M=({p,q,r},{0,1},,p,{r}) – НКА, где функция переходов задана графом:
Недетерминированный автомат M допускает все цепочки из {0,1}*, заканчивающиеся двумя единицами: (0+1)*11.
Представим функцию переходов в табличном виде (таблица справа). вход
состояние 0 1
p {p} {p,q}
q – {r}
r – –
вход Далее создадим все возможные новые состояния, которые могут получиться в результате сочетаний исходных состояний, и занесём их в таблицу. Новые состояния будем записывать в виде {pq}. Тогда из состояния p по символу 1 переход будет происходить в такое состояние pq. В таблице присутствуют недостижимые состояния q, r, pr и qr, которые можно удалить без изменения результата.
состояние 0 1 p {p} {pq} q – {r} r – – pq {p} {pqr} pr {p} {pq} qr – {r} pqr {p} {pqr} Можно было упростить процесс и сразу заносить в новую таблицу только те состояния, которые действительно могут возникнуть. Тогда состояния pr и qr в ней бы не появились. После удаления недостижимых состояний таблица примет вид:
вход Для удобства переобозначим состояния: заменим p на A, pq на B, pqr – на C. Тогда начальным состоянием будет A, конечным C. вход
состояние 0 1 состояние 0 1
p {p} {pq} A {A} {B}
pq {p} {pqr} B {A} {C}
pqr {p} {pqr} C {A} {C}
В итоге полученный детерминированный автомат, эквивалентный исходному НКА, будет иметь вид: M=({A,B,C},{0,1},,A,{C}), граф функции переходов :
A
B
C
0
1
1
0
0
1


Пусть q1 и q2 – состояния автомата M, на вход подается цепочка символов w длины k0: wV*, wk, (q1,w) ├─* (q3,), (q2,w) ├─* (q4,). Если одно из состояний (q3 или q4) входит в F, а другое – нет, то говорят, что цепочка w различает состояния q1 и q2. Если же для любой входной цепочки w длины k она не различает состояния q1 и q2, то говорят, что они являются k-эквивалентными или k-неразличимыми. Множество K-эквивалентных состояний составляет класс эквивалентности R(k).
Очевидно, что множества F и Q\F являются 0-эквивалентными, записывается этот факт следующим образом: R(0)={F,Q\F}.
Для построения минимального автомата строятся классы эквивалентности R(n).
Алгоритм 3.3. Построение классов эквивалентности:
Полагаем n:=0, строится R(0)= {F,Q\F}.
n:=n+1. Строится R(n) на основании R(n–1): в класс эквивалентности R(n) входят те состояния, которые по одинаковым символам переходят в n–1-эквивалентные состояния: R(n):={rij(n): {qijQ: aV (qij,a) rj(n–1)} i,jN}.
Если R(n)= R(n–1), то работа заканчивается. Иначе переход на шаг 2.
Алгоритм 3.4. Минимизация автомата:
Исключить все недостижимые состояния.
Построить классы эквивалентности.
Каждый из этих классов становится состоянием нового автомата.
Функция переходов строится на основании функции переходов исходного автомата и новых состояний.
q0
q1
q2
q3
q4
q5
0
0
0
0
1
1
1
0,1
0,1
1
Рассмотрим пример. Пусть ДКА имеет вид: M = ({q0, q1, q2, q3, q4, q5}, {0,1}, , q0, {q4, q5}), а функция переходов задана графом:
Требуется минимизировать данный автомат.
q0
q1
q4
0
0
0,1
1
1
Недостижимых состояний нет. Построим классы эквивалентности: R(0)={{q0,q1,q2,q3}, {q4,q5}}. Из состояния q2 по 0 происходит переход в q3, а из q1 – в q4. Состояния q3 и q4 находятся в разных классах эквивалентности R(0) q1 и q2 будут входить в разные классы R(1). Аналогично рассуждая про остальные состояния, получим: R(1)={{q4,q5},{q0,q2},{q1,q3}}. Аналогично: R(2)={{q4,q5}, {q0,q2}, {q1,q3}}. В новом автомате 3 состояния. Обозначим их по номеру одного из состояний каждого класса. M’ = {q0,q1,q4}, {0,1}, ’, q0, {q4}).























3.3.5 Расширения регулярных выражений
С тех пор как в 1950-х годах Клини (Kleene) ввел регулярные выражения с базовыми операторами для объединения, конкатенации и замыкания Клини, к ним было добавлено много расширений, повышающих их способность определять строковые шаблоны. К сожалению, в настоящее время не определены стандарты на запись расширенных регулярных выражений, и в языках программирования нотация записи шаблонов может несколько отличаться. Здесь мы рассмотрим несколько расширений в записи регулярных выражений, которые первоначально появились в утилитах Unix, таких как Lex, и которые в особенности полезны при определении лексических анализаторов.

Выражение Соответствие Пример
с Один неоператорный символ с а
\с Символ с буквально \*
"s" Строка s буквально "**"
• Любой символ, кроме символа новой строки \n а.*b
^ Начало строки ^аbс
$ Конец строки abc$
[s] Любой символ из s [abc]
[^s] Любой символ, не входящий в s [^abc]
r* Нуль или более строк, соответствующих r а*
г+ Одна или более строк, соответствующих r а+
г? Нуль или одно r а?
r{m,n} От т до n повторений r а{1,5}
r1r2 r1, за которым следует r2, конкатенация ab
r1|r2 r1 или r2, объединение а|b
(г) То же, что и r, группировка (a|b)
r1/r2 r1, если за ним следует r2 abc/123
Рис. 3.8. Регулярные выражения Lex.
3.5 Генератор лексических анализаторов Lex
В этом разделе мы познакомимся с программным инструментом под названием Lex (или, в более поздних реализациях, Flex), который позволяет определить лексический анализатор, указывая регулярные выражения для описания шаблонов токенов. Входные обозначения для Lex обычно называют языком Lex, а сам инструмент — компилятором Lex. Компилятор Lex преобразует входные шаблоны в диаграмму переходов и генерирует код (в файле с именем lex.yy.c), имитирующий данную диаграмму переходов.
3.5.1 Использование Lex
На рис. 3.22 показана схема использования Lex. Входной файл lex.1 написан на языке Lex и описывает генерируемый лексический анализатор. Компилятор Lex преобразует lex.1 в программу на языке программирования С в файле с именем lex.yy.c. Этот файл компилируется компилятором С в файл с названием а.out, как обычно. Выход компилятора С представляет собой работающий лексический анализатор, который может получать поток входных символов и выдавать поток токенов.

Рис. 3.22. Создание лексического анализатора с помощью Lex
Обычно скомпилированная программа на языке С, которая на рис. 3.22 показана как a.out, используется в качестве подпрограммы синтаксического анализатора. Это функция на языке программирования С, которая возвращает целое число, представляющее собой код одного из возможных имен токенов. Значение атрибута, которое может быть другим числовым кодом, указателем на запись таблицы символов или просто отсутствовать, помещается в глобальную переменную yylval, которая совместно используется лексическим и синтаксическим анализаторами. Этот метод позволяет вернуть из функции как имя токена, так и значение его атрибута.
3.5.2 Структура программ Lex
Программа Lex имеет следующий вид:
Объявления %%
Правила трансляции %%
Вспомогательные функции
Раздел объявлений включает объявления переменных, именованные константы (manifest constant - идентификаторы констант, например имена токенов) и регулярные определения в стиле раздела 3.3.4.
Правила трансляции имеют вид
Шаблон { Действие }
Каждый шаблон является регулярным выражением, которое может использовать регулярные определения из раздела объявлений. Действия представляют собой фрагменты кода, обычно написанные на языке программирования С, хотя созданы многие разновидности Lex для других языков программирования. Внутри действий в правилах можно использовать некоторые специальные конструкции и функции Lex'а:
yytext – указатель на отождествленную цепочку символов, оканчивающуюся нулем;
yyleng – длина этой цепочки;
yyless(n) – вернуть последние n символов цепочки обратно во входной поток;
yymore() – считать следующие символы в буфер yytext после текущей цепочки;
yyunput(c) – поместить байт c во входной поток;
ECHO – копировать текущую цепочку в yyout;
yylval – еще одно возвращаемое значение.
Третий раздел содержит различные дополнительные функции, используемые в действиях. Эти функции могут также компилироваться отдельно и загружаться лексическим анализатором во время работы.
Лексический анализатор, созданный Lex, работает во взаимодействии с синтаксическим анализатором. При вызове синтаксическим анализатором лексический анализатор считывает по одному символу оставшийся непрочитанным входной поток, пока не будет найден самый длинный префикс входного потока, соответствующий одному из шаблонов Рi. Затем лексический анализатор выполняет связанные с ним действия Ai. Обычно Ai содержит возврат в синтаксический анализатор, но если это не так (например, если Pi описывает пробельные символы или комментарии), то лексический анализатор продолжает поиск дополнительных лексем, пока одно из соответствующих действий не приведет к возврату из функции лексического анализатора в синтаксический анализатор. Лексический анализатор возвращает синтаксическому анализатору единственное значение, имя токена, но использует при этом совместно используемую целочисленную переменную yylval для передачи при необходимости дополнительной информации о найденной лексеме.
Пример 3.11. На рис. 3.23 приведена программа Lex, которая распознает токены, представленные на рис. 3.12, и возвращает найденный токен синтаксическому анализатору. Рассмотрение приведенного кода поможет нам изучить многие важные возможности Lex.

В разделе объявлений мы встречаем пару специальных скобок — %{ и %}. Все, что заключено в эти скобки, копируется непосредственно в lex. уу.с и не рассматривается как регулярное определение. Обычно здесь помещаются определения именованных констант с использованием конструкции #def ine языка программирования С для назначения каждой именованной константе уникального целочисленного кода. В нашем примере мы перечислили в комментарии именованные константы LT, IF и другие, но не привели определения, назначающие им конкретные числовые значения.
%{
/* Определения именованных констант LT, LE, EQ, NE, GT, GE,
IF, THEN, ELSE, ID, NUMBER, RELOP */
%}
/* Регулярные определения */
delim [ \t\n]
ws {delim}+
letter [A-Za-z]
digit [0-9]
id {letter)({letter}|{digit})*
number {digit}+(\.{digit}+)?(E[+-]?{digit}+)?
%%
{ws} {/* Нет действий и выхода из функции */}
if {return(IF);}
then {return(THEN);}
else {return(ELSE);}
{id} {yylval = (int) installID(); return(ID);}
{number} {yylval = (int) installNum(); return(NUMBER);}
"<" {yylval = LT; return(RELOP);}
"<=" {yylval = LE; return(RELOP);}
"=" {yylval = EQ; return(RELOP);}
"<>" {yylval = NE; return(RELOP);}
">" {yylval = GT; return(RELOP);}
">=" {yylval = GE; return(RELOP);}
%%
int installID() {/* Функция для внесения лексемы (на первый символ которой указывает указатель yytext и длина которой равна yyleng) в таблицу символов. Возвращает указатель на соответствующую запись таблицы символов */
}
int installNum() {/* Аналогична функции installlD, но помещает числовые константы в отдельную таблицу */
}
Рис. 3.23. Программа Lex для распознавания токенов на рис. 3.12
Кроме того, в разделе объявлений имеется последовательность регулярных определений. Они используют расширенную запись регулярных выражений, описанную в разделе 3.3.5. Регулярные определения, используемые в следующих за ними определениях или шаблонах правил трансляции, помещаются в фигурные скобки. Так, например, delim определено как сокращение для класса символов, состоящего из пробела, символа табуляции и символа новой строки (последние два символа представлены при помощи обратной косой черты, за которой следует соответственно буква t или n). Затем ws определено как один или несколько разделителей при помощи регулярного выражения {delim}+.
Обратите внимание, что в определениях id и number скобки используются в качестве метасимволов группирования и не обозначают сами себя. Напротив, буква Е в определении number означает саму себя. Если мы хотим использовать один из метасимволов Lex, такой как любая скобка, ., +, * или ?, так, чтобы он обозначал сам себя, то его следует предварить обратной косой чертой. Например, в определении number имеется последовательность \ ., представляющая обычную точку, поскольку просто точка в регулярных выражениях является метасимволом, представляющим "любой символ", как это принято в регулярных выражениях UNIX.
В разделе вспомогательных функций имеются функции installID() и installNum(). Так же, как и часть раздела объявлений, находящаяся между %{...%}, все, что находится во вспомогательном разделе, просто копируется в файл lex. уу. с, но может использоваться в действиях.
Наконец, рассмотрим некоторые из шаблонов и правил в среднем разделе на рис. 3.23. Первым указан идентификатор ws, объявленный в первом разделе и связанный с пустым действием. Если встречается пробельный символ, то выполняется не возврат в синтаксический анализатор, а поиск новой лексемы. Второй токен имеет простой шаблон регулярного выражения if. Если во входном потоке встречаются две буквы if, за которыми не следует другая буква или цифра (в этом случае мы имеем дело с более длинным префиксом входной строки, соответствующим шаблону для id), лексический анализатор выбирает эти символы из входного потока и возвращает имя токена IF, т.е. целое число, которому соответствует именованная константа IF. Ключевые слова then и else обрабатываются аналогично.
Пятый токен имеет шаблон, определенный при помощи id. Заметим, что, хотя ключевые слова наподобие i f соответствуют как своему шаблону, так и данному, Lex в ситуации, когда наибольший префикс соответствует двум или большему количеству шаблонов, выбирает первый из них. Действие при обнаружении соответствия шаблону id включает следующее. 1. Вызывается функция installlD(), которая помещает найденную лексему в таблицу символов.
2. Эта функция возвращает указатель на запись в таблице символов, который сохраняется в глобальной переменной yylval и может быть использован синтаксическим анализатором или другим компонентом компилятора. Функция installlD() имеет доступ к двум переменным, которые автоматически устанавливаются генерируемым Lex лексическим анализатором:
а) указатель yytext на начало лексемы — аналог указателя lexemeBegin на рис. 3.3;
б) целочисленная переменная yyleng, содержащая длину найденной лексемы.
3. Синтаксическому анализатору возвращается имя токена ID.
При обнаружении лексемы, соответствующей шаблону number, выполняются аналогичные действия, но с использованием вспомогательной функции installNum().3.5.3 Разрешение конфликтов в Lex
Следует упомянуть о двух правилах, которыми руководствуется Lex при выборе лексемы в случае, когда несколько префиксов входной строки соответствуют одному или нескольким шаблонам.
1. Предпочтение всегда отдается более длинному префиксу.
2. Если наибольший возможный префикс соответствует двум и более шаблонам, предпочтение отдается шаблону, указанному в программе Lex первым.
Пример 3.12. Первое правило гласит, что необходимо продолжать чтение букв и цифр для поиска наибольшего префикса из этих символов, который и будет представлять собой искомый идентификатор. Оно же гласит, что <= следует рассматривать как единую лексему, а не как две лексемы, < и =. Второе правило делает ключевые слова зарезервированными, если они перечислены до id в программе Lex. Например, если наибольший префикс входной строки, соответствующий какому-либо из шаблонов — then, и при этом шаблон then в программе предваряет шаблон { id}, как на рис. 3.23, то лексический анализатор возвращает токен THEN, а не токен ID.
3.5.4 Прогностический оператор
Lex автоматически считывает один дополнительный символ за последним символом, образующим лексему, а затем выполняет возврат его во входной поток с тем, чтобы из потока была изъята только распознанная лексема. Однако иногда требуется, чтобы входная строка соответствовала определенному шаблону только тогда, когда за ней следуют некоторые (предопределенные) другие символы. В этом случае в шаблоне можно использовать символ косой черты, который указывает конец той части шаблона, которой должна соответствовать лексема. Все, что следует за /, представляет собой дополнительный шаблон, которому должен соответствовать остаток входной строки после найденной лексемы, чтобы было принято решение о том, что найденная лексема соответствует рассматриваемому токену. Однако часть входной строки, соответствующая второй части шаблона, не входит в найденную лексему и остается во входном потоке для последующей обработки.
Пример 3.13. В Fortran и некоторых других языках ключевые слова не являются зарезервированными. Это создает много проблем. Так, например, в инструкции
IF(I,J) = 3
IF представляет собой имя массива, а не ключевое слово. В противоположность этому в инструкции вида
IF ( condition ) THEN ...
IF представляет собой ключевое слово. К счастью, за ключевым словом IF всегда следуют левая скобка, некоторый текст (условие), который может содержать скобки, правая скобка и буква. Таким образом, правило Lex для ключевого слова IF можно записать как
IF / \( .* \) {letter}
Это правило гласит, что лексема, соответствующая шаблону, состоит из двух букв IF. Косая черта указывает, что имеется и дополнительный шаблон, не соответствующий лексеме. Первым символом этого шаблона является левая скобка. Поскольку скобка является метасимволом языка Lex, она должна быть предварена обратной косой чертой, указывающей, что имеется в виду буквальное значение данного символа. Точка со звездочкой означает "любая строка без символа начала новой строки". Точка в языке Lex представляет собой метасимвол, который означает "любой символ, кроме символа начала новой строки". Далее следует правая скобка, предваренная обратной косой чертой, обозначающей буквальное значение следующего за ней метасимвола. Наконец, за правой скобкой следует символ letter, который является регулярным определением, представляющим класс символов, состоящий из всех букв.
Для надежной работы этого шаблона из входного потока предварительно должны быть удалены пробельные символы. В шаблоне не приняты меры ни на случай наличия пробельных символов, ни на случай, когда условие не содержится целиком в одной строке, поскольку точка не соответствует символу новой строки.
Предположим, например, что выясняется соответствие этого шаблона следующему префиксу входной строки:
IF(A<(B+C)*D)THEN...
Первые два символа соответствуют IF, следующий — комбинации \(, девять символов после левой скобки — шаблону .*, а идущие за ними два символа соответствуют \) и letter. Обратите внимание на то, что первая правая скобка (после С) не рассматривается, поскольку за ней следует символ, не являющийся буквой. В результате мы делаем вывод, что буквы IF составляют лексему, являющуюся экземпляром токена if.

Приложенные файлы

  • docx 9132143
    Размер файла: 5 MB Загрузок: 0

Добавить комментарий