グラフ構造スタック

コンピュータサイエンスにおいて、グラフ構造スタック（GSS）は、有向非巡回グラフであり、各有向パスはスタックを表す。グラフ構造スタックは富田アルゴリズムの重要な部分であり、プッシュダウンオートマトンにおける通常のスタックを置き換える。これにより、アルゴリズムは曖昧な文法を解析する際の非決定的な選択を符号化することができ、場合によってはより効率的に解析できる。

次の図には、{7,3,1,0}、{7,4,1,0}、{7,5,2,0}、{8,6,2,0} の 4 つのスタックがあります。

非決定性をシミュレートする別の方法は、必要に応じてスタックを複製することです。頂点が共有されないため、複製の効率は低くなります。この例では、9つの頂点ではなく16つの頂点が必要になります。

オペレーション

GSSnode * GSS::add ( GSSnode * prev , int elem ) { int prevlevel = prev -> level ; assert ( levels.size () >= prevlevel + 1 ); int level = prevlevel + 1 ; if ( levels.size ( ) == level ) { levels.resize ( level + 1 ) ; } GSSnode * node = findElemAtLevel ( level , elem ); if ( node == nullptr ) { node = new GSSnode (); node - > elem = elem ; node -> level = level ; levels [ level ] .push_back ( node ) ; } node - > add ( prev ) ; return node ; }    

	   
	    
	     
	   
	
		  
	
	    
	   
	
		   
		  
		  		
		
	
	
	 

void GSS::remove ( GSSnode * node ) { if ( levels.size ( ) > node- > level + 1 ) if ( findPrevAtLevel ( node- > level + 1 , node )) throw Exception ( "上からのみ削除できます。" ); for ( int i = 0 ; i < levels [ node- > level ] .size (); i ++ ) if ( levels [ node- > level ][ i ] == node ) { levels [ node- > level ] .erase ( levels [ node- > level ] .begin () + i ); break ; }ノードを削除; }  

	     
		      
	        
		   
		
			  
			
		
	 

参考文献

• 富田勝.グラフ構造スタックと自然言語解析. 計算言語学会年次大会, 1988. [1]
• エリザベス スコット、エイドリアン ジョンストンGLL 解析gll.pdf