[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: computer-go: SGF parser in C++

To: computer-go@xxxxxxxxxxxxxxxxx
Subject: RE: computer-go: SGF parser in C++
From: "Sheppard, Brian" <BSheppard@xxxxxxxxxx>
Date: Thu, 6 Jan 2000 15:51:27 -0500
Reply-to: computer-go@xxxxxxxxxxxxxxxxx
Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
The following code builds a parse tree for an SGF file. I wrote it because
existing public-domain code mixes parsing and semantic analysis in
convoluted ways. I am releasing this code to the public domain in the hope
that someone (e.g. Gnu, OpenGo, or PubGo) will maintain it.

The program is a Bison grammar with an embedded hand-coded lexical analyzer.
It constructs a tree-structure representation of the SGF file in the form of
C++ objects. You need to obtain Bison from a Gnu mirror site. I have only
compiled this program under MS Visual C++.

I have been using this program for only a month, and only with SGF files
from specific sources, so I cannot be sure that the grammar covers every
possible valid SGF file. But it is pretty good and quite easy to modify if
it turns out that I have missed a case.

This code is a good basis for a standard SGF parser because it strictly
separates parsing and semantic analysis.

The program includes some code for traversing the parse tree for Go SGF
files. That code should be further separated from the parser. Also, it needs
to be greatly extended, as I have only implemented the attributes I need to
test my Go-playing program.

Error detection is thorough but coarse; no error recovery is attempted.
Error-reporting is minimal.

I hope this helps.

Warm Regards,
Brian Sheppard


////////////////////////////////////////////////////////////////////////////
//
// File SGF.h should be included in any program that uses the SGF parser.
#ifndef _SGF_H_
#define _SGF_H_

class SGFParseTreeClass;
class GoBoard;

// Call the following to construct a parse tree for an SGF file.
SGFParseTreeClass *SGFNew(const char *FileName);

// Call the following after you are finished with an SGF parse tree:
void SGFDelete(SGFParseTreeClass *);

// Call the following to traverse the tree. This routine calls (*Handler)
for
// every position in the tree. When (*Handler) is called it is passed a
position
// and the row and column of the move made in that position and the color of
// the player that made that move.
//
// This routine assumes the parse tree is for the game of Go, and it does
not
// handle the majority of attributes, only those that affect the status of
// the board. While it isn't particularly robust, it does show the flavor of
// code that manipulates the SGF parse tree.
//
void SGFParseTreeTraverse(SGFParseTreeClass *t, void (*Handler)(const
GoBoard& Board, int Row, int Column, int Color));

#endif
////////////////////////////////////////////////////////////////////////////
//


// File SGF.y, which contains the parser and all supporting code:
%{
#include "SGF.h"

// You have to supply the following file, which must define the class
GoBoard, the
// extern integer GoBoardSize, and the constants Black and White.
#include "GoBoard.h"


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

static int SideToMove;

bool GetPoint(const char *p, int *row, int *col) {

	if (p[0] >= 'a' + GoBoardSize || p[1] >= 'a' + GoBoardSize || p[0] <
'a' || p[1] < 'a' || p[2] != 0) {
		printf("Invalid point: %s\n", p);
		return(false);
	}

	*col = p[0] - 'a';
	*row = p[1] - 'a';
	return(true);
}

int GetInt(const char *p) {
	return(atoi(p));
}

int GetColor(const char *p) {
	if (p[1] != 0 || (*p != 'B' && *p != 'W')) {
		printf("Invalid color %s\n", p);
		return(Black);
	}
	return(*p == 'B' ? Black : White);
}

// C declarations
class ValueClass {
	char *First;
	char *Second;
public:
	ValueClass(char *f, char *s) {
		First = f;
		Second = s;
	}
	~ValueClass() {
		delete First;
		delete Second;
	}
	void Traverse(GoBoard& b, const char *ID, void (*Handler)(const
GoBoard&, int, int, int)) {

		if (0 == strcmp(ID, "ID")) {
			printf("ID %s\n", First);
		} else if (0 == strcmp(ID, "SZ")) {
			GoBoardSize = GetInt(First);
			printf("GoBoardSize %d\n", GoBoardSize);
		} else if (0 == strcmp(ID, "B")) {
			int row, col;
			if (GetPoint(First, &row, &col)) {
				if (Empty == b(row, col)) {

					(*Handler)(b, row, col, Black);

					b.MakeMove(row, col, Black);
				} else {
					printf("Black move on occupied
point: %s\n", First);
				}
			}
		} else if (0 == strcmp(ID, "W")) {
			int row, col;
			if (GetPoint(First, &row, &col)) {
				if (Empty == b(row, col)) {

					(*Handler)(b, row, col, Black);

					b.MakeMove(row, col, White);
				} else {
					printf("White move on occupied
point: %s\n", First);
				}
			}
		} else if (0 == strcmp(ID, "PL")) {
			SideToMove = GetColor(First);
			printf("%s to move\n", SideToMove == Black ? "Black"
: "White");
		} else if (0 == strcmp(ID, "AB") || 0 == strcmp(ID, "AW")) {
			int c = GetColor(&ID[1]);
			int row, col;
			if (GetPoint(First, &row, &col)) {
				if (Second == 0) {
					b.SetPoint(row, col, c);
				} else {
					int LastRow, LastCol;
					if (GetPoint(First, &LastRow,
&LastCol)) {
						for (int i = row; i <=
LastRow; i++) {
							for (int j = col; j
<= LastCol; j++) {
	
b.SetPoint(i, j, c);
							}
						}
					}
				}
			}
		} else {
			printf("Traverse %s Value %s %s\n", ID, First,
Second ? Second : "");
		}
	}
};

class ValueListClass {
	ValueListClass *Next;
	ValueClass *Value;
public:
	ValueListClass(ValueListClass *n, ValueClass *v) {
		Next = n;
		Value = v;
	}
	~ValueListClass() {
		delete Next;
		delete Value;
	}
	void Traverse(GoBoard& b, const char *ID, void (*Handler)(const
GoBoard&, int, int, int)) {
		Value->Traverse(b, ID, Handler);
		if (Next) Next->Traverse(b, ID, Handler);
	}

	ValueListClass *Reverse(void) {
		ValueListClass *n = 0, *Head = this;
		while (Head) {
			ValueListClass *SaveNext = Head->Next;
			Head->Next = n;
			n = Head;
			Head = SaveNext;
		}
		return(n);
	}
};

class PropertyClass {
	char *Id;
	ValueListClass *Value;
public:
	PropertyClass(char *i, ValueListClass *v) {
		Id = i;
		Value = v->Reverse();
	}
	~PropertyClass() {
		delete Id;
		delete Value;
	}
	void Traverse(GoBoard& b, void (*Handler)(const GoBoard&, int, int,
int)) {
		Value->Traverse(b, Id, Handler);
	}
};

class PropertyListClass {
	PropertyListClass *Next;
	PropertyClass *Property;
public:
	PropertyListClass(PropertyListClass *next, PropertyClass *property)
{
		Next = next;
		Property = property;
	}
	~PropertyListClass() {
		delete Next;
		delete Property;
	}
	void Traverse(GoBoard& b, void (*Handler)(const GoBoard&, int, int,
int)) {
		Property->Traverse(b, Handler);
		if (Next) Next->Traverse(b, Handler);
	}
	PropertyListClass *Reverse(void) {
		PropertyListClass *n = 0, *Head = this;
		while (Head) {
			PropertyListClass *SaveNext = Head->Next;
			Head->Next = n;
			n = Head;
			Head = SaveNext;
		}
		return(n);
	}
};

class NodeListClass {
	NodeListClass *Next;
	PropertyListClass *Node;
public:
	NodeListClass(NodeListClass *next, PropertyListClass *node) {
		Next = next;
		Node = node->Reverse();
	}
	~NodeListClass() {
		delete Next;
		delete Node;
	}
	void Traverse(GoBoard& b, void (*Handler)(const GoBoard&, int, int,
int)) {
		Node->Traverse(b, Handler);
		if (Next) Next->Traverse(b, Handler);
	}
	NodeListClass *Reverse(void) {
		NodeListClass *n = 0, *Head = this;
		while (Head) {
			NodeListClass *SaveNext = Head->Next;
			Head->Next = n;
			n = Head;
			Head = SaveNext;
		}
		return(n);
	}
};

class SGFParseTreeClass;

class GameTreeClass {
	NodeListClass *Node;
	SGFParseTreeClass *Tree;
public:
	GameTreeClass(NodeListClass *node, SGFParseTreeClass *tree);
	~GameTreeClass();

	void Traverse(GoBoard& b, void (*Handler)(const GoBoard&, int, int,
int));
};

class SGFParseTreeClass {
	SGFParseTreeClass *Next;
	GameTreeClass *Game;
public:
	SGFParseTreeClass(SGFParseTreeClass *next, GameTreeClass *game) {
		Next = next;
		Game = game;
	}
	~SGFParseTreeClass() {
		delete Next;
		delete Game;
	}

	void Traverse(GoBoard& b, void (*Handler)(const GoBoard&, int, int,
int)) {
		for (SGFParseTreeClass *p = this; p; p = p->Next) {
			GoBoard VariationBoard = b;
			p->Game->Traverse(VariationBoard, Handler);
		}
	}
	SGFParseTreeClass *Reverse(void) {
		SGFParseTreeClass *n = 0, *Head = this;
		while (Head) {
			SGFParseTreeClass *SaveNext = Head->Next;
			Head->Next = n;
			n = Head;
			Head = SaveNext;
		}
		return(n);
	}
};

GameTreeClass::GameTreeClass(NodeListClass *node, SGFParseTreeClass *tree) {
	Node = node->Reverse();
	Tree = tree->Reverse();
}

GameTreeClass::~GameTreeClass() {
	delete Node;
	delete Tree;
}

void GameTreeClass::Traverse(GoBoard& b, void (*Handler)(const GoBoard&,
int, int, int)) {
	Node->Traverse(b, Handler);
	if (Tree) Tree->Traverse(b, Handler);
}

static SGFParseTreeClass *SGFParseTree;

// The following definitions cause yyparse and yylex to have a void*
argument named file.
#define YYPARSE_PARAM file
#define YYLEX_PARAM file
%}

%pure_parser		/* Makes parser reentrant */

%union {			/* Specifies types that can be used on the
value stack. */
	char *String;
	SGFParseTreeClass *SGFFilePtr;
	GameTreeClass *GameTreePtr;
	NodeListClass *NodeListPtr;
	PropertyClass *PropertyPtr;
	PropertyListClass *PropertyListPtr;
	ValueListClass *ValueListPtr;
	ValueClass *ValuePtr;
}

/* Declare the terminals and their values. */
%token <String> ATOM

/* Declare the non-terminals and their values. */
%type <SGFFilePtr> SGFFile
%type <GameTreePtr> GameTree
%type <NodeListPtr> NodeList
%type <PropertyPtr> Property
%type <PropertyListPtr> Node PropList
%type <ValueListPtr> ValueList
%type <ValuePtr> Value;


%%
SGFFile		: /* empty */			{ SGFParseTree = $$ = 0; }
			| SGFFile GameTree		{ SGFParseTree = $$
= new SGFParseTreeClass($1, $2); }
			;

GameTree	: '(' NodeList SGFFile ')'		{ $$ = new
GameTreeClass($2, $3); }
			;

NodeList	: Node				{ $$ = new NodeListClass(0,
$1); }
			| NodeList Node		{ $$ = new NodeListClass($1,
$2); }
			;

Node		: ';' PropList		{ $$ = $2; }
			;

PropList	: /* empty */			{ $$ = 0; }
			| PropList Property		{ $$ = new
PropertyListClass($1, $2); }
			;

Property	: ATOM ValueList		{ $$ = new PropertyClass($1,
$2); }
			;

ValueList	: '[' Value ']'					{ $$ = new
ValueListClass(0, $2); }
			| ValueList '[' Value ']'		{ $$ = new
ValueListClass($1, $3); }
			;

Value		: ATOM				{ $$ = new ValueClass($1,
0); }
			| ATOM ':' ATOM		{ $$ = new ValueClass($1,
$3); }
			;
%%

int yylex(YYSTYPE *lvalp, void *file) {
	FILE *ifp = (FILE *) file;

	// Skip whitespace:
	int c;
	do {
		c = fgetc(ifp);
		if (c == EOF) return(0);
	} while (isspace(c));

	// Check for delimiters:
	if (c == '[' || c == ']' || c == ';' || c == ':' || c == '(' || c ==
')') return(c);

	// This is an ATOM. Read until a '[' or ']', then push that
delimiter back.
	int i = 0;
	char buffer[1024];
	do {
		// identifier too long:
		if (i == sizeof(buffer) - 1) return(0);

		// If we read a backslash, save the next character instead.
		if (c == '\\') {
			c = fgetc(ifp);
			if (c == EOF) return(0);		//
end-of-file is bad.
		}

		buffer[i++] = c;

		c = fgetc(ifp);
		if (c == EOF) return(0);		// end-of-file is
bad.

	} while (c != ']' && c != '[');

	// Terminate the array:
	buffer[i] = 0;

	ungetc(c, ifp);

	// printf("%s\n", buffer);

	// Save the string:
	lvalp->String = strcpy((char *) malloc(i+1), buffer);
	return(ATOM);
}

void yyerror(char *s) {
	fprintf(stderr, "%s\n", s);
}



void SGFDelete(SGFParseTreeClass *s) {
	delete s;
}

SGFParseTreeClass *SGFNew(const char *filename) {
	FILE *ifp = fopen(filename, "r");
	if (ifp == 0) return(0);

	if (SGFparse(ifp)) {
		if (SGFParseTree) delete SGFParseTree;
		return(0);
	}

	fclose(ifp);

	return SGFParseTree->Reverse();
}

void SGFParseTreeTraverse(SGFParseTreeClass *t, void (*Handler)(const
GoBoard&, int, int, int)) {
	GoBoard Board;
	t->Traverse(Board, Handler);
}
Prev by Date: RE: computer-go: SGF parser in C++
Next by Date: Re: computer-go: Photos of the 16 top ranked Japanese female go players
Previous by thread: RE: computer-go: SGF parser in C++
Next by thread: computer-go: Photos of the 16 top ranked Japanese female go players
Index(es):
- Date
- Thread