AS COMPILADORES - Análise Léxica e Análise Sintática

Resumo

Compiladores

- Quantificadores:

? : 0 ou 1 ocorrência

+ : 1 ou mais ocorrências

* : 0 ou mais ocorrências

Capítulo 3 - A ANÁLISE LÉXICA:

Linguagem Lex: linguagem de ações baseada em padrões para a especificação de analisadores léxicos. Os padrões são especificados por expressões regulares e um compilador Lex pode gerar um autômato finito que reconheça as expressões regulares.

Analisador léxico: é a primeira fase de um compilador. Sua tarefa principal é a de ler os caracteres de entrada e produzir uma sequência de tokens que o parser utiliza para a análise sintática. Ele também realiza algumas tarefas secundárias, como: remover os comentários e os espaços em branco (espaços, tabulações e caracteres de avanço de linha), controlar o número de caracteres examinados (mensagens de erro) do programa-fonte.

Padrão (regra): reconhece cada cadeia do conjunto. Descreve o conjunto de lexemas que podem representar um token particular nos programas-fonte.

Lexema: conjunto de caracteres no programa-fonte que é reconhecido pelo padrão de algum token.

Tokens: símbolos terminais.

Exemplo

TOKEN

LEXEMA

DESCRIÇÃO INFORMAL DO PADRÃO

relação

< , > , <= , >= , != , =

< ou > ou <= ou >= ou != ou =

id

pi, contador, D2

letra seguida por letras e/ou dígitos

num

3.1416 , 0

qualquer constante numérica

Erros léxicos: possíveis ações de recuperação de erros -> remover um caractere estranho, inserir um caractere ausente, substituir um caractere incorreto por um correto, transpor dois caracteres adjacentes. Uma forma de se encontrar erros no programa é computar o número mínimo de transformações de erros requeridas para tornar um programa errado em um que seja sintaticamente bem formado.

Assuntos da prova (Paloma me passou): Encontrar a linguagem de uma gramática, ambiguidade, recursividade à esquerda, derivações topdown e bottonup. (capítulos 3 e 4 do livro)

Compilador x Interpretador

Um compilador é um programa de sistema que traduz um programa descrito em uma linguagem de alto nível para um programa equivalente em código de máquina para um processador. Ex.: Java, C, C++, C#, Rust, Switch.

Vantagens dos compiladores: o código já é traduzido para a linguagem de máquina, com isso, se obtém um tempo menor de execução;

a confiabilidade do código final, já que os processos do compilador são bem severos e conseguem validar e otimizar muito bem o código.

Desvantagens dos compiladores: você não pode mudar o código sem ter que recompilar todo o programa;

mesmo com diversas otimizações, o compilador acaba sofrendo com o seu tempo de finalização do código;

outro problema que podemos ter é no suporte de várias versões de um programa que é gerado a partir do mesmo compilador.

O interpretador também é um programa, porém, ele não tem o processo de traduzir todo o programa em um arquivo para conseguir rodar, e sim, ele inclui cada instrução da sua linguagem de alto nível no código de máquina. Ex.: PHP, JavaScript, Lisp, Matlab, Perl.

Vantagens dos interpretadores: são fáceis de usar, especialmente para iniciantes;

a execução é linha por linha, sendo assim fica mais fácil de encontrar o erro;

nenhum código intermediário, por tanto, utiliza a memória de maneira mais inteligente.

Desvantagens dos interpretadores: o tempo de execução é muito grande, devido a forma de que se é traduzido;

para ser executado deve-se ter um programa correspondente ao interpretador;

menos seguro.

Fases do Compilador

Análise léxica (fluxo de tokens) -> Análise sintática (árvore de parsing) -> Análise semântica (árvore de parsing - semanticamente verificável) -> geração de código intermediário (código de três endereços) -> otimização de código (código de três endereços) -> geração de código (assembly)

Gramática

Mecanismo de geração (de palavras) de uma linguagem.

G = (V, T, P, S)

V -> variáveis

T -> terminais

P -> regras de produção

S -> variável inicial

Conclusão: assim é possível notar que iniciando a derivação com produções diferentes, obtivemos árvores diferentes para uma mesma gramática e para um mesmo w. Dessa forma, constatamos que há ambiguidade na gramática.

A gramática deve ser: não ambígua, recursiva à direita e determinística.

Ambiguidade de gramática

Quando há derivações diferentes, ou seja, árvores de derivação diferentes pertencentes à mesma palavra. Problema: o compilador (analisador sintático) não tem como saber qual das árvores ele tem que escolher. E no caso de operações matemáticas onde há uma hierarquia entre os operadores aritméticos, pode causar erro (cálculo e resultados errados). Não há uma outra forma de determinar se uma gramática é ambígua ou não senão na tentativa e erro. Como nos exemplos pega-se uma palavra mínima (de preferência) e faz a derivação, caso haja árvores diferentes, a gramática é ambígua.

Se a árvore