Sintaxe Abstracta

Sintaxe Abstracta

Princípios

• Associar cada terminal e não terminal com valor semântico.
• Ex: num calculador E e INT poderiam ser int.
• Outros tokens não têm que ter valor.
• para regra E -> E + E valor seria a soma dos dois operandos.

Descida Recursiva: Semântica

• NUM carrenga int e ID carrega símbolo.
• O tipo associado com E, T, F é int, acções semânticas são fáceis de implementar.
• Se fosse T -> T * F seria:

  {int a; a=T(); eat(TIMES); return a*F();}
  

• Para T' é mais complicado, uma solução é passar o valor de F para a função que calcula T'.

Descida Recursiva: Semântica

int F_follow[] = {PLUS,TIMES,RPAREN,EOF,-1};
int F(void) { switch (tok) {
  case ID: {int i=lookup(tokval.id);
            advance(); return i;}
  case NUM:{int i=tokval.num;
            advance(); return i;}
  case LPAREN: eat(LPAREN); {int i=E();
            eatOrSkipTo(RPAREN, F_follow);
            return i;}
  default: printf("expected ID, NUM, (");
           skipto(F_FOLLOW); return(0);
}}

int T_follow[] = {PLUS,RPAREN,EOF,-1};
int T(void) { switch (tok) {
  case ID: case NUM: case LPAREN:
          return Tprime(F());
  default: ....
}}

int Tprime(int a) {switch(tok) {
  case TIMES: eat(TIMES);return Tprime(a*F());
  case PLUS: case RPAREN; case EOF: return a;
  default: ....
}}

YACC: Semântica

%{ yylex e yyerror }%
%union {int num; string id;}
%token <num> INT
%token <id> ID
%type  <num> exp
%start exp

%left PLUS MINUS
%left TIMES
%left UMINUS
%%

exp : INT           {$$ = $1;}
    | exp PLUS exp  {$$ = $1+$3;}
    | exp MINUS exp {$$ = $1-$3;}
    | exp TIMES exp {$$ = $1*$3;}
    | MINUS exp % prec UMINUS {$$ = -$2;}

YACC: Semântica

• Declaração union indica quais os tipos possíveis.
• Cada terminal e não-terminal indica qual o seu tipo.
• Implementação: manter uma pilha de valores paralela à pilha de tokens:
  • Quando parser faz redução tb executa acção semântica olhando para a pilha.
  • para E -> E+E os três elementos no topo da pilha são exp1, vazio, e exp2.
• Sabemos que o parser atravessa a árvore de parser em post-order, ie, de baixo para cima: os argumentos já estão prontos quando chamarmos a redução para uma regra.
• Interpretador: associar nós a side-effects (eg, alteração de uma variável).

YACC: Execução

Árvores Abstractas de Parse

• Possível construir um compilador nas acções semânticas.
• Modularidade: construir uma estrutura intermédia.
• Árvore de parse concreta tem uma folha por token e um nó por regra.
• Inconveniente por ser demasiado detalhada!
• Árvore abstracta estabelece uma interface limpa entre o parser e análise semântica: tem a estrutura das frases sem interpretação semântica.
• Compiladores antigos não tinham árv. abstractas: falta de memória.
• Vantagem tb com forward references para ids. definidos mais tarde (ML, Modula-3, Java).
• Fácil com árvores abstractas, senão obriga a segundo parse.

Árvores Abstractas: Implementação

• YACC usa uma gramática concreta para construir uma árvore segundo a gramática abstracta.
• Exemplo com programa para calculadora:

Árvores Abstractas: Exemplo

prog: stm                      {$$=$1}

stm : stm SEMICOLON stm  
                  {$$=A_CompoundStm($1,$3);}
stm : ID ASSIGN exp            
                  {$$=A_AssignStm($1,$3);}
stm : PRINT LPAREN exps RPAREN 
                  {$$=A_PrintStm($3);}

exps: exp         {$$=A_ExpList($1,NULL);}
exps: exp COMMA exps
                  {$$=A_ExpList($1,$3);}

exp: INT          {$$=A_NumExp($1);}
exp: ID           {$$=A_IdExp($1);}
exp: exp PLUS exp {$$=A_OpExp($1,A_plus,$3);}
exp: exp MINUS exp
                  {$$=A_OpExp($1,A_minus,$3);}
exp: exp TIMES exp
                  {$$=A_OpExp($1,A_times,$3);}
exp: exp DIV exp  {$$=A_OpExp($1,A_div,$3);}
exp: stm COMMA exp
                  {$$=A_EseqExp($1,$3);}
exp: LPAREN exp RPAREN
                  {$$=$1;}

Recuperação de Erros

• Problema: como as outras fases vão saber onde o erro aconteceu?
• Exemplo: uso de variável do tipo errado...
• A posição corrente do analizador lexical é o EOF.
• Solução: acrescentar campos pos a cada nó da árvore sintáctica.
• Bison mantém uma pilha de posições em paralelo com a pilha de valores.
• Yacc obriga a definir um novo símbolo não terminal na produção, pode levar a conflitos:

  exp : expl PLUS pos exp
         {$$=A_OpExp($1,A_plus,$4,$3);}
  

  e

  exp : pos expl PLUS exp
        {$$=A_OpExp($2,A_plus,$4,$1);}
  

Sintaxe Abstracta