Projeto do Compilador - Análise Semântica

Aprendemos como um analisador constrói árvores de análise na fase de análise de sintaxe. A árvore de análise simples construída nessa fase geralmente não tem utilidade para um compilador, pois não carrega nenhuma informação de como avaliar a árvore. As produções de gramática livre de contexto, que fazem as regras da língua, não acomodam como interpretá-las.

Por exemplo

E → E + T

A produção CFG acima não tem nenhuma regra semântica associada a ela e não pode ajudar a dar qualquer sentido à produção.

Semântica

A semântica de uma linguagem fornece significado para suas construções, como tokens e estrutura de sintaxe. A semântica ajuda a interpretar os símbolos, seus tipos e suas relações uns com os outros. A análise semântica avalia se a estrutura da sintaxe construída no programa de origem obtém algum significado ou não.

CFG + semantic rules = Syntax Directed Definitions

Por exemplo:

int a = “value”;

não deve emitir um erro na fase de análise lexical e sintática, pois é lexical e estruturalmente correto, mas deve gerar um erro semântico conforme o tipo de atribuição é diferente. Essas regras são definidas pela gramática da língua e avaliadas na análise semântica. As seguintes tarefas devem ser realizadas na análise semântica:

Resolução de escopo
Verificação de tipo
Verificação de limite de matriz

Erros Semânticos

Mencionamos alguns dos erros de semântica que se espera que o analisador semântico reconheça:

Tipo incompatível
Variável não declarada
Uso indevido do identificador reservado.
Declaração múltipla de variável em um escopo.
Acessando uma variável fora do escopo.
Incompatibilidade de parâmetro real e formal.

Gramática de Atributos

A gramática de atributos é uma forma especial de gramática livre de contexto, onde algumas informações adicionais (atributos) são anexadas a um ou mais de seus não terminais para fornecer informações sensíveis ao contexto. Cada atributo tem um domínio de valores bem definido, como inteiro, flutuante, caractere, string e expressões.

A gramática de atributos é um meio para fornecer semântica à gramática livre de contexto e pode ajudar a especificar a sintaxe e a semântica de uma linguagem de programação. A gramática de atributos (quando vista como uma árvore de análise) pode passar valores ou informações entre os nós de uma árvore.

Example:

E → E + T { E.value = E.value + T.value }

A parte direita do CFG contém as regras semânticas que especificam como a gramática deve ser interpretada. Aqui, os valores dos não terminais E e T são somados e o resultado é copiado para o não terminal E.

Os atributos semânticos podem ser atribuídos aos seus valores de seu domínio no momento da análise e avaliados no momento da atribuição ou condições. Com base na maneira como os atributos obtêm seus valores, eles podem ser amplamente divididos em duas categorias: atributos sintetizados e atributos herdados.

Atributos sintetizados

Esses atributos obtêm valores dos valores de atributo de seus nós filhos. Para ilustrar, assuma a seguinte produção:

S → ABC

Se S está pegando valores de seus nós filhos (A, B, C), então é dito ser um atributo sintetizado, já que os valores de ABC são sintetizados em S.

Como em nosso exemplo anterior (E → E + T), o nó pai E obtém seu valor de seu nó filho. Atributos sintetizados nunca obtêm valores de seus nós pais ou de quaisquer nós irmãos.

Atributos herdados

Em contraste com os atributos sintetizados, os atributos herdados podem receber valores dos pais e / ou irmãos. Como na produção a seguir,

S → ABC

A pode obter valores de S, B e C. B pode obter valores de S, A e C. Da mesma forma, C pode obter valores de S, A e B.

Expansion : Quando um não terminal é expandido para terminais de acordo com uma regra gramatical

Reduction: Quando um terminal é reduzido ao seu não terminal correspondente de acordo com as regras gramaticais. As árvores de sintaxe são analisadas de cima para baixo e da esquerda para a direita. Sempre que ocorre redução, aplicamos suas regras semânticas correspondentes (ações).

A análise semântica usa traduções direcionadas por sintaxe para realizar as tarefas acima.

O analisador semântico recebe AST (Abstract Syntax Tree) de seu estágio anterior (análise de sintaxe).

O analisador semântico anexa informações de atributo com AST, que são chamados de AST atribuído.

Os atributos são dois valores de tupla, <nome do atributo, valor do atributo>

Por exemplo:

int value  = 5;
<type, “integer”>
<presentvalue, “5”>

Para cada produção, anexamos uma regra semântica.

SDT atribuído a S

Se um SDT usa apenas atributos sintetizados, é chamado de SDT atribuído a S. Esses atributos são avaliados usando SDTs atribuídos a S que têm suas ações semânticas escritas após a produção (lado direito).

Conforme descrito acima, os atributos em SDTs atribuídos a S são avaliados na análise de baixo para cima, já que os valores dos nós pais dependem dos valores dos nós filhos.

SDT atribuído a L

Esta forma de SDT usa atributos sintetizados e herdados com restrição de não receber valores de irmãos certos.

Em SDTs atribuídos a L, um não terminal pode obter valores de seus nós pai, filho e irmão. Como na seguinte produção

S → ABC

S pode obter valores de A, B e C (sintetizado). A pode obter valores de S apenas. B pode obter valores de S e A. C pode obter valores de S, A e B. Nenhum não terminal pode obter valores do irmão à sua direita.

Os atributos em SDTs atribuídos a L são avaliados pela maneira de análise de profundidade e da esquerda para a direita.

Podemos concluir que se uma definição é atribuída a S, então ela também é atribuída a L, pois a definição atribuída a L inclui as definições atribuídas a S.