Un limbaj natural sau artificial (in particular multimea programelor corecte intr-un limbaj de programare dat) este o multime de secvente formate cu caracterele (simbolurile) unei multimi date (vocabular). Daca un limbaj este finit, atunci reprezentarea limbajului se poate face prin enumerarea secventelor sale. Daca limbajul este infinit atunci sunt necesare metode finite de reprezentare a multimii infinite de secvente. In acelasi timp, metodele de reprezentare trebuie sa reflecte o anumita structura a secventelor, specifica limbajului considerat.
Se porneste cu o secventa oarecare si se analizeaza daca secventa face parte din limbajul dat.
Altfel spus, secventele limbajului dat sunt recunoscute sau acceptate.
Metodelor generative le corespund gramaticile formale.
O gramatica formala genereaza secventele unui limbaj.
Metodelor analitice le corespund automatele. Un automat recunoaste sau accepta secventele unui limbaj.
Prin alfabet intelegem orice multime finita si nevida. Uneori in locul termenului de alfabet se foloseste termenul echivalent vocabular.
Elementele unui alfabet se numesc simboluri sau caractere.
unde 2. SISTEME DE RESCRIERE Notiunea de sistem de rescriere permite tratarea unitara a celor doua modele de descriere a limbajelor: modelul generativ si modelul analitic. Ideea de baza a acestei notiuni este aceea ca secventele unui limbaj se pot obtine unele din altele prin rescrierea anumitor subsecvente. Definitie. Un sistem de rescriere este un cuplu SR= (V, P) unde V este un alfabet iar P este o multime finita de perechi de secvente pe alfabetul V.
daca secventele si (admit reprezentarea: Notatia (pentru relatia deriva direct a devenit o notatie consacrata in teoria limbajelor formale.
Cand aceasta notatie se foloseste intr-un context in care apare si implicatia logica, vom prefera sa folosim pentru implicatia logica notatia (Putem considera si puterile relaiei (. De obicei, notiunile generale de sisteme de rescriere si limbaj generat definite mai sus li se aduc modificari. Una dintre acestea consta in partitionarea vocabularului V in doua submultimi: O alta modificare ar fi aceea ca multimea AX sa contina o singura axioma X.
In raport cu aceste modificari, limbajul generat de sistemul de rescriere definit in relatia (4) se inlocuieste cu: Transformarea unui sistem de rescriere intr-un mecanism analitic se face prin fixarea unui sistem de axiome.
De aceasta data axiomele vor fi rezultatul derivatiei.
Sunt acceptate (sau recunoscute) de catre sistemul de rescriere SR acele secvente w pe vocabularul terminal care prin aplicarea unui numar finit de reguli de rescriere se reduc la axioma X.
CAPITOLUL II LIMBAJE INDEPENDENTE DE CONTEXT A?1. Gramatici formale.
Gramaticile formale sunt cazuri particulare de sisteme de rescriere.
Spunem ca G este de tip 0 (fara restrictii). In realitate toate incluziunile precedente sunt stricte. Se spune ca gramatica G este dependenta de context daca toate productiile sale sunt de forma A?2. GRAFURI SI ...
AHO A. , ULLMAN J. - "THE THEORY OF PARSING" - TRANSLATION AND COMPILING, PRENTICE - HALL, 1972
CAZANESCU V. - "INTRODUCERE IN TEORIA LIMBAJELOR FORMALE" - EDITURA ACADEMIEI, BUCURESTI, 1983
DINCA A. , ANDREI M. - "LIMBAJE FORMALE SI APLICATII" - EDITURA UNIVERSITARIA, CRAIOVA, PAG. 316, 2002
HOPCROFT J. , ULLMAN J. - "INTRODUCTION TO AUTOMATA THEORY" - LANGUAGES AND COMPUTATION, ADDISON - WESLEY, 1979
HOPCROFT J. , ULLMAN J. - "FORMAL LANGUAGES AND THEIR RELATION TO AUTOMATA" - ADDISON - WESLEY, 1969
IANCU I. - "PROIECTAREA COMPILATOARELOR" - EDITURA UNIVERSITARIA, CRAIOVA, 2002
MARCUS S. - "GRAMATICI SI AUTOMATE FINITE" - EDITURA ACADEMIEI, BUCURESTI, 1964
SALOMAA A. - "FORMAL LANGUAGES" - ACADEMIC PRESS, NEW YORK, 1973
SALOMAA A. , ROZENBERG G. - "HANDBOOK OF FORMAL LANGUAGES" - SPRINGER, 1977
RUS T. - "MECANISME FORMALE PENTRU SPECIFICAREA LIMBAJELOR" - EDITURA ACADEMIEI, BUCURESTI, 1983
SIMOVICI D. - "LIMBAJE FORMALE SI TEHNICI DE COMPILARE" - EDITURA DIDACTICA SI PEDAGOGICA, BUCURESTI, 1978
SERBANATI L. D. - "LIMBAJE DE PROGRAMARE SI COMPILATOARE" - EDITURA ACADEMIEI, BUCURESTI, 1987
VAIDA D. - "LIMBAJE FORMALE SI TEHNICI DE COMPILARE" - TIPOGRAFIA UNIVERSITATII DIN BUCURESTI, 1976
VAIDA D. - "LIMBAJE FORMALE SI TEHNICI DE COMPILARE" - TIPOGRAFIA UNIVERSITATII DIN BUCURESTI, 1984
Pentru a descărca acest document,
trebuie să te autentifici in contul tău.
