М.Ю. Харламов, ВНУ им. В.Даля, 2009

Лексический анализатор - часть компилятора, которая читает исходную программу и выделяет в ее тексте лексемы входного языка Тема 4. Лексический анализ Таблица идентификаторов Лексический анализатор Синтаксический анализатор Исходная программа Очередная лексема Обращение за лексемой

Функции лексического анализатора исключение из текста ис­ходной программы комментариев, незначащих пробелов, символов табуляции выделение лексем следующих типов таблица лексем Результат работы – таблица лексем (содержит весь текст исходной программы, обработанный ЛА) Тема 4. Лексический анализ … begin for I := 1 to N do fg := fg * 0.5 … begin for I := 1 to N do fg := fg * 0.5 …

Регулярное множество в алфавите T определяется рекурсивно следующим образом: 1) - регулярное множество в алфавите T 2) {e} - регулярное множество в алфавите T (e - пустая цепочка); 3) {a} - регулярное множество в алфавите T для каждого a T; 4) если P и Q- регулярные множества в алфавите T, то регулярными являются и множества а) P Q (объединение) б) PQ (конкатенация, т.е. множество {pq, p P, q Q}) в) P* (итерация) 5) ничто другое не является регулярным множеством в алфавите T. Регулярное выражение в алфавите T (и обозначаемое им регулярное множество) определяются рекурсивно следующим образом: 1) - регулярное выражение, обозначающее множество ; 2) e - регулярное выражение, обозначающее множество {e}; 3) a - регулярное выражение, обозначающее множество {a}; 4) если p и q- регулярные выражения, обозначающие регулярные множества P и Q соответственно, то а) (p|q) - регулярное выражение, обозначающее регулярное множество P Q, б) (pq) - регулярное выражение, обозначающее регулярное мно­жество PQ, в) (p*) - регулярное выражение, обозначающее регулярное мно­жество P*; 5) ничто другое не является регулярным выражением в алфавите T. Тема 4. Лексический анализ

Эквивалентное преобразование регулярных выражений Тема 4. Лексический анализ Примеры а) a(e | a)b - обозначает множество {ab, aab}; б) a(a |b)* - обозначает множество всевозможных цепочек, состоящих из a и b, начинающихся с a; в) (a| b)*(a | b)(a| b )* - обозначает множество всех непустых цепочек, состоя­щих из a и b, т.е. множество {a, b}+; г) ((0|1)(0|1)(0|1))* - обозначает множество всех цепочек, состоящих из ну­лей и единиц, длины которых делятся на 3 а) a(e | a)b - обозначает множество {ab, aab}; б) a(a |b)* - обозначает множество всевозможных цепочек, состоящих из a и b, начинающихся с a; в) (a| b)*(a | b)(a| b )* - обозначает множество всех непустых цепочек, состоя­щих из a и b, т.е. множество {a, b}+; г) ((0|1)(0|1)(0|1))* - обозначает множество всех цепочек, состоящих из ну­лей и единиц, длины которых делятся на 3 а) Регулярное выражение для множества идентификаторов. Letter = a | b | c |... |x|y|z Digit = 0|1|... |9 Identifier = Letter(Letter|Digit)* б) Регулярное выражение для множества чисел в десятичной записи Digit = 0|1|... |9 Integer = Digit + Fraction =.Integer|e Exponent = (E(+| - |e)Integer)|e Number = Integer Fraction Exponent а) Регулярное выражение для множества идентификаторов. Letter = a | b | c |... |x|y|z Digit = 0|1|... |9 Identifier = Letter(Letter|Digit)* б) Регулярное выражение для множества чисел в десятичной записи Digit = 0|1|... |9 Integer = Digit + Fraction =.Integer|e Exponent = (E(+| - |e)Integer)|e Number = Integer Fraction Exponent

НКА M =(Q,T,D,q 0,F) Недетерминированный конечный автомат (НКА) - это пятерка M =(Q,T,D,q 0,F),где Q - конечное множество состояний; T - конечное множество допустимых входных символов; D - функция переходов, определяющая поведение управляющего устройства; q 0 Q- начальное состояние управляющего устройства; F Q – множество заключительных состояний. Тема 4. Лексический анализ Состояние a Текущий входной символ Прочитанная часть входной цепочки Непрочитанная часть входной цепочки

Детерминированный конечный автомат (ДКА) – это КА, для которого выполняются условия: 1) D(q, e) = для любого q Q, 2) D(q, a) содержит не более одного элемента для любых q Q и a T. Конфигурация автомата M - пара (q, w) Q x T*, где q - текущее состояние УУ, w - цепочка символов на входной ленте, состоящая из символа под головкой и всех символов справа от него. (q 0, w) – начальная конфигурация (q, e) – заключительная (допускающая) конфигурация Тактом автомата M называется бинарное отношение, определенное следующим образом: если p D(q, a), где a T {e}, то (q, aw) (p, w) для всех w T*. Автомат M допускает цепочку w, если (q 0, w) * (q, e) для некоторого q F Тема 4. Лексический анализ

Для L = L (r), где r = (a|b)*a(a|b)(a|b) Тема 4. Лексический анализНКА M = {{1, 2, 3, 4}, {a, b}, D, 1, {4}}, D(1, a) = {1,2},D(1, b) = {1}, D(2,a) = {3},D(2,b) = {3}, D(3, b) = {4},D(3, a) = {4}. ДКА M = {{1, 2, 3, 4, 5, 6, 7, 8}, {a, b}, D, 1, {3, 5, 6, 8}}, D(1,a)=2, D(1,b) = 1, D(2,a)=4, D(2,b) = 7, D(3, a) = 3, D(3,b)=5, D(4,a) = 3, D(4,b)=5, D(5,a) = 8, D(5,b) = 6, D(6,a) = 2, D(6,b) = 1, D(7,a) = 8, D(7,b) = 6, D(8,a) = 4, D(8,b)=7. a b aa,b b a b a b b aa b a b a b ba w = ababa: (1, ababa) (1, baba) (1,aba) (2, ba) (3, a) (4, e) w = ababa: (1, ababa) (1, baba) (1,aba) (2, ba) (3, a) (4, e) w = ababab: (1, ababab) (2, babab) (7, abab) (8, bab) (7, ab) (8, b) (7, e) w = ababab: (1, ababab) (2, babab) (7, abab) (8, bab) (7, ab) (8, b) (7, e)

Алгоритм преобразования произвольного КА M(Q, T, D, q 0, F) в эквивалентный ему ДКА M'(Q, T, D, q 0, F): 1. Q' автомата М' строится из комбинаций всех состояний множества Q автомата М: [q 1,q 2,..,q m ], 0 < m n, где Q={q i } 2. D' автомата М' строится так: d([q 1,q 2,…, q m ], a)=[r 1, r 2, … r k ], где 0<j<k 0<i<m так, что d(q i, a) = r j, (0<m n) 3. q' 0 = [q 0 ]. 4. Множество F ' автомата М' строится из всех состояний, имеющих вид […f i, …], где f i F – конечные состояния М 5. Удаление недостижимых состояний: a. R := {q 0 }; i:= 0; Р 0 := {q 0 }. {R – множество достижимых состояний} b. Р i+1 :=.{P – множество текущих активн.состояний} c. a T, q P i : Р i+1 := P i+1 d(q, a). d. Если Р i+1 - R =, то выполнение алгоритма закончено, иначе R := R P i+1, i:= i + 1 и перейти к шагу с. Тема 4. Лексический анализ

Для M({Н,A,B,S},{a,b},D, H, {S}) D: d(H,b)=B, d(В,а)=А, d(A,b)={B,S} Тема 4. Лексический анализ Построим эквивалентный ДКА 1. Q'={[H], [A], [B], [S], [HA], [HB], [HS], [AB], [AS], [BS], [HAB], [HAS], [HBS], [ABS], [HABS]} 2. Функция переходов d'([H],b)=[B], d'([A],b)=[BS], d'([В],а)=[А], d'([HA],b)=[BS], d'([HB],a)=[A], d'([HB],b)=[B], d'([HS],b)=[B], d[AB],a)=[A], d'([AB],b)=[BS], d'([AS],b)=[BS], d'([BS],a)=[A], d[HAB],a)=[A], d[HAB],b)=[BS], d([HAS],b)=[BS], d'([HBS],b)=[B], d'([HBS],a)=[A], d'([ABS],b)=[BS], d'([ABS],a)=[A], d'([HABS],a)=[A], d'([HABS],b)=[BS] 3. Начальное состояние q 0 ' = [Н] 4. F = {[S],[HS],[AS],[BS],[HAS],[HBS],[ABS],[HABS]} 5. Достижимые состояния R = {[Н], [В], [А], [BS]} Результат: M{{[H],[B],[A],[BS]},{a.b},D, [H], {[BS]}), d([H],b)=[В], d([В],а)=[А], d([A],b)=[BS],d([BS],a)=[A] bb a HBAS b ba b HBABS a

Минимизация КА Минимизация КА -построение эквивалентного КА с меньшим числом состояний n-эквивалентными Состояния называются n-эквивалентными, n >0 n N {e}, если, находясь в одном из этих состояний и получив на вход любую цепочку символов w: w T*, |w| n, автомат может перейти в одно и то же множество конечных состояний Алгоритм минимизации: Алгоритм минимизации: 1. Из КА M(Q,T,D,q 0, F) исключаются все недостижимые состояния 2. Строятся классы эквивалентности автомата a. n:=0; R(0)= {F, Q-F} b. n:= n + 1, R(n) строится на основе R(n-1): R(n) = {r i (n): {q ij Q: a T d(q ij,a) r j (n-1)} i,j N}. c. Если R(n) = R(n-1), то работа алгоритма закончена, иначе необходимо вернуться к b. 3. Классы эквивалентности состояний исходного КА становятся состояниями результирующего минимизированного КА 4. Функция переходов результирующего КА очевидным образом строится на основе функции переходов исходного КА Тема 4. Лексический анализ

Задан автомат М({А,В,С,D,E,F,G},{0,1},D,A, {D,E}), d(А,0)={В}, d(А,1)={С}, d(B,1)={D}, d(C,1)={Е}, d(D,0)={C}, d(D,1)={E}, d(E,0)={B}, d(E,1)={D}, d(F,0)={D}, d(F,1)={G}, d(G,0)={F}, d(G,1)={F} Тема 4. Лексический анализ A DB C F EG Состояния F и G – недостижимые 2. Классы эквивалентности: R(0)={{A,B,C},{D,E}}, n=0; R(1)={{A},{B,C},{D,E}}, n=1; R(2)={{A},{B,C},{D,E}}, n=2. 3. Минимизированный КА M({A,BC,DE}, {0,1}, d', A, {DE}) d'(A,0)={BC}, d'(А,1)={ВС}, d(ВС,1)={DЕ}, d'(DE,0)={BC}, d'(DE,1)={DE} ADE ,111 BC 0,

Тема 4. Лексический анализ fi fi e a fi i if M(s)M(t) M(s) M(t) e e e e M(s) e ee f e M(s) и M(t) – НКА для регулярных выражений s и t. i – новое начальное состояние, f – новое заключительное состояние M(s) и M(t) – НКА для регулярных выражений s и t. i – новое начальное состояние, f – новое заключительное состояние e Для выражения e a Для выражения a (a VT) s|t Для выражения s|t s t Для выражения s t s * Для выражения s *

ЛА может быть оформлен как подпрограмма. При обращении к ЛА, вырабатываются как минимум два результата: тип выбранной лексемы и ее значение (ес­ли оно есть) В основе ЛА лежит диаграмма переходов соответствующего конеч­ного автомата! Тема 4. Лексический анализ i Ключевое слово if Идентификатор f Не буква и не цифра Буква или цифра n t Не f и не n Не t Ключевое слово int Не буква и не цифра

LEX Для автоматизации разработки ЛА разработано много средств. Входным языком для них служат либо грамматики, либо язык регулярных выра­ жений. Пример - LEX. Тема 4. Лексический анализ Компилятор LEX Исходная программа Lex lex.l lex.yy.c

Тема 4. Лексический анализ %{ /*определения констант 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=install_id(); return(ID);} {number} {yylval=install_num(); 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);} % install_id() {/* подпрограмма для помещения лексемы в таблицу символов*/} install_num() {/*подпрограмма для размещения лексемы числа*/ } %{ /*определения констант 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=install_id(); return(ID);} {number} {yylval=install_num(); 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);} % install_id() {/* подпрограмма для помещения лексемы в таблицу символов*/} install_num() {/*подпрограмма для размещения лексемы числа*/ } Пример программы

1) Построить синтаксическое дерево для пополненного регулярного выражения (r)# 2) Вычислить значения функций nullable, firstpos, lastpos и followpos с помощью рекурсивного обхода синтаксического дерева в глубину 3) Определить q 0 = firstpos(root), где root - корень синтаксического дерева 4) Добавить q 0 в Q как непомеченное состояние 5) Выполнить следующую процедуру: while (в Q есть непомеченное состояние R) { пометить R; for (каждого входного символа a R, такого, что в R имеется позиция, которой соответствует a){ пусть символ a в R соответствует позициям p 1,...,p n, и пусть if (S ) { if (S Q) добавить S в Q как непомеченное состояние; определить D(R, a) = S; } 6) Определить F как множество всех состояний из Q, содержащих позиции с # Тема 4. Лексический анализ

firstpos(n) - дает множество позиций, которые соответствуют первым символам в подцепочках, генерируемых подвыражением с вершиной в узле n lastpos(n) - дает множество позиций, которым соответствуют последние символы в подцепочках, генерируемых подвыражениями с вершиной n Для узла n, поддеревья которого могут породить пустое слово - nullable(n) = true, а для остальных узлов nullable(n) = false followpos(i) есть множество позиций j таких, что существует некоторая строка... cd..., входящая в язык, описывае­мый регулярным выражением, такая, что позиция i соответствует этому вхождению c, а позиция j – вхождению d. Тема 4. Лексический анализ