Baixe o app para aproveitar ainda mais
Prévia do material em texto
Prof. Sergio da Costa FerreiraProf. Sergio da Costa Ferreira sergiodcf@anhanguera.comsergiodcf@anhanguera.com CompiladoresCompiladores Geração de código intermediárioGeração de código intermediário Compiladores Introdução No modelo de análise e síntese de um compilador, os módulos de vanguarda traduzem o programa- fonte numa representação intermediária, a partir da qual os módulos da retaguarda geram o código- alvo. ANALISADOR LÉXICO ANALISADOR SINTÁTICO ANALISADOR SEMÂNTICO GERADOR CÓDIGO INTERMEDIÁRIO GERADOR CÓDIGO VANGUARDA RETAGUARDA Compiladores Introdução Apesar de se poder traduzir o programa-fonte diretamente para a linguagem-alvo, alguns benefícios em se usar uma forma intermediária independente da máquina são: Um compilador para uma máquina diferente pode ser criado atrelando-se à vanguarda existente a uma retaguarda para a nova máquina. Um otimizador de código independente da máquina pode ser aplicado à representação intermediária. Compiladores Linguagens Intermediárias As duas formas mais usuais de representação intermediária são: Código de três endereços Notação pós-fixa Compiladores Código de três endereços O código de três endereços é uma sequência de enunciados da forma geral: x := y op z Onde x, y e z são nomes, constantes ou objetos de dados temporários, op é qualquer operador. Não são permitidas expressões aritméticas construídas, na medida em que só há um operador no lado direito do enunciado. Então, uma expressão do tipo x+y*z seria traduzida assim: t1 := y * z t2 := x + t1 Compiladores Código de três endereços O código nessa linguagem intermediária tem uma estrutura próxima daquela dos programas em linguagens simbólicas, cujas instruções representam as operações elementares do processador. Por esse motivo, um programa em linguagem intermediária pode ser facilmente convertido para uma linguagem-alvo. Uma especificação de uma linguagem de três endereços envolve quatro tipos básicos de instruções: (i) atribuição, (ii) desvios, (iii) invocação de rotinas e (iv) endereçamento. Compiladores Código de três endereços (i) Instruções de atribuição Possui três formas básicas: Cópia de valor de uma variável para outra. le := ld Armazenar o resultado de uma operação. le := ld1 op ld2 Aplicação de um operador unário. le := op ld Compiladores Código de três endereços (i) Instruções de atribuição Expressões mais complexas demandam a utilização de variáveis intermediárias. Ex.: a = b + c * d Uma árvore sintática para essa expressão pode ser representada como ld1 expr op ld2:=le b +=a op ld2.2ld2.1 * dc Compiladores Código de três endereços (i) Instruções de atribuição Para a geração de código, uma estrutura de árvore simplificada é adotada. Nessa representação, os operadores são representados nos nós internos. = +a *b dc Compiladores Código de três endereços (i) Instruções de atribuição No nó * é utilizada outra operação, então na geração de código intermediário, esse nó é associado a uma variável temporária. A expressão ficaria assim: t1 := c * d a := b + t1 Compiladores Código de três endereços (ii) Desvios Possuem duas formas básicas: Desvio incondicional goto L L é o rótulo que identifica a linha do código Desvio condicional if x opr y goto L opr é um operador relacional de comparação. Compiladores Código de três endereços (ii) Desvios Interação while (i++ <= k) x [ i ] = 0; x [ 0 ] = 0; Tradução para código intermediário L1: if i > k goto L2 i := i + 1 x[i] := 0 goto L1 L2: x[0] := 0 Compiladores Código de três endereços (iii) Invocação de rotinas A invocação de rotina é normalmente realizada por uma instrução que altera o ponto de execução para outra região da memória ao mesmo tempo que preserva o ponto de execução atual, para retomá-lo quando a rotina for concluída. Na linguagem de código intermediário, a instrução call realiza a chamada de rotina. O retorno ao ponto de execução, após a conclusão da rotina, é realizada pela instrução return. Compiladores Código de três endereços (iii) Invocação de rotinas Também é usada a instrução param, que prepara cada um dos argumentos a serem consumidos pela rotina. Rotina: x = f ( a, b, c ) Tradução para código intermediário param a param b param c x := call f, 3 3 é o número de parâmetros da rotina. Compiladores Código de três endereços (iii) Invocação de rotinas Outra rotina: a = g ( b, h(c) ) Tradução para código intermediário param b param c t1 := call h, 1 param t1 a := call g, 2 A rotina h consome o último argumento passado pela instrução param (c). Já a rotina g consome os dois argumentos que ainda não haviam sido consumidos por outras rotinas (b e t1). Compiladores Código de três endereços (iv) Endereçamento Modo direto x := y Modo indireto Está associado a manipulação de variáveis que contêm endereços. x := &y, atribuição do endereço da variável y à variável x. w := *x, atribuição do valor armazenado no endereço x à variável w. *x := z, atribuição do valor da variável z à posição endereçada por x. Compiladores Código de três endereços (iv) Endereçamento Expressão: *p1 = a + *p2++ Tradução para código intermediário t1 := *p2 p2 := p2 + 4 t2 := a + t1 *p1 := t2 O conteúdo do endereço indicado por *p2 é somado ao valor de a e o resultado é atribuído ao endereço indicado por *p1. A variável *p2 está sendo incrementada de uma posição, se o valor inteiro (1) foi definido como de 4 bytes, então *p2 deve ser incrementado em 4. Compiladores Código de três endereços (iv) Endereçamento Modo indexado x := y[i] Atribui à variável x o conteúdo do endereço indicado pela soma da variável y com o valor de i. Na linguagem intermediária, z[5] leva à posição que está 20 bytes adiante da posição de z, caso z seja um vetor de inteiros de 4 bytes. Compiladores Código de três endereços (iv) Endereçamento Expressão: for (i=0; i<10; i++) s[ i ] = a[ i ] + b[ i ] Tradução para código intermediário i := 0 L1: if i >= 10 goto L2 t1 := 4*i t2 := a[t1] t3 := 4*i t4 := b[t3] t5 := t2 + t4 t6 := 4*i s[t6] := t5 i := i+1 goto L1 L2: ... Compiladores Código de três endereços Representação interna É feita dentro de uma estrutura de tabelas. O armazenamento de instruções utiliza quádruplas, que são tabelas com quatro colunas. Cada instrução é uma linha com a especificação de quatro elementos: 1º: operador 2º: primeiro argumento 3º: segundo argumento (se existir) 4º: resultado (se existir) Compiladores Representação interna Expressão: a = b + c * d z = f ( a ) Código intermediário t1 := c*d a := b + t1 param a z := call f, 1 operador arg1 arg2 resultado 1 * c d t1 2 + b t1 a 3 param a 4 call f 1 z Tabela Código de três endereços Compiladores Notação pós-fixa A notação tradicional para expressões aritméticas, que representa uma operação binária na forma x+y, ou seja, como operador entre seus dois operandos, é conhecida como notação infixa. Uma notação alternativa para esse tipo de expressão é a notação pós-fixa, na qual o operador é expresso após seus operandos. A vantagem desta notação é que ela dispensa o uso de parênteses ao adotar a noção de pilha para representação das expressões. Assim, quando um operador binário aparece na sequência, ele é aplicado aos dois últimos elementos e o resultado está disponível como um novo elemento. Compiladores Notação pós-fixa Exemplo Infixa: a + b Pós-fixa: a b + Ambos representam a mesma expressão, cuja árvore sintática é: + ba Compiladores Notação pós-fixa Exemplo Infixa: a * b + c Pós-fixa: a b * c + Árvore sintática: + c* ba Compiladores Notação pós-fixa Exemplo Infixa: a * ( b + c ) Pós-fixa: a b c + * Árvore sintática: * +a cb Compiladores Exercícios Escreva as expressões abaixo em código de três endereços x = (a + b + c) * (b + c) - d r = a * b + pow(c, 2) b[i] = a[i] + a[i-1] Compiladores Exercícios Escreva as expressões abaixo em notação pós-fixa a - (b - a * (c + b / d)) (a + b) - (a - (c – d) * (e – f)) Compiladores Exercícios Apresente o código intermediário de três endereços para o fragmento de código abaixo: i = 0; while (i < 10){ a[i] = 0; i = i + 1; } x=i; Compiladores Exercícios Apresente o código intermediário de três endereços para o fragmento de código abaixo: if(i>10){ a=i*b; b++; }else{ b=a*i; a--; } Compiladores Exercícios Apresente o código intermediário de três endereços para o fragmento de código abaixo: if(a<b){ x++; }else{ if(c<d) y++; } Compiladores Bibliografia AHO, A.; ULLMANN, J.; REVI, S.. Compiladores: princípios, técnicas e ferramentas. 3ª ed. Rio de Janeiro: LTC – Livros Técnicos e Científicos, 2006. RICARTE, IVAN. Introdução à compilação. Rio de Janeiro: Elsevier: 2008. Slide 1 Slide 2 Slide 3 Slide 4 Slide 5 Slide 6 Slide 7 Slide 8 Slide 9 Slide 10 Slide 11 Slide 12 Slide 13 Slide 14 Slide 15 Slide 16 Slide 17 Slide 18 Slide 19 Slide 20 Slide 21 Slide 22 Slide 23 Slide 24 Slide 25 Slide 26 Slide 30 Slide 33 Slide 35 Slide 37 Slide 39
Compartilhar