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>, Void>. Use a classe SymbolTable<T> que usamos em sala para a tabela de símbolos.

9. 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: loadv() retira da pilha o endereço de um vetor e um índice, e empilha o elemento que está naquele índice, enquanto storev() 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.

10. 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.

11. 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 topo da pilha de labels 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. Caso uma expressão booleana seja visitada com a pilha de labels vazia ela deve gerar código para empilhar seu valor booleano, ao invés de saltar para um label específico.

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
  }
  ...
}

12. Referências são um recurso em algumas linguagens de programação em que podemos apontar para uma variável ou parte de uma estrutura de dados e tanto acessar o valor que está lá quanto escrever um novo valor lá. Existem três operações com referências: obter uma referência para algo atribuível (um l-value), ler uma referência para obter seu valor, e guardar um novo valor em uma referência.

As classes abaixo correspondem aos nós da AST para as duas operações de referências, Ref, que cria uma referência para uma variável, Deref, que lê o valor de uma referência, e Aref, que atualiza uma referência:

class Ref implements Exp {
  String id;
}

class Deref implements Exp {
  Exp ref;
}

class Aref implements Cmd {
  Exp ref;
  Exp val;
}

Podemos representar o tipo de uma referência com "^t", onde t é o tipo base da referência. Implemente as funções do visitor de verificação de tipos Visitor<SymbolTable<String>, String> para referências. Você pode verificar que a string tipo corresponde a um tipo referência com tipo.startsWith("^"), e pode obter o tipo base com tipo.substring(1).

Última Atualização: 2018-06-05 18:03