/*
**
** Módulo de Expressões Regulares em C
**
** Métodos de Programação III
**
** 2000/2001
**
*/

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>

/* 
** TAGS para identificar os tipos de nodos que constituem uma árvore de 
** Expressões Regulares
*/

#define EPSILON 0
#define LITERAL 1
#define OR      2
#define THEN    3
#define STAR    4

/*
** Tipo de dados C para definir a estrutura abstracta de expressões regulares
** i.e., para definir a árvore de expressões regulares
*/

typedef struct s
{ int utype;         /* Union Type */

  union {
    struct {
      char l;
    } lit;
    struct {
      struct s *er1;
      struct s *er2;
    } or ;
    struct {
      struct s *er1;
      struct s *er2;
    } then ;
    struct {
      struct s *er;
    } star ;
  } u;
} *RegExp;


/*
** Funções Construtoras dos vários tipo de nodos 
*/

RegExp consEPSILON ()
{ RegExp aux;
  aux = (RegExp) malloc (sizeof (struct s));
  aux->utype = EPSILON;
  return aux;
}

RegExp consLITERAL (char l)
{ RegExp aux;
  aux = (RegExp) malloc (sizeof (struct s));
  aux->utype = LITERAL;
  aux->u.lit.l = l;
  return aux;
}

RegExp consOR (RegExp er1 , RegExp er2)
{ RegExp aux;
  aux = (RegExp) malloc (sizeof (struct s));
  aux->utype = OR;
  aux->u.or.er1 = er1;
  aux->u.or.er2 = er2;  
  return aux;
}

RegExp consTHEN (RegExp er1 , RegExp er2)
{ RegExp aux;
  aux = (RegExp) malloc (sizeof (struct s));
  aux->utype = THEN;
  aux->u.then.er1 = er1;
  aux->u.then.er2 = er2;  
  return aux;
}

RegExp consSTAR (RegExp er)
{ RegExp aux;
  aux = (RegExp) malloc (sizeof (struct s));
  aux->utype = STAR;
  aux->u.star.er = er;
  return aux;
}

/*
** Função showRE: implementada como um procedimento que tem o efeito lateral
**                de escrever no output
** (a função que devolve a string é deixada como exercício...)
*/

void showRE (RegExp er)
{ switch (er->utype) 
  { case EPSILON : printf("@");
                   break;
    case LITERAL : printf("%c",er->u.lit.l);
	           break;
    case OR : printf("(");
              showRE(er->u.or.er1);
              printf(" + ");
              showRE(er->u.or.er2);
              printf(")");
	      break;
    case THEN : printf("(");
                showRE(er->u.then.er1);
                showRE(er->u.then.er2);
                printf(")");
	        break;
    case STAR : printf("(");
                showRE(er->u.star.er);
                printf(")*");
	        break;
  }
}

/*
** Função main que define a espressão regular: a + a(b*)
** e faz o show
**
*/

int main()
{
  RegExp a , b , er1 ;

  a = consLITERAL('a');
  b = consLITERAL('b');

  er1 = consOR(a , consTHEN(a , consSTAR(b)));

  showRE(er1);

  printf("\n");
  return 0;
}