Started precedence implementation.

6 files changed, 130 insertions, 4 deletions

diff --git a/colm/lmparse.kh b/colm/lmparse.kh
index bac8a62d..47678353 100644
--- a/colm/lmparse.kh
+++ b/colm/lmparse.kh
@@ -60,6 +60,8 @@ struct Parser
 
 	token KW_Include, KW_Preeof;
 
+	token KW_Left, KW_Right, KW_Nonassoc, KW_Prec;
+
 	}%%
 
 	%% write instance_data;
@@ -99,6 +101,8 @@ struct Parser
 
 	String curDefineId;
 	ProdElList *curProdElList;
+
+	PredType predType;
 };
 
 %% write token_defs;
diff --git a/colm/lmparse.kl b/colm/lmparse.kl
index 799418a1..489f0bf8 100644
--- a/colm/lmparse.kl
+++ b/colm/lmparse.kl
@@ -77,6 +77,7 @@ root_item: iter_def commit final { $$->stmt = 0; };
 root_item: global_def commit final { $$->stmt = $1->stmt; };
 root_item: statement commit final { $$->stmt = $1->stmt; };
 root_item: pre_eof commit final { $$->stmt = 0; };
+root_item: precedence commit final { $$->stmt = 0; };
 
 nonterm block_open
 {
@@ -248,6 +249,36 @@ global_def: KW_Global var_def opt_def_init
 		}
 	};
 
+precedence: pred_type pred_token_list final { pd->predValue++; };
+
+pred_type: KW_Left final { predType = PredLeft; };
+pred_type: KW_Right final { predType = PredRight; };
+pred_type: KW_Nonassoc final { predType = PredNonassoc; };
+
+pred_token_list: pred_token_list ',' pred_token;
+pred_token_list: pred_token;
+
+pred_token: 
+	region_qual TK_Word 
+	final {
+		PdaFactor *factor = new PdaFactor( $2->loc, false, $1->nspaceQual,
+				$2->data, 0, false, false );
+		pd->resolveReferenceFactor( factor );
+		factor->langEl->predType = predType;
+		factor->langEl->predValue = pd->predValue;
+	};
+
+pred_token: 
+	region_qual TK_Literal 
+	final {
+		PdaLiteral *literal = new PdaLiteral( $2->loc, *$2 );
+		PdaFactor *factor = new PdaFactor( $2->loc, false, $1->nspaceQual,
+				literal, 0, false, false );
+		pd->resolveLiteralFactor( factor );
+		factor->langEl->predType = predType;
+		factor->langEl->predValue = pd->predValue;
+	};
+
 cfl_def: cfl_def_head obj_var_list properties_list cfl_prod_list
 	final {
 		/* Get the language element. */
@@ -1970,7 +2001,7 @@ void Parser::addProduction( InputLoc &loc, const String &name,
 	Definition *newDef = new Definition( loc, prodName, 
 		prodElList, commit, redBlock,
 		pd->prodList.length(), Definition::Production );
-
+	
 	prodName->defList.append( newDef );
 	pd->prodList.append( newDef );
 
diff --git a/colm/lmscan.rl b/colm/lmscan.rl
index 83283c35..8d42f274 100644
--- a/colm/lmscan.rl
+++ b/colm/lmscan.rl
@@ -390,6 +390,10 @@ void Scanner::endSection( )
 		'deref' => { token( KW_Deref ); };
 		'require' => { token( KW_Require ); };
 		'preeof' => { token( KW_Preeof ); };
+		'left' => { token( KW_Left ); };
+		'right' => { token( KW_Right ); };
+		'nonassoc' => { token( KW_Nonassoc ); };
+		'prec' => { token( KW_Prec ); };
 
 		# Identifiers.
 		ident => { token( TK_Word, ts, te ); } ;
diff --git a/colm/parsedata.cpp b/colm/parsedata.cpp
index c0f086b5..116e576d 100644
--- a/colm/parsedata.cpp
+++ b/colm/parsedata.cpp
@@ -428,7 +428,8 @@ ParseData::ParseData( const String &fileName, const String &sectionName,
 	nextFrameId(0),
 	nextParserId(0),
 	nextLabelId(0),
-	revertOn(true)
+	revertOn(true),
+	predValue(0)
 {
 }
 
@@ -1243,11 +1244,23 @@ void ParseData::resolveFactor( PdaFactor *fact )
 	}
 }
 
+/* Resolves production els and computes the precedence of each prod. */
 void ParseData::resolveProductionEls()
 {
 	for ( DefList::Iter prod = prodList; prod.lte(); prod++ ) {
+		/* First resolve. */
 		for ( ProdElList::Iter fact = *prod->prodElList; fact.lte(); fact++ )
 			resolveFactor( fact );
+
+		/* Compute the precedence of the productions. */
+		for ( ProdElList::Iter fact = prod->prodElList->last(); fact.gtb(); fact-- ) {
+			/* Production inherits the precedence of the last terminal with
+			 * precedence. */
+			if ( fact->langEl->predType != PredNone ) {
+				prod->predOf = fact->langEl;
+				break;
+			}
+		}
 	}
 }
 
diff --git a/colm/parsedata.h b/colm/parsedata.h
index ab60f859..416dfa4a 100644
--- a/colm/parsedata.h
+++ b/colm/parsedata.h
@@ -75,6 +75,8 @@ typedef Vector< PdaFactor* > FactorVect;
 typedef AvlMap<String, long, CmpStr> StringMap;
 typedef AvlMapEl<String, long> StringMapEl;
 
+enum PredType { PredLeft, PredRight, PredNonassoc, PredNone };
+
 /* Graph dictionary. */
 struct Definition 
 :
@@ -87,7 +89,7 @@ struct Definition
 		loc(loc), prodName(prodName), prodElList(prodElList), 
 		prodCommit(prodCommit), redBlock(redBlock), prodId(prodId), 
 		type(type), fsm(0), fsmLength(0), uniqueEmptyLeader(0), 
-		isLeftRec(false), localFrame(0), lhsField(0) {}
+		isLeftRec(false), localFrame(0), lhsField(0), predOf(0) {}
 
 	InputLoc loc;
 	KlangEl *prodName;
@@ -112,6 +114,8 @@ struct Definition
 
 	ObjectDef *localFrame;
 	ObjField *lhsField;
+
+	KlangEl *predOf;
 };
 
 struct CmpDefById
@@ -206,6 +210,9 @@ struct KlangEl : public DListEl<KlangEl>
 	GenericType *generic;
 
 	long parserId;
+
+	PredType predType;
+	long predValue;
 };
 
 struct PdaFactor
@@ -510,6 +517,9 @@ struct ParseData
 
 	void analyzeAction( Action *action, InlineList *inlineList );
 	void analyzeGraph( FsmGraph *graph );
+	void resolvePrecedence( PdaGraph *pdaGraph );
+	KlangEl *predOf( PdaTrans *trans, long action );
+	bool precedenceSwap( KlangEl *l1, KlangEl *l2 );
 
 	void initKeyOps();
 
@@ -903,6 +913,8 @@ struct ParseData
 
 	PdaGraph *pdaGraph;
 	PdaTables *pdaTables;
+
+	long predValue;
 };
 
 void afterOpMinimize( FsmGraph *fsm, bool lastInSeq = true );
diff --git a/colm/pdabuild.cpp b/colm/pdabuild.cpp
index 4c718399..7d424e2f 100644
--- a/colm/pdabuild.cpp
+++ b/colm/pdabuild.cpp
@@ -85,7 +85,9 @@ KlangEl::KlangEl( Namespace *nspace, const String &name, Type type )
 	thisSize(0),
 	ofiOffset(0),
 	generic(0),
-	parserId(-1)
+	parserId(-1),
+	predType(PredNone),
+	predValue(0)
 {
 }
  
@@ -907,6 +909,65 @@ void ParseData::verifyParseStopGrammar( KlangEl *langEl, PdaGraph *pdaGraph )
 	}
 }
 
+KlangEl *ParseData::predOf( PdaTrans *trans, long action )
+{
+	KlangEl *lel;
+	if ( action == SHIFT_CODE )
+		lel = langElIndex[trans->lowKey];
+	else
+		lel = prodIdIndex[action >> 2]->predOf;
+	return lel;
+}
+
+bool ParseData::precedenceSwap( KlangEl *l1, KlangEl *l2 )
+{
+	bool swap = false;
+	if ( l2->predValue > l1->predValue )
+		swap = true;
+	else if ( l1->predValue == l2->predValue ) {
+		if ( l1->predType == PredLeft && trans->actions[i] == SHIFT_CODE )
+			swap = true;
+		else if ( l1->predType == PredRight && trans->actions[j] == SHIFT_CODE )
+			swap = true;
+	}
+	return swap;
+}
+
+void ParseData::resolvePrecedence( PdaGraph *pdaGraph )
+{
+	for ( PdaStateList::Iter state = pdaGraph->stateList; state.lte(); state++ ) {
+		assert( CmpDotSet::compare( state->dotSet, state->dotSet2 ) == 0 );
+		for ( TransMap::Iter tel = state->transMap; tel.lte(); tel++ ) {
+			PdaTrans *trans = tel->value;
+
+again:
+			/* Find action with precedence. */
+			for ( int i = 0; i < trans->actions.length(); i++ ) {
+				KlangEl *li = predOf( trans, trans->actions[i] );
+					
+				if ( li != 0 && li->predValue != PredNone ) {
+					/* Find another action with precedence. */
+					for ( int j = i+1; j < trans->actions.length(); j++ ) {
+						KlangEl *lj = predOf( trans, trans->actions[j] );
+
+						if ( lj != 0 && lj->predValue != PredNone ) {
+							/* Conflict to check. */
+							bool swap = precedenceSwap( li, lj );
+							
+							if ( swap ) {
+								long t = trans->actions[i];
+								trans->actions[i] = trans->actions[j];
+								trans->actions[j] = t;
+								goto again;
+							}
+						}
+					}
+				}
+			}
+		}
+	}
+}
+
 void ParseData::analyzeMachine( PdaGraph *pdaGraph, KlangElSet &parserEls )
 {
 	pdaGraph->maxState = pdaGraph->stateList.length() - 1;
@@ -929,6 +990,7 @@ void ParseData::analyzeMachine( PdaGraph *pdaGraph, KlangElSet &parserEls )
 
 	pdaActionOrder( pdaGraph, parserEls );
 	sortActions( pdaGraph );
+	resolvePrecedence( pdaGraph );
 	advanceReductions( pdaGraph );
 	pdaGraph->setStateNumbers();
 	reduceActions( pdaGraph );