Segunda Lista de Exercícios

1. Considere a gramática a seguir:

  E -> ( L ) | a
  L -> L , E | 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 LR(0) (se possível) ou SLR(1).

2. Considere a gramática a seguir:

  S -> S ( S ) | *vazio*

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 LR(0) (se possível) ou SLR(1).

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

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

5. 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?

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

6. Acrescente os operadores de comparação <=, >, >= e <> (diferente de) à espeficação Jacc do analisador sintático TINY.

7. Acrescente os operadores booleanos and, or e not à especificação Jacc do analisador sintático TINY.

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

  decl -> var-lista : tipo
  var-lista -> var-lista , id | id
  tipo -> integer | real

Escreva a especificação de uma AST Java para termos dessa gramática, e implemente a verificação de tipos nessa AST. Assuma que já existe a implementação de uma tabela de símbolos nos moldes da que foi vista em sala.

9. Apresente uma organização possível para os ambientes de execução do programa C a seguir, após entrar nos blocos A da função f e B da função g:

int a[10];
char *s = "hello";

int f(int i, int* b) {
  int j = i;
  A:
  {
    int i = j;
    int c = b[i];
    ...
  }
  return 0;
}

int g(char * s) {
  char c = s[0];
  B:
  {
    int a[5];
    ...
  }
}

int main() {
  int x = 1;
  x = f(x, a);
  g(s);
  return 0;
}

10. Considere o procedimento em C a seguir:

void f(char c, char s[10], double r) {
  int *x;
  int y[5];
}

Com base nas convenções de passagem de parâmetros C x86, e assumindo que inteiros e endereços têm 4 bytes, caracteres têm 1 byte e doubles têm 8 bytes, determine os deslocamentos a partir de EBP para os seguintes casos: c, s[7], y[2]. Lembre-se que os parâmetros são passados por valor.

11. Execute o programa em C a seguir e explique sua saída em termos do ambiente de execução:

#include <stdio.h>

void g() {
  {
    int x;
    printf("%d\n", x);
    x = 3;
  }
  {
    int y;
    printf("%d\n", y);
  }
}

int *f() {
  int x;
  printf("%d\n", x);
  return &x;
}

void main() {
  int *p;
  p = f();
  *p = 1;
  f();
  g();
}

12. Acrescente construções while e do-while ao compilador TINY, indo desde o analisador léxico até a geração de código.