Anàlisi lèxica
En informàtica l'anàlisi lèxica és el procés de convertir una seqüència de caràcters en una seqüència de tokens.[1] Un programa o funció que realitza l'anàlisi lèxica s'anomena un analitzador lèxic, lexicalitzador, o un escànner. Un analitzador lèxic sovint té la forma d'una sola funció que és cridada per un programa d'anàlisi o una altra funció.
Gramàtica lèxica
[modifica]L'especificació d'un llenguatge de programació sovint inclou un conjunt de regles que defineixen el lèxic. Aquestes regles en general consisteixen en expressions regulars, i defineixen el conjunt de possibles seqüències de caràcters que s'utilitzen per formar fitxes o lexemes individuals. Un programa de lèxic reconeix cadenes. Per a cada tipus de cadena trobada el programa lèxic fa una acció.
En els llenguatges de programació que delimiten blocs' amb símbols -anomenats tokens- (per exemple, "{" i "}"), a diferència dels anomenats llenguatges de regles de fora de joc-que delimiten blocs amb sangria- l'espai en blanc també es defineix per una expressió regular i influeix en el reconeixement dels altres tokens però no genera símbols per ell mateix. L'espai en blanc es diu que és no significatiu en aquests idiomes.
Símbol (o token)
[modifica]Un símbol o token és una sèrie de caràcters classificats d'acord amb les regles com un símbol (per exemple, l'identificador, nombre, coma). El procés de formació de tokens partir d'un flux d'entrada de caràcters es diu tokenització, i l'analitzador lèxic els classifica d'acord amb un tipus de símbol. Un símbol (o token) pot ser qualsevol cosa que és útil per processar un flux d'entrada de text o un arxiu de text.
L'analitzador lèxic generalment no fa res amb combinacions de símbols; aquesta tasca es deixa per a un analitzador. Per exemple, un típic analitzador lèxic reconeix parèntesi com tokens, però no fa res per assegurar-se que cada símbol "(" es correspon amb un altre ")" final.
Penseu en la possibilitat d'aquesta expressió en el llenguatge de programació C:
sum = 3 + 2;
Tokenitzats en la següent taula:
| Lexema | Tipologia de token |
|---|---|
| sum | Identificador |
| = | Operador d'assignació |
| 3 | Literal enter |
| + | Operador d'adició |
| 2 | Literal enter |
| ; | Fi de la declaració |
Els tokens es defineixen sovint per expressions regulars, que són enteses per un generador d'analitzadors lèxics com a lema. L'analitzador lèxic (ja sigui generat automàticament per una eina com lema, o fet a mà) llegeix una seqüència de caràcters, identifica els lexemes dins la cadena i els classifica en tokens. Això s'anomena "tokenització". Si l'analitzador lèxic troba un símbol no vàlid, s'informarà d'un error.
Després de la tokenizació ve l'anàlisi A partir d'aquí, les dades interpretades poden ser carregades en les estructures de dades per a l'ús general, interpretació o compilació.
Escaneig
[modifica]La primera etapa, l'escaneig, es basa en general en una màquina d'estats finits (FSM). S'ha codificat dins d'ella informació sobre les possibles seqüències de caràcters que pot contenir dins de qualsevol dels tokens que maneja (els exemples individuals d'aquestes seqüències de caràcters es coneixen com a lexemes). Per exemple, un token de nombre sencer pot contenir qualsevol seqüència de caràcters digitals numèrics. En molts casos, el primer espai no en blanc es pot utilitzar per deduir el tipus de token (o símbol) que segueix i les entrades de caràcters posteriors es processen immediatament a continuació, fins a arribar a un caràcter que no està en el conjunt de caràcters acceptables per a aquest token (aquesta és coneguda com la "regla del màxim mastegat", o "norma de la major correspondència". En alguns idiomes, les regles de creació lexemes són més complicades i poden implicar fer marxa enrere sobre caràcters llegits prèviament. Per exemple, en C, el caràcter "L" per si sol no és suficient per distingir entre un identificador que comença amb "L" i una cadena de caràcters amples literal.
Tokenizació
[modifica]La tokenizació és el procés de demarcació i la possible classificació de les seccions d'una cadena de caràcters d'entrada. Els símbols (tokens) resultants es passen a alguna altra forma de processament. El procés pot ser considerat com una sub-tasca de d'anàlisi sintàctica.
Prenguem, per exemple, la cadena següent:
The quick brown fox jumps over the lazy dog
La cadena no està implícitament segmentada en espais, com faria un parlant anglès. L'entrada inicial, els 43 caràcters, s'ha de dividir de manera explícita en els 9 tokens amb un espai delimitador donat (és a dir, coincident amb la cadena " " o l'expressió regular /\s{1}/).
Els tokens poden ser representats en XML,
<sentence>
<word>The</word>
<word>quick</word>
<word>brown</word>
<word>fox</word>
<word>jumps</word>
<word>over</word>
<word>the</word>
<word>lazy</word>
<word>dog</word>
</sentence>
O en una expressió:
(sentence
((word The) (word quick) (word brown)
(word fox) (word jumps) (word over)
(word the) (word lazy) (word dog)))
Un lexema és només una cadena de caràcters coneguda per ser d'un cert tipus (per exemple, un cadena literal, una seqüència de lletres). Per construir un token, l'analitzador lèxic necessita una segona etapa, l'avaluador, que repassa els caràcters del lexema per produir un valor. El tipus del lexema combinat amb el seu valor és el que pròpiament constitueix un token, que pot ser tractat després per un analitzador. (Alguns tokens com els parèntesis en realitat no tenen valors, per la qual cosa l'avaluador de funcions d'aquests pot no tornar cap valor. Els avaluadors de nombres enters, identificadors i cadenes poden ser considerablement més complexos. De vegades, els avaluadors poden suprimir per complet un lexema, ocultant l'analitzador, cosa que és útil per espais en blanc i comentaris.)
Per exemple, en el codi font d'un programa d'ordinador, la cadena:
net_worth_future = (assets - liabilities);
pot ser convertida (amb espais en blanc suprimits) a la cadena lèxica de tokens següent:
NAME "net_worth_future" EQUALS OPEN_PARENTHESIS NAME "assets" MINUS NAME "liabilities" CLOSE_PARENTHESIS SEMICOLON
Encara que és possible i a vegades necessari escriure un analitzador lèxic a mà (a causa de les restriccions de llicència dels programes d'anàlisi existents o perquè la llista de tokens sigui petita) els analitzadors es generen sovint amb instruments automatitzats. Aquestes eines generalment accepten les expressions regulars que descriuen els tokens permesos en el flux d'entrada. Cada expressió regular s'associa amb una regla de producció en la gramàtica lèxica del llenguatge de programació que avalua els lexemes que coincideixen amb l'expressió regular. Aquestes eines poden generar codi font que pot ser compilat i executat o construir una taula d'estats per a una màquina d'estats finits (que s'afegeix al codi base per a la compilació i execució).
Les expressions regulars compactes representen patrons que els caràcters de lexemes poden seguir. Per exemple, per a l'idioma anglès, el token"NAME" pot ser qualsevol caràcter alfabètic anglès o un caràcter subratllat, seguit per qualsevol nombre d'exemples de qualsevol caràcter alfanumèric ASCII o un guió baix. Això pot ser representat de forma compacta per la cadena [a-zA-Z_][a-zA-Z_0-9]*. Això vol dir "qualsevol caràcter az, AZ o _, seguit de 0 o més az, AZ, _ o 0-9".
Les expressions regulars i les màquines d'estats finits que generen no són prou potents com per manejar els patrons recurrents, com ara "parèntesi d'obertura n, seguit d'una oració, seguit de n parèntesi de tancament." No són capaços de mantenir el recompte i verificació que n és el mateix en ambdós costats - a menys que tingui un conjunt finit de valors permesos per n. Es necessita un programa d'anàlisi en tota regla per reconèixer aquests patrons en tota la seva generalitat. Un analitzador pot deixar els parèntesi en una llista a banda i després tractar de treure'ls fora i veure si la llista està buida al final.
L'eina de programació Lex i el seu compilador estan dissenyats per a generar codi per a analitzadors lèxics ràpids sobre la base d'una descripció formal de la sintaxi lèxica. En general no es considera suficient per a aplicacions amb un complicat conjunt de regles lèxiques i uns requisits exhaustius de rendiment, per exemple, la col·lecció de compiladors de GNU utilitza generadors lèxics manuals.
Generadors lèxics
[modifica]Anàlisi lèxica sovint es pot realitzar d'una sola passada, si la lectura es fa caràcter a caràcter. Els generadors lèxics d'un sol pas es poden generar mitjançant eines com ara la flexió.
La gran utilitat d'usar un generador d'escànner no s'ha de descartar, especialment en la fase de desenvolupament, quan les especificacions del llenguatge poden canviar cada dia. La capacitat d'expressar construccions lèxiques com expressions regulars facilita la descripció d'un analitzador lèxic. Algunes eines ofereixen l'especificació de la condició prèvia i posterior a l'anàlisi, que és difícil de programar a mà. En aquest cas, l'ús d'un generador d'escànner pot estalviar un munt de temps de desenvolupament, almenys quan el fet d'obtenir un òptim rendiment extrem no és molt important.
Generadors d'analitzadors lèxics
[modifica]- Antlr - Pot generar analitzadors lèxics i sintàctics.
- Flex - variant alternativa del clàssic "lex" (C / C + +).
- JFlex - Una reescriptura de JLex.
- Ragel - Una màquina d'estats i el generador d'analitzador lèxic amb suport de sortida per a C, C + +, C #, Objective-C, D, Java, Go i el codi font de Ruby.
Els següents analitzadors lèxics poden manejar Unicode:
- JavaCC - JavaCC genera analitzadors lèxics escrits en Java.
- JLex - Un generador d'analitzador lèxic per a Java.
- Quex (o "Queχ") - Un generador d'analitzador lèxic universal de forma ràpida per a C i C + +.
Referències
[modifica]- ↑ Mena, Jesus. Machine Learning Forensics for Law Enforcement, Security, and Intelligence (en anglès). CRC Press, 2011, p. 97. ISBN 1439860696.
Bibliografia
[modifica]- Compiling with C# and Java, Pat Terry, 2005, ISBN 032126360X
- Algorithms + Data Structures = Programs, Niklaus Wirth, 1975, ISBN 0-13-022418-9
- Compiler Construction, Niklaus Wirth, 1996, ISBN 0-201-40353-6
- Sebesta, RW (2006). Concepts of programming languages (Seventh edition) pp. 177. Boston: Pearson / Addison-Wesley.
Enllaços externs
[modifica]- Word Mention Segmentation Task pàgina d'anàlisi.
- Sobre l'aplicabilitat de la norma de la màxima concordança en l'anàlisi lèxica Arxivat 2012-02-25 a Wayback Machine.