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. 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 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 !!) Automate echivalente. Functionarea automatelor - miscare , blocare, oprire (si stationare). Stari accesibile, stari inaccesibile. Algoritmul de determinare a starilor accesibile. . Cursul nr. 7 Ora I: Ora a II-a: 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. Cartile se gasesc la Biblioteca si la Anticariat. (real si virtual) Reveniti cu Back pe pagina principala. Pagina este in dezvoltare. (inceputa pe 6 oct 2008) Browser recomandat: Mozilla Firefox.