• Autentificare
  • Înregistrarea
Conspecte.ro » Conspcete » Curs » INTRODUCERE - ORGANIZAREA UNUI COMPILATOR

0
0
00


Continul conspectului

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
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:

Descarcarea Conspectului

Vizitator, lasă un comentariu?

Nume:*
E-Mail:



Last Viewed