Pila estructurada en grafos

En informática , una pila estructurada en grafo (GSS, por sus siglas en inglés) es un grafo dirigido acíclico donde cada camino dirigido representa una pila . La pila estructurada en grafo es una parte esencial del algoritmo de Tomita , donde reemplaza la pila habitual de un autómata de pila . Esto permite que el algoritmo codifique las decisiones no deterministas al analizar una gramática ambigua , a veces con mayor eficiencia.

En el siguiente diagrama, hay cuatro pilas: {7,3,1,0}, {7,4,1,0}, {7,5,2,0} y {8,6,2,0}.

Otra forma de simular el no determinismo sería duplicar la pila según sea necesario. La duplicación sería menos eficiente, ya que los vértices no se compartirían. En este ejemplo, se necesitarían 16 vértices en lugar de 9.

Operaciones

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 ( " Solo se puede eliminar desde arriba." ); 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 ; } delete node ; }

Referencias

Masaru Tomita. Pila estructurada en grafos y análisis sintáctico del lenguaje natural . Reunión anual de la Asociación de Lingüística Computacional, 1988.
Elizabeth Scott, Adrian Johnstone GLL Análisis gll.pdf