Cuprins
- 1 INTRODUCERE - ORGANIZAREA UNUI COMPILATOR 2
- 1.1 Analiza lexicala 4
- 1.2 Analiza sintactică 4
- 1.3 Analiza semantică 5
- 1.4 Generarea de cod intermediar 5
- 1.5 Optimizarea codului intermediar 5
- 1.6 Generarea codului obiect 6
- 1.7 Optimizarea codului obiect 6
- 1.8 Gestiunea tabelei de simboluri 6
- 1.9 Detectarea erorilor 6
- 2 ELEMENTE DE TEORIA LIMBAJELOR FORMALE 7
- 2.1 Gramatici 7
- 2.1.1 Ierarhia Chomsky 8
- 2.1.1.1 Exerciţii 9
- 2.1.2 Verificarea limbajului generat de către o gramatică 10
- 2.1.2.1 Exerciţii 11
- 2.1.3 Transformări asupra gramaticilor independente de context 11
- 2.1.3.1 Eliminarea ambiguităţii 12
- 2.1.3.2 Eliminarea λ- producţiilor 16
- 2.1.3.3 Eliminarea recursivităţii stânga 16
- 2.1.3.4 Factorizare stânga 18
- 2.1.3.5 Eliminarea simbolilor neterminali neutilizaţi 19
- 2.1.3.6 Substituţia de începuturi(corner substitution) 20
- 2.1.4 Construcţii dependente de context 22
- 2.1.4.1 Exerciţii 23
- 2.1.5 Proprietăţi ale limbajelor independente de context 24
- 2.1.5.1 Exerciţii 25
- 2.2 Mulţimi regulate, expresii regulate 25
- 2.3 Acceptoare 28
- 2.3.1 Automate finite 29
- 2.3.1.1 Construcţia unui automat finit nedeterminist care acceptă limbajul descris de o expresie regulată
- dată 30
- 2.3.1.2 Conversia unui automat finit nedeterminist (AFN) într-un automat finit determinist(AFD) 34
- 2.3.1.3 Construcţia unui automat finit determinist care acceptă limbajul descris de o expresie regulată
- dată 37
- 2.3.1.4 Simularea unui automat finit determinist 43
- 2.3.1.5 Simularea unui automat finit nedeterminist 44
- 2.3.1.6 Probleme de implementare pentru automatele finite deterministe şi nedeterministe 45
- 2.3.1.7 Minimizarea numărului de stări pentru AFD 46
- Irina Athanasiu 3/1/2002 Limbaje formale şi automate
- 2
- 2.3.2 Automate cu stivă (pushdown) 49
- 2.3.2.1 Automate cu stivă cu acceptare prin stivă goală 52
- 2.3.2.2 Relaţia între automate cu stivă şi limbajele independente de context 53
- 2.3.3 Maşina Turing 57
- 2.3.3.1 Calcule realizate de Maşina Turing 60
- 2.3.3.2 Compunerea maşinilor Turing 63
- 2.3.3.3 Extensii pentru maşina Turing 67
- 2.3.3.4 Automate liniar mărginite 73
- 2.3.3.5 Relaţia între maşina Turing şi gramatici 74
- 2.3.3.6 Elemente de calculabilitate 77
- 2.3.3.6.1 Maşina Turing Universală 77
- 2.3.3.7 Maşina Turing cu limită de timp 81
- 3 2. ANALIZA LEXICALĂ 83
- 3.1 Interfaţa analizorului lexical 87
- 3.2 Un exemplu elementar de analizor lexical 89
- 4 ANALIZA SINTACTICĂ 99
- 4.1 Analiza sintactica top - down 103
- 4.1.1 Analiza sintactica predictiva (descendent recursiva) 104
- 4.1.1.1 Gramatici LL(1) 109
- 4.1.1.2 Tratarea erorilor în analiza predictivă 115
- 4.1.2 Analiza sintactica bottom-up 117
- 4.1.2.1 Analiza sintactica de tip deplaseaza şi reduce 117
- 4.1.2.2 Implementarea analizei sintactice bottom-up deplasează şi reduce 117
- 4.1.2.3 Analiza sintactica de tip LR(k) 121
- 4.1.2.3.1 Analiza SLR 129
- 4.1.2.3.2 Analiza canonica LR 136
- 4.1.2.3.3 Analiza sintactică LALR 142
Extras din curs
1 Introducere - organizarea unui compilator
Un compilator este un program complex care realizează traducerea unui program sursă într-un
program obiect. De obicei programul sursă este scris într-un limbaj de nivel superior celui în care este
scris programul obiect.
Structura generală pentru un compilator este:
Irina Athanasiu 3/1/2002 Limbaje formale şi automate
În acest arbore au fost evidenţiate relaţiile (din punctul de vedere al modului de evaluare) între
componentele expresiei. Dacă se doreşte însă să se evidenţieze structura expresiei din punctul de vedere al
unităţilor sintactice din care este formată, atunci se va utiliza pentru reprezentarea expresiei un arbore de
derivare (parse tree). Pentru exemplul considerat un arbore de derivare ar putea să fie de forma:
Preview document
Conținut arhivă zip
- Limbaje Formale si Automate.pdf
Alții au mai descărcat și
Scopul lucrarii: 1. În descrierea neformală a unui limbaj dată să se evidenţieze lexemele. Pentru fiecare tip de lexemă să se construiască un...
Dupa cum multi dintre noi cunosc ,atomul este format din particule materiale si anume un nucleu incarcat electric pozitiv si mai multi electroni...
CAPITOLUL 1. TEORIA BAZELOR DE DATE RELATIONALE 1.1. MODELUL RELATIONAL Modelul relational a fost propus de catre IBM si a revolutionat...
Java - Sectiunea 3 Reducerea efectului de palpaire la crearea animatiilor Efectul suparator de palpaire a imaginii in cazul animatiilor, se poate...
Arbori Binari Optimi Despre arbori binari optimi putem vorbi atunci cand, pentru fiecare dintre cheile unui arbore binar ordonat cunoastem...
Computer Graphics Cristian Rusu Office 3-8 cristian.rusu@ucv.cl What will be? It will not be an ENGLISH course! ENGLISH will be an...
Te-ar putea interesa și
I. EXPRESII REGULATE 1. Introducere Ce este o expresie regulată- O expresie regulată, pe scurt denumită şi RegEx sau RegExp, este un şir de...
Calcul adn Calculatoarele de astăzi sunt de milioane de ori mai puternice decât rudimentarii lor strămoşi din anii 40 sau 50. Aproape la fiecare...
#include <iostream.h> #include <conio.h> #include <string.h> #include "afd.h" #include "afdc.h" #define L 100 void main(){ clrscr(); AFD a;...
Scopul lucrării: 1.Pentru gramatica formală G=(VN, VT, P, S) construiţi 5 şiruri care aparţin limbajului L(G) generat de această gramatică....
Lucrarea practică № 1 1. Pentru gramatica formală G=(VN, VT, P, S) construiți 5 șiruri care aparțin limbajului L(G) generat de această gramatică....
1. Descrierea logică a functionării sistemelor cu evenimente discrete 1.1 Consideratii teoretice Sistemele cu evenimente discrete (SED) se...
INTRODUCERE Interacţia cu sfera obiectelor tehnice se realizează astăzi, din ce în ce mai mult prin gestul binar al tastării. Apăsam sau nu pe...
INTRODUCERE Interacţia cu sfera obiectelor tehnice se realizează astăzi, din ce în ce mai mult prin gestul binar al tastării. Apăsam sau nu pe...