RUI GUSTAVO CRESPO

"A Construção de compiladores constitui uma disciplina central nos cursos de informática das universidades de todo o mundo. A presente obra, preenchendo uma lacuna no universo dos textos pedagógicos de língua portuguesa, vai certamente contribuir para uma maior difusão desta disciplina a nível nacional."

Vasco Thudichum Vasconcelos
Professor Auxiliar do Departamento de Informática
da Faculdade de Ciências de Lisboa

Depois de obter os graus de Licenciado (1981) e Mestre (1984) em Engenharia Electrotécnica e de Computadores no Instituto Superior Técnico, Rui Gustavo Crespo doutorou-se em Engenharia Informática e de Computadores, também no IST, em 1993. Actualmente é Professor Auxiliar do IST, tendo sido regente de várias disciplinas na Licenciatura em Engenharia Informática e de Computadores, nomeadamente “Ambientes de Desenvolvimento”, “Compiladores” e “Projecto de Compiladores”. Participou, em 1985, no SINTEF (Trondheim, Noruega), no projecto de reinstalação do compilador do CHILL no VAX/VMS. Estagiou, de 1989 a 1991, no Imperial College of London  (Department of Computing, sob a orientação do Prof. Manny Lehman) bem como em 1995 na Ohio State University  (Rensable Software Research Group).

INFORMAÇÕES

FORMATO: 235 x 169 mm

490 Págs.

ISBN: 972-8469-18-7   ANO: 2001  2ª Edição

PVP: € 24.00 (5% IVA incluído)

Colecção Ensino da Ciência e da Tecnologia - n.º 2

ÍNDICE

Preâmbulo ix

Prefácio xi

I - Linguagens e Processadores: Introdução 1

1 Introdução 5

1.1.1 O Que É uma Linguagem 7

1.1.2 Como Se Especifica uma Linguagem 9

1.2 Processadores de Linguagens 10

1.2.2 Tarefas dum Processador de Linguagens 12

1.2.3 Estratégias de Processamento 13

1.2.4 Compiladores, Assemblers e Interpretadores 13

1.2.5 Tratamento de Erros 20

1.2.6 Os Primeiros Compiladores 22

2 Definição de Linguagens 25

2.2 Linguagens e Expressões Regulares 29

2.2.2 Expressões Regulares 30

2.3 Gramáticas 34

2.3.2 Árvores de Derivação 40

2.3.3 Gramáticas Independentes de Contexto 42

2.3.4 Ambiguidade em Gramáticas 43

2.3.5 Recursividade 47

2.3.6 FIRST, FOLLOW e LOOKAHEAD 48

2.4 Gramáticas Reduzidas 51

2.4.2 Eliminação de Símbolos Inacessíveis 53

2.5 Gramáticas Regulares 55

2.6 Formas Normais 56

2.6.2 Formal Normal de Greibach 59

2.7 Gramáticas LL(1) 60

2.8 Gramáticas Atributivas 63

2.8.2 Grafos de Dependência Local 66

2.9 Sintaxe Abstracta 68

2.9.2 Predicados 70

2.9.3 Identificação da Sintaxe Abstracta a partir do BNF 73

2.10 Exercícios 73

II - Análise 77

3 Análise Léxica 81

3.1.1 Autómato Finito Não-Determinista-AFND 84

3.1.2 Geração de Um AFND a partir de Uma Expressão Regular 87

3.1.3 Autómato Finito Determinista-AFD 90

3.1.4 Conversão de um AFND num AFD 91

3.1.5 Conversão de Uma Expressão Regular numa Gramática Regular 95

3.2 Codificação em C de Um AFD 96

3.2.2 Estrutura de Dados de Leitura 98

3.2.3 Funções Auxiliares 98

3.3 Autómatos com Saída 99

3.3.2 Máquinas de Mealy 101

3.3.3 Equivalência entre Máquinas de Moore e de Mealy 103

3.4 Autómatos Reactivos 107

3.5 Interligação entre os Analisadores Léxico e Sintáctico 109

3.6 Exercícios 110

4 Análise Sintáctica Descendente 113

4.2 Reconhecimento Descendente 119

4.2.2 Vantagens e Inconvenientes do Método Geral de Análise Descendente 122

4.3 Analisador Descendente Antecipável 123

4.4 Analisador Descendente por Tabela 126

4.4.2 Reconhecimento de Uma Frase 127

4.4.3 Construção da Tabela do Analisador Sintáctico 130

4.5 Exercícios 131

5 Análise Sintáctica Ascendente 135

5.2 Análise Sintáctica Ascendente CKY 138

5.3 Análise Sintáctica Orientada à Precedência de Operadores 142

5.3.2 Reconhecimento de Uma Frase 147

5.4 Análise Sintáctica Ascendente LR 149

5.4.2 Tabelas do Analisador Sintáctico Ascendente LR 151

5.4.3 Reconhecimento de Uma Frase 152

5.5 Construção de Tabelas SLR 155

5.5.2 Itens LR(0) de Uma Gramática 156

5.5.3 Autómato LR(0) 156

5.5.4 Tabelas de Acções e de Saltos 160

5.5.5 Conflitos entre Acções 162

5.6 Construção de Tabelas LR Canónico 164

5.6.2 Autómato LR(1) 166

5.6.3 Tabelas de Acções e de Saltos 170

5.7 Construção de Tabelas LALR 172

5.7.2 Dimensão das Tabelas 174

5.7.3 Listagem no Yacc das Tabelas do Analisador 175

5.8 Exercícios 176

6 Análise Semântica 179

6.2 Estrutura Global da Tabela de Símbolos 190

6.2.2 Árvores 194

6.2.3 Tabelas de Dispersão 199

6.3 Avaliação de atributos 203

6.4 Eliminação de Atributos Herdados 206

6.5 Tradução Orientada pela Sintaxe 210

6.5.2 Tradução Assistida por Atributos 213

6.6 Tradução Orientada pela Semântica 214

6.7 Exercícios 216

III - Geração de Código 221

7 Código Intermédio 225

7.1.1 Representação em C de Árvores de Instruções 227

7.1.2 Geração no Yacc de Árvores de Instruções 231

7.1.3 Verificação do Tipo de Uma Árvore de Expressões 238

7.1.4 Grafos Dirigidos Acíclicos 240

7.2 Notação Pós-Fixada 241

7.2.2 Representação em C da Notação Pós-Fixada 242

7.2.3 Cálculo de Expressões em Notação Pós-Fixada 242

7.2.4 Geração no Yacc de Expressões Aritméticas 243

7.2.5 Controlo de Execução de Programas 245

7.3 Código de Triplo Endereço 247

7.3.2 Representação em C do C3E 252

7.3.3 Geração no Yacc de Expressões Aritméticas 252

7.3.4 Geração no Yacc de Acessos a Tabelas 259

7.3.5 Geração no Yacc de Expressões Booleanas 268

7.3.6 Geração no Yacc do Controlo de Fluxo de Programas 278

7.3.7 Acesso a Valores Retornados por Funções 282

7.4 Exercícios 282

8 Código Final 285

8.1.1 Distribuição de Memória 288

8.1.2 Geração de Código para um Bloco Básico 300

8.1.3 Entradas e Saídas de Dados 316

8.2 Geração de Código Final a partir de Árvores 318

8.2.2 Reescrita de Árvores 324

8.3 Exercícios 329

9 Optimização de Código 331

9.1.1 Optimização Individual 335

9.1.2 Optimização de Subexpressões 340

9.2 Optimização entre Blocos 348

9.2.2 Deslocamento de Código Invariante 351

9.2.3 Substituição de Variáveis de Ciclo 355

9.2.4 Substituição de Variáveis Induzidas 358

9.3 Optimização Global 361

9.4 Exercícios 363

A Lex e Yacc 365

A.1 Gerador de Analisadores Léxicos LEX 367

A.2 Gerador de Analisadores Sintácticos YACC 377

A.3 Interacção entre o LEX e o YACC 386

B PRECC 389

B.1 Passos na Geração de Um Analisador Sintáctico 391

B.2 Formato do Ficheiro de Especificação 392

B.2.2 Atributos 396

B.2.3 Gestão de Erros 398

C Ox 401

C.1 Inserção de Gramáticas Atributivas no Lex e no Yacc 403

C.2 Declaração de Atributos e Acesso às Suas Instâncias 404

C.2.2 Acesso às Instâncias de Atributos 405

C.2.3 Modos Anunciadores de Definições 407

C.2.4 Acesso a Instâncias de Atributos em Ficheiros L 409

C.3 Percurso de Árvores Semânticas 410

D BURG 413

D.1 Passos na Geração de Um Gerador de Código 415

D.2 Organização do Ficheiro de Especificações 416

D.2.2 Zona de Declarações 417

D.2.3 Regras 418

D.3 Rotinas do Burg 418

Referências Bibliográficas 425

Índice Remissivo 430

COMPRAR CATÁLOGO INÍCIO