Expresii regulate şi generatoarele de analizoare lexicale LFAC (Limbaje formale, automate şi compilatoare – An2Sem1)

Prima etapă în înţelegerea unui program este descompunerea lui în lexeme. Se numeşte lexemă, un

şir de caractere de la intrare care este în curs de analizare. De exemplu, în C avem lexeme de forma

for, while, etc., dar nu lexeme de forma %$#@. In plus, într-un program C putem întâlni lexeme de

genul variabila_cea_mare. Există deci un număr potenţial infinit de lexeme (dacă presupunem că

numele de variabile nu au nicio limită pentru lungime). Totalitatea tuturor lexemelor legale este la

rândul ei un limbaj; acesta nu trebuie confundat cu limbajul C: în limbajul C ''cuvintele'' sunt

programele corecte, în limbajul lexemelor C, cuvintele legale sunt toate lexemele care pot apărea în

vreun program C.

Teoreticienii au propus cu mult timp în urmă (în anii '60) un meta-limbaj extrem de concis

pentru a descrie lexeme. Limbajul acesta este limbajul expresiilor regulate. O expresie regulată

este un şir de caractere care descrie o mulţime de cuvinte posibile (poate chiar o mulţime

infinită). Lexemele tuturor limbajele de programare moderne pot fi descrise prin expresii regulate.

Pe baza expresiilor regulate se poate construi un automat cu stări finite, care stă la baza

funcţionării unui analizor lexical. Un automat cu stări finite este o maşină abstractă care poate analiza

şi recunoaşte expresiile regulate, iar implementarea software a unui astfel a automat nu este dificilă.

Expresii regulate pentru limbaje de programare

Folosind expresiile regulate, se poate defini o gramatică de expresii pentru un limbaj sursă.

Semnificaţia expresiilor regulate:

• . Semnifică orice caracter cu excepţia lui newline: ‘\n’. • * Semnifică zero sau mai multe apariţii ale expresiei regulate precedente. • [] Semnifică o clasă de caractere. • ^ Un circumflex la începutul unei expresii regulate semnifică faptul că

expresia respectivă trebuie să apară chiar la începutul unei linii în limbajul

sursă. • $ Un dolar la începutul unei expresii regulate semnifică faptul că

expresia respectivă trebuie să apară chiar la sfârşitul unei linii în limbajul

sursă. • {} Indică un domeniu restrâns de copii ale expresiei regulate

precedente. De exemplu, (abc){3,8} semnifică între 3 şi 8 apariţii ale cuvântului

'abc'. • + Semnifică una sau mai multe apariţii ale expresiei regulate precedente. • ? Semnifică zero sau o singură apariţie a expresiei regulate precedente. • | Expresia regulată precedentă, sau expresia regulată următoare. • "…" Tot ce este cuprins între ghilimele se interpretează literal. • () Grupează o serie de expresii regulate într-o expresie nouă.

Exemple de expresii regulate

• a* este o expresie regulată care reprezintă şirurile ε | a | aa | aaa | …, adică un limbaj ai

cărui atomi conţin zero sau mai multe simboluri 'a', unde 'ε' reprezintă şirul vid.

• a+ este o expresie regulată care reprezintă şirurile a | aa | aaa | …, adică un limbaj ai

cărui atomi conţin unul sau mai mulţi 'a'.

• [abcd] este o expresie regulată care descrie un limbaj ce are numai 4 tipuri de atomi posibili:

a, b, c, d. În general, parantezele drepte semnifică "oricare din caracterele dintre paranteze". O expresie regulată între paranteze drepte se numeşte clasă de caractere.

• abcd+ semnifică 'a' urmat de 'b' urmat de 'c' urmat de unul sau mai mulţi 'd'. Deci

elementele limbajului constau din şiruri de forma: abcd, abcdd, abcddd, abcdddd, şi aşa mai departe.

• (abcd)+ Parantezele rotunde grupează expresiile regulate. Această expresie semnifică abcd

repetat o dată sau de mai multe ori, adică: abcd, abcdabcd, abcdabcdabcdabcd, şi aşa mai departe.

• [pq][0123] Expresiile regulate se pot concatena pentru a forma expresii mai complexe. Această expresie semnifică oricare expresie descrisă de prima pereche de paranteze drepte urmată de oricare expresie din a doua pereche de paranteze drepte: p0, p1, p2, p3, q0, q1, q2, q3.

• ([a-l]*) O liniuţă de unire într-o clasă de caractere semnifică un domeniu de caractere.

Astfel, '[a-l]' este o prescurtare pentru '[abcdefghijkl]'. Parantezele rotunde s-au adăugat doar

pentru claritate. Întreaga expresie semnifică zero sau mai multe caractere din domeniul 'a-l' : able,

babble, abcabcllljk, gif şi aşa mai departe.

• [a-z][0-9]* Un singur element din prima clasă urmat de zero sau mai multe elemente din a

doua clasă: x, m31, k9, b00000882 şi aşa mai departe.

• ([a-z]*)[-+*] Unul sau mai multe elemente din domeniul de la a la z, urmate de un '-', un

'+', sau un '*': abcabcd+, z- şi aşa mai departe. Se specifică faptul că '-' într-o clasă de caractere

semnifică un domeniu de caractere, cu excepţia cazului în care el urmează imediat după paranteza

dreaptă, când semnifică chiar caracterul '-'. Totodată, într-o clasă de caractere, toate celelalte

caractere speciale îşi pierd semnificaţia şi se reprezintă pe ele însele. Astfel, '+' şi '*' reprezintă

caracterele '+' şi '*'.

• ([a-z]*)|[-+*] Semnifică fie zero sau mai multe elemente din domeniul de la a la z, fie

un singur '-', un '+', sau un '*': aa, acd, compilator, +.

• (alfa)? Semnifică zero sau o singură apariţie a cuvântului 'alfa'.

• rara? cuvântul rar urmat de zero sau o singură apariţie a lui 'a'. Se notează că '?', cu

semnificaţia zero sau o singură apariţie a expresiei regulate anterioare are precedenţă faţă de

concatenare.

În cele ce urmează, se vor lua în considerare trei tipuri de exresii regulate de bază. În

ordinea crescătoare a precedenţei, ele sunt:

1. Reuniune sau alternaţie, cu sensul de SAU, indicat de simbolul | (r|s corespunde cu

orice şir care corespunde cu r sau cu s).

De exemplu: a | b = {a, b}

a | e = {a, e}

2. Concatenaţie, indicat prin juxtapunere: rs corespunde cu orice şir care este o

concatenaţie a două şiruri, din care primul corespunde cu r şi al doilea cu s.

De exemplu: ab = {ab}

(a|b)c = {ac, bc}

(a|b)(c|d) = {ac, ad, bc, bd}

3. Repetiţie sau închidere, indicat de * . Pentru orice expresie regulată r, r corespunde

cu orice conatenaţie finită de şiruri, care corespund fiecare cu r.

De exemplu:

a* = {ε, a, aa, aaa, aaaa, …}

ab* = {a, ab, abb, abbb, abbbb, …}

Observaţii:

• Parantezele se pot folosi pentru a modifica precedenţa. De exemplu:

ab* = {a, ab, abb, abbb, abbbb, …}

(ab)* = (ε, ab, abab, ababab, abababab, …}

a|b* = {ε, a, b, bb, bb, bbb, bbbb,…}

• Expresiile regulate se pot asocia cu nume: De exemplu:

cifra = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Atomii unui limbaj de programare se pot clasifica în următoarele categorii:

• cuvinte rezervate sau cuvinte cheie, de exemplu if, while, do

• simboluri speciale, de exemplu := = < ++

• identificatori

• literali şi constante, de exemplu "Meniu" ,'a', 67

Expresiile regulate corespunzătoare sunt:

• Expresii regulate pentru cuvinte cheie:

cheie = if | while | do | else | …

• Expresii regulate pentru simboluri speciale:

simb = := |= | < | ++ | …

• Expresii regulate pentru identificatori:

litera = [a-zA-Z], cifra = [0-9], identificator = litera (litera | cifra)*

• Expresii regulate pentru numere:

nat = [0-9]+, intreg = (+|-)? nat, numar = intreg ("." nat)? (E intreg)?

Este cunoscut faptul că analizorul lexical ignoră comentariile. Acesta este motivul pentru care

nu se definesc atomi de comentarii.

Atomii sunt separaţi de spaţii, paranteze sau operatori.

• Expresii regulate pentru spaţii:

sp = (newline|blank|tab|comentariu)+

Există şi cazuri în care atomii nu sunt separaţi de spaţii. De exemplu, x=y. În acest caz, semnul

egal este cel care serveşte ca delimitator.

După ce se defineşte gramatica de expresii regulate, este necesar un program care să decidă dacă o secvenţă de expresii corespunde cu o expresie regulată particulară.

Pe baza expresiilor regulate se pot construi instrumente software care generează automat

programe de analiză lexicală. Aceste se numesc generatoare de analizoare lexicale.

Nota: Materialul de mai sus este găsit şi editat de mine (sursă mi-e necunoscută); el nu

aparţine Facultăţii de Informatică din Iaşi.