■

とりあえず前回作った規則を元にC++でコーディング
(a|b)とか(a+|b)とかa+|b*|cとか((a+|b)|c*)とかを正しくTREEにしてくれた。
次はこの木構造を元にNFAを作成するクラスを作る予定

#include <iostream>
using namespace std;

#define eleft e.child.left
#define eright e.child.right
#define ech e.ch

enum op_t {
  e_union,
  e_concat,
  e_closure,
  e_pclosure,
  e_empty,
  e_char
};

struct Leaf {
  op_t op;
  /*
   * if op == "char", then the param of this union is character
   * , else the param of this union is the struct that represents
   * a left tree and a right tree.
   */
  union Entity {
	char ch;
	struct {
	  Leaf *left;
	  Leaf *right;
	} child;
  } e;
};

class Stree {
  char current;
  char *inspectedStr, *baseStr;
  Leaf *root;

  void perror(const char * ptr);
  char getNextCurrent();
  char getBackCurrent();
  void setNextCurrent();
  Leaf* growTree(Leaf* left, Leaf* right, op_t op);
  Leaf* regexp();
  Leaf* regItr1();
  Leaf* regItr2();
  Leaf* regItr3();
  void showItem(Leaf *leaf, int count);

public:
  Stree(char *setch) {
	inspectedStr = setch;
	baseStr = setch;
	current = *(inspectedStr);
	root = regexp();
  }

  void showAll();
};

inline char Stree::getNextCurrent()
{
  return *(inspectedStr+1);
}

inline char Stree::getBackCurrent()
{
  if (baseStr < (inspectedStr-1))
	return '\0';
  return *(inspectedStr-1);
}

inline void Stree::setNextCurrent()
{
  current = *(++inspectedStr);
}

/*
 * This function is mainly dealing with "union".
 */
Leaf* Stree::regexp()
{
  Leaf *xLeaf, *yLeaf;

  xLeaf = regItr1();

  if (current == '|') {
	setNextCurrent();
	yLeaf = regexp();
	xLeaf = growTree(xLeaf, yLeaf, e_union);
  }

  return xLeaf;
}

/*
 * This function is mainly dealing with "concat".
 */
Leaf* Stree::regItr1()
{
  Leaf *xLeaf, *yLeaf;

  xLeaf = regItr2();

  if (xLeaf == NULL)
	return NULL;

  if (current != '\0' && current != '|' && current != ')') {
	yLeaf = regItr1();
	xLeaf = growTree(xLeaf, yLeaf, e_concat);
  }

  return xLeaf;
}

Leaf* Stree::regItr2()
{
  Leaf *xLeaf;

  xLeaf = regItr3();

  if (xLeaf == NULL)
	return NULL;

  if (current == '*') {
	xLeaf = growTree(xLeaf, NULL, e_closure);
	setNextCurrent();
  } else if (current == '+') {
	xLeaf = growTree(xLeaf, NULL, e_pclosure);
	setNextCurrent();
  }

  return xLeaf;
}

Leaf* Stree::regItr3()
{
  Leaf *xLeaf = new Leaf();
  xLeaf->eleft = NULL;
  xLeaf->eright = NULL;

  if (current == '(') {
	setNextCurrent();
	xLeaf = regexp();
	if (current != ')')
	  perror("parse error");
	else
	  setNextCurrent();
  } else if (isalpha(current)) {
	xLeaf->op = e_char;
	xLeaf->ech = current;
	setNextCurrent();
  } else {
	if (current == '|') {
	  xLeaf->op = e_empty;
	  setNextCurrent();
	} else if (getBackCurrent() == '|'){
	  xLeaf->op = e_empty;
	  setNextCurrent();
	} else if (current == '\0') {
	  return NULL;
	} else {
	  perror("sentence error");
	}
  }

  return xLeaf;
}

Leaf* Stree::growTree(Leaf *left, Leaf *right, op_t op)
{
  Leaf *leaf = new Leaf();
  leaf->op = op;
  leaf->eleft = left;
  leaf->eright = right;

  return leaf;
}

void Stree::showAll()
{
  showItem(root, 0);
}

void Stree::showItem(Leaf *leaf, int count)
{
  if (leaf == NULL)
	return;

  if (leaf->op != e_char) {
	for (int i=0; i<=count; i++)
	  cout << " ";
	cout << "left" << endl;
	showItem(leaf->eleft, count+1);
  }

  for (int i=0; i<=count; i++)
	cout << " ";
  switch (leaf->op) {
  case e_union:
	cout << '|';
	break;
  case e_concat:
	break;
  case e_closure:
	cout << '*';
	break;
  case e_pclosure:
	cout << '+';
	break;
  case e_empty:
	cout << "empty" << endl;;
	return;
  case e_char:
	cout << leaf->ech << endl;;
	return;
  }
  cout << endl;

  for (int i=0; i<=count; i++)
	cout << " ";
  cout << "right" << endl;
  showItem(leaf->eright, count+1);
}

void Stree::perror(const char * ptr)
{
  cout << ptr << endl;
  exit(1);
}

int main(int argc, char **argv)
{
  if (argc != 3) {
	cout << "Usage: Stree (regex string) (checking string)" << endl;
	exit(0);
  }
  char *regex = new char[strlen(argv[1])];
  char *check = new char[strlen(argv[2])];
  strncpy(regex, argv[1], strlen(argv[1]));
  strncpy(check, argv[2], strlen(argv[2]));

  Stree st(regex);
  st.showAll();

  delete regex;
  delete check;

  return 0;
}