root/tools/tree.c

DEFINITIONS

1. _newNode
2. makeRule
3. findRule
4. beginRule
5. Rule_setExpression
6. makeVariable
7. makeName
8. makeDot
9. makeCharacter
10. makeString
11. makeClass
12. makeAction
13. makePredicate
14. makeError
15. makeAlternate
16. Alternate_append
17. makeSequence
18. Sequence_append
19. makePeekFor
20. makePeekNot
21. makeQuery
22. makeStar
23. makePlus
24. dumpStack
25. push
26. top
27. pop
28. Node_fprint
29. Node_print
30. Rule_fprint
31. Rule_print
32. Rule_free
33. freeRules

/* Copyright (c) 2007 by Ian Piumarta
 * Copyright (c) 2013 by perl11 org
 * All rights reserved.
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the 'Software'),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, provided that the above copyright notice(s) and this
 * permission notice appear in all copies of the Software.  Acknowledgement
 * of the use of this Software in supporting documentation would be
 * appreciated but is not required.
 * 
 * THE SOFTWARE IS PROVIDED 'AS IS'.  USE ENTIRELY AT YOUR OWN RISK.
 * 
 * Last edited: 2013-10-01 12:19:49 rurban
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "greg.h"

Node *actions= 0;
Node *rules= 0;
Node *thisRule= 0;
Node *start= 0;

FILE *output= 0;

int actionCount= 0;
int ruleCount= 0;
int lastToken= -1;

static inline Node *_newNode(NodeType type, int size)
{
  Node *node= calloc(1, size);
  node->type= type;
  return node;
}

#define newNode(T)      _newNode(T, sizeof(struct T))

Node *makeRule(char *name, int defined)
{
  Node *node= newNode(Rule);
  node->rule.name= strdup(name);
  node->rule.id= ++ruleCount;
  node->rule.flags= defined ? RuleUsed : 0;
  node->rule.next= rules;
  rules= node;
  return node;
}

Node *findRule(char *name, int defined)
{
  Node *n;
  char *ptr;
  for (ptr= name;  *ptr;  ptr++) if ('-' == *ptr) *ptr= '_';
  for (n= rules;  n;  n= n->any.next)
    {
      assert(Rule == n->type);
      if (!strcmp(name, n->rule.name))
        return n;
    }
  return makeRule(name, defined);
}

Node *beginRule(Node *rule)
{
  actionCount= 0;
  return thisRule= rule;
}

void Rule_setExpression(Node *node, Node *expression)
{
  assert(node);
#ifdef DEBUG
  Node_print(node);  fprintf(stderr, " [%d]<- ", node->type);  Node_print(expression);  fprintf(stderr, "\n");
#endif
  assert(Rule == node->type);
  node->rule.expression= expression;
  if (!start || !strcmp(node->rule.name, "start"))
    start= node;
}

Node *makeVariable(char *name)
{
  Node *node;
  assert(thisRule);
  for (node= thisRule->rule.variables;  node;  node= node->variable.next)
    if (!strcmp(name, node->variable.name))
      return node;
  node= newNode(Variable);
  node->variable.name= strdup(name);
  node->variable.next= thisRule->rule.variables;
  thisRule->rule.variables= node;
  return node;
}

Node *makeName(Node *rule)
{
  Node *node= newNode(Name);
  node->name.rule= rule;
  node->name.variable= 0;
  rule->rule.flags |= RuleUsed;
  return node;
}

Node *makeDot(void)
{
  return newNode(Dot);
}

Node *makeCharacter(char *text)
{
  Node *node= newNode(Character);
  node->character.value= strdup(text);
  return node;
}

Node *makeString(char *text)
{
  Node *node= newNode(String);
  node->string.value= strdup(text);
  return node;
}

Node *makeClass(char *text)
{
  Node *node= newNode(Class);
  node->cclass.value= (unsigned char *)strdup(text);
  return node;
}

Node *makeAction(char *text)
{
  Node *node= newNode(Action);
  char name[1024];
  assert(thisRule);
  sprintf(name, "_%d_%s", ++actionCount, thisRule->rule.name);
  node->action.name= strdup(name);
  node->action.text= strdup(text);
  node->action.list= actions;
  node->action.rule= thisRule;
  actions= node;
  {
    char *ptr;
    for (ptr= node->action.text;  *ptr;  ++ptr)
      if ('$' == ptr[0] && '$' == ptr[1])
        ptr[1]= ptr[0]= 'y';
  }
  return node;
}

Node *makePredicate(char *text)
{
  Node *node= newNode(Predicate);
  node->predicate.text= strdup(text);
  return node;
}

Node *makeError(Node *e, char *text)
{
  Node *node= newNode(Error);
  node->error.element= e;
  node->error.text= strdup(text);
  return node;
}

Node *makeAlternate(Node *e)
{
  if (Alternate != e->type)
    {
      Node *node= newNode(Alternate);
      assert(e);
      assert(!e->any.next);
      node->alternate.first=
        node->alternate.last= e;
      return node;
    }
  return e;
}

Node *Alternate_append(Node *a, Node *e)
{
  assert(a);
  a= makeAlternate(a);
  assert(a->alternate.last);
  assert(e);
  a->alternate.last->any.next= e;
  a->alternate.last= e;
  return a;
}

Node *makeSequence(Node *e)
{
  if (Sequence != e->type)
    {
      Node *node= newNode(Sequence);
      assert(e);
      assert(!e->any.next);
      node->sequence.first=
        node->sequence.last= e;
      return node;
    }
  return e;
}

Node *Sequence_append(Node *a, Node *e)
{
  assert(a);
  a= makeSequence(a);
  assert(a->sequence.last);
  assert(e);
  a->sequence.last->any.next= e;
  a->sequence.last= e;
  return a;
}

Node *makePeekFor(Node *e)
{
  Node *node= newNode(PeekFor);
  node->peekFor.element= e;
  return node;
}

Node *makePeekNot(Node *e)
{
  Node *node= newNode(PeekNot);
  node->peekNot.element= e;
  return node;
}

Node *makeQuery(Node *e)
{
  Node *node= newNode(Query);
  node->query.element= e;
  return node;
}

Node *makeStar(Node *e)
{
  Node *node= newNode(Star);
  node->star.element= e;
  return node;
}

Node *makePlus(Node *e)
{
  Node *node= newNode(Plus);
  node->plus.element= e;
  return node;
}


static Node  *stack[1024];
static Node **stackPointer= stack;


#ifdef DEBUG
static void dumpStack(void)
{
  Node **p;
  for (p= stack + 1;  p <= stackPointer;  ++p)
    {
      fprintf(stderr, "### %ld\t", p - stack);
      Node_print(*p);
      fprintf(stderr, "\n");
    }
}
#endif

Node *push(Node *node)
{
  assert(node);
  assert(stackPointer < stack + 1023);
#ifdef DEBUG
  dumpStack();  fprintf(stderr, " PUSH ");  Node_print(node);  fprintf(stderr, "\n");
#endif
  return *++stackPointer= node;
}

Node *top(void)
{
  assert(stackPointer > stack);
  return *stackPointer;
}

Node *pop(void)
{
  assert(stackPointer > stack);
#ifdef DEBUG
  dumpStack();  fprintf(stderr, " POP\n");
#endif
  return *stackPointer--;
}


static void Node_fprint(FILE *stream, Node *node)
{
  assert(node);
  switch (node->type)
    {
    case Freed:         return;
    case Rule:          fprintf(stream, " %s", node->rule.name);                                break;
    case Variable:      fprintf(stream, " %s", node->variable.name);                            break;
    case Name:          fprintf(stream, " %s", node->name.rule->rule.name);                     break;
    case Dot:           fprintf(stream, " .");                                                  break;
    case Character:     fprintf(stream, " '%s'", node->character.value);                        break;
    case String:        fprintf(stream, " \"%s\"", node->string.value);                         break;
    case Class:         fprintf(stream, " [%s]", node->cclass.value);                           break;
    case Action:        fprintf(stream, " { %s }", node->action.text);                          break;
    case Predicate:     fprintf(stream, " ?{ %s }", node->action.text);                         break;
    case Error:         fprintf(stream, " ~{ %s }", node->error.text);                          break;

    case Alternate:     node= node->alternate.first;
                        fprintf(stream, " (");
                        Node_fprint(stream, node);
                        while ((node= node->any.next))
                          {
                            fprintf(stream, " |");
                            Node_fprint(stream, node);
                          }
                        fprintf(stream, " )");
                        break;

    case Sequence:      node= node->sequence.first;
                        fprintf(stream, " (");
                        Node_fprint(stream, node);
                        while ((node= node->any.next))
                          Node_fprint(stream, node);
                        fprintf(stream, " )");
                        break;

    case PeekFor:       fprintf(stream, "&");  Node_fprint(stream, node->query.element);        break;
    case PeekNot:       fprintf(stream, "!");  Node_fprint(stream, node->query.element);        break;
    case Query:         Node_fprint(stream, node->query.element);  fprintf(stream, "?");        break;
    case Star:          Node_fprint(stream, node->query.element);  fprintf(stream, "*");        break;
    case Plus:          Node_fprint(stream, node->query.element);  fprintf(stream, "+");        break;
    default:
      fprintf(stream, "\nunknown node type %d\n", node->type);
      exit(1);
    }
}

void Node_print(Node *node)     { Node_fprint(stderr, node); }

static void Rule_fprint(FILE *stream, Node *node)
{
  assert(node);
  assert(Rule == node->type);
  fprintf(stream, "%s.%d =", node->rule.name, node->rule.id);
  if (node->rule.expression)
    Node_fprint(stream, node->rule.expression);
  else
    fprintf(stream, " UNDEFINED");
  fprintf(stream, " ;\n");
}

void Rule_print(Node *node)     { Rule_fprint(stderr, node); }

void Rule_free(Node *node)
{
  switch (node->type)
    {
    case Freed:         return;
    case Rule:
      {
        Node *var= node->rule.variables;
#ifdef DEBUG
        //Rule_print(node);
        fprintf(stderr, "free Rule %s.%d\n", node->rule.name, node->rule.id);
#endif
        free(node->rule.name);
        while (var) {
          Node *tmp= var->any.next; Rule_free(var); var= tmp;
        }
        if (node->rule.expression)
          Rule_free(node->rule.expression);
        break;
      }
    case Name:          break;
    case Variable:      free(node->variable.name);              break;
    case Dot:           break;
    case Character:     free(node->character.value);            break;
    case String:        free(node->string.value);               break;
    case Class:         free(node->cclass.value);               break;
    case Action:
#ifdef DEBUG
        fprintf(stderr, "free Action %s\n", node->action.name);
#endif
        free(node->action.text); free(node->action.name);       break;
    case Predicate:     free(node->predicate.text);             break;
    case Error:         free(node->error.text);                 break;
    case Alternate:
      {
        Node *root= node;
#ifdef DEBUG
        fprintf(stderr, "free Alternate %p\n", node);
#endif
        node= node->alternate.first;
        while (node->any.next) {
          Node *tmp= node->any.next; Rule_free(node); node= tmp;
        }
        Rule_free(node);
        node= root;
        break;
      }
    case Sequence:
      {
        Node *root= node;
#ifdef DEBUG
        fprintf(stderr, "free Sequence %p\n", node);
#endif
        node= node->sequence.first;
        while (node->any.next) {
          Node *tmp= node->any.next; Rule_free(node); node= tmp;
        }
        Rule_free(node);
        node= root;
        break;
      }
    case PeekFor:       break;
    case PeekNot:       break;
    case Query:         break;
    case Star:          break;
    case Plus:          break;
    default:
      fprintf(stderr, "\nunknown node type %d\n", node->type);
      return;
    }
  assert(node);
  node->type = Freed;
#ifndef DD_CYCLE
  free(node);
#endif
}

void freeRules (void) {
  Node *n;
  for (n= rules; n; ) {
    if (n->type > 0) {
      Node *tmp= n->any.next;
      Rule_free(n);
      if (tmp)
        n= tmp->any.next;
      else
        n= NULL;
    }
    else {
      n= n->any.next;
    }
  }
#ifdef DD_CYCLE
  for (n= rules; n; ) {
    if (n->type == Freed) {
      Node *tmp= n->any.next;
      free(n);
      if (tmp)
        n= tmp->any.next;
      else
        n= NULL;
    }
    else {
      n= n->any.next;
    }
  }
#endif
}