Curs 7 - plan
Proiectarea unui analizor lexical
Descriere lexical
Interpretare
Interpretare orientat dreapta
Descriere lexical bine format
Generatorul Lex. Exemple
Gh. Grigoras 1
Compilare - Interpretare
Programul surs secven de caractere
Analiza
lexical
Programul secven de uniti lexicale
Analiza
sintactic
Arborele sintactic
Analiza
semantic
Arborele sintactic decorat
Cod
intermediar
Program n cod intermediar
Compilare: Interpretare:
cod main Execuia
(asamblare) codului
Program n cod main sau n limbaj de asamblare
Gh. Grigoras 2
Implementarea limbajelor - istorie
1957 Fortran: primul compilator (expresii aritmetice,
instruciuni, proceduri)
1960 Algol: prima utilizare a definiiilor formale
(gramatici, BNF, structura de bloc, recursie)
1970 Pascal: tipuri utilizator, maini virtuale (P-code)
1972 C: variabilele dinamice, multitasking,
gestionarea ntreruperilor
1983 ADA: primul limbaj standardizat
1985 C++: orientare-obiect, excepii, template-uri
1995 Java: just-in-time compilation
2000 C#: Tehnologia .NET
Gh. Grigoras 3
Proiectarea unui analizor lexical
Definiia 1 Fie un alfabet (al unui limbaj de
programare). O descriere lexical peste este o
expresie regulat E = (E1 | E2 || En)+, unde n este
numrul unitilor lexicale, iar Ei descrie o unitate
lexical, 1 i n.
Definiia 2 Fie E o descriere lexical peste ce conine
n uniti lexicale i w +. Cuvntul w este corect
relativ la descrierea E dac w L(E). O interpretare
a cuvntului w L(E) este o secven de perechi (u1,
k1), (u2, k2), , (um, km), unde w = u1u2um, ui L(Eki)
1 i m, 1 ki n.
Gh. Grigoras 4
Exemplu:
w = alpha := beta = 542
Interpretri ale cuvntului w:
(alpha, Id), (:=, Asignare), (beta, Id), (=, Egal),
(542, Intreg)
(alp, Id), (ha, Id), (:=, Asignare), (beta, Id), (=,
Egal), (542, Intreg)
(alpha, Id), (:, Dp), ( =, Egal), (beta, Id), (=,
Egal), (542, Intreg)
Gh. Grigoras 5
Definiia 3 Fie E o descriere lexical peste i w L(E). O
interpretare a cuvntului w, (u1, k1)(u2, k2), (um, km), este
interpretare drept - orientat dac (i) 1 i m, are loc:
|ui| = max{|v| /v L(E1 | E2 || En) Pref(uiui+1um)}.
(unde Pref(w) este mulimea prefixelor cuvntului w ).
Observaie Exist descrieri lexicale E n care nu orice cuvnt din
L(E) admite o interpretare drept-orientat. Fie descrierea
E = (a | ab | bc)+ i w = abc.
Singura interpretare a cuvntului w este (a, 1), (bc, 3) dar
aceasta nu este drept orientat pentru c a nu este cel mai
lung cuvnt din L(a | ab | bc) i Pref(abc)
Gh. Grigoras 6
Definiia 4 O descriere lexical E este bine - format
dac orice cuvnt w din limbajul L(E) are exact o
interpretare drept-orientat.
Teorem Dat o descriere lexical E este decidabil dac
E este bine format
Definiia 5 Fie E o descriere lexical bine format peste
. Un analizor lexical (scanner) pentru E este un
program ce recunoate limbajul L(E) i produce,
pentru fiecare w L(E), interpretarea sa drept-
orientat.
Gh. Grigoras 7
Dat o descriere lexical E peste alfabetul ,
proiectarea unui analizor lexical cuprinde
urmtoarele proceduri:
1. Se construiete automatul finit (cu - tranziii) A,
astfel ca L(E) = L(A)
2. Se aplic Algoritmul descris i se obine automatul
determinist echivalent cu E, fie acesta A.
3. (Opional) Se aplic o procedur adecvat pentru a
obine automatul minimal echivalent cu A.
4. Se scrie un program care implementeaz evoluia
automatului obinut.
Gh. Grigoras 8
Exemplul S considerm descrierea lexical:
litera a | b ||z
cifra 0 | 1 || 9
identificator litera (litera | cifra)*
semn + | -
numar (semn | ) cifra+
operator + | - | * | / | < | > | <= | >= | < >
asignare :=
doua_puncte :
cuvinte_rezervate if | then |else
paranteze ) | (
Gh. Grigoras 9
Ai
An
Ao
q0 Aa
Ad
Ac
Ap
Gh. Grigoras 10
litera, cifra
litera 1 #i sau #c
cifra
cifra #n
2
cifra
+, - #o
3
operator-{+,-} #o
4
: #a
5 = 6
#d
), ( #p
7
Gh. Grigoras 11
Implementare
buffer zona de memorie unde se ncarc o unitate lexical,
getnext(), store(c)
c = getnext(); empty(); stare = 0;
while(1){
switch(stare){
case 0:
if(isspace(c)){
c = getnext(); stare = 0;
}
if(isalpha(c)){
store(c); c = getnext(); stare = 1;
}
else if(isdigit(c)){
store(c); c = getnext(); stare = 2;
}
else if(c == '+' || c == '-'){
store(c); c = getnext(); stare = 3;
}
Gh. Grigoras 12
Lex (Flex)
Bell Laboratories 1975 M.E. Lesk i E. Schmidt
instrument standard UNIX ncepnd cu versiunea a 7-a
Proiectul GNU al Fundaiei Free Software distribuie FLEX
(Fast LEXical Analyzer Generator)
exist versiuni pentru sistemele de operare DOS i WINDOWS;
una dintre acestea este PCLEX lansat de Abraxax Software Inc.
YooLex (Yet another Object-Oriented Lex)
[Link]
Flex++: [Link] (variantele
Bison, Flex care produc cod C++)
Gh. Grigoras 13
1. Scrierea specificaiilor LEX care reprezint
descrierea lexical (fiier cu extensia .l)
2. Executarea programului LEX (FLEX, PCLEX) cu
intrarea fiierul construit:
lex [optiuni] <nume_fiier>
flex [optiuni] <nume_fiier>
pclex [optiuni] <nume_fiier>
Se obine un program n C
3. Se compileaz acest program mpreun, eventual,
cu alte fiiere surs.
Gh. Grigoras 14
O specificare LEX (fiierul de intrare) are structura:
Declaraii
%%
Reguli
%%
Cod C auxiliar
Seciunea Declaraii conine dou pri:
declaraii C pentru elementele care se vor folosi ulterior
definiii ce se folosesc n specificaiile LEX n seciunea Reguli
O definiie (macro pentru expresii regulate) are forma:
<nume> <expresie>
<expresie> este o expresie (regulat) ce poate folosi orice caracter mpreun cu
urmtorii operatori (metacaractere):
" \ [ ] ^ - ? . * + | () / {} % <>
Exemple:
cifra [0-9]
litera [a-zA-Z]
operator [+*/-]
Gh. Grigoras 15
Metacaractere
. Orice caracter cu excepia newlin
\n newline
* zero sau mai multe copii ale expresiei precedente
+ una sau mai multe copii ale expresiei precedente
? zero sau o copie a expresiei precedente
^ nceput de linie
$ sfrit de linie
a|b a or b
(ab)+ una sau mai multe copii ale lui ab
() grupare de caractere
"a+b" literalul "a+b
[] clasa de caractere
Gh. Grigoras 16
Exemple de expresii
Expresia Candidai ce se potrivesc
abc abc
abc* ab abc abcc abccc ...
abc+ abc abcc abccc ...
a(bc)+ abc abcbc abcbcbc ...
a(bc)? a abc
[abc] unul dintre caracterele: a, b, c
[a-z] orice liter, a-z
[a\-z] unul din caracterele: a, -, z
[-az] unul din caracterele: -, a, z
[A-Za-z0-9]+ unul sau mai multe caractere alfanumerice
[ \t\n]+ spaii
[^ab] orice cu excepia caracterelor: a, b
[a^b] unul din caracterele : a, ^, b
[a|b] unul din caracterele : a, |, b
a|b unul din caracterele : a, b
Gh. Grigoras 17
Seciunea Declaraii mai poate conine blocuri
%{%}:
%{
#include <stdio.h>
#define pereche 2
%}
Seciunea Reguli:
exp_1 {Aciune_1}
exp_2 {Aciune_2}
.
.
.
exp_n {Aciune_n}
Gh. Grigoras 18
Variabile lex predefinite
Nume Funcia
int yylex(void) lexerul, este apelat in main()
char *yytext pointer la unitatea lexical(token) gsit
yyleng lungimea tokenului gsit
yylval valoarea asociat tokenului
FILE *yyout fiierul de ieire
FILE *yyin fiierul de intrare
Gh. Grigoras 19
Exemplul 1
%{
int yylineno;
%}
%%
^(.*)\n printf("%4d\t%s", ++yylineno, yytext);
%%
int main(int argc, char *argv[]) {
yyin = fopen(argv[1], "r");
yylex();
fclose(yyin);
}
Gh. Grigoras 20
Exemplul 2
letter [A-Za-z]
digit [0-9]
%{
int count;
%}
%%
{letter}({letter}|{digit})* {count++;}
. {}
%%
int main(void) {
yylex();
printf("number of identifiers = %d\n",
count);
return 0;
}
Gh. Grigoras 21
Exemplul 3
%{
int nchar, nword, nline;
%}
%%
\n { nline++; nchar++; }
[^ \t\n]+ { nword++, nchar += yyleng; }
. { nchar++; }
%%
int main(void) {
yylex();
printf("%d\t%d\t%d\n", nchar, nword, nline);
return 0;
}
Gh. Grigoras 22
Exemplul 4
%{
# include <stdio.h>
%}
litera [a-zA-Z]
cifra [0-9]
cifre ({cifra})+
semn [+-]
operator [+*/<>=-]
spatiu [' \t\n]
%%
"if" | "then" | "else" {printf("%s cuvant rezervat\n", yytext);}
({litera})({litera}|{cifra})* {printf("%s identificator\n", yytext);}
{cifre}|({semn})({cifre}) {printf("%s numar intreg\n", yytext);}
{operator} {printf("%c operator\n", yytext[0]);}
\:\= {printf("%s asignare\n", yytext);}
\: {printf("%c doua puncte\n", yytext[0]);}
(\()|(\)) {printf("%c paranteza\n", yytext[0]);}
{spatiu} {}
. {printf("%c caracter ilegal\n", yytext[0]);}
%%
int main( ){
yylex( );
return 0;
}
Gh. Grigoras 23