summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAdrian Thurston <thurston@complang.org>2008-11-21 19:26:50 +0000
committerAdrian Thurston <thurston@complang.org>2008-11-21 19:26:50 +0000
commit1d941596a7dd116d8b5a2d403da7c3929f3e0254 (patch)
treeec1f7bc18d4ee2cbb8971875f261cd287ccf4899
parent478bc4d7e154e06269d33576432d9e49151131ee (diff)
downloadcolm-1d941596a7dd116d8b5a2d403da7c3929f3e0254.tar.gz
Moved the fields from the Alg structure into Tree.
-rw-r--r--colm/bytecode.cpp5
-rw-r--r--colm/fsmrun.cpp37
-rw-r--r--colm/pdabuild.cpp14
-rw-r--r--colm/pdarun.cpp129
-rw-r--r--colm/pdarun.h2
-rw-r--r--colm/tree.cpp10
6 files changed, 95 insertions, 102 deletions
diff --git a/colm/bytecode.cpp b/colm/bytecode.cpp
index 0e05ea97..539a5797 100644
--- a/colm/bytecode.cpp
+++ b/colm/bytecode.cpp
@@ -93,13 +93,10 @@ void send( Tree **root, Program *prg, PdaRun *parser, Tree *tree, bool ignore )
tree_upref( tree );
}
- assert( tree->alg == 0 );
- tree->alg = prg->algPool.allocate();
-
if ( tree->id >= prg->rtd->firstNonTermId )
tree->id = prg->rtd->lelInfo[tree->id].termDupId;
- tree->alg->flags |= AF_ARTIFICIAL;
+ tree->flags |= AF_ARTIFICIAL;
/* FIXME: Do we need to remove the ignore tokens
* at this point? Will it cause a leak? */
diff --git a/colm/fsmrun.cpp b/colm/fsmrun.cpp
index 8c6b3aed..abd77b51 100644
--- a/colm/fsmrun.cpp
+++ b/colm/fsmrun.cpp
@@ -189,9 +189,7 @@ void FsmRun::sendBackText( const char *data, long length )
void FsmRun::queueBack( Kid *input )
{
- Alg *alg = input->tree->alg;
-
- if ( alg->flags & AF_GROUP_MEM ) {
+ if ( input->tree->flags & AF_GROUP_MEM ) {
#ifdef COLM_LOG_PARSE
LangElInfo *lelInfo = parser->tables->rtd->lelInfo;
cerr << "queuing back: " << lelInfo[input->tree->id].name << endl;
@@ -245,21 +243,19 @@ void FsmRun::sendBackIgnore( Kid *ignore )
#endif
Head *head = ignore->tree->tokdata;
- bool artificial = ignore->tree->alg != 0 &&
- ignore->tree->alg->flags & AF_ARTIFICIAL;
+ bool artificial = ignore->tree->flags & AF_ARTIFICIAL;
if ( head != 0 && !artificial )
sendBackText( string_data( head ), head->length );
/* Check for reverse code. */
- Alg *alg = ignore->tree->alg;
- if ( alg != 0 && alg->flags & AF_HAS_RCODE ) {
+ if ( ignore->tree->flags & AF_HAS_RCODE ) {
Execution execution( prg, parser->reverseCode,
parser, 0, 0, 0 );
/* Do the reverse exeuction. */
execution.rexecute( parser->root, parser->allReverseCode );
- alg->flags &= ~AF_HAS_RCODE;
+ ignore->tree->flags &= ~AF_HAS_RCODE;
}
ignore = ignore->next;
@@ -271,13 +267,12 @@ void FsmRun::sendBack( Kid *input )
#ifdef COLM_LOG_PARSE
LangElInfo *lelInfo = parser->tables->rtd->lelInfo;
cerr << "sending back: " << lelInfo[input->tree->id].name;
- if ( input->tree->alg->flags & AF_ARTIFICIAL )
+ if ( input->tree->flags & AF_ARTIFICIAL )
cerr << " (artificial)";
cerr << endl;
#endif
- Alg *alg = input->tree->alg;
- if ( alg->flags & AF_NAMED ) {
+ if ( input->tree->flags & AF_NAMED ) {
/* Send back anything that is in the buffer. */
inputStream->pushBack( p, pe-p );
p = pe = runBuf->buf;
@@ -287,20 +282,20 @@ void FsmRun::sendBack( Kid *input )
inputStream->pushBackNamed();
}
- if ( !(alg->flags & AF_ARTIFICIAL) ) {
+ if ( !(input->tree->flags & AF_ARTIFICIAL) ) {
/* Push back the token data. */
sendBackText( string_data( input->tree->tokdata ),
string_length( input->tree->tokdata ) );
}
/* Check for reverse code. */
- if ( alg->flags & AF_HAS_RCODE ) {
+ if ( input->tree->flags & AF_HAS_RCODE ) {
Execution execution( prg, parser->reverseCode,
parser, 0, 0, 0 );
/* Do the reverse exeuction. */
execution.rexecute( parser->root, parser->allReverseCode );
- alg->flags &= ~AF_HAS_RCODE;
+ input->tree->flags &= ~AF_HAS_RCODE;
}
/* Always push back the ignore text. */
@@ -355,7 +350,7 @@ void set_AF_GROUP_MEM( PdaRun *parser )
/* Only bother with non-ignore tokens. */
if ( !lelInfo[queued->tree->id].ignore ) {
if ( sendCount > 0 )
- queued->tree->alg->flags |= AF_GROUP_MEM;
+ queued->tree->flags |= AF_GROUP_MEM;
sendCount += 1;
}
queued = queued->next;
@@ -465,11 +460,8 @@ void execute_generation_action( Program *prg, PdaRun *parser, Code *code, Head *
* token. */
Tree *tree = parser->queue->tree;
bool hasrcode = make_reverse_code( parser->allReverseCode, parser->reverseCode );
- if ( hasrcode ) {
- if ( tree->alg == 0 )
- tree->alg = prg->algPool.allocate();
- tree->alg->flags |= AF_HAS_RCODE;
- }
+ if ( hasrcode )
+ tree->flags |= AF_HAS_RCODE;
/* Mark generated tokens as belonging to a group. */
set_AF_GROUP_MEM( parser );
@@ -510,10 +502,9 @@ Kid *FsmRun::makeToken( int id, Head *tokdata, bool namedLangEl, int bindId )
Kid *input = 0;
input = prg->kidPool.allocate();
input->tree = prg->treePool.allocate();
- input->tree->alg = prg->algPool.allocate();
if ( namedLangEl )
- input->tree->alg->flags |= AF_NAMED;
+ input->tree->flags |= AF_NAMED;
input->tree->refs = 1;
input->tree->id = id;
@@ -694,7 +685,6 @@ void FsmRun::sendEOF( )
Kid *input = prg->kidPool.allocate();
input->tree = prg->treePool.allocate();
- input->tree->alg = prg->algPool.allocate();
input->tree->refs = 1;
input->tree->id = parser->tables->rtd->eofId;
@@ -770,7 +760,6 @@ long PdaRun::undoParse( Tree *tree, CodeVect *rev )
assert( stackTop->next == 0 );
- prg->algPool.free( stackTop->tree->alg );
prg->treePool.free( stackTop->tree );
prg->kidPool.free( stackTop );
return 0;
diff --git a/colm/pdabuild.cpp b/colm/pdabuild.cpp
index cfe69546..58ccb220 100644
--- a/colm/pdabuild.cpp
+++ b/colm/pdabuild.cpp
@@ -1385,7 +1385,7 @@ void ParseData::makeRuntimeData()
void mapNodes( Program *prg, int &count, Kid *kid )
{
if ( kid != 0 ) {
- kid->tree->alg->state = count++;
+ kid->tree->state = count++;
Kid *ignore = tree_ignore( prg, kid->tree );
while ( tree_is_ignore( prg, ignore ) ) {
@@ -1401,15 +1401,15 @@ void fillNodes( Program *prg, Bindings &bindings, long &bindId,
PatReplNode *nodes, Kid *kid )
{
if ( kid != 0 ) {
- long ind = kid->tree->alg->state;
+ long ind = kid->tree->state;
PatReplNode &node = nodes[ind++];
Kid *child = tree_child( prg, kid->tree );
/* Set up the fields. */
node.id = kid->tree->id;
- node.child = child == 0 ? -1 : child->tree->alg->state;
- node.next = kid->next == 0 ? -1 : kid->next->tree->alg->state;
+ node.child = child == 0 ? -1 : child->tree->state;
+ node.next = kid->next == 0 ? -1 : kid->next->tree->state;
node.length = string_length( kid->tree->tokdata );
node.data = string_data( kid->tree->tokdata );
@@ -1429,7 +1429,7 @@ void fillNodes( Program *prg, Bindings &bindings, long &bindId,
ignore = ignore->next;
}
- node.stop = kid->tree->alg->flags & AF_TERM_DUP;
+ node.stop = kid->tree->flags & AF_TERM_DUP;
/* Recurse. */
fillNodes( prg, bindings, bindId, nodes, child );
@@ -1469,7 +1469,7 @@ void ParseData::fillInPatterns( Program *prg )
for ( PatternList::Iter pat = patternList; pat.lte(); pat++ ) {
runtimeData->patReplInfo[pat->patRepId].offset =
- pat->pdaRun->stackTop->next->tree->alg->state;
+ pat->pdaRun->stackTop->next->tree->state;
/* BindIds are indexed base one. */
runtimeData->patReplInfo[pat->patRepId].numBindings =
@@ -1483,7 +1483,7 @@ void ParseData::fillInPatterns( Program *prg )
for ( ReplList::Iter repl = replList; repl.lte(); repl++ ) {
runtimeData->patReplInfo[repl->patRepId].offset =
- repl->pdaRun->stackTop->next->tree->alg->state;
+ repl->pdaRun->stackTop->next->tree->state;
/* BindIds are indexed base one. */
runtimeData->patReplInfo[repl->patRepId].numBindings =
diff --git a/colm/pdarun.cpp b/colm/pdarun.cpp
index 50b8b90f..71ca612e 100644
--- a/colm/pdarun.cpp
+++ b/colm/pdarun.cpp
@@ -90,9 +90,8 @@ void PdaRun::init()
/* Init the element allocation variables. */
stackTop = prg->kidPool.allocate();
stackTop->tree = prg->treePool.allocate();
- stackTop->tree->alg = prg->algPool.allocate();
- stackTop->tree->alg->state = -1;
+ stackTop->tree->state = -1;
stackTop->tree->refs = 1;
numRetry = 0;
errCount = 0;
@@ -109,12 +108,12 @@ void PdaRun::init()
long PdaRun::stackTopTarget()
{
long state;
- if ( stackTop->tree->alg->state < 0 )
+ if ( stackTop->tree->state < 0 )
state = tables->startState;
else {
state = tables->targs[(int)tables->indicies[tables->offsets[
- stackTop->tree->alg->state] +
- (stackTop->tree->id - tables->keys[stackTop->tree->alg->state<<1])]];
+ stackTop->tree->state] +
+ (stackTop->tree->id - tables->keys[stackTop->tree->state<<1])]];
}
return state;
}
@@ -135,7 +134,7 @@ long PdaRun::stackTopTarget()
bool been_committed( Kid *kid )
{
- return kid->tree->alg->flags & AF_COMMITTED;
+ return kid->tree->flags & AF_COMMITTED;
}
Code *backup_over_rcode( Code *rcode )
@@ -151,7 +150,6 @@ Code *backup_over_rcode( Code *rcode )
* linked left-to-right. */
void commit_kid( PdaRun *parser, Tree **root, Kid *lel, Code *&rcode, long &causeReduce )
{
- Alg *alg = 0;
Tree *tree = 0;
Tree **sp = root;
Tree *restore = 0;
@@ -165,21 +163,20 @@ head:
/* Load up the parsed tree. */
tree = lel->tree;
- alg = tree->alg;
/* Check for reverse code. */
restore = 0;
- if ( alg->flags & AF_HAS_RCODE ) {
+ if ( tree->flags & AF_HAS_RCODE ) {
/* If tree caused some reductions, now is not the right time to backup
* over the reverse code. We need to backup over the reductions first. Store
* the count of the reductions and do it when the count drops to zero. */
- if ( alg->causeReduce > 0 ) {
+ if ( tree->causeReduce > 0 ) {
/* The top reduce block does not correspond to this alg. */
#ifdef COLM_LOG_PARSE
cerr << "commit: causeReduce found, delaying backup: " <<
- (long)alg->causeReduce << endl;
+ (long)tree->causeReduce << endl;
#endif
- causeReduce = alg->causeReduce;
+ causeReduce = tree->causeReduce;
}
else {
rcode = backup_over_rcode( rcode );
@@ -193,6 +190,10 @@ head:
}
}
+ /* FIXME: Need to sort out the storage of parse algorithm data. Is it in
+ * the restored node or the original? This needs to be reconciled with the
+ * parse and unparse algorithms. */
+
if ( restore != 0 )
tree = restore;
@@ -200,7 +201,7 @@ head:
* belonging to a nonterminal that caused previous reductions. */
if ( causeReduce > 0 &&
tree->id >= parser->tables->rtd->firstNonTermId &&
- !(alg->flags & AF_TERM_DUP) )
+ !(tree->flags & AF_TERM_DUP) )
{
causeReduce -= 1;
@@ -215,18 +216,18 @@ head:
}
/* Reset retries. */
- if ( alg->retry_lower > 0 ) {
+ if ( tree->retry_lower > 0 ) {
parser->numRetry -= 1;
- alg->retry_lower = 0;
+ tree->retry_lower = 0;
}
- if ( alg->retry_upper > 0 ) {
+ if ( tree->retry_upper > 0 ) {
parser->numRetry -= 1;
- alg->retry_upper = 0;
+ tree->retry_upper = 0;
}
- alg->flags |= AF_COMMITTED;
+ tree->flags |= AF_COMMITTED;
/* Do not recures on trees that are terminal dups. */
- if ( !(alg->flags & AF_TERM_DUP) && tree_child( parser->prg, tree ) != 0 ) {
+ if ( !(tree->flags & AF_TERM_DUP) && tree_child( parser->prg, tree ) != 0 ) {
vm_push( (Tree*)lel );
lel = tree_child( parser->prg, tree );
@@ -308,9 +309,9 @@ void PdaRun::parseToken( Kid *input )
if ( cs < 0 )
return;
- input->tree->alg->region = nextRegionInd;
- input->tree->alg->state = cs;
- if ( tables->tokenRegions[input->tree->alg->region+1] != 0 )
+ input->tree->region = nextRegionInd;
+ input->tree->state = cs;
+ if ( tables->tokenRegions[input->tree->region+1] != 0 )
numRetry += 1;
again:
@@ -328,15 +329,15 @@ again:
induceReject = false;
targState = tables->targs[pos];
action = tables->actions + tables->actInds[pos];
- if ( lel->tree->alg->retry_lower )
- action += lel->tree->alg->retry_lower;
+ if ( lel->tree->retry_lower )
+ action += lel->tree->retry_lower;
if ( *action & act_sb ) {
#ifdef COLM_LOG_PARSE
cerr << "shifted: " << tables->rtd->lelInfo[lel->tree->id].name;
#endif
input = input->next;
- lel->tree->alg->state = cs;
+ lel->tree->state = cs;
lel->next = stackTop;
stackTop = lel;
@@ -345,14 +346,14 @@ again:
tables->rtd->lelInfo[lel->tree->id].termDupId > 0 )
{
lel->tree->id = tables->rtd->lelInfo[lel->tree->id].termDupId;
- lel->tree->alg->flags |= AF_TERM_DUP;
+ lel->tree->flags |= AF_TERM_DUP;
}
if ( action[1] == 0 )
- lel->tree->alg->retry_lower = 0;
+ lel->tree->retry_lower = 0;
else {
- lel->tree->alg->retry_lower += 1;
- assert( lel->tree->alg->retry_upper == 0 );
+ lel->tree->retry_lower += 1;
+ assert( lel->tree->retry_upper == 0 );
numRetry += 1; /* FIXME: Has the retry already been counted? */
#ifdef COLM_LOG_PARSE
cerr << " retry: " << stackTop;
@@ -366,9 +367,8 @@ again:
if ( tables->commitLen[pos] != 0 ) {
long causeReduce = 0;
if ( input != 0 ) {
- Alg *alg = input->tree->alg;
- if ( alg->flags & AF_HAS_RCODE )
- causeReduce = alg->causeReduce;
+ if ( input->tree->flags & AF_HAS_RCODE )
+ causeReduce = input->tree->causeReduce;
}
commit_full( this, causeReduce );
}
@@ -379,7 +379,7 @@ again:
Alg *redAlg;
if ( input != 0 )
- input->tree->alg->causeReduce += 1;
+ input->tree->causeReduce += 1;
redLel = prg->kidPool.allocate();
redLel->tree = prg->treePool.allocate();
@@ -391,8 +391,8 @@ again:
redLel->next = 0;
redAlg->causeReduce = 0;
redAlg->retry_lower = 0;
- redAlg->retry_upper = lel->tree->alg->retry_lower;
- lel->tree->alg->retry_lower = 0;
+ redAlg->retry_upper = lel->tree->retry_lower;
+ lel->tree->retry_lower = 0;
/* Allocate the attributes. */
objectLength = tables->rtd->lelInfo[redLel->tree->id].objectLength;
@@ -419,7 +419,7 @@ again:
redAlg->retry_upper = 0;
else {
redAlg->retry_upper += 1;
- assert( lel->tree->alg->retry_lower == 0 );
+ assert( lel->tree->retry_lower == 0 );
numRetry += 1;
#ifdef COLM_LOG_PARSE
cerr << " retry: " << redLel;
@@ -432,7 +432,7 @@ again:
/* When the production is of zero length we stay in the same state.
* Otherwise we use the state stored in the first child. */
- targState = rhsLen == 0 ? cs : child->tree->alg->state;
+ targState = rhsLen == 0 ? cs : child->tree->state;
assert( redLel->tree->refs == 1 );
@@ -480,14 +480,21 @@ again:
}
/* Save the algorithm data in the reduced tree. */
- redLel->tree->alg = redAlg;
+ redLel->tree->state = redAlg->state;
+ redLel->tree->region = redAlg->region;
+ redLel->tree->causeReduce = redAlg->causeReduce;
+ redLel->tree->retry_lower = redAlg->retry_lower;
+ redLel->tree->retry_upper = redAlg->retry_upper;
+ redLel->tree->flags = redAlg->flags;
+
+ prg->algPool.free( redAlg );
if ( induceReject ) {
#ifdef COLM_LOG_PARSE
cerr << "error induced during reduction of " <<
tables->rtd->lelInfo[redLel->tree->id].name << endl;
#endif
- redLel->tree->alg->state = cs;
+ redLel->tree->state = cs;
redLel->next = stackTop;
stackTop = redLel;
cs = targState;
@@ -513,9 +520,9 @@ parseError:
while ( 1 ) {
if ( input != 0 ) {
- assert( input->tree->alg->retry_upper == 0 );
+ assert( input->tree->retry_upper == 0 );
- if ( input->tree->alg->retry_lower != 0 ) {
+ if ( input->tree->retry_lower != 0 ) {
#ifdef COLM_LOG_PARSE
cerr << "found retry targ: " << input << endl;
#endif
@@ -524,14 +531,14 @@ parseError:
cerr << "found retry: " << input << endl;
#endif
- cs = input->tree->alg->state;
+ cs = input->tree->state;
goto again;
}
/* If there is no retry and there are no reductions caused by the
* current input token then we are finished with it. Send it back. */
- if ( input->tree->alg->causeReduce == 0 ) {
- int next = input->tree->alg->region + 1;
+ if ( input->tree->causeReduce == 0 ) {
+ int next = input->tree->region + 1;
fsmRun->queueBack( input );
input = 0;
@@ -561,7 +568,7 @@ parseError:
/* Either we are dealing with a terminal that was
* shifted or a nonterminal that was reduced. */
if ( stackTop->tree->id < tables->rtd->firstNonTermId ||
- (stackTop->tree->alg->flags & AF_TERM_DUP) )
+ (stackTop->tree->flags & AF_TERM_DUP) )
{
#ifdef COLM_LOG_PARSE
cerr << "backing up over effective terminal: " <<
@@ -572,9 +579,9 @@ parseError:
stackTop = stackTop->next;
/* Undo the translation from termDup. */
- if ( undoLel->tree->alg->flags & AF_TERM_DUP ) {
+ if ( undoLel->tree->flags & AF_TERM_DUP ) {
undoLel->tree->id = tables->rtd->lelInfo[undoLel->tree->id].termDupId;
- undoLel->tree->alg->flags &= ~AF_TERM_DUP;
+ undoLel->tree->flags &= ~AF_TERM_DUP;
}
/* Queue it as next input item. */
@@ -587,18 +594,20 @@ parseError:
tables->rtd->lelInfo[stackTop->tree->id].name << endl;
#endif
+ /* FIXME: Need to reconcile the storage of alg data here. */
+
/* Take the alg out of undoLel. */
- Alg *alg = undoLel->tree->alg;
- assert( alg != 0 );
- undoLel->tree->alg = 0;
+ //Alg *alg = undoLel->tree->alg;
+ //assert( alg != 0 );
+ //undoLel->tree->alg = 0;
/* Check for an execution environment. */
- if ( alg->flags & AF_HAS_RCODE ) {
+ if ( undoLel->tree->flags & AF_HAS_RCODE ) {
Execution execution( prg, reverseCode, this, 0, 0, 0 );
/* Do the reverse exeuction. */
execution.rexecute( root, allReverseCode );
- alg->flags &= ~AF_HAS_RCODE;
+ undoLel->tree->flags &= ~AF_HAS_RCODE;
if ( execution.lhs != 0 ) {
/* Get the lhs, it may have been reverted. */
@@ -632,26 +641,26 @@ parseError:
/* If there is an input queued, this is one less reduction it has
* caused. */
if ( input != 0 )
- input->tree->alg->causeReduce -= 1;
+ input->tree->causeReduce -= 1;
- if ( alg->retry_upper != 0 ) {
+ if ( undoLel->tree->retry_upper != 0 ) {
/* There is always an input item here because reduce
* conflicts only happen on a lookahead character. */
assert( input != undoLel );
assert( input != 0 );
- assert( alg->retry_lower == 0 );
- assert( input->tree->alg->retry_upper == 0 );
+ assert( undoLel->tree->retry_lower == 0 );
+ assert( input->tree->retry_upper == 0 );
/* Transfer the retry from undoLel to input. */
- input->tree->alg->retry_lower = alg->retry_upper;
- input->tree->alg->retry_upper = 0;
- input->tree->alg->state = stackTopTarget();
+ input->tree->retry_lower = undoLel->tree->retry_upper;
+ input->tree->retry_upper = 0;
+ input->tree->state = stackTopTarget();
}
/* Free the reduced item. */
tree_downref( prg, root, undoLel->tree );
prg->kidPool.free( undoLel );
- prg->algPool.free( alg );
+ //prg->algPool.free( alg );
}
}
diff --git a/colm/pdarun.h b/colm/pdarun.h
index 27d15a4a..ec0c13ad 100644
--- a/colm/pdarun.h
+++ b/colm/pdarun.h
@@ -74,8 +74,6 @@ struct Tree
Head *tokdata;
- Alg *alg;
-
/* Parsing algorithm. */
long state;
long region;
diff --git a/colm/tree.cpp b/colm/tree.cpp
index 43e2e285..0d25aaa9 100644
--- a/colm/tree.cpp
+++ b/colm/tree.cpp
@@ -861,11 +861,11 @@ free_tree:
else if ( tree->id == LEL_ID_STREAM )
stream_free( prg, (Stream*) tree );
else {
- if ( tree->alg != 0 ) {
- //assert( ! (tree->alg->flags & AF_HAS_RCODE) );
- //vm_push( tree->alg->parsed );
- prg->algPool.free( tree->alg );
- }
+ //if ( tree->alg != 0 ) {
+ // //assert( ! (tree->alg->flags & AF_HAS_RCODE) );
+ // //vm_push( tree->alg->parsed );
+ // prg->algPool.free( tree->alg );
+ //}
string_free( prg, tree->tokdata );
Kid *child = tree->child;