Fabio Mascarenhas

MAB 471 - Compiladores I

Gabarito P2 2012.2 - 11/03/2013

1.

a) Contagem das regras começa de 1:

shift
shift
reduce 7
shift
shift
reduce 7
shift
reduce 4
shift
reduce 7
shift
shift
reduce 5
reduce 2
shift
reduce 7
shift
shift
shift
shift
shift
reduce 6
reduce 3
shift
reduce 1
accept

A sequência de configurações até o accept (não era necessária na resposta):

<<EOF>>,0 | class id extends id { id id ; id id ( ) { } }
<<EOF>>,0 class,1 | id extends id { id id ; id id ( ) { } }
<<EOF>>,0 class,1 id,2 | extends id { id id ; id id ( ) { } }
<<EOF>>,0 class,1 TIPO,3 | extends id { id id ; id id ( ) { } }
<<EOF>>,0 class,1 TIPO,3 extends,4 | id { id id ; id id ( ) { } }
<<EOF>>,0 class,1 TIPO,3 extends,4 id,2 | { id id ; id id ( ) { } }
<<EOF>>,0 class,1 TIPO,3 extends,4 TIPO,5 | { id id ; id id ( ) { } }
<<EOF>>,0 class,1 TIPO,3 extends,4 TIPO,5 {,6 | id id ; id id ( ) { } }
<<EOF>>,0 class,1 TIPO,3 extends,4 TIPO,5 {,6 MEMBROS,7 | id id ; id id ( ) { } }
<<EOF>>,0 class,1 TIPO,3 extends,4 TIPO,5 {,6 MEMBROS,7 id,2 | id ; id id ( ) { } }
<<EOF>>,0 class,1 TIPO,3 extends,4 TIPO,5 {,6 MEMBROS,7 TIPO,8 | id ; id id ( ) { } }
<<EOF>>,0 class,1 TIPO,3 extends,4 TIPO,5 {,6 MEMBROS,7 TIPO,8 id,12 | ; id id ( ) { } }
<<EOF>>,0 class,1 TIPO,3 extends,4 TIPO,5 {,6 MEMBROS,7 TIPO,8 id,12 ;,13 | id id ( ) { } }
<<EOF>>,0 class,1 TIPO,3 extends,4 TIPO,5 {,6 MEMBROS,7 CAMPO,11 | id id ( ) { } }
<<EOF>>,0 class,1 TIPO,3 extends,4 TIPO,5 {,6 MEMBROS,7 | id id ( ) { } }
<<EOF>>,0 class,1 TIPO,3 extends,4 TIPO,5 {,6 MEMBROS,7 id,2 | id ( ) { } }
<<EOF>>,0 class,1 TIPO,3 extends,4 TIPO,5 {,6 MEMBROS,7 TIPO,8 | id ( ) { } }
<<EOF>>,0 class,1 TIPO,3 extends,4 TIPO,5 {,6 MEMBROS,7 TIPO,8 id,12 | ( ) { } }
<<EOF>>,0 class,1 TIPO,3 extends,4 TIPO,5 {,6 MEMBROS,7 TIPO,8 id,12 (,14 | ) { } }
<<EOF>>,0 class,1 TIPO,3 extends,4 TIPO,5 {,6 MEMBROS,7 TIPO,8 id,12 (,14 ),15 | { } }
<<EOF>>,0 class,1 TIPO,3 extends,4 TIPO,5 {,6 MEMBROS,7 TIPO,8 id,12 (,14 ),15 {,16 | } }
<<EOF>>,0 class,1 TIPO,3 extends,4 TIPO,5 {,6 MEMBROS,7 TIPO,8 id,12 (,14 ),15 {,16 },17 | }
<<EOF>>,0 class,1 TIPO,3 extends,4 TIPO,5 {,6 MEMBROS,7 METODO,9 | }
<<EOF>>,0 class,1 TIPO,3 extends,4 TIPO,5 {,6 MEMBROS,7 | }
<<EOF>>,0 class,1 TIPO,3 extends,4 TIPO,5 {,6 MEMBROS,7 },10 |
<<EOF>>,0 CLASSE,null |

b) O nó do autômato:

CLASSE -> class TIPO extends TIPO { MEMBROS . }
MEMBROS -> MEMBROS . CAMPO
MEMBROS -> MEMBROS . METODO
CAMPO -> . TIPO id ;
METODO -> . TIPO id ( ) { }
TIPO -> . id

Transição em } para:

CLASSE -> class TIPO extends TIPO { MEMBROS } .

Transição em CAMPO para:

MEMBROS -> MEMBROS CAMPO .

Transição em METODO para:

MEMBROS -> MEMBROS METODO .

Transição em TIPO para:

CAMPO -> TIPO . id ;
METODO -> TIPO . id ( ) { }

Transição em id para:

TIPO -> id .

2.

a)

boolean subClasseDe(Classe sup) {
  // Toda classe é subclasse dela mesma
  if(this == sup)
    return true;
  // Sou a raiz da árvore, então não sou
  // subclase de ninguém exceto eu mesmo
  if(superClasse == null)
    return false;
  // Sou subclasse de sup se minha superclasse
  // é subclasse de sup (transitividade)
  return superClasse.subClasseDe(sup);
}

b)

Classe tipoExp(Env<Classe> tenv) {
  Classe tobj = objetio.tipoExp(tenv);
  Metodo m = tobj.metodos.get(metodo);
  if(m.tipoParams.size() != args.size())
    throw new RuntimeException("erro de tipagem");
  for(int i = 0; i < args.size(); i++) {
    Classe tparam = m.tipoParams.get(i);
    Classe targ = args.get(i).tipoExp(tenv);
    if(!targ.subClasseDe(tparam))
      throw new RuntimeException("erro de tipagem");
  }
  return m.tipoRet;
}

c)

void checaTipo(Classe tipoThis) {
  Env<Classe> tenv = new SymbolTable<Classe>();
  tenv.associa("this", tipoThis);
  for(int i = 0; i < nomeParams.size(); i++) {
    tenv.associa(nomeParams.get(i), tipoParams.get(i));
  }
  Classe tret = null;
  for(Exp exp : corpo) {
    tret = exp.tipoExp(tenv);
  }
  if(!tret.subClasseDe(tipoRet))
    throw new RuntimeException("erro de tipagem");
}