(Parte 1 de 11)

URICER – Universidade Regional Integrada do Alto Uruguai e das Missões – Campus de Erechim

Apostila de COMPILADORES

Erechim, agosto de 2001.

1 CONCEITOS BÁSICOS (revisão)4
2 LINGUAGENS E SUAS REPRESENTAÇÕES6
2.1 Conceito6
2.2 Tipos7
2.3 Especificação de uma linguagem8
3 INTRODUÇÃO À COMPILAÇÃO1
3.1 Tipos de Compilação1
3.2 Interpretação pura13
3.3 Sistemas de Interpretação Híbridos15
3.4 Construção de Compiladores16
3.5 Processadores de linguagens16
3.6 Estrutura geral de um compilador19
3.6.1 Analisador léxico (ou scanner)19
3.6.2 Analisador sintático (ou parser)20
3.6.3 Analisador semântico21
3.6.4 Otimização de código2
3.6.5 Geração de código2
3.7 Formas de construção de um compilador25
3.8 Ferramentas para a construção de compiladores26
4 ANALISADOR LÉXICO27
4.1 Função27
4.2 Reconhecimento de tokens: autômato finito27
4.3 Implementação28
5 ANALISADOR SINTÁTICO29
5.1 Função29
5.2 Especificação das regras sintáticas: gramática livre de contexto29
5.2.1 Notações29
5.2.2 Árvore de derivação ou árvore sintática30
5.2.3 Análise sintática descendente e ascendente3
5.3 Autômato de pilha36
5.4 Tipos de analisadores sintáticos36
5.4.1 Analisador sintático ascendente (bottom-up)36
5.4.2 Analisador sintático descendente (top-down)37
5.5 A Implementação da Análise Shift-Reduce através de pilhas38
5.5.1 O Analisador de gramáticas de precedência de operadores39
5.6 Simplificações de Gramáticas Livres de Contexto41
5.6.1 Símbolos Inúteis ou Improdutivos41
5.6.2 ε - Produções4
5.6.4 Fatoração47
5.6.5 Eliminação de Recursão à Esquerda49
5.7 Tipos Especiais de GLC50
5.8 Principais Notações de GLC51
5.9 Conjuntos First e Follow51
5.9.1 Conjunto First51
5.9.2 Conjunto Follow53
Lista de Exercícios de Simplificação de GLC’s56

1 CONCEITOS BÁSICOS (REVISÃO)

Segundo MENEZES (1997), os estudos sobre linguagens formais iniciaram-se na década de 50 com o objetivo de definir matematicamente as estruturas das linguagens naturais. No entanto, verificou-se que a teoria desenvolvida aplicava-se ao estudo das linguagens de programação.

A teoria de linguagens formais engloba, basicamente, o estudo das características, propriedades e aplicações das linguagens formais, bem com a forma de representação da estrutura (sintaxe) e determinação do significado (semântica) das sentenças das linguagens. Segundo FURTADO (1992), a importância desta teoria é dupla: tanto apóia outros aspectos teóricos da teoria da computação, tais como decibilidade, computabilidade, complexidade, etc. como fundamenta diversas aplicações computacionais, como por exemplo processamento de linguagens, reconhecimento de padrões, modelagem de sistemas, etc. Mas, o que é uma linguagem?

• uma linguagem é uma forma de comunicação, usada por sujeitos de uma determinada comunidade;

• uma linguagem é o conjunto de SÍMBOLOS e REGRAS para combinar esses símbolos em sentenças sintaticamente corretas.

• "uma linguagem é formal quando pode ser representada através de um sistema com sustentação matemática" (PRICE; EDELWEISS, 1989).

Assim sendo, são necessários conceitos matemáticos para o estudo das linguagens formais.

• Símbolo

letras dos alfabetos, tem-se a ordenação A < B < C << Z. A principal utilidade dos

Um símbolo é uma entidade abstrata básica sem definição formal. São exemplos de símbolos as letras, os dígitos, etc. Símbolos são ordenáveis lexicograficamente e, portanto, podem ser comparados quanto à igualdade ou precedência. Por exemplo, tomando as símbolos está na possibilidade de usá-los como elementos atômicos em definições de linguagens.

• Sentença (ou palavra)

Uma sentença (ou palavra) é uma seqüência finita de símbolos. Sejam P, R, I, M, e A símbolos, então PRIMA é uma sentença. As sentenças vazias, representadas por ε, é uma sentença constituída por nenhum símbolo.

• Tamanho de uma sentença

O tamanho (ou comprimento) de uma sentença w, denotado por |w|, é dado pelo número de símbolos que compõem w. Assim, o tamanho da sentença PRIMA é 5 e o tamanho da sentença vazia é 0.

• Alfabeto

Um alfabeto, denotado por V, é um conjunto finito de símbolos. Assim, considerando os símbolos dígitos, letras, etc., tem-se os seguintes alfabetos Vbinário = {0, 1}; Vvogais = {a, e, i, o, u}. É importante observar que um conjunto vazio também pode ser considerado um alfabeto.

O fechamento reflexivo de um alfabeto V, denotado por V*, é o conjunto infinito de todas as sentenças que podem ser formadas com os símbolos de V, inclusive a sentença vazia. O fechamento transitivo de um alfabeto V, denotado por V+ , é dado por V* - {ε}. Seja V o alfabeto dos dígitos binários, V = {0, 1}. O fechamento transitivo de V é V+

10, 1, 0, 001, 010, 01,}, enquanto que o fechamento reflexivo de V

2 LINGUAGENS E SUAS REPRESENTAÇÕES

2.1 CONCEITO

Uma linguagem formal L é um conjunto de sentenças formadas por símbolos tomados de algum alfabeto V. Isto é, uma linguagem sobre o alfabeto V é um subconjunto de V* (L ⊆ V*). Assim, por exemplo, o conjunto de sentenças válidas da língua portuguesa poderia ser definido extensionalmente como um subconjunto de {a, b, c,..., z}+ .

Uma linguagem pode ser:

• finita: quando é composta por um conjunto finito de sentenças. Seja V = {a, b} um alfabeto, L1, L2 e L3 linguagens definidas conforme segue:

L1 = {w | w ∈ V* ∧ |w| < 3}, ou seja, L1 é uma linguagem constituída por todas as sentenças de tamanho menor que 3 formadas por símbolos de V. Portanto, L1 = {ε, a, b, a, ab, ba, b}

L3 = {ε} As linguagens L2 e L3 são diferentes.

• infinita: quando é composta por um conjunto infinito de sentenças. Seja V = {a, b} um alfabeto, L1, L2 e L3 linguagens definidas conforme segue:

L1 = {w | w ∈ V* ∧ |w| MOD1 2 = 0}, ou seja, L1 é uma linguagem constituída por

a, ab, ba, b, aa, aab, aba,}

todas as sentenças de tamanho par formadas por símbolos de V. Portanto, L1 = {ε,

= {ε, a, b, a, b, aba, bab,}

L2 = {w | w é uma palíndrome2}. Portanto L2

L3 = linguagem de programação PASCAL, ou seja, o conjunto infinito de programas escritos na linguagem de programação em questão.

Como definir/representar uma linguagem? Uma linguagem finita pode ser definida através da enumeração das sentenças constituintes ou através de uma descrição algébrica. Uma linguagem infinita deve ser definida através de representação finita. Reconhecedores ou sistemas geradores são dois tipos de representações finitas. Um reconhecedor é um dispositivo formal usado para verificar se uma determinada sentença pertence ou não à linguagem. São exemplos de reconhecedores autômatos finitos, autômatos de pilha e máquinas de Turing. Um sistema gerador é um dispositivo formal usado para gerar de forma sistemática as sentenças de uma dada linguagem. São exemplos de sistemas geradores as gramáticas.

Todo reconhecedor e todo sistema gerador pode ser representado por um algoritmo.

1 MOD é uma operação que representa o rreesstto da ddiivviissãão inteira..

2 Uma palíndrome é um palavra que tem a mmessmma lleiittuurra dda essquerrdda pparra a ddiirreiitta e vviicce--vverrssa..

2.2 TIPOS

Noam Chomsky definiu uma hierarquia de linguagens como modelos para linguagens naturais. As classes de linguagens são: regular, livre de contexto, sensível ao contexto e irrestrita. As inclusões dos tipos de linguagens são apresentadas na figura abaixo.

FIGURA 8: hierarquia de Chomsky

Pode-se ver que uma linguagem do tipo 3 é também do tipo 2, uma linguagem do tipo 2 é também do tipo 1, e uma linguagem do tipo 1 é também do tipo 0. Estas inclusões são estritas, isto é, existem linguagens do tipo 0 que não são do tipo 1, existem linguagens do tipo 1 que não são do tipo 2 e existem linguagens do tipo 2 que não são do tipo 3.

As linguagens regulares constituem um conjunto de linguagens bastante simples. Essas linguagens podem ser reconhecidas por autômatos finitos, geradas por gramáticas regulares e facilmente descritas por expressões simples, chamadas expressões regulares. Segundo MENEZES (1997), algoritmos para reconhecimento e geração de linguagens regulares são de grande eficiência, fácil implementação e pouca complexidade. HOPCROFT; ULLMAN (1979) afirmam que vários são os problemas cujo desenvolvimento pode ser facilitado pela conversão da especificação feita em termos de expressões regulares na implementação de um autômato finito correspondente. Dentre as várias aplicações, podemos citar: analisadores léxicos e editores de texto. Para descrever precisamente a regra de formação (padrão) de tokens mais complexos de linguagens de programação, tais como identificadores, palavras reservadas, constantes e comentários, usa-se a notação das expressões regulares, as quais podem ser automaticamente convertidas em autômatos finitos equivalentes cuja a implementação é trivial. A operação de busca e substituição de palavras (ou trechos de palavras) também pode ser realizada através da implementação de um autômato finito a partir da especificação da expressão regular correspondente.

A importância das linguagens livres de contexto reside no fato de que especificam adequadamente as estruturas sintáticas das linguagens de programação, tais como parênteses balanceados, construções aninhadas, entre outras. A maioria das linguagens de programação pertence ao conjunto das linguagens livre de contexto e pode ser analisada por algoritmos eficientes. Essas linguagens podem ser reconhecidas por autômatos de pilha e geradas por gramáticas livre de contexto(GLC). Segundo FURTADO (1992), dentre as várias aplicações dos conceitos de linguagens livre de contexto, podemos citar: definição e

LINGUAGEM REGULAR (ou tipo 3)

LINGUAGEM LIVRE DE CONTEXTO (ou tipo 2)

LINGUAGEM SENSÍVEL AO CONTEXTO (ou tipo 1)

LINGUAGEM IRRESTRITA (ou tipo 0) especificação de linguagens de programação; implementação eficiente de analisadores sintáticos; implementação de tradutores de linguagens e processadores de texto em geral; estruturação formal e análise computacional de linguagens naturais.

Segundo MENEZES (1997), as linguagens sensíveis ao contexto e irrestritas "permitem explorar os limites da capacidade de desenvolvimento de reconhecedores ou geradores de linguagens, ou seja, estuda a solucionabilidade do problema da existência de algum reconhecedor ou gerador para determinada linguagem". Essas linguagens podem ser respectivamente reconhecidas por máquinas de Turing limitadas e geradas por gramáticas sensíveis ao contexto(GSC); reconhecidas por máquinas de Turing e geradas por gramáticas irrestritas.

MENEZES (1997) observa que nem sempre as linguagens de programação são tratadas adequadamente na hierarquia de Chomsky. Assim, para a especificação de determinadas linguagens de programação pode-se fazer necessário o uso de outros formalismos como por exemplo gramática de grafos.

2.3 ESPECIFICAÇÃO DE UMA LINGUAGEM

Foi dito que uma linguagem L é qualquer subconjunto de sentenças sobre um alfabeto V. Mas, qual subconjunto é esse, como defini-lo? Uma gramática é um dispositivo formal usado para definir qual subconjunto de V* forma determinada linguagem. A gramática define uma estrutura sobre um alfabeto de forma a permitir que apenas determinadas combinações de símbolos sejam consideradas sentenças.

O que é GRAMÁTICA? É um sistema gerador de linguagens; é um sistema de reescrita; é uma maneira finita de descrever uma linguagem; é um dispositivo formal usado para especificar de maneira finita e precisa uma linguagem infinita.

(Parte 1 de 11)

Comentários