Exercício de exame

a) escreva um parser em descida recursiva que corresponda gramática;
b) diga se a frase abc(+ba) pertence à gramática justificando através da apresentação de uma árvore de derivação.

Resposta

a) esta gramática pode ser traduzida directamente para um parser em descida recursiva predictivo, pois so necessita da análise de 1 token para saber a hipótese a escolher.

Este parser utiliza as variáveis globais token e nerros, e a função yylex() que devolve o próximo token.

enum{A,B,C,MAIS,A_PAR,F_PAR,FIM}

int token,nerros=0;

void s();
void a();
void b();
void c();

void erro(char *s)
{
  nerros++;
  printf("Erro %d: %s\n",nerros,s);
}

void s() /* S→AB */
{
  a();
  b();
}

void a() /* A→aB | vazio  */
{
  if (token == A)
  {
     token=yylex();
     b();
  }
  
  /* vazio - como tem a hipótese vazio, não dá erro */
}

void b() /* B→bAC | vazio  */
{
  if (token == B)
  {
     token=yylex();
     a();
     c();
  }
  
  /* vazio - como tem a hipótese vazio, não dá erro */
}

void c() /* C→c(A+B) */
{
  /* esta produção faz comparação token a token, em caso de erro continua */

  if (token == C)
      token=yylex();
  else
      erro("falta c");
  if (token == A_PAR)
      token=yylex();
  else
      erro("falta '('");
  a();
  if (token == MAIS)
      token=yylex();
  else
      erro("falta '+'");
  b();
  if (token == F_PAR)
      token=yylex();
  else
      erro("falta ')'");
}

void main()
{
  token=yylex(); /* vai buscar o 1º token */
  s();           /* chama a produção inicial */

  if (nerros==0 && token==FIM)
       printf("Expressao válida \n");
  else
       printf("Expressao inválida \n");
}

A frase não pertence à gramática, pois dentro dos parêntesis existe um b e não existe nenhum c.

Nota: Se tivéssemos chegado ao fim da expressão, e nas folhas da árvore só restassem terminais analisados ou vazio, a expressão era válida.

Pergunta

Resposta