Limbaje algebrice

Limbaje algebrice

In acest prim capitol vom introduce gramaticile algebrice care sunt utilizate pentru a descrie limbajele de programare si anumite aspecte ale limbilor naturale. Gramaticile algebrice pot sa reprezinte limbaje care nu sunt reprezentabile de nici o expresie rationala. Tot in acest capitol vom dovedi echivalenta intre gramaticile algebrice si acceptorii nedeterministi ai stivelor. Vom defini notiuni esentiale ca ambiguitatea si vom studia cateva proprietati de inchidere. Vom vedea mai multe metode de a standardiza o gramatica algebrica in acelasi fel cu diferiti algoritmi utilizati in cimpilare. Vom da in particular un algoritm care permite testarea apartenentei la un limbaj algebric dat.

Definitia unui limbaj printr-o ecuatie

Anumite limbaje pot sa fie definite printr-o formula pe care o construim cu inceperea literelor, cu ajutorul operatiilor ??rationale (unirea, concatenarea si inmultirea ) adica printr-o expresie rationala. Exemplu :

(1

Exista totusi limbaje care nu pot sa fie definite prin nici o expresie rationala dar care pot sa fie definite implicit printr-o ecuatie unde numele limbajului apare el insusi in expresia definita :

X= # aXa bXb

(care seamana cu o definitie recursiva). Vom spune ca o asemenea ecuatie care autorizeaza unirea si concatenarea in membrul drept este o ecuatie algebrica ( am putea defini o clasa de " ecuatii algebrice intinse " autorizand

utilizarea de * in membrul drept si am obtine aceeasi clasa de limbaje solutii.

De fapt aici am urmat prezentarea clasica de limbaje algebrice).Numele limbajului necunoscut de gasit este numit variabila . Presupunem ca X = L

este o solutie a ecuatiei precedente . Aceasta ne spune ca limbajul contine

litera # si toate cuvintele de la forma awa si bwb unde w este un cuvant al lui L. Numim "pals" elementele lui L. Ecuatia definitiei lui L poate atunci sa se reformuleze in felul urmator : un "pals" poate fi # , a urmat de un "pals" el insusi urmat de un a, sa fie egal cu b ,urmat de un pals si un b. Vom putea sa calculam cu ajutorul acestei definitii "palele" interval .

lungime 1 : # e un pals

a # a , b # b - pals

aa # a , ab # ba , ba # ab , bb # bb -pals

aaa # aaa , aab # baa , aba # aba , abb # bba , baa # aab ,

bab # bab , bba # abb bbb # bbb -pals .

Daca ne intrebam de ce L este cel mai mic limbaj solutie al ecuatiei precedente , o recurenta structurala evidenta permite sa aratam ca "pals" sunt toate cuvintele simetrice pe care poseda un singur # . Pals este un sinonim al lui "palindrome a marquer central " . O aplicatie a primei teoreme iterative cu z= a^N # a^N arata ca L nu e un limbaj fixat. Ecuatiile algebrice permit sa definim limbaje pe care expresiile fixate nu le pot defini.

Vom face un pas in plus si vom defini mai multe limbaje prin sistemele de ecuatii algebrice . In genere unul dintre ele va fi limbajul vrem in mod real sa-l definim si altele vor fi limbaje auxiliare utile ca ansamblu de fraze nominale sau de predicate in gramatica . Figura 5.1 da un sistem extrem de simplificat si redus. figura 5.2 da un sistem simplificat de ecuatii descriind introducerile unui limbaj de programare de tip pascal. Prezentam un sistem de ecuatii care defineste anumite notiuni matematice , de stiut expresiile aritmetice ca : a x (b +a) x c x b + c ; care apar adesea in programare V, F, T, E desemneaza in aceste ecuatii de limbaj pe alfabetul .

V= a b c

F= V (E)

T= F T x F

E=T E + T

Variabilele sunt a,b,c.

Factorii sunt variabile sau expresii inconjurate de expresii.

Termenii sunt factori sau termeni multiplicati de un factor.

Expresiile sunt termeni sau expresii carora li sau adaugat un termen (acesta nu este sistemul de ecuatii cel mai simplu pentru expresiile aritmetice dar respecta bine regulile uzuale de precedenta ale operatorilor ) .

< fraza > = < subiect > < predicat >

< subiect > = < pronume1 > < fraza_nominala >

< pronume1 > =

< fraza_nominala > = ( L < articol >) < fraza_nominala_simpla>

< articol > =

< fraza_nominala_simpla > = < nume > < adjectiv > <fraza_nominala

simpla > <fraza_nominala_simpla > < adjectiv >

< predicat > = < verb > ( L < complement_direct >)

< complement_direct > = <fraza_nominala >

Figura 1. Un sistem foarte simplu de ecuatii algebrice.

Cuvintele dintre < , > reprezinta variabile. N-am dat ecuatii pentru <nume>, <verb> , <adj> pentru a economisi spatiu. Am omis toate notiunile gramaticale complexe ( acordul vrbului , timpuri, punctuatii ). Numeroase clase de fraze nu sunt luate in calcul de aceasta gramatica. Acest sistem autorizeaza fraze ca : "Ea conduce o frumoasa masina decapotabila neagra" dar si fraze fara coada si cap ca : " Dragutul strada iubeste groasa frumoasa prajitura normala verde ". Mai mult nu ne putem da seama de frazele complexe ca " Cand vrem sa reluam cu utilitate si sa aratam altuia ca se insala trebuie sa observam prin ce latura examineaza lucrul si sa-i marturisim acest adevar dar sa-i descoperim latura pe unde ea este stramba - deformata".

A gasi o sintaxa adecvata pentru orice limbaj fixat este o problema importanta intotdeauna nefixata.O parte a dificultatiivine din faptul ca trebuie sa avem mai multe cunostiinte pentru a ridica ambiguitati care nu pun probleme unei fiinte umane. Ganditi de exemplu ca : "Un porumbel a zburat pe cer" .

<insrtuctiune> = L <instructiune_simpla> <instructiune_compusa>

<instructiune_IF> <instructiune_WHILE> <instructiune_REPEAT>

<instructiuneFOR>

<instructiune simpla>=<CALL> < nume procedura>

<instructiune compusa>=BEGIN<lista instructiuni>END

<lista instructiuni>= <instructiune>(L ;<lista instructiuni>)

<instructiune_IF>= IF< conditie > THEN <instructiune > ( L ELSE

<instructiune> ).

<instructiune_WHILE > = WHILE <conditie > DO < instructiune >

<instructiune_REPEAT> = REPEAT <lista instructiuni> UNTIL <conditie>

<instructiune_FOR> = FOR <_ _> la <expresie > DO < instructiune >

Figura 5.2. Un sistem simplificat de ecuatii fixate pentru instructiunile unui limbaj de programare PASCAL . Cuvintele intre < , > desemneaza variabilele, pentru a ramane simplu nu am dat ecuatii pentru <CALL> si <nume procedura>