diff options
author | Adrian Thurston <thurston@colm.net> | 2019-12-27 17:09:11 +0200 |
---|---|---|
committer | Adrian Thurston <thurston@colm.net> | 2019-12-27 17:14:21 +0200 |
commit | 76c61145948c8c7918d3f1b3a6a1e91be457629c (patch) | |
tree | 467b70914b86282db1f4f63f8d24af6d5fbb50f6 /colm | |
parent | 2589d8bc96cced6519a09dba1996a021cd2cf34d (diff) | |
download | colm-76c61145948c8c7918d3f1b3a6a1e91be457629c.tar.gz |
colm: proper implementation of both left and right recursion in c++
Not doing these in colm. Relying on th existing correct implementation. Also
removed the naming conflict between left and right recursion.
Diffstat (limited to 'colm')
-rw-r--r-- | colm/compiler.cc | 13 | ||||
-rw-r--r-- | colm/compiler.h | 2 | ||||
-rw-r--r-- | colm/consinit.cc | 10 | ||||
-rw-r--r-- | colm/consinit.h | 4 | ||||
-rw-r--r-- | colm/loadfinal.cc | 45 | ||||
-rw-r--r-- | colm/loadinit.cc | 4 | ||||
-rw-r--r-- | colm/parsetree.h | 3 | ||||
-rw-r--r-- | colm/prog.lm | 15 | ||||
-rw-r--r-- | colm/resolve.cc | 20 |
9 files changed, 66 insertions, 50 deletions
diff --git a/colm/compiler.cc b/colm/compiler.cc index f6276e9d..6b2b1032 100644 --- a/colm/compiler.cc +++ b/colm/compiler.cc @@ -808,10 +808,11 @@ LangEl *Compiler::makeRepeatProd( const InputLoc &loc, Namespace *nspace, } LangEl *Compiler::makeListProd( const InputLoc &loc, Namespace *nspace, - const String &listName, UniqueType *ut ) + const String &listName, UniqueType *ut, bool left ) { LangEl *prodName = addLangEl( this, nspace, listName, LangEl::NonTerm ); prodName->isList = true; + prodName->leftRecursive = left; /* Build the first production of the list. */ TypeRef *typeRef1 = TypeRef::cons( loc, ut ); @@ -822,8 +823,14 @@ LangEl *Compiler::makeListProd( const InputLoc &loc, Namespace *nspace, ProdEl *factor2 = new ProdEl( ProdEl::ReferenceType, loc, 0, false, typeRef2, 0 ); ProdElList *prodElList1 = new ProdElList; - prodElList1->append( factor2 ); - prodElList1->append( factor1 ); + if ( left ) { + prodElList1->append( factor2 ); + prodElList1->append( factor1 ); + } + else { + prodElList1->append( factor1 ); + prodElList1->append( factor2 ); + } Production *newDef1 = Production::cons( loc, prodName, prodElList1, String(), false, 0, diff --git a/colm/compiler.h b/colm/compiler.h index bf465dc6..f22b33e3 100644 --- a/colm/compiler.h +++ b/colm/compiler.h @@ -744,7 +744,7 @@ struct Compiler LangEl *makeRepeatProd( const InputLoc &loc, Namespace *nspace, const String &repeatName, UniqueType *ut, bool left ); LangEl *makeListProd( const InputLoc &loc, Namespace *nspace, - const String &listName, UniqueType *ut ); + const String &listName, UniqueType *ut, bool left ); LangEl *makeOptProd( const InputLoc &loc, Namespace *nspace, const String &optName, UniqueType *ut ); void resolveProdEl( ProdEl *prodEl ); diff --git a/colm/consinit.cc b/colm/consinit.cc index 7c719615..4f59b07c 100644 --- a/colm/consinit.cc +++ b/colm/consinit.cc @@ -343,21 +343,21 @@ ProdEl *ConsInit::prodRefName( const String &capture, const String &name ) return prodEl; } -ProdEl *ConsInit::prodRefNameRepeat( const String &name ) +ProdEl *ConsInit::prodRefNameLeftRepeat( const String &name ) { ProdEl *prodEl = prodElName( internal, name, NamespaceQual::cons( curNspace() ), 0, - RepeatLeft, false ); + RepeatLeftRepeat, false ); return prodEl; } -ProdEl *ConsInit::prodRefNameRepeat( const String &capture, const String &name ) +ProdEl *ConsInit::prodRefNameLeftRepeat( const String &capture, const String &name ) { ObjectField *captureField = ObjectField::cons( internal, ObjectField::RhsNameType, 0, capture ); ProdEl *prodEl = prodElName( internal, name, NamespaceQual::cons( curNspace() ), captureField, - RepeatLeft, false ); + RepeatLeftRepeat, false ); return prodEl; } @@ -763,7 +763,7 @@ void ConsInit::item() void ConsInit::startProd() { - ProdEl *prodEl1 = prodRefNameRepeat( "ItemList", "item" ); + ProdEl *prodEl1 = prodRefNameLeftRepeat( "ItemList", "item" ); Production *prod1 = production( prodEl1 ); definition( "start", prod1 ); diff --git a/colm/consinit.h b/colm/consinit.h index 7485445c..614f19d4 100644 --- a/colm/consinit.h +++ b/colm/consinit.h @@ -41,8 +41,8 @@ struct ConsInit ProdEl *prodRefName( const String &name ); ProdEl *prodRefName( const String &capture, const String &name ); - ProdEl *prodRefNameRepeat( const String &name ); - ProdEl *prodRefNameRepeat( const String &capture, const String &name ); + ProdEl *prodRefNameLeftRepeat( const String &name ); + ProdEl *prodRefNameLeftRepeat( const String &capture, const String &name ); ProdEl *prodRefLit( const String &lit ); Production *production(); diff --git a/colm/loadfinal.cc b/colm/loadfinal.cc index a6496f15..4162140d 100644 --- a/colm/loadfinal.cc +++ b/colm/loadfinal.cc @@ -380,7 +380,7 @@ struct LoadColm return name; } - ObjectDef *walkVarDefList( _repeat_var_def varDefList ) + ObjectDef *walkVarDefList( _lrepeat_var_def varDefList ) { ObjectDef *objectDef = ObjectDef::cons( ObjectDef::UserType, String(), pd->nextObjectId++ ); @@ -530,7 +530,7 @@ struct LoadColm return list; } - PatternItemList *walkPatSqConsDataList( _repeat_sq_cons_data sqConsDataList, CONS_SQ_NL Nl ) + PatternItemList *walkPatSqConsDataList( _lrepeat_sq_cons_data sqConsDataList, CONS_SQ_NL Nl ) { PatternItemList *list = new PatternItemList; @@ -557,7 +557,7 @@ struct LoadColm return list; } - ConsItemList *walkConsSqConsDataList( _repeat_sq_cons_data sqConsDataList, CONS_SQ_NL Nl ) + ConsItemList *walkConsSqConsDataList( _lrepeat_sq_cons_data sqConsDataList, CONS_SQ_NL Nl ) { ConsItemList *list = new ConsItemList; @@ -584,7 +584,7 @@ struct LoadColm return list; } - PatternItemList *walkLitpatElList( _repeat_litpat_el litpatElList, LIT_DQ_NL Nl, + PatternItemList *walkLitpatElList( _lrepeat_litpat_el litpatElList, LIT_DQ_NL Nl, LangVarRef *patternVarRef ) { PatternItemList *list = new PatternItemList; @@ -608,7 +608,7 @@ struct LoadColm return list; } - PatternItemList *walkPatternElList( _repeat_pattern_el patternElList, + PatternItemList *walkPatternElList( _lrepeat_pattern_el patternElList, LangVarRef *patternVarRef ) { PatternItemList *list = new PatternItemList; @@ -781,7 +781,7 @@ struct LoadColm StmtList *walkInclude( _include Include ) { String lit = ""; - _repeat_sq_cons_data sqConsDataList = Include.SqConsDataList(); + _lrepeat_sq_cons_data sqConsDataList = Include.SqConsDataList(); RepeatIter<sq_cons_data> sqConsDataIter( sqConsDataList ); @@ -866,11 +866,10 @@ struct LoadColm repeatType = RepeatOpt; break; case opt_repeat::LeftStar: - repeatType = RepeatLeft; + repeatType = RepeatLeftRepeat; break; case opt_repeat::LeftPlus: - error( OptRepeat.loc() ) << "<* and <+ are implemented as a " - "colm transformation, they are not accepted at this stage" << endp; + repeatType = RepeatLeftList; break; } return repeatType; @@ -988,8 +987,12 @@ struct LoadColm opt_repeat::prod_name orpn = El.opt_repeat().prodName(); if ( orpn == opt_repeat::Star ) fieldName = "_repeat_" + fieldName; + else if ( orpn == opt_repeat::LeftStar ) + fieldName = "_lrepeat_" + fieldName; else if ( orpn == opt_repeat::Plus ) fieldName = "_list_" + fieldName; + else if ( orpn == opt_repeat::LeftPlus ) + fieldName = "_llist_" + fieldName; else if ( orpn == opt_repeat::Question ) fieldName = "_opt_" + fieldName; else if ( strcmp( fieldName, defName ) == 0 ) @@ -1460,7 +1463,7 @@ struct LoadColm return list; } - ConsItemList *walkLitConsElList( _repeat_lit_cons_el litConsElList, + ConsItemList *walkLitConsElList( _lrepeat_lit_cons_el litConsElList, LIT_DQ_NL Nl, TypeRef *consTypeRef ) { ConsItemList *list = new ConsItemList; @@ -1522,7 +1525,7 @@ struct LoadColm return list; } - ConsItemList *walkConsElList( _repeat_cons_el consElList, TypeRef *consTypeRef ) + ConsItemList *walkConsElList( _lrepeat_cons_el consElList, TypeRef *consTypeRef ) { ConsItemList *list = new ConsItemList; @@ -1597,7 +1600,7 @@ struct LoadColm return list; } - ConsItemList *walkLitStringElList( _repeat_lit_string_el litStringElList, LIT_DQ_NL Nl ) + ConsItemList *walkLitStringElList( _lrepeat_lit_string_el litStringElList, LIT_DQ_NL Nl ) { ConsItemList *list = new ConsItemList; @@ -1653,7 +1656,7 @@ struct LoadColm return list; } - ConsItemList *walkStringElList( _repeat_string_el stringElList ) + ConsItemList *walkStringElList( _lrepeat_string_el stringElList ) { ConsItemList *list = new ConsItemList; @@ -1729,7 +1732,7 @@ struct LoadColm return list; } - ConsItemList *walkLitAccumElList( _repeat_lit_accum_el litAccumElList, LIT_DQ_NL Nl ) + ConsItemList *walkLitAccumElList( _lrepeat_lit_accum_el litAccumElList, LIT_DQ_NL Nl ) { ConsItemList *list = new ConsItemList; @@ -1785,7 +1788,7 @@ struct LoadColm return list; } - ConsItemList *walkAccumElList( _repeat_accum_el accumElList ) + ConsItemList *walkAccumElList( _lrepeat_accum_el accumElList ) { ConsItemList *list = new ConsItemList; @@ -1853,7 +1856,7 @@ struct LoadColm list->append( init ); } - FieldInitVect *walkFieldInit( _repeat_field_init fieldInitList ) + FieldInitVect *walkFieldInit( _lrepeat_field_init fieldInitList ) { FieldInitVect *list = new FieldInitVect; @@ -2515,7 +2518,7 @@ struct LoadColm String name = structDef.id().data(); structHead( structDef.id().loc(), curNspace(), name, ObjectDef::StructType ); - _repeat_struct_item structItemList = structDef.ItemList(); + _lrepeat_struct_item structItemList = structDef.ItemList(); RepeatIter<struct_item> structItemIter( structItemList ); @@ -2606,7 +2609,7 @@ struct LoadColm } } - void walkRedItemList( _repeat_host_item itemList, ReduceTextItemList &list ) + void walkRedItemList( _lrepeat_host_item itemList, ReduceTextItemList &list ) { RepeatIter<host_item> itemIter( itemList ); @@ -2657,7 +2660,7 @@ struct LoadColm } } - void walkReductionList( _repeat_reduction_item itemList ) + void walkReductionList( _lrepeat_reduction_item itemList ) { RepeatIter<reduction_item> itemIter( itemList ); @@ -2852,7 +2855,7 @@ struct LoadColm walkLiteralList( literalDef.literal_list() ); } - void walkNamespaceItemList( _repeat_namespace_item itemList, StmtList *stmtList ) + void walkNamespaceItemList( _lrepeat_namespace_item itemList, StmtList *stmtList ) { /* Walk the list of items. */ RepeatIter<namespace_item> itemIter( itemList ); @@ -2862,7 +2865,7 @@ struct LoadColm } } - StmtList *walkRootItemList( _repeat_root_item rootItemList ) + StmtList *walkRootItemList( _lrepeat_root_item rootItemList ) { StmtList *stmtList = new StmtList; diff --git a/colm/loadinit.cc b/colm/loadinit.cc index 65e7e062..f5281da3 100644 --- a/colm/loadinit.cc +++ b/colm/loadinit.cc @@ -63,7 +63,7 @@ void LoadInit::walkProdElList( String defName, ProdElList *list, prod_el_list &p if ( El.OptRepeat().Star() != 0 ) repeatType = RepeatRepeat; if ( El.OptRepeat().LeftStar() != 0 ) - repeatType = RepeatLeft; + repeatType = RepeatLeftRepeat; ProdEl *prodEl = prodElName( internal, typeName, NamespaceQual::cons( curNspace() ), @@ -393,7 +393,7 @@ void LoadInit::go( long activeRealm ) } /* Walk the list of items. */ - _repeat_item ItemList = Start.ItemList(); + _lrepeat_item ItemList = Start.ItemList(); RepeatIter<item> itemIter( ItemList ); while ( !itemIter.end() ) { diff --git a/colm/parsetree.h b/colm/parsetree.h index 6981880d..f2d94226 100644 --- a/colm/parsetree.h +++ b/colm/parsetree.h @@ -2111,7 +2111,8 @@ enum RepeatType { RepeatRepeat, RepeatList, RepeatOpt, - RepeatLeft, + RepeatLeftRepeat, + RepeatLeftList, }; /* diff --git a/colm/prog.lm b/colm/prog.lm index f024228f..b04a8341 100644 --- a/colm/prog.lm +++ b/colm/prog.lm @@ -7,6 +7,13 @@ A: str = argv->pop() F: stream = open( A, 'r' ) parse P: start [ F ] +alias prod_map map<prod_list, id> +alias unique_prod map_el<prod_list, id> + +global PM: prod_map = new prod_map() +global NextId: int = 1 +global Modified: bool = false + prod_list cons_prod( SLA: prod_sublist ) { if match SLA [Left: prod_sublist BAR prod_el_list] @@ -15,13 +22,6 @@ prod_list cons_prod( SLA: prod_sublist ) return cons prod_list[ '[ ' SLA.prod_el_list ' ]' ] } -alias prod_map map<prod_list, id> -alias unique_prod map_el<prod_list, id> - -global PM: prod_map = new prod_map() -global NextId: int = 1 -global Modified: bool = false - cfl_def rewrite_cfl_def( CflDef: ref<cfl_def> ) { NewDef: cfl_def @@ -78,7 +78,6 @@ void rewrite( P: ref<start> ) if P { while ( rewrite( P ) ) {} - #print "final:\n[P] } ColmTree = P diff --git a/colm/resolve.cc b/colm/resolve.cc index a8c3df2a..8c8e853e 100644 --- a/colm/resolve.cc +++ b/colm/resolve.cc @@ -361,25 +361,32 @@ void TypeRef::resolveRepeat( Compiler *pd ) LangEl *declLangEl = 0; switch ( repeatType ) { - case RepeatLeft: { + case RepeatRepeat: { /* If the factor is a repeat, create the repeat element and link the * factor to it. */ String repeatName( 128, "_repeat_%s", typeName.data ); - declLangEl = pd->makeRepeatProd( loc, nspace, repeatName, uniqueType, true ); + declLangEl = pd->makeRepeatProd( loc, nspace, repeatName, uniqueType, false ); break; } - case RepeatRepeat: { + case RepeatLeftRepeat: { /* If the factor is a repeat, create the repeat element and link the * factor to it. */ - String repeatName( 128, "_repeat_%s", typeName.data ); - declLangEl = pd->makeRepeatProd( loc, nspace, repeatName, uniqueType, false ); + String repeatName( 128, "_lrepeat_%s", typeName.data ); + declLangEl = pd->makeRepeatProd( loc, nspace, repeatName, uniqueType, true ); break; } case RepeatList: { /* If the factor is a repeat, create the repeat element and link the * factor to it. */ String listName( 128, "_list_%s", typeName.data ); - declLangEl = pd->makeListProd( loc, nspace, listName, uniqueType ); + declLangEl = pd->makeListProd( loc, nspace, listName, uniqueType, false ); + break; + } + case RepeatLeftList: { + /* If the factor is a repeat, create the repeat element and link the + * factor to it. */ + String repeatName( 128, "_llist_%s", typeName.data ); + declLangEl = pd->makeListProd( loc, nspace, repeatName, uniqueType, true ); break; } case RepeatOpt: { @@ -389,7 +396,6 @@ void TypeRef::resolveRepeat( Compiler *pd ) declLangEl = pd->makeOptProd( loc, nspace, optName, uniqueType ); break; } - case RepeatNone: break; } |