/*
   sc.c -- Simple 'Infix to Prefix/Postfix' Compiler.

   Copyright (C) 2004 Wojciech Polak.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.
 
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
 
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
*/

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

#define NOP -1
#define END  0
#define NUMBER     256
#define IDENTIFIER 257

/* data structures */
struct symbol_struct
{
  struct symbol_struct *next;
  char *name;
};

typedef struct symbol_struct SYMBOL;

enum node_type
{
  NODE_NUMBER,
  NODE_OPERATOR,
  NODE_IDENTIFIER
};

enum opcode_type
{
  OPCODE_ADD,
  OPCODE_SUB,
  OPCODE_MUL,
  OPCODE_DIV
};

struct node_struct
{
  struct node_struct *left;
  struct node_struct *right;
  unsigned long node_id;

  enum node_type type;
  union {
    int number;
    SYMBOL *symbol;
    enum opcode_type opcode;
  } v;
};

typedef struct node_struct NODE;

/* prototypes */
int lexer (void);
void parser (void);
void read (int);
NODE *expr (NODE *, NODE *);
NODE *term (NODE *, NODE *);
NODE *factor (NODE *, NODE *);
NODE *addnode (enum node_type, NODE *, NODE *);
void freenode (NODE *);
void print_prefix (NODE *);
void print_infix (NODE *);
void print_postfix (NODE *);
void print_tree (NODE *);
SYMBOL *putsym (SYMBOL **, const char *);
SYMBOL *getsym (SYMBOL *, const char *);
void free_symbols (SYMBOL *);
void error (void);

/* global data */
int ch;
int mode = 3; /* postfix by default */
int line_number = 1;
int errorstate;
SYMBOL *symbols;
unsigned long last_node_id;

union
{
  int ival;
  SYMBOL *sval;
} lexval;

/*** Lexical analysis ***/

int
lexer (void)
{
  int t;
  while (1)
  {
    t = getchar ();
    if (t == ' ' || t == '\t')
      ; /* ignore whitespace */
    else if (t == '\n')
    {
      line_number++;
    }
    else if (isdigit (t))
    {
      ungetc (t, stdin);
      scanf ("%d", &lexval.ival);
      return NUMBER;
    }
    else if (isalpha (t))
    {
      int b = 0;
      char idbuf[128];
      SYMBOL *s;

      while (isalnum (t))
      {
	idbuf[b] = t;
	t = getchar ();
	b++;
	if (b >= 128) {
	  fprintf (stderr, "error: identifier too long\n");
	  break;
	}
      }
      idbuf[b] = '\0';
      if (t != EOF)
	ungetc (t, stdin);

      s = getsym (symbols, idbuf);
      if (s)
	lexval.sval = s;
      else
	lexval.sval = putsym (&symbols, idbuf);
      return IDENTIFIER;
    }
    else if (t == EOF)
    {
      return END;
    }
    else {
      lexval.ival = NOP;
      return t;
    }
  }
}

/*** Syntactic analysis ***/

/*
  Grammar:

 start -> stmt eof
  stmt -> expr ; stmt
       |  e
  expr -> term rE
    rE -> + term rE
       |  - term rE
       |  e
  term -> fact rF
    rF -> * fact rF
       |  / fact rF
       |  e
  fact -> ( expr )
       |  id
       |  number
*/

void
parser (void)
{
  NODE *root;

  ch = lexer ();
  while (ch != END)
  {
    root = expr (NULL, NULL);

    if (errorstate)
    {
      freenode (root);
      free_symbols (symbols);
      error ();
    }

    switch (mode) {
    case 1:
      print_prefix  (root);
      putchar ('\n');
      break;
    case 2:
      print_infix   (root);
      putchar ('\n');
      break;
    case 3:
      print_postfix (root);
      putchar ('\n');
      break;
    case 4:
      printf ("id\tleft\tright\tkey\n");
      print_tree (root);
      putchar ('\n');
    }

    freenode (root);
    read (';');
  }

  free_symbols (symbols);
  symbols = NULL;
}

NODE *
expr (NODE *left, NODE *right)
{
  NODE *p1, *p2;
  int s;

  p1 = term (left, right);

  while (1)
  {
    switch (ch) {
    case '+':
    case '-':
      s = ch;
      read (ch);
      p2 = term (NULL, NULL);
      p1 = addnode (NODE_OPERATOR, p1, p2);
      if (s == '+')
	p1->v.opcode = OPCODE_ADD;
      else if (s == '-')
	p1->v.opcode = OPCODE_SUB;
      break;
    default:
      return p1;
    }
  }
}

NODE *
term (NODE *left, NODE *right)
{
  NODE *p1, *p2;
  int s;

  p1 = factor (left, right);

  while (1)
  {
    switch (ch) {
    case '*':
    case '/':
      s = ch;
      read (ch);
      p2 = factor (NULL, NULL);
      p1 = addnode (NODE_OPERATOR, p1, p2);
      if (s == '*')
	p1->v.opcode = OPCODE_MUL;
      else if (s == '/')
	p1->v.opcode = OPCODE_DIV;
      break;
    default:
      return p1;
    }
  }
}

NODE *
factor (NODE *left, NODE *right)
{
  NODE *t;
  switch (ch) {
  case '(':
    read ('(');
    t = expr (left, right);
    read (')');
    return t;
  case NUMBER:
    t = addnode (NODE_NUMBER, NULL, NULL);
    t->v.number = lexval.ival;
    read (NUMBER);
    return t;
  case IDENTIFIER:
    t = addnode (NODE_IDENTIFIER, NULL, NULL);
    t->v.symbol = lexval.sval;
    read (IDENTIFIER);
    return t;
  default:
    errorstate = 1;
    return NULL;
  }
}

void
read (int s)
{
  if (ch == s)
    ch = lexer ();
  else
    errorstate = 1;
}

/*** Trees ***/

NODE *
addnode (enum node_type type, NODE *left, NODE *right)
{
  NODE *new = (NODE *)malloc (sizeof (NODE));
  if (!new)
    exit (EXIT_FAILURE);

  new->left     = left;
  new->right    = right;
  new->node_id  = ++last_node_id;
  new->type     = type;

  return new;
}

/* Recursively free all nodes */
void
freenode (NODE *node)
{
  if (!node)
    return;

  freenode (node->left);
  freenode (node->right);
  free (node);
}

void
print_node (NODE *node)
{
  if (node->type == NODE_NUMBER)
  {
    printf ("%d ", node->v.number);
  }
  else if (node->type == NODE_IDENTIFIER)
  {
    printf ("%s ", node->v.symbol->name);
  }
  else if (node->type == NODE_OPERATOR)
  {
    switch (node->v.opcode) {
    case OPCODE_ADD:
      printf ("+ ");
      break;
    case OPCODE_SUB:
      printf ("- ");
      break;
    case OPCODE_MUL:
      printf ("* ");
      break;
    case OPCODE_DIV:
      printf ("/ ");
      break;
    }
  }
}

void
print_prefix (NODE *node)
{
  if (!node)
    return;

  print_node (node);
  print_prefix (node->left);
  print_prefix (node->right);
}

void
print_infix (NODE *node)
{
  if (!node)
    return;

  print_infix (node->left);
  print_node (node);
  print_infix (node->right);
}

void
print_postfix (NODE *node)
{
  if (!node)
    return;

  print_postfix (node->left);
  print_postfix (node->right);
  print_node (node);
}

void
print_tree (NODE *node)
{
  if (!node)
    return;

  printf ("%4.4lu\t", node->node_id);
  if (node->left)
    printf ("%4.4lu\t", node->left->node_id);
  else
    printf ("NIL\t");
  if (node->right)
    printf ("%4.4lu\t", node->right->node_id);
  else
    printf ("NIL\t");

  print_node (node);
  putchar ('\n');

  print_tree (node->left);
  print_tree (node->right);
}

/*** Symbols ***/

SYMBOL *
putsym (SYMBOL **s, const char *name)
{
  SYMBOL *new = (SYMBOL *)malloc (sizeof (SYMBOL));
  if (!new)
    exit (EXIT_FAILURE);

  new->name = strdup (name);

  if (*s)
    new->next = *s;
  else
    new->next = NULL;
  *s = new;
  return new;
}

SYMBOL *
getsym (SYMBOL *s, const char *name)
{
  if (!s)
    return NULL;

  for (; s; s = s->next)
  {
    if (!strcmp (s->name, name))
      return s;
  }
  return NULL;
}

void
free_symbols (SYMBOL *s)
{
  SYMBOL *next;

  if (!s)
    return;

  for (; s; s = next)
  {
    next = s->next;
    free (s);
  }
}

/*** Main ***/

void
error (void)
{
  fprintf (stderr, "syntax error on line %d\n", line_number);
  exit (1); /* no error recovery in this simple example */
}

int
main (int argc, char *argv[])
{
  if (argc > 1)
  {
    if (!strcmp (argv[1], "prefix"))
      mode = 1;
    else if (!strcmp (argv[1], "infix"))
      mode = 2;
    else if (!strcmp (argv[1], "postfix"))
      mode = 3;
    else if (!strcmp (argv[1], "tree"))
      mode = 4;
    else
      fprintf (stderr, "unknown mode, using default postfix\n");
  }

  parser ();
  return 0;
}