path: root/src/grammar.c

#include "grammar.h"

struct Rule_s {
  NT left;
  List *right;                  /* a list of TNT's */
};

typedef struct {
  /* this group holds rules for this non-terminal */
  NT left;
  /* a list of lists of TNT's */
  List *rights;
} Rule_group;

/* rule_grps and names should have the same length */
struct Grammar_s {
  /* a list of Rule_group's */
  List *rule_grps;
  /* a list of names of non-terminals

     Each element is an array of code-points.

     To print them, first encode them into normal strings. */
  List *names;
};

static void
destroy_rule_group(void *rule_grp, int flag)
{
  Rule_group *rg = (Rule_group *) rule_grp;

  switch (flag) {
  case 1:
    map_list(rg->rights, destroy_list_free_all);
    break;
  case 2:
    map_list(rg->rights, destroy_list_free_first);
    break;
  default:
    map_list(rg->rights, destroy_list_no_free);
    break;
  }

  destroy_list(rg->rights, 0);

  free(rule_grp);
}

UNUSED
static void
destroy_rule_group_no_free(void *rule_grp)
{
  destroy_rule_group(rule_grp, 0);
}

UNUSED
static void
destroy_rule_group_free_all(void *rule_grp)
{
  destroy_rule_group(rule_grp, 1);
}

UNUSED
static void
destroy_rule_group_free_first(void *rule_grp)
{
  destroy_rule_group(rule_grp, 2);
}

static void
print_sep()
{
  printf(", ");
}

static void
print_rule_group(void *rule_grp)
{
  Rule_group *rg = (Rule_group *) rule_grp;

  for (int i = 0; i < list_length(rg->rights); i++) {
    List *str = (List *) list_nth(rg->rights, i);
    printf("Rule %u => ", rg->left);
    map_list_between(str, print_tnt, print_sep);
    printf("\n");
  }
}

TNT *
new_tnt(int type, ...)
{
  va_list args;
  va_start(args, type);

  TNT *result = MYALLOC(TNT, 1);
  result->type = type;

  if (type) result->data.nt = va_arg(args, NT);
  else result->data.t = va_arg(args, T);

  va_end(args);

  return result;
}

Rule *
new_rule(NT left, const List * const right)
{
  if (!right) return NULL;

  Rule *rule = MYALLOC(Rule, 1);

  rule->left = left;
  rule->right = (List *) right;

  return rule;
}

Grammar *
new_grammar()
{
  Grammar *g = MYALLOC(Grammar, 1);
  return g;
}

/* We classify the rules into different rule groups. */
BOOL
build_grammar(Grammar *g, const List *rules, const List * const names)
{
  g->names = (List *) names;

  NUM len = list_length(names);
  NUM rule_len = list_length(rules);

  /* If a rule corresponds to a non-terminal not on the list, signal
     an error. */
  for (int i = 0; i < rule_len; i++) {
    if (((Rule *) list_nth(rules, i))->left >= len) {
      fleprintf("%d, Rule contains weird non-terminal\n", i);
      return 1;
    }
  }

  List *rule_grps = new_list();

  if (rule_grps == NULL) {
    fleprintf0("Cannot create list\n");
    return 1;
  }

  if (list_assure_size(rule_grps, len)) {
    fleprintf0("Cannot assure size of rule groups\n");
    return 1;
  }

  List *temp_ls = NULL;
  void *temp_pointer = NULL;

  /* Initialize the list of rule groups */
  for (int i = 0; i < len; i++) {
    if ((temp_ls = new_list()) == NULL) {
      fleprintf("%d, Cannot create list\n", i);

      map_list(rule_grps, destroy_rule_group_no_free);
      destroy_list(rule_grps, 0);
      return 1;
    }

    temp_pointer = MYALLOC(Rule_group, 1);

    if (temp_pointer == NULL) {
      fleprintf0("Cannot malloc\n");
      map_list(rule_grps, destroy_rule_group_no_free);
      destroy_list(rule_grps, 0);
      destroy_list(temp_ls, 0);
      return 1;
    }

    ((Rule_group *) temp_pointer)->left = i;
    ((Rule_group *) temp_pointer)->rights = temp_ls;

    int result = add_to_list(rule_grps, temp_pointer);

    if (result) {
      fleprintf("%d, Cannot add to list\n", i);

      map_list(rule_grps, destroy_rule_group_no_free);
      destroy_list(rule_grps, 0);
      destroy_list(temp_ls, 0);
      free(temp_pointer);
      return 1;
    }
  }

  /* Now fill in rule groups */

  for (int i = 0; i < rule_len; i++) {
    Rule *r = (Rule *) list_nth(rules, i);

    int result = add_to_list
      (((Rule_group *) list_nth(rule_grps, r->left))->rights,
       r->right);

    if (result) {
      fleprintf("%d, Cannot add to list\n", i);

      for (int j = 0; j < list_length(rule_grps); j++) {
        Rule_group *rg = (Rule_group *) list_nth(rule_grps, j);

        map_list(rg->rights, destroy_list_free_all);
        destroy_list(rg->rights, 0);
        free(rg);
      }

      destroy_list(rule_grps, 0);

      return 1;
    }
  }

  g->rule_grps = rule_grps;

  return 0;
}

void
print_tnt(void *element)
{
  TNT *tnt = (TNT*) element;

  if (tnt->type)
    printf("NT %u", tnt->data.nt);
  else
    printf("T %lu", tnt->data.t);
}

void
print_rule(void *r)
{
  Rule *rule = (Rule *) r;
  printf("Rule: %u => ", rule->left);

  map_list(rule->right, print_tnt);

  printf("\n");
}

NUM
find_in_cpa_list(const NUM * const restrict string, NUM size,
                 const List * const restrict list)
{
  NUM len = list_length(list), index = 0;

  BOOL foundp = 0;

  for (; !foundp && index < len;) {
    cpa *cpap = list_nth(list, index);

    if (cpap->size != (UNUM) size) {
      index++;
      continue;
    }

    foundp = 1;

    for (NUM j = 0; j < size; j++) {
      if (*(string+j) != *(cpap->array+j)) {
        foundp = 0;
        break;
      }
    }

    if (!foundp) index++;
  }

  return (foundp) ? index : -1;
}

void
print_name(void *element)
{
  cpa *array = (cpa *) element;
  char *carray = MYALLOC(char, 5);
  str *string = new_str(carray, 5);

  for (UNUM i = 0; i < array->size; i++) {
    int result = encode(*(array->array+i), string);

    if (result) {
      fleprintf("%llu, fail to encode\n", i);
      str_set_length(string, 5);
      continue;
    }

    carray = get_data(string);
    *(carray+str_length(string)) = 0;

    printf("%s", carray);
    str_set_length(string, 5);
  }

  destroy_str(string, 1);
}

/* REVIEW: Print the names of non-terminals out, instead of printing
   the numbers? */
void
print_grammar(const Grammar * const g)
{
  printf("Printing a grammar:\n");
  map_list_between(g->names, print_name, print_sep);
  printf("\n");

  for (int i = 0; i < list_length(g->rule_grps); i++) {
    print_rule_group(list_nth(g->rule_grps, i));
    printf("\n");
  }

  printf("\n");
}

List *
new_tnt_string(char *format, int format_len, ...)
{
  /* FORMAT_LEN does not include the terminating null byte, so it
     should be > 0. */

  if (format_len <= 0) return NULL;

  List *result = new_list();

  va_list args;
  va_start(args, format_len);

  for (int point = 0; point < format_len; point++) {
    switch (*(format+point)) {
    case 'n':
      add_to_list(result, new_tnt(1, va_arg(args, NT)));
      break;
    case 't':
      add_to_list(result, new_tnt(0, va_arg(args, T)));
      break;
    default:
      eprintf("Wront character: %c\n", *(format+point));
      destroy_list(result, 1);
      va_end(args);
      return NULL;
      break;
    }
  }

  va_end(args);

  return result;
}

TNT *
new_tnt_pointer(size_t size)
{
  return MYALLOC(TNT, size);
}

void
destroy_rule(void *rule, int flag)
{
  Rule * r = (Rule *) rule;
  destroy_list(r->right, flag);
  free(rule);
}

void
destroy_rule_and_free_all(void *rule)
{
  destroy_rule(rule, 1);
}

void
destroy_rule_and_free_first(void *rule)
{
  destroy_rule(rule, 2);
}

void
destroy_rule_no_free(void *rule)
{
  destroy_rule(rule, 0);
}

void
destroy_cpa_and_free_all(void *element)
{
  cpa *c = (cpa *) element;
  free(c->array);
  free(c);
}

void
destroy_grammar(void *grammar, int flag)
{
  Grammar *g = (Grammar *) grammar;

  if (flag == 1)
    map_list(g->rule_grps, destroy_rule_group_free_all);
  else if (flag == 2)
    map_list(g->rule_grps, destroy_rule_group_free_first);
  
  destroy_list(g->rule_grps, 0);
  
  /* CPA structure has no concept of freeing first.  So if flag is
     non-zero, we just free everything, and hope no disaster
     ensues. */
  if (flag) map_list(g->names, destroy_cpa_and_free_all);

  destroy_list(g->names, 0);

  free(grammar);
}