S-au facut comparatii intre implementarea din lucrare si obtinerea partii de front-end folosind unelte precum YACC?

Exista mai multe raspunsuri afirmative, bazate pe diferite argumente si diferite calitati ale limbajului Haskell si combinatorilor de parsere modulare care dovedesc superioritatea parserelor modulare in multe priviinte.

Lucrarea la care se face referinta este in intrebare este Practica interpretarii monadice care a fost extinsa la dimensiunea unei teze de doctorat.

Exemplul 1: Limbajul PI dat de o gramatica infinita

El dovedeste ca algoritmii care combina parsere modulare se pot folosi acolo unde YACC si unelte similare nu se pot utiliza sau nu se pot utiliza direct, asa cum sunt.

Plan:

• Definim o gramatica infinita care defineste la randul ei un limbaj.
• Aratam ca limbajul este decidabil si poate fi analizat cu un algoritm bazat pe parsere modulare si combinatori de parsere.
• Aratam ca parserul nu poate fi realizat cu unelte precum YACC nici:
  • folosind algoritmul de la punctul anterior
  • nici implementand in fisierul YACC gramatica infinita a limbajului

Atomii lexicali ai limbajului Se aleg 10 atomi lexicali, identificatori distincti si li se asociaza printr-o bijectie evidenta cifrele de la 0 la 9.

Definitia sintaxei Definim drept program corect de n cuvinte scris in limbajul PI secventa acestor atomi lexicali cu proprietatea ca cifrele lor asociate sunt primele n zecimale ale lui PI si nici un alt program nu este corect (sintactic).

Dovada de decidabilitate Algoritmul care decide daca un program de o anumita lungime este corect: Pas 1: Se calculeaza numarul de cuvinte din program. Fie acesta n. Pas 2: Se genereaza primele n zecimale ale lui PI. Pas 3: Parcurgand lista acestor n zecimale ale lui PI si apelind de fiecare data parserul modular care recunoaste atomul lexical cu numarul dat de cifra respectiva se verifica daca programul este corect scris.

Varianta a Pasului 3: Operatorii monadici (>>, >>=. _sequence) oferiti de monada parserelor sunt folositi pentru a construi un singur parser (din cele exact n module necesare) care este capabil sa verifice daca programul apartine limbajului. Nota: Am putea chiar spune ca este un parser adaptiv, care isi adapteaza numarul de pasi si pasii la lungimea si specificul intrarii.

Avem deci un algoritm care in timp proportional cu numarul de atomi lexicali ai intrarii decide daca un program este corect. Deci limbajul este decidabil.

Pe de alta parte, algoritmul descris apeleaza pentru analiza atomilor lexicali la parserele modulare pe care le combina.

Nota: numarul PI nu este relevant in aceasta argumentatie decat ca un furnizor al unei secvente infinite de cifre.

Argumentul 2

Deoarece limbajele de programare moderne sunt stratificate in sensul ca poseda un set de atomi lexicali (corespund nivelului L3 din Ierarhia Chomsky) iar acesti atomi lexicali servesc drept simboluri in alfabetul unui limbaj independent de context (de pe nivelu 2 din Ierarhia lui Chomsky)

rezulta imediat ca pentru orice algoritm de analiza sintactica al unui limbaj de programare putem sa inlocuim pur si simplu automatele acceptoare ale atomilor lexicali cu parsere modulsare si sa obtinem un analizor sintactic comparabil bazat pe parsere modulare.

Acest lucru nu exclude realizarea unor alte analizoare sintactice pentru limbajul respectiv, tot cu parsere modulare, si cu diferite alte avantaje sau dezavantaje.

In concluzie: parserele modulare si bibliotecile de parsere modulare sunt superioare parserelor ("rigide") realizate cu Yacc, fiind o generalizare a acestora si a altor algoritmi.

Argumentul al doilea ne garanteaza si ca pot exista implementari in Haskell (limbaj care ofera biblioteci de parsere modulare) ale algoritmilor clasici de analiza sintactica. Ajunsi in acest punct putem face din nou referinta la lucrarile lui Simon Marlow si colegii care au realizat Happy si la alte lucrari destinate parsingului transcris in limbaje functionale, fie ca foloseste sau nu combinatorii.

Alte argumente

Combinatorii de parsere sunt mult mai flexibili:

YACC si alte generatoare sunt proiectate pentru gramatici LALR. Parserele modulare se pot folosi si la alte categorii de gramatici si dau dovada de o flexibilitate superioara fiind modulare.

Aici putem cita lucrarile lui Daan Leijen despre o (alta) biblioteca de parsere modulare numita Parsec. Prin simpla folosire a unui combinator cum este "try" programatorul poate trece de la parsere cu look-ahead egal cu 1 la cele cu 2 cu n sau chiar infinit.

Bibliografie

.. in curs de elaborare Daan Leijen .. lucrari despre Parsec J.Fokker (?) - teza despre parsing in limbaje functionale Graham Hutton si Erik Meijer - lucrari despre primele biblioteci de parsere monadice modulare din care a derivat ParseLib-ul si indirect Parsec-ul. Simon P.J - A History of Haskell

---

pagina in curs de elaborare