Limbaje Formale, Automate i CompilatoareCurs: G. Grigora, grigoras@info.uaic.roSeminar, Laborator: Oana Prisecaru, otto@info.uaic.roIonel Ancua, ancuta.ionel@info.uaic.roTematica cursului Limbaje i gramatici Gramatici i limbaje regulate Gramatici i limbaje independente de context Limbaje de programare: proiectare i implementare Analiza lexical Analiza sintactic Traducere n cod intermediar2 G. Grigoras, LFACTematica seminar Exemple de limbaje i gramatici Automate finite deterministe, nedeterministe, cu epsilon-tranziii - Exemple Expresii regulate Exemple cu referire la unitile lexicale din limbajele de programare Gramatici independente de context, arbori de derivare, eliminarea simbolurilor inutile, eliminarea regulilor de tergere, a redenumirilor Forma normal Chomsky, recunoaterea -algoritmul CYK Automate pushdown - exemple3 G. Grigoras, LFACTematica laborator Analiza lexical Analizor lexical manual Analizor obinut cu un instrument de tip LEX Analiza sintactic folosind instrumente de tip YACC Interpreter construit cu LEX i YACC4 G. Grigoras, LFACBibliografie Grigoras, Gh. Constructia compilatoarelor - Algoritmi fundamentali, Ed. Universitatii Al. I. "Cuza Iasi", ISBN 973-703-084-2, 274 pg., 2005 Jucan Toader - Limbaje formale i automate, Editura Matrix Rom, Bucureti, 1999, 162 p. Jucan Toader, tefan Andrei Limbaje formale i teoria automatelor. Teorie i practic, Editura Universitii Al. I. Cuza, Iai, 2002, 327p. Stoughton Alley, Formal Language Theory, Kansas State University, Draft of Fall 2007. Yehezkael R.B., Course notes on Formal Languages and Compilers, Jerusalem College of Technology, December 2004. Manual LEX,Manual FLEX,Manual YACC,Manual Bison,Compiler Construction using Flex and Bison5 G. Grigoras, LFACCurs 1 - plan Alfabet, cuvnt, mulime de cuvinte Limbaj (formal) Non limbaj Gramatici Definiie Derivare, limbaj generat Exemple Tipurile de gramatici, ierarhia lui Chomsky Gramatici i limbaje de tip 3 Definiie, exemple, proprieti6 G. Grigoras, LFACAlfabet, cuvnt, mulime de cuvinte Alfabet: V o mulime finit, elementele simboluri Simbolurile le vom nota a, b, etc. Cuvnt: ir finit de simboluri Cuvintele le vom nota u, v, w, x, z, y V* - mulimea tuturor cuvintelor, inclusiv cuvntul nul notat (epsilon) sau (lambda) {0,1}* = {, 0, 1, 00, 01, 10, 11, 000, 001,... } V+- mulimea tuturor cuvintelor nenule {0,1}+= {0, 1, 00, 01, 10, 11, 000, 001,... } Lungimea unui cuvnt u: numrul simbolurilor sale. Notaie: | u | | 0 | = 1, | 010 | = 3, | | = 07 G. Grigoras, LFACAlfabet, cuvnt, mulime de cuvinte Concatenarea a dou cuvinte x, y: cuvntul xy obinut din simbolurile lui x, n ordinea n care apar, urmate de cele ale lui y de asemenea n ordinea n care apar: x = 0100, y = 100, xy = 0100100 x = 000, y = , xy = 000 Concatenarea este asociativ este element neutru (V*, ) este monoid, se numete monoidul liber generat de V n continuare xyse va nota xy Cuvntul v este un prefix al cuvntului u dac -w e V*, u = vw; dac w e V+atunci v este un prefix propriu Cuvntul v este un sufix al cuvntului u dac - w e V*, u = wv; dac w e V+atunci v este un sufix propriu8 G. Grigoras, LFACLimbaj (formal) Fie V un alfabet. O submulime L _ V* esteun limbaj(formal) peste alfabetul V (sau V-limbaj) dac L are o descriere finit. O descriere poate fi: neformal (n limbaj natural): mulimea cuvintelor peste alfabetul {0,1} care conin un numr par de 0 i un numr par de 1. L = {x e V* : |x| este par}. { 0n1n| n e N}. {w e {0, 1}* | w este palindrom }. formal (descriere matematic): o descriere inductiv a cuvintelor o descriere generativ a cuvintelor (gramatic generativ) o descriere a unei metode de recunoatere a cuvintelor din limbaj (automat finit, automat pushdown, etc.)9 G. Grigoras, LFACNon - limbaj Exist submulimi de cuvinte din V* care nu sunt limbaje? Rspunsul este DA! Fie V = {a} i presupunem c fiecare submulime din V* este limbaj. S enumerm aceste limbaje (se poate ): L0, L1, , Ln, Considerm mulimea S = {an| aneLn, n>=0}. Descrierea lui S este finit nct S este limbaj, adic exist k astfel nct S = Lk. Atunci: ake S ddac ake Lkddac ake S- absurd! Aadar, exist submulimi din V* care nu sunt limbaje10 G. Grigoras, LFACGramatici Sistemul G = (N, T, S, P) este o gramatic dac: N i T sunt vocabulare disjuncte N este mulimea neterminalilor utilizai pentru a descrie structura limbajului T este mulimea simbolurilor terminale caracterele care formeaz cuvintele limbajului S este neterminalul iniial (simbol de start), S e N P este o mulime finit de reguli (producii, reguli de nlocuire, reguli de rescriere) de forma x yunde x, ye (N T)* i x conine cel puin un neterminal11 G. Grigoras, LFACDerivare, limbaj generat Fie G = (N, T, S, P) o gramatic, u, v e (N T)* Spunem c v este derivat ntr-un pas dela u prin aplicarea regulii x y , i scriem u v, dac u = pxq iar v = pyq. Dac u1u2 un, n > 1,spunem c uneste derivat din u1n G i scriem u1+un Scriem u * v dac u = v sau u +v Limbajul generat de G este definit prin:L(G) = {w e T*| S +w} Dou gramatici G1 i G2 sunt echivalente dac genereaz acelai limbaj: L(G1) = L(G2)12 G. Grigoras, LFACClasificarea gramaticilor(Chomsky)Tipul gramaticii Restricii asupra regulilorAvantaje/DezavantajeGramatici generale(Tip 0)Nu sunt Poate fi descrise orice limbaj / Nu exist un algoritm general de recunoatereGramaticidependente de context(Tip 1)pxq pyq undey c, p,q e (N T)*S , caz n care S nu apare n dreapta produciilorPot fi descrise toate trsturile limbajelor de programare, exist algoritmi generali de recunoatere dar sunt ineficieniGramaticiindependente de context(Tip 2)A y undeA e N i y e (N T)*Algoritmi generali de recunoatere eficieni, utilizai n practic (compilare). Nu pot fi exprimate trsturi semantice (ex. legtura ntre utilizarea variabilelor i declararea acestora)Gramatici regulate(Tip 3)A u sau A uBunde A, B e N i u e T*. Exist metode secveniale de recunoatere, Pot fi descrise doar trsturi secveniale ale limbajelor de programare (identificatori, constante etc.) dar nu expresii, instruciuni13 G. Grigoras, LFACExemple L = {anbncn| n1} Definiia inductiv: a1b1c1= abc e L Dac anbncn e L atunci i an+1bn+1cn+1 e L Nici un alt cuvnt nu face parte din L Definiia generativ (o gramatic): G = (N, T, S, P), N = {S, X}, T = {a, b, c}, P const din:S abc, SaSXc, cXXc, bX bb Derivarea cuvntului a3b3c3:S aSXc aaSXcXc aaabcXcXc aaabXccXcaaabbccXc aaabbcXccaaabbXccc aaabbbccc = a3b3c3 Obs. G este gramatic de tip 114 G. Grigoras, LFACExemple Construii o gramatic de tip 1 pentru limbajul {anbncndn| n 1} Construii o gramatic de tip 2 pentru limbajul {anbn| n 1} Construii o gramatic de tip 3 pentru limbajul {anbm| n, m 1} Fie G = ({E}, {a, +, -, (, )}, E, {Ea, E(E+E), E(E-E)}). Ce tip are gramatica G ? Construii derivri din E pentru cuvintele (a+a) i ((a+a)-a) Cuvntul (a+a-a) poate fi derivat din E? Descriei limbajul L(G) 15 G. Grigoras, LFACIerarhia lui Chomsky Un limbaj L este de tipul j dac exist o gramatic G de tipul j astfel nct L(G) = L, unde j e {0, 1, 2, 3}. Vom nota cu Ljclasa limbajelor de tipul j, unde j e{0, 1, 2, 3}. Ierarhia lui Chomsky: L3c L2c L1c L0 Incluziunile sunt stricte: orice limbaj de tip j+1 este i de tip j e {0, 1, 2}. exist limbaje de tip j care nu sunt de tip j+1, j e {0, 1, 2}.16 G. Grigoras, LFACOperaii cu limbaje Limbajele fiind mulimi, suntem ndreptii s vorbim despre reuniune, intersecie, etc. de limbaje Exist i operaii specifice : Produsul de limbaje: L1L2= { uv | u eL1, v eL2 } Iteraia (produs Kleene): L* = n>0Ln , unde L0= {c} iar Ln+1= LnL Pref(L) = { u | uv eL} LR= { wR| w eL}; dac w = a1anatunci wR= ana1 Proprieti Fiecare din familiile Ljcu 0 j 3 conine toate limbajele finite. Fiecare din familiile Ljcu 0 j 3 este nchis la operaia de reuniune17 G. Grigoras, LFACGramatici i limbaje regulate O gramatic G = (N, T, S, P) este de tip 3 (regulat) dac regulile sale sunt de forma A u sau A uB unde A, B e N iar u e T*. O gramatic de tip 3 este n form normal dac regulile sale sunt de formaA a sau A aB, undea e T, i eventual S c(n care caz S nu apare n dreapta regulilor). Orice gramatic de tip 3 admite o form normal echivalent: Orice regul de forma A a1a2anse nlocuiete cu A a1B1, B1 a2B2, , Bn-2 an-1Bn-1, Bn-1ann > 1, B1,, Bn-1 fiind neterminali noi Orice regul de forma A a1a2anB se nlocuiete cu A a1B1, B1 a2B2, ,Bn-2 an-1Bn-1, Bn-1anB n > 1, B1,, Bn-1 fiind neterminali noi Se poate arta c pot fi eliminate regulile de forma A B (redenumiri) i cele de forma A c (reguli de tergere), cu excepia, eventual a reguliiS c Transformrile care se fac nu modific limbajul generat de gramatic18 G. Grigoras, LFACExemple Considerm gramatica G1= ( {A, B} , {l,d} , A, P1)unde P1const din regulile:A lB B lB|dB|l|d l = liter, d = cifr L(G1) este mulimea identificatorilor Considerm gramatica G2= ( {A, B} , {+,-,d} , A, P2)unde P2const din regulile:A +B|-B|dB|d B dB|d d = cifr L(G2) este mulimea constantelor ntregi19 G. Grigoras, LFACProprieti de nchidere Fie L, L1, L2 limbaje regulate, ceea ce nseamn c exist gramaticile G, G1, G2 astfel ca L = L(G), L1 = L(G1) i L2 = L(G2). Atunci, urmtoarele limbaje sunt de asemenea regulate:(a) L1 L2 (b) L1 L2 (c) L1 L2(d) L1\L2 (e) L*(e) LR20 G. Grigoras, LFACProprieti de nchidereDemonstraiiFie G1 = (N1, T1, S1, P1) siG2 = (N2, T2, S2,P2) cu L1 = L(G1), L2 = L(G2)Presupunem N1 N2 = (eventual prin redenumirea simbolurilor se obine acest lucru).(a)Gramatica G = (N1 N2 {S}, T1 T2, S, P1 P2 {S S1, S S2}) genereaz limbajul L1 L2(b)Gramatica G = (N1 N2, T1 T2, (S1, S2), P), unde P const din: (S1, S2) dac S1 i S2 (A1, B1) a(A2, B2) dac A1 aA2 i B1 aB2 (A1, A2) a dac A1 a i A2 a genereaz limbajul L1 L2 (s-au considerat G1, G2 n form normal)21 G. Grigoras, LFACProprieti de nchidere(c) Gramatica G = (N1 N2, T1 T2, S1, P)unde P const din:- regulile de forma A uB din P1- reguli A uS2 pentru orice regul A u din P1- toate regulile din P2 genereaz limbajul L1L2(e) G=(N ,T,S,P)P: -reguli A uB din P-reguli A uS, pentru orice regula A u din P- regula S cgenereaz L*etc. (exerciiu)22 G. Grigoras, LFACLema de pompare (Bar Hillel)Fie L un limbaj de tip 3. Exist un numr m astfel nctoricare ar fi cuvntul w e L cu |w| m, acesta are odescompunere de forma w = xyz, unde 0 < |y| m, i xyiz e L oricare ar fi i 0.DemonstraieFie G=(N, T, S, P) astfel ca L(G)=L. Dac |N| este numrul simbolurilor din N , m=|N|+1, se arat c are loc proprietatea enunat:Fie w=a1a2.an, n m n |N|+1S a1A1a1a2A2 . a1a2akAk.. a1a2ak ak+1..asAs .a1a2ak ak+1..asas+1.an-1An-1 a1a2ak ak+1..asas+1.an-1anAk=As23 G. Grigoras, LFACLema de pompare (Bar Hillel)w=a1a2.an, n mS a1A1a1a2A2 . a1a2akAk.. a1a2ak ak+1..asAka1a2ak ak+1..asas+1.an-1An-1 a1a2ak ak+1..asas+1.an-1anAtunci: Ak * ak+1..asAk siAk *as+1.an-1anFie x= a1a2ak, y=ak+1..as si z= as+1.an-1an- Pentru i=0, xz eL(G):S a1a2akAk * a1a2ak as+1.an-1an = xz24 G. Grigoras, LFACLema de pompare (Bar Hillel)w=a1a2.an, n mS a1A1a1a2A2 . a1a2akAk.. a1a2ak ak+1..asAk a1a2ak ak+1..asas+1.an-1An-1 a1a2ak ak+1..asas+1.an-1anAk * ak+1..asAk siAk *as+1.an-1anx= a1a2ak, y=ak+1..as z= as+1.an-1an- Pentru i > 0, xyiz eL(G):S a1a2akAk *a1a2ak (ak+1..as )Ak * *a1a2ak (ak+1..as ) (ak+1..as )Ak *** a1a2ak (ak+1..as ).(ak+1..as )Ak **a1a2ak (ak+1..as ).(ak+1..as ) as+1.an-1an= xyiz25 G. Grigoras, LFAC