Ro/Haskell/Limbaje formale

Folosim Haskell in cadrul lucrarilor de laborator si seminariilor de la Cursul de Limbaje Formale de la Universitatea din Bacau.
(Si nu numai noi ... asa ca mai astept sa se completeze niste pagini web ))!!!
De ce Haskell pentru limbaje formale ? Haskell este cel mai productiv limbaj functional ! Haskell este limbajul folosit de autorii limbajului Perl 6 si ales de echipa Linspire. El este folosit la productia de limbaje (DSL-uri cum este Rodin).
Iar procesarea structurilor cu substructuri are o sumedenie de alte aplicatii: proiectare automata de scheme electronice, prelucrare de texte in limbaje diferite (limbaje structurate) etc. V-am starnit curiozitatea ? Cititi: Intrebarile incepatorului. Am adaugat raspunsuri noi (16 dec. 2007- 10 feb. 2008). Vedeti si Stiri Ro/Haskell

Limbaje formale

Programa de mai jos urmeaza indeaproape jurnalul unui an precedent. In schimb bibliografia s-a actualizat. Vedeti si la Mini-Biblioteca.

Prezentarea motivatiilor existentei unui asemenea curs am facut-o la seminarul nr. 1, desfasurat (cf. orarului) inaintea cursului. (Anul scolar nu a inceput luni.)

Avertisment: Cursul va fi impartit in doua serii de expuneri, (thread-uri) interclasate. Din acest motiv este perfect posibil ca cele doua ore ale sale sa aiba grade de dificultate diferite. In aceste conditii plecarea de la ora a II-a pe motiv ca: Stiu ce se face la cursul de azi, ca am vazut la prima ora - este o atitudine nepotrivita. Riscati sa pierdeti chiar chestiile interesante.

. Cursul nr. 1

6 oct

Ora I: Notiuni matematice preliminare. Lista notiunilor inspirata de volumul Limbaje Formale si acceptori de Gabriel Orman. Incepem cu notiuni de Teoria Multimilor. Multimi, implicite, explicite, cu un element, vide, cardinal, submultime, reuniune, reuniunea unei familii de multimi, reuniunea unei familii indexate de multimi, intersectie, multimi disjuncte, familie disjuncta de multimi, complementara, proprietati algebrice, diferenta de multimi, relatiile lui De Morgan, diferenta simetrica, produsul cartezian samd. Motivatia existentei unor cursuri de limbaje formale si automate: Nevoia de a prelucra structuri de date cu substructuri. Nevoia de a scrie limbaje de programare si DSL-uri (mici limbaje specializate).

Nota: Am avut ocazia sa constat ca studentii nostri au privit recapitularea acestor notiuni ca pe ceva aproape inutil, ei declarand ca le cunosc.

Ora a II-a: Interpretoare, o privire de ansamblu, tipuri de interpretoare. Interpretorul direct al atomilor lexicali, interpretorul cu executie directa, interpretorul bazat pe compilare directa si interpretare de bytecode, interpretorul cu executie pe arborele sintaxei abstracte, interpretorul bazat pe compilare de arbore si interpretare de bytecode, altele. Exemple: Forth (1), Interpretor de expresii (2), nevoia de a avea o tabela de simboluri, masini virtuale , Java si portabilitatea. (Continuarea acestui subiect se va prezenta in cursul al II-lea). O privire generala a domeniului Limbaje formale si Automate.

De adaugat capitolul de carte despre interpretoare, pentru download.

. Cursul nr. 2

Ora I: Notiuni matematice necesare: Relatii, relatii binare, tipuri de relatii, inchiderea unei relatii. Inductie, scheme de inductie, inductie cu mai multe reguli (ev. multimi definite inductiv). Recursia, recursivitatea ca instrument de realizare a interpretoarelor / compilatoarelor. Notiuni de grafuri, varfuri/noduri, arce, drum/circuit, reprezentari grafice.

Ora a II-a: Mai multe detalii despre interpretorul pe care il vom construi: Interpretor de arbore (fara generare de bytecode). Schema generala, functiile fiecarei componente.

. Cursul nr. 3

Notiuni matematice necesare: Limbaje formale, Limbaje vazute ca multimi de cuvinte, Reuniuni si operatii cu limbaje.

Gramatici de limbaje, Derivare (exemple mai multe la seminar). ex: Gramatica unui limbaj de programare.

. Cursul nr. 4

Clasificarea gramaticilor, Ierarhia lui Chomsky, gr. de tip 0,1,2,3, exemple. Echivalenta gramaticilor, Limbaje decidabile. BNF / EBNF , despre notatii ale gramaticilor.

. Cursul nr. 5

Ora I: Automate finit deterministe.

Complexitatea analizei sintactice. De ce limbajele de tip 3 sunt interesante. O gramatica de tip 3.

Introducere informala in automate. Analogii cu lumea reala. (Broasca si automobilul de parcat... retineti acesti termeni pt. a va reaminti exemplele.) Tranzitii deterministe si tranzitii nedeterministe. AFD si AFN.

Introducere formala in automate. Modelul fizic al unui automat: banda, cap, unitate vs. modelul formal al unui automat. Configuratii si relatii de tranzitie. Configuratie reala, configuratie finala cu stare finala. Limbaje acceptate de automatele finite. Automate, reprezentari de automate, tabelar, sub forma de graf. Exemple: Limbajul cuvintelor cu numar par de zerouri si unitati. (atentie la paragraful din carte, corectati eventualele erori de tipar !!)

Ora a II-a: Haskell. Tipuri simple in Haskell (Int, Integer, Char, Bool, Float). Tipuri compuse in Haskell si constructorii lor. Liste , Perechi, T-uple, zero-uple, Functii. Variabile de tip si cel mai mic tip posibil al unei expresii. constantele sunt functii de zero argumente. Variabile de tip. cel mai mic tip posibil al unei expresii. Pattern matching. Operatorul ++, alti operatori.

. Cursul nr. 6

Haskell, functii in Haskell. (altfel n-am putea lucra cu automate, functia delta samd). Functii de nivel superior. Ex: Functia sigma de sumare. Alte functii. Functii recursive, siruri de functii. Nu se permit doua variabile identice in pattern. Pattern-uri cu garda. Functia sign -um. Functia sigma refacuta. Studentii de la sectia de TI care nu au venit la curs sunt invitati pe pagina cu Capitole de manual. Sau cititi in manualul tiparit, primele capitole, pina la Cap. all III-lea exclusiv.) Atentie: Desi cursul nu este cu prezenta obligatorie,lipsa de la curs este printre elementele asociate cu rata mare de cadere la examen. Cititi si pagina despre restantieri. Sunteti avertizati.

. Cursul nr. 7

Automate echivalente. Functionarea automatelor - miscare , blocare, oprire (si stationare). Stari accesibile. Stari productive. Algoritm de determinare a starilor accesibile si respectiv a starilor productive. Echivalenta AFD - AFN. Transformarea AFN in AFD . Exemplu.

. Cursul nr. 8

Echivalenta intre stari. (Despre minimizarea automatelor finite.) Definitia AFD redus. Automate cu epsilon miscari. Eliminarea epsilon-miscarilor. Transformarea unui AF cu epsilon tranzitii intr-un AF fara epsilon tranzitii.

. Cursul nr. 9

Expresii regulare. Definirea multimilor regulare prin inductie structurala. Expresii regulare asociate multimilor. Operatiile cu automate asociate lor. Automate cu epsilon miscari ce corespund expresiilor regulare. Exemple de limbaje. Proprietati algebrice ale expresiilor regulare.

. Cursul nr. 10

Constructia expresiei regulare echivalente cu limbajul recunoscut de un automat. (Metoda nr.1) Constructia expresiei regulare echivalente cu limbajul recunoscut de un automat. (Metoda nr.2) Exemple bazate pe rezolvarea unui sistem de ecuatii liniare.

. Cursul nr. 11

Gramatici si limbaje regulare. Echivalenta limbajelor regulare specificate prin gramatici de tip trei cu limbaje recunoscute de automate. Teorema de existenta a automatului echivalent cu o gramatica de tip 3. Teorema de existenta a gramaticii de tip 3 echivalente cu un automat.

. Cursul nr. 12

Gramatici si limbaje independente de context. Proprietati de inchidere pentru limbaje de tip doi. Reuniune, produs si iteratie (a limbajelor de tip doi). Arbori de derivare. Analiza sintactica. Analiza sintactica ascendenta si descendenta. Frontiera (uneori apare numita: frontul) unui arbore de analiza sintactica. Gramatici ambigue si gramatici neambigue. Exemple. Simplificarea gramaticilor independente de context. (Despre: simboluri inaccesibile, despre simboluri neproductive, despre simboluri neutilizabile).

. Cursul nr. 13

Simboluri neproductive. Eliminarea lor. Simboluri neutilizabile. Eliminarea lor. Epsilon productii. (Lema 4.) Eliminarea lor. Redenumiri. Eliminarea lor.

. Cursul nr. 14

Recursivitate si eliminarea recursivitatii (stangi sau drepte) Forma normala Chomsky. Exemple. Forma noramla Greibach. Exemple. Leme de pompare pentru limbaje independente de context. Alte forme normale (daca mai ramane timp).

Bibliografie neterminata :) 1. Limbaje Formale si Acceptori de Gabriel Orman ... va urma. 2. Limbaje Formale si Teoria Automatelor de Grigor Moldovan, Edusoft, 2005 3. Practica interpretarii monadice de Dan Popa - vedeti la stiri. 4. Introducere in Haskell 98 prin Exemple de Dan Popa, Edusoft, 2007

Cartile se gasesc la Biblioteca si la Anticariat. (real si virtual)

Nota: Am preferat notatiile cu epsilon nu cele cu lambda pentru notiuni cum ar fi epsilon-miscare sau epsilon-productie pentru a nu se confunda acest lambda de la limbaje formale (ex. lambda productie) cu lambda de la lambda calcul. De altfel realizand interpretoare in limbaje functionale (vedeti proiectul Rodin) avem de lucru si cu lambda expresii ca in lambda calcul, ceea ce ar fi produs o veritabila confuzie. Alte centre universitare (Iasi) folosesc totusi in teoria limbajelor formale lambda ... si nu ma intrebati cum se descurca studentii de acolo.

Reveniti cu Back pe pagina principala. http://www.haskell.org/haskellwiki/Ro/Haskell

Pagina este in dezvoltare. (inceputa pe 6 oct 2008)

Browser recomandat: Mozilla Firefox.