Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
branch: master
Fetching contributors…

Cannot retrieve contributors at this time

664 lines (624 sloc) 14.917 kb
/*
Copyright (c) 2002-2012 René Ladan. All rights reserved.
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:
1. Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in the
documentation and/or other materials provided with the distribution.
THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
SUCH DAMAGE.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "parsetree.h"
ParseTree::ParseTree(char *infilename, char *outfilename, int size, int range) {
tree = new Tree(NULL);
if (infilename != NULL) {
src = fopen(infilename, "r");
} else {
src = stdin;
}
if (src == NULL) {
fprintf(stderr, "Could not open %s\n", infilename);
exit(1);
}
if (outfilename != NULL) {
dst = fopen(outfilename, "w");
} else {
dst = stdout;
}
if (dst == NULL) {
fprintf(stderr, "Could not open %s\n", outfilename);
exit(1);
}
srcname = infilename;
mysize = size;
myrange = range;
need__i = 0;
need__stdio = 0;
need__range = 0;
}
ParseTree::~ParseTree() {
if (tree != NULL) {
delete tree;
tree = NULL;
}
if (dst != stdout) {
fclose(dst);
}
if (src != stdin) {
fclose(src);
}
printf("Files closed.\n");
}
int ParseTree::balance(int plus, int minus, int current) {
int r = 0;
int c;
for (c = current; (c == plus) || (c == minus); c = getc(src)) {
if (c == plus) {
r++;
}
if (c == minus) {
r--;
}
}
if (c != EOF) {
ungetc(c, src);
}
return r;
}
int ParseTree::count(int plus) {
int r = 0;
int c;
for (c = plus; c == plus; c = getc(src)) {
r++;
}
if (c != EOF) {
ungetc(c, src);
}
return r;
}
Token* ParseTree::scan() {
int c;
int num;
Token *token;
c = getc(src);
switch (c) {
case EOF:
token = new Eof();
break;
case '+' :
case '-' :
token = new Val();
token->setValue(balance('+', '-', c));
break;
case '>' :
case '<' :
token = new Ptr();
token->setValue(balance('>', '<', c));
break;
case ',' :
need__stdio++;
token = new Get();
num = count(',');
if (num > 1) {
need__i++;
printf("{notification} Run of , detected.\n");
}
token->setCount(num);
break;
case '.' :
need__stdio++;
token = new Put();
num = count('.');
if (num > 1) {
need__i++;
}
token->setCount(num);
break;
case '[' :
token = new Do();
break;
case ']' :
token = new Od();
break;
default :
token = new Token();
break;
}
return token;
}
void ParseTree::build() {
Token *token;
printf("Building parse tree.\n");
token = pProg(&tree);
if (tree->getToken() == NULL) {
delete tree;
tree = NULL;
}
if (token->getType() != ttEof) {
printf("{error} %s instead of EOF found.\n", token->getName());
exit(1);
}
}
Token *ParseTree::pStat(Tree **base) {
Token *token;
do {
token = scan();
if (token->isUsable()) {
if ((*base)->getToken() != NULL) {
(*base)->append(token);
*base = (*base)->next();
} else {
(*base)->setToken(token);
}
}
} while ((token->getType() != ttDo) && (token->getType() != ttOd) &&
(token->getType() != ttEof));
return token;
}
Token *ParseTree::pProg(Tree **base) {
Token *token;
do {
token = pStat(base);
if (token->getType() == ttOd) {
return token;
}
if (token->getType() == ttDo) {
// make subtree, recurse into it
if ((*base)->getToken() == NULL) {
(*base)->setToken(new Do());
} else {
(*base)->append(new Do());
*base = (*base)->next();
}
(*base)->insertChild(NULL); // overwrite later
*base = (*base)->child();
if (pProg(base)->getType() == ttEof) {
printf("{error} EOF instead of ] found.\n");
exit(1);
}
*base = (*base)->parent();
}
} while (token->getType() != ttEof);
return token;
}
void ParseTree::reset() {
if (tree != NULL) {
while (tree->hasParent()) {
tree = tree->parent();
}
while (tree->hasPrev()) {
tree = tree->prev();
}
}
}
void ParseTree::dump() {
if (tree != NULL) {
printf("Dumping parse tree.\n");
fprintf(dst, "/* generated by bf2c.cc from %s */\n"
"\n"
"#define SIZE %i\n", srcname, mysize);
if (need__range != 0) {
fprintf(dst, "#define RANGE %i\n", myrange);
}
fprintf(dst, "\n"
"#include <string.h>\n");
if (need__stdio != 0) {
fprintf(dst, "#include <stdio.h>\n");
}
fprintf(dst, "\n"
"int main(void) {\n");
if (need__i != 0) {
fprintf(dst, "\tint i;\n");
}
fprintf(dst, "\tsigned char a[SIZE];\n"
"\tunsigned short p;\n"
"\n"
"\tmemset(a, 0, SIZE);\n"
"\tp = 0;\n"
"\n"
"\t/* start of translation */\n"
"\n");
dumpMain(&tree, 1);
fprintf(dst, "\n"
"\t/* end of translation */\n"
"\n"
"\treturn(0);\n"
"}\n");
} else {
printf("Tree is empty!\n");
}
}
void ParseTree::dumpMain(Tree **base, int numTabs) {
Tree *start = *base;
while (*base != NULL) {
putTabs(numTabs);
fprintf(dst, "%s\n", (*base)->getToken()->getCode());
if ((*base)->getToken()->getType() == ttDo) {
if ((*base)->hasChild() &&
(*base)->child()->getToken() != NULL) {
Tree *here = *base;
*base = (*base)->child();
dumpMain(base, numTabs + 1);
*base = here;
}
// insert OD
putTabs(numTabs);
fprintf(dst, "%s\n", (new Od())->getCode());
}
*base = (*base)->next();
}
*base = start;
}
void ParseTree::putTabs(int numTabs) {
for (int i = 0; i < numTabs; i++) {
fprintf(dst,"\t");
}
}
void ParseTree::removeTail() {
printf("Removing non-i/o tail.\n");
while ((tree != NULL) && tree->hasNext()) {
tree = tree->next();
}
while ((tree != NULL) &&
(tree->getToken()->getType() != ttDo) &&
(tree->getToken()->getType() != ttPut) &&
(tree->getToken()->getType() != ttGet)) {
Tree *temp = tree;
tree = tree->prev();
delete temp;
temp = NULL;
}
}
void ParseTree::cleanTokens() {
if (tree != NULL) {
printf("Cleaning parse tree.\n");
packTokens(&tree);
}
}
void ParseTree::packTokens(Tree **base) {
Tree *start = *base;
Tree *current;
Tree *temp;
Token *t;
Token *t2;
while ((*base != NULL) && ((*base)->getToken() != NULL)) {
// find first non-DO
while ((*base != NULL) && ((*base)->getToken() != NULL) &&
((*base)->getToken()->getType() == ttDo)) {
Tree *here = *base;
*base = (*base)->child();
if (*base != NULL) {
packTokens(base);
}
*base = here->next(); // go to parent.next
// delete dead code (all DOs before a GET/VAL/PTR)
while ((*base != NULL) &&
((t = (*base)->getToken()) != NULL) &&
(t->getType() != ttGet) &&
(t->getType() != ttVal) &&
(t->getType() != ttPtr)) {
if (t->getType() == ttDo) {
temp = *base;
*base = (*base)->next();
delete temp;
temp = NULL;
} else {
*base = (*base)->next();
}
}
*base = here->next();
}
if ((*base == NULL) || ((*base)->getToken() == NULL)) {
// only do's
*base = start;
return;
}
current = *base;
Token *t = current->getToken();
*base = (*base)->next();
// join all equal nodes
while ((*base != NULL) && ((*base)->getToken() != NULL) &&
((*base)->getToken()->getType() == t->getType())) {
temp = *base;
if (t->getType() == ttMulzero) {
if (t->getOffsetDestination() ==
(*base)->getToken()->getOffsetDestination()) {
t->setMultiplier(
t->getMultiplier() +
(*base)->getToken()->
getMultiplier());
current->setToken(t);
*base = (*base)->next();
delete temp;
temp = NULL;
} else {
*base = (*base)->next();
}
} else {
// join if equal offsets
t2 = (*base)->getToken();
if ((t->getOffset() == t2->getOffset()) &&
(t->isAbsoluteOffset() ==
t2->isAbsoluteOffset())) {
// join if both not absval VAL
if (t->getType() != ttVal ||
(!t->isAbsoluteValue() &&
(!t2->isAbsoluteValue()))) {
t->setValue(t->getValue() +
t2->getValue());
t->setCount(t->getCount() +
t2->getCount());
if ((t->getCount() > 1) &&
((t->getType() == ttPut) ||
(t->getType() == ttGet))) {
need__i++;
}
current->setToken(t);
*base = (*base)->next();
delete temp;
temp = NULL;
} else {
*base = (*base)->next();
}
} else {
// not 2 mulzero's with unequal offsets
// thanks Pieter for pointing me in the
// direction
*base = (*base)->next();
}
}
}
// join VAL/GET nodes with equal offsets
if ((*base != NULL) && (*base)->hasNext()) {
Token *t2 = (*base)->next()->getToken();
t = (*base)->getToken();
if ((t->getOffset() == t2->getOffset()) &&
(t->isAbsoluteOffset() == t2->isAbsoluteOffset()) &&
(t->getType() == ttVal)) {
if (t2->getType() == ttGet) {
// delete t
temp = *base;
*base = (*base)->next();
delete temp;
temp = NULL;
} else if (t2->getType() == ttVal) {
if (t->isAbsoluteValue()) {
if (!(t2->isAbsoluteValue())) {
t2->makeAbsoluteValue(true);
t2->setValue(t2->getValue() +
t->getValue());
}
// delete t
temp = *base;
*base = (*base)->next();
(*base)->setToken(t2);
delete temp;
temp = NULL;
} else {
// t has relative value
if (!(t2->isAbsoluteValue())) {
t2->setValue(t2->getValue() +
t->getValue());
}
temp = *base;
*base = (*base)->next();
(*base)->setToken(t2);
delete temp;
temp = NULL;
}
}
}
}
// if result == NULL, delete node, creating possible empty tree
t = current->getToken();
if (((((t->getType() == ttVal) && (!t->isAbsoluteValue())) ||
(t->getType() == ttPtr)) && (t->getValue() == 0))
||
((t->getType() == ttMulzero) &&
(t->getMultiplier() == 0))) {
if (start == current) {
start = start->next();
}
temp = current;
*base = current->next();
delete temp;
temp = NULL;
}
}
*base = start;
return;
}
void ParseTree::convertMulzero() {
if (tree != NULL) {
printf("Converting mulzero's.\n");
mulzero(&tree);
}
}
void ParseTree::mulzero(Tree **base) {
Tree* start;
start = *base;
while ((*base != NULL) && ((*base)->getToken() != NULL)) {
if ((*base)->getToken()->getType() == ttDo) {
if (!tryMulzero(base)) {
Tree* here = *base;
*base = (*base)->child();
mulzero(base);
*base = here;
}
}
*base = (*base)->next();
}
*base = start;
}
bool ParseTree::tryMulzero(Tree** base) {
Tree* list = new Tree(NULL);
Token *t;
bool ret = true;
int ptr = 0;
int val = 0;
int mval = 0;
int num_mval = 0;
int ptr_added = 0;
int val_added = 0;
Tree* start = *base;
*base = (*base)->child();
while (ret && (*base != NULL) && ((*base)->getToken() != NULL)) {
switch ((*base)->getToken()->getType()) {
case ttVal:
if (ptr == 0) {
num_mval++;
if (num_mval == 1) {
mval = (*base)->getToken()->getValue();
if ((mval < -1) || (mval > 1)) {
ret = false;
}
ptr_added = 0;
} else {
ret = false;
}
} else {
val = (*base)->getToken()->getValue();
val_added++;
}
break;
case ttPtr:
ptr += (*base)->getToken()->getValue();
ptr_added++;
break;
default:
ret = false;
break;
}
if ((ret) && (ptr_added + val_added == 2)) {
t = new Mulzero();
t->setOffsetDestination(ptr);
t->setMultiplier(val);
if (list->getToken() == NULL) {
list->setToken(t);
} else {
list->prepend(t);
list = list->prev();
}
ptr_added = val_added = 0;
}
*base = (*base)->next();
}
if ((num_mval == 0) || (mval == 0) || (ptr != 0)) {
ret = false;
} // occurs with [A],[ttPtr] with A not "mulzero"
*base = start;
if (ret) {
packTokens(&list);
(*base)->delList((*base)->child());
(*base)->removeChild();
t = new Val();
t->makeAbsoluteValue(true);
(*base)->setToken(t);
while ((list != NULL) && (list->getToken() != NULL)) {
t = list->getToken();
if (mval == 1) {
t->setWrapped(true);
}
(*base)->prepend(t);
list = list->next();
*base = (*base)->prev();
}
}
if (mval == 1) {
need__range++;
}
*base = start;
return ret;
}
/* FIXME absoluteheader code temporarily not called, causes bus errors */
void ParseTree::convertAbsoluteHeader() {
if (tree != NULL) {
printf("Making header absolute.\n");
putAbsolute(&tree);
}
}
void ParseTree::putAbsolute(Tree** base) {
unsigned ptr, *val, *state;
val = new unsigned[mysize + 1];
state = new unsigned[mysize + 1];
Token *t;
Tree *temp, *start;
start = *base;
memset(val, 0, mysize + 1);
memset(state, 0, mysize + 1);
ptr = 0;
while ((*base != NULL) && ((t = (*base)->getToken()) != NULL) &&
(t->getType() != ttDo)) {
printf("again\n");
t->interpret(&val, &ptr, false, myrange);
switch (t->getType()) {
case ttPtr:
state[ptr] |= CSPTRABSOLUTE;
temp = *base;
*base = (*base)->next();
if (temp == start) {
start = *base;
}
delete temp;
temp = NULL;
break;
case ttMulzero:
state[ptr] |= CSABSOLUTE;
t->makeAbsoluteOffsetDestination(true);
t->setOffsetDestination(ptr + t->getOffsetDestination());
t->makeAbsoluteOffsetSource(true);
t->setOffsetSource(ptr + t->getOffsetSource());
(*base)->setToken(t);
break;
case ttGet:
state[ptr] |= CSGETFOUND;
t->makeAbsoluteOffset(true);
t->setOffset(ptr + t->getOffset());
break;
default: // currently ttVal, ttPut
if (t->isAbsoluteValue()) {
state[ptr] &= ~CSGETFOUND;
}
state[ptr] |= CSABSOLUTE;
t->makeAbsoluteOffset(true);
t->setOffset(ptr + t->getOffset());
if ((state[ptr] & CSGETFOUND) == 0) {
t->makeAbsoluteValue(true);
t->setValue(val[ptr]);
}
(*base)->setToken(t);
break;
}
printf("done\n");
if (t != NULL && t->getType() != ttPtr) {
*base = (*base)->next();
}
printf("done2\n");
}
if ((*base != NULL) && (t != NULL)) {
t = new Ptr();
t->makeAbsoluteValue(true);
t->setValue(ptr);
(*base)->prepend(t);
}
*base = start;
delete[] val;
val = NULL;
delete[] state;
state = NULL;
}
Jump to Line
Something went wrong with that request. Please try again.