Segunda Lista de Exercícios

1. Considere a gramática a seguir:

E -> ( L )
E -> a
L -> L , E
L -> E

Construa o DFA de itens LR(0) para essa gramática. Ela é LR(0)? Se não for, indentifique o conflito. Construa a tabela de análise sintática shift-reduce LR(0) (se possível) ou SLR(1).

2. Considere a gramática a seguir:

S -> S ( S )
S ->

Construa o DFA de itens LR(0) para essa gramática. Ela é LR(0)? Se não for, indentifique o conflito. Construa a tabela de análise sintática shift-reduce LR(0) (se possível) ou SLR(1).

3. Considere a gramática a seguir, para um fragmento de TINY:

LISTA -> CMD ; LISTA | CMD
CMD -> id := EXP
EXP -> id | id ( ) | num

a) Dê a sequência de ações (shift, reduce, accept) do analisador LR para o termo id := num ; id := id ().

b) Construa o DFA de itens LR(0) dessa gramática.

4. Considere a gramática a seguir:

S -> E
E -> E + E | E - E | E * E | ( E ) | id | num

a) Dê duas sequência de ações (shift, reduce, accept) do analisador LR para o termo num + num * num. Não é preciso dar o número dos estados nas ações de shift. Mostre como essas duas sequências de ações provam que a gramática é ambígua.

b) Dê o estado inicial do autômato LR(0) dessa gramática, as transições que saem desse estado, e os estados alvo dessas transições.

c) Escreva a implementação em Java de uma AST e o visitor para verificação de tipos para termos dessa gramática. Os nós da AST devem implementar a interface abaixo:

interface Exp {
  <C, R> R accept(Visitor<C, R> visitor, C ctx);
}

Para a verificação de tipos o visitor tem tipo Visitor<SymbolTable<String>, String>: um numeral literal tem tipo int, as operações aritméticas têm tipo int se suas partes tiverem tipo int, caso contrário temos um erro. O tipo dos identificadores é dado pela tabela de símbolos. Use a classe SymbolTable<T> que usamos em sala para a tabela de símbolos.

5. Um analisador LR(0) pode efetuar mais ou menos reduções que um analisador SLR(1) antes de declarar um erro? Justifique sua resposta.

6. Suponha que sejam removidas as especificações de associatividade e precedência dos operadores na especificação Jacc da gramática a seguir (tornando, portanto, a gramática ambígua). Quais seriam a associatividade e precedência dos operadores usando as regras de eliminação de ambiguidade de Jacc (shift em caso de conflito shift-reduce, reduce pela regra que vem primeiro em caso de conflito reduce-reduce)?

exp  : '(' exp ')'
     | NUM
     | ID
     | exp '<' exp
     | exp '=' exp
     | exp '+' exp
     | exp '-' exp
     | exp '*' exp
     | exp '/' exp
     ;

7. Acrescente os operadores ^ (exponenciação) e - (menos unário) à especificação de TINY. A precedência da exponenciação é maior do que a dos outros operadores binários, e ela é associativa à direita. A precedência do menos unário é maior que a dos operadores binários.

8. Considere a gramática a seguir para declarações simples em Pascal:

DECL -> VAR-LISTA : TIPO
VAR-LISTA -> VAR-LISTA , id
VAR-LISTA -> id
TIPO -> integer
TIPO -> real

Escreva a especificação de uma AST Java para termos dessa gramática e de uma interface visitor para essa AST, e implemente a verificação de tipos nessa AST como um Visitor<SymbolTable<String>, String>. Use a classe SymbolTable<T> que usamos em sala para a tabela de símbolos.

9. Considere o seguinte programa TINY:

procedure soma(x, y: int): int
  soma := x + y  { aqui }
end;
    
procedure f(int y, int z): int
  a := y;
  if a < z then
    b := 10;
    a := soma(a, b)
  end;
  f := a
end;

var a, b, c: int;
a := 0;
b := 0;
c := 10;
write f(b, c)

Desenhe a pilha (e seu conteúdo) Windows x64 para esse programa no momento em que a linha comentada é executada, a partir do registro de ativação de main, e marque na pilha a localização de cada registro de ativação.

10. Considere o seguinte programa TINY:

procedure f(x: int): int
  a := 0;
  if 0 < x then
    b := 2;
    c := 3;
    a := b + c;
  end;
  if 0 < a then
    d := 4;
    a := a - d   { aqui }
  end;
  f := a
end;
    
write f(5)

Desenhe a pilha (e seu conteúdo) Windows x64 para esse programa no momento em que a linha comentada é executada, a partir do registro de ativação de main, e marque na pilha a localização de cada registro de ativação.

11. Vetores são um tipo de dado bastante comum em linguagems de programação. Eles são um tipo composto: se t é um tipo qualquer da linguagem, t[] é um vetor em que cada elemento tem tipo t. A operação principal em um vetor é a indexação, que pode ser para leitura ou escrita.

Na indexação de leitura, uma expressão que deve ter o tipo t[] é indexada por uma expressão de tipo inteiro, e o resultado é um valor do tipo t (assumindo que o índice está dentro dos limites do vetor), o elemento correspondente ao índice.

class IndexaLe implements Exp {
  Exp vetor;
  Exp indice;
}

Na indexação de escrita, uma expressão que deve ter tipo t[] e indexada por uma expressão de tipo inteiro está do lado esquerdo de uma atribuição, e uma expressão do tipo t deve estar do lado direito. O resultado é substituir o elemento na posição dada pelo índice pelo resultado do lado direito da atribuição.

class IndexaEscreve implements Cmd {
  Exp vetor;
  Exp indice;
  Exp ldir;
}

a) Implemente a verificação de tipos para as operações de indexação de vetores, dados os fragmentos da AST acima. Assuma que o visitor de verificação de tipos é um Visitor<SymbolTable<String>, String>; se tipo é uma string, tipo.endsWith("[]") testa se é ele é um tipo vetor, e tipo.substring(0, tipo.size()-2) extrai o tipo base de um tipo vetor.

b) Implemente a geração de código para as operações de indexação de vetores, dados os fragmentos de AST acima. Assuma que o objeto Contexto para geração de código tem duas operações com vetores: iloadv() retira da pilha o endereço de um vetor e um índice, e empilha o elemento que está naquele índice, enquanto istorev() retira da pilha o endereço de um vetor, um índice e outro valor e guarda esse valor no vetor, na posição dada pelo índice.

12. Acrescente um comando for ao compilador TINY. A sintaxe é

CMD -> for ID := exp TO exp BEGIN cmds END

O comportamento de um comando for é executar o bloco até que a variável de controle ultrapasse o valor da segunda expressão dada. O valor inicial é dado pela primeira expressão, e a cada iteração o valor é incrementado em 1. Se o valor inicial for maior que o final o for não executa nenhuma vez. A variável de controle é local ao for, estando no escopo do bloco de comandos dele. As duas expressões devem ter tipo inteiro, e esse é o tipo da variável de controle também. Faça todo o trabalho: modificação do analisador léxico para incluir as palavras chave for e to, modificação do analisador sintático para gerar o nó apropriado, e implementação da classe Java que representa esse nó, com sua análise de escopos, tipo e geração de código.

12. O curto-circuito de expressões booleanas é um recurso bastante comum em linguagens de programação. No curto circuito, uma expressão e1 and e2 (e lógico) não precisa avaliar e2 se e1 já for falsa, e uma expressão e1 or e2 (ou lógico) não precisa avaliar e2 se e1 já for verdadeira.

Em um gerador de código para expressões booleanas, geralmente geramos código que salta para determinado rótulo se a expressão for falsa. Esse rótulo é dado pelo campo labFalso no Contexto de geração de código.

Faça a geração de código para as expressões LogE, correspondente a and, e LogOu, correspondente a or. Assuma que a verificação de tipo já está garantindo que tanto e1 quanto e2 são expressões booleanas, e visitá-las vai gerar código para saltar para label apontado por labFalso caso elas sejam falsas.

class LogE implements Expressao {
  Expressao esq;
  Expressao dir;
}

class LogOu implements Expressao {
  Expressao esq;
  Expressao dir;
}

public class CodegenVisitor implements Visitor<SymbolTable<Endereco>, Void> {
  ...
  public Void visit(LogE no, SymbolTable<Endereco> ctx) {
    // implemente esse método
  }
  public Void visit(LogOu no, SymbolTable<Endereco> ctx) {
    // implemente esse método
  }
  ...
}

Última Atualização: 2017-06-26 12:54