Análise Contextual
• Tem o objetivo de verificar se o programa está de acordo com as restrições contextuais da linguagem fonte.
Análise Contextual
• Tipicamente, em uma linguagem com tipos estáticos e ligação estática ela:– Verifica regras de escopo;– Verifica regras de tipos;
Análise Contextual
• Consiste de duas fases:– Identificação: associa ocorrências de nomes a
suas definições– Verificação de tipos: aplica regras de tipos para
cada expressão, inferindo os tipos, e depois compara com os tipos esperados.
Identificação
• Faz a ligação entre uso de nomes e sua definição.
• Usa uma tabela de identificação (tabela de símbolos), com nome e atributos de cada identificador.
• Cada definição tem o seu escopo – parte do programa sobre a qual ela tem efeito.
• Um bloco delimita o escopo da declaração.
Escopo - Exemplo
• let D in C• proc I (FPS) ~ C
Estrutura de Blocos de um programa
• Define a organização da tabela de símbolos.• Monolítica: Basic, Cobol;• Plana: Fortran;• Aninhada: Pascal, Ada, C, Java
Estrutura de Blocos Monolítica
• O único bloco é o programa inteiro, ou seja, todas as declarações estão em um escopo global.
• Regras de escopo: – nenhum identificador pode ser declarado mais
de uma vez;– Nenhum identificador pode ser usado sem ter
sido definido.
Estrutura de Blocos Monolítica - Exemplo
• Program integer b = 10 integer n char cbegin ... n = n * b ... write cend
Ident. Attr.b (1)n (2)c (3)
Estrutura de Blocos Monolítica – em Java
public class Attribute { ... }public class IdentificationTable { public IdentificationTable( ) { ... } public void enter (String id, Attribute attr) { ... } public Attribute retrieve (String id) { ... }}
Estrutura de Blocos Plana
• O programa pode ser particionado em vários blocos disjuntos.
• Dois níveis de escopo:– Escopo local: ocorrencias de identificadores
declarados localmente são restritos a um bloco em particular
– Outras declarações têm escopo global
Exemplo Nível Ident. Attr.global Q (1)local r (2)local pi (3)
Nível Ident. Attr.global Q (1)global R (4)local c (5)
Nível Ident. Attr.global Q (1)global R (4)
procedure Q real r real pi = 3.14 begin ... endprocedure R integer c begin ... call Q ... endprogram integer i boolean b char c begin ... end
Nível Ident. Attr.Global Q (1)Global R (4)local i (6)local b (7)local c (8)
Estrutura de Blocos Plana – em Java
public class Attribute { ... }public class IdentificationTable { public IdentificationTable( ) { ... } public void enter (String id, Attribute attr) { ... } public Attribute retrieve (String id) { ... } public void openScope ( ) { ... }
public void closeScope ( ) { ... }}
Estrutura de Blocos Aninhada
• Blocos podem ser aninhados um dentro do outro.
• Vários níveis de escopo:– Declarações no nível mais externo têm escopo
global (nível 1)– Declarações dentro de um bloco interno são
locais ao bloco; cada bloco está dentro de outro bloco, com um nível a mais.
Atributos
public class Attribute { byte kind; // CONST ou VAR byte type; // BOOL ou INT public static final byte CONST = 0, VAR = 1; public static final byte BOOL = 0, INT = 1; ...}
Tipos
public abstract class Type {...}public class BoolType extends Type {...}public class CharType extends Type {...}public class IntType extends Type {...}public class RecordType extends Type { FieldList fields; }public class ArrayType extends Type { int elementCount; Type elementType; }
Atributos (2)
public abstract class Attribute {...}public class ConstAttribute extends Attribute {Type type;}public class VarAttribute extends Attribute {Type type;}public class ProcAttribute extends Attribute {FormalList formals;}public class FuncAttribute extends Attribute {FormalList formals; Type resultType;}
Atributos representados pela AST
• Informações sobre atributos são guardadas como ponteiro (referência) para os nós da árvore que contém as declarações, onde ficam informações de tipos etc.
Ambiente padrão
• Informações sobre tipos, variáveis e constantes predefinidas
• java.lang em Java• Prelude em Haskell
Verificação de Tipos
• Inferencia dos tipos de construções mais simples, e em seguida das construções mais complexas
• Literais: o tipo de um literal é obtido diretamente:325 é um inteiro, ‘a’ é um caracter etc.
• Identificador: o tipo do identificador é obtido de sua declaração.
Verificação de Tipos
• Aplicação de operador unário: expressão O E onde O tem tipo T1 T2, é verificado que E tem tipo equivalente a T1 e deduz que O E tem tipo T2 .
• Aplicação de operador binário: expressão E1 O E2 onde O tem tipo T1 T2 T3, é verificado que E1 tem tipo equivalente a T1 , E2 tem tipo equivalente a T2 e deduz que E1 O E2 tem tipo T3 .
Verificação de tipos em Java
public class Type { private byte kind; public static final byte BOOL = 0, INT = 1; public static Type (byte sort) { this.sort = sort; } public boolean equals (Object other) { Type otherType = (Type) other; return (this.kind == otherType.kind); }}
Equivalência de tipos
• Equivalência estrutural: tipos são equivalentes se sua estrutura é a mesma.Em Java a comparação seria feita com o método ‘equals’ na classe Type.
• Equivalência por nome: toda ocorrência de um construtor de tipos (array ou registro) cria um novo tipo distinto; a comparação é feita através da comparação dos ponteiros para objetos que representam tipos (em Java, usaria ‘==’)
Algorítmo de análise contextual
• O resultado da identificação pode ser guardado através de um ponteiro do local de uso para o local da definição na árvore do programa;
• O resultado da verificação de tipos é guardado anotando em cada nó da árvore o seu tipo (e.g. a classe Expression tem um atributo que guarda seu tipo).
Exemplo
let var n : Integer; var c: Charin begin c := ‘&’; n := n + 1 end
AST
n
sequentialDeclaration
Program
LetCommand
VarDeclaration VarDeclaration
Ident. Ident.
Integer
SimpleT.
c
Ident.
Char
SimpleT.
sequentialCommand
AssignCommand AssignCommand
Ident.
CharExpr.
CharLit.
‘&’
SimpleV.
c
Ident.
...
AST
1+
Program
LetCommand
sequentialCommand
AssignCommand
IntExpr.
Op.
BinaryExpr.
...
IntLit.SimpleV.
n
Ident.n
Ident.
SimpleV. VnameExpr.
...
AST decorada – Análise Contextual
n
sequentialDeclaration
Program
LetCommand
VarDeclaration VarDeclaration
Ident. Ident.
Integer
SimpleT.
c
Ident.
Char
SimpleT.
sequentialCommand
AssignCommand AssignCommand
Ident.CharLit.
‘&’
SimpleV.
c
Ident.
...: charCharExpr.
AST decorada – Análise Contextual
1+
Program
LetCommand
sequentialCommand
AssignCommand
Op.
...
IntLit.
n
Ident.n
Ident.
SimpleV.
...
: int
: int : intSimpleV. IntExpr.
: int
: intVnameExpr.
BinaryExpr.
Novos atributos
public abstract class Expression extends AST { public Type type; … }public abstract class Vname extends AST { public Type type; public boolean variable; }public class Identifier extends Terminal { public Declaration decl; }public class Operator extends Terminal { public OperatorDeclaration decl; }
Implementando a análise contextual
• Uso do padrão de projetos Visitor• Esse padrão de projeto será usado também para
geração de código.
Classes e Objetos Visitorpublic interface Visitor {
public Object visitProgram (Program prog, Object arg);public Object visitAssignCommand (AssignCommand com, Object arg);public Object visitCallCommand (CallCommand com, Object arg);...Public Object visitBinaryExpression (BinaryExpression expr, Object arg);...
}
Mudando a classe AST
public abstract class AST { ... public abstract Object visit (Visitor v, Object arg);}public class AssignCommand extends Command { ... public Object visit (Visitor v, Object arg) { return v.visitAssignCommand(this, arg); }}
VisitAssignCommand
public Object visitAssignCommand (AssignCommand com, Object arg) { Type vType = (Type) com.V.visit(this, null); Type eType = (Type) com.E.visit(this, null); if (! com.V.variable) ... if (! eType.equals(vType)) ...
return null;}
VisitSequentialCommand
public Object visitSequentialCommand (SequentialCommand com, Object arg) { com.C1.visit(this, null); com.C2.visit(this, null); return null;}
VisitIfCommand
public Object visitIfCommand (IfCommand com, Object arg) { Type eType = (Type) com.E.visit(this, null); if (! eType.equals(Type.bool)) ... com.C1.visit(this, null); com.C2.visit(this, null); return null;}
VisitLetCommand
public Object visitLetCommand (LetCommand com, Object arg) { idTable.openScope( ); com.D.visit(this, null); com.C.visit(this, null); idTable.closeScope( ); return null;}
VisitBinaryExpression
public Object visitBinaryExpression (BinaryExpression expr, Object arg) { Type e1Type = (Type) expr.E1.visit (this, null); Type e2Type = (Type) expr.E2.visit (this, null); OperatorDeclaration opdecl = (OperatorDeclaration) expr.O.visit (this, null); if (opdecl instanceof BinaryOperatorDeclaration) ... return expr.type;}
Classe Checker
public final class Checker implements Visitor {private IdentificationTable idTable;...public void check (Program prog) { idTable = new IdentificationTable ( ); idTable.enter(“false”,...); ... prog.visit(this, null);}
}