| Materie: | Limbaje Formale |
| Categorie: | Cursuri |
| Universitatea: | Universitatea de Vest - Timisoara |
| Facultatea: | Facultatea Matematica si Informatica |
| Domeniu: | Informatica |
| Profesor(i): | Mircea Dragan |
| Descriere: |
Limbaje Formale »si Tehnici de Compilare
Dr¸agan Mircea
April 19, 2006
1
P R E F A T» ¸A
Materialul prezentat constituie notele de curs t»inute student»ilor din primii
doi ani la Sect»ia Informatic¸a a Facult¸at»ii de Matematic¸a »si Informatic¸a de la
Universitatea de Vest Timi»soara.
^In primul capitol, Introducere se trec ^³n revist¸a not»iunile fundamentale din
teoria limbajelor formale »si se prezint¸a problema general¸a a compil¸arii.
Capitolul al doilea, Limbaje regulate »si analiza lexical¸a, prezint¸a chestiunile
teoretice fundamentale privind teoria automatelor »si echivalent»a cu limbajele de
tipul trei, propriet¸at»i speciale »si mecanisme echivalente cu automatele ¯nite. Sunt
prezentate de asemenea »si principiile analizei lexicale, ¯nalizate cu realizarea unui
analizor lexical.
Capitolul al treilea, Limbaje independente de context este dedicat studiului
teoretic al mecanismelor de generare »si de recunoa»stere a limbajelor de tipul
doi. Sunt prezentate formele normale ale gramaticilor independente de context
»si c^ateva propriet¸at»i speciale.
Capitolul patru, Analiza sintactic¸a este dedicat prezent¸arii principiilor gen-
erale de analiz¸a sintactic¸a »si a algoritmilor specializat»i de analiz¸a. Pentru ¯ecare
tip de algoritm analizat s-au considerat exemple practice de aplicare.
Capitolul al cincilea, Sinteza programelor trateaz¸a formele intermediare uzuale
pentru traducerea programelor »si generarea codului obiect pornind de la for-
matul intermediar. Pentru cazul expresiilor aritmetice sunt prezentat»i »si algoritmi
direct»i de generarea a formatului intermediar, ^³mpreun¸a cu proceduri standard
de optimizare a codului generat.
Ultimul capitol, Ma»sina Turing prezint¸a succint mecanismul formal ce de-
¯ne»ste modelul de calculabilitate.
La sf^ar»situl ¯ec¸arui capitol sunt date c^ateva exercit»ii (nerezolvate), aplicat»ii
directe la chestiunile teoretice prezentate. Acestea pot ¯ parcurse ^³n cadrul orelor
de seminar »si laborator.
^In expunerea algoritmilor s-a folosit un limbaj mai put»in rigid, f¸ar¸a prea multe
reguli stricte. ^In general s-a urm¸arit descrierea c^at mai simpl¸a a structurilor care
apar ^³n text.
2
Cuprins
1 Introducere 5
1.1 Limbaje formale . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Gramatici generative de tip Chomsky . . . . . . . . . . . . . . . . 8
1.3 Ierarhia Chomsky . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Traducerea programelor . . . . . . . . . . . . . . . . . . . . . . . 17
1.5 Probleme propuse . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2 Limbaje Regulate »si Analiza Lexical¸a 23
2.1 Automate ¯nite »si limbaje regulate . . . . . . . . . . . . . . . . . 23
2.2 Propriet¸at»i speciale ale limbajelor regulate . . . . . . . . . . . . . 29
2.3 Expresii regulate »si sisteme tranzit»ionale . . . . . . . . . . . . . . 34
2.4 Analiza lexical¸a . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.5 Probleme propuse . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3 Limbaje Independente de Context 51
3.1 Arbori de derivare . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.2 Ambiguitate ^³n familia L2. . . . . . . . . . . . . . . . . . . . . . . 54
3.3 Forme normale pentru gramatici de tipul 2 . . . . . . . . . . . . . 56
3.4 Lema Bar{Hillel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.5 Automate push-down (APD) . . . . . . . . . . . . . . . . . . . . . 65
3.6 Automate push{down deterministe . . . . . . . . . . . . . . . . . 73
3.7 Probleme propuse . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4 Analiza Sintactic¸a 79
4.1 Algoritmi TOP-DOWN . . . . . . . . . . . . . . . . . . . . . . . . 80
4.1.1 Algoritmul general de analiz¸a top-down . . . . . . . . . . . 80
4.1.2 Analiza top-down f¸ar¸a reveniri . . . . . . . . . . . . . . . . 81
4.1.3 Programarea unui analizor sintactic. Studiu de caz . . . . 84
4.2 Algoritmi BOTTOM-UP . . . . . . . . . . . . . . . . . . . . . . . 90
4.2.1 Gramatici cu precedent»¸a simpl¸a . . . . . . . . . . . . . . . 90
4.2.2 Relat»ii de precedent»¸a . . . . . . . . . . . . . . . . . . . . . 92
4.2.3 Propriet¸at»i ale gramaticilor cu precedent»¸a simpl¸a . . . . . 93
3
4 CUPRINS
4.2.4 Determinarea relat»iilor de precedent»¸a pentru gramatici cu
precedent»¸a simpl¸a . . . . . . . . . . . . . . . . . . . . . . . 95
4.2.5 Studiu de caz . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.2.6 Gramatici operatoriale . . . . . . . . . . . . . . . . . . . . 97
4.2.7 Gramatici operatoriale . . . . . . . . . . . . . . . . . . . . 100
4.2.8 Determinarea relat»iilor de precedent»¸a pentru gramatici op-
eratoriale . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
4.2.9 Studiu de caz . . . . . . . . . . . . . . . . . . . . . . . . . 104
5 Sinteza Programelor 107
5.1 Forme interne ale programelor . . . . . . . . . . . . . . . . . . . . 107
5.1.1 Tabelele compilatorului . . . . . . . . . . . . . . . . . . . . 107
5.1.2 Cvadruple »si triplete . . . . . . . . . . . . . . . . . . . . . 109
5.2 Generarea formatului intermediar . . . . . . . . . . . . . . . . . . 114
5.2.1 Generarea cvadruplelor . . . . . . . . . . . . . . . . . . . . 115
5.2.2 Generarea tripletelor . . . . . . . . . . . . . . . . . . . . . 117
5.2.3 Generarea »sirului polonez . . . . . . . . . . . . . . . . . . 118
5.3 Generarea formatului intermediar pentru instruct»ii clasice . . . . . 121
5.3.1 Instruct»iunea de atribuire . . . . . . . . . . . . . . . . . . 121
5.3.2 Instructiunea If . . . . . . . . . . . . . . . . . . . . . . . . 121
5.3.3 Variabile indexate . . . . . . . . . . . . . . . . . . . . . . . 121
6 Masina Turing 123
6.1 Limbaje de tipul zero . . . . . . . . . . . . . . . . . . . . . . . . . 123
6.2 Ma»sina Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 |
| Document: |
1262989474_complexvirtual_ro_LfTc.pdf |
| Downloads: | 39 |
| Actiuni: |
Nota: Pentru a descarca acest fisier trebuie sa fiti autentificat
|
Trimite unui prieten folosind Yahoo messenger
