Графикалық құрылымды стек - Graph-structured stack

Жылы есептеу техникасы, а графикалық құрылымды стек (GSS) - бұл бағытталған ациклдік график қайда бағытталды жол білдіреді стек.Графикалық құрылымды стек оның маңызды бөлігі болып табылады Томитаның алгоритмі, ол әдеттегі ауыстырады стек а басу автоматы. Бұл алгоритмге анды талдауда анықталмаған таңдауды кодтауға мүмкіндік береді анық емес грамматика, кейде үлкен тиімділікпен.

Келесі диаграммада төрт стек бар: {7,3,1,0}, {7,4,1,0}, {7,5,2,0} және {8,6,2,0} .

Graph-structured_stack _-_ Borneq.png

Нодетерминизмді имитациялаудың тағы бір тәсілі - қажет болған жағдайда стектің көшірмесін жасау. Көтеру тиімділігі төмен болар еді, өйткені шыңдар бөлісілмейді. Бұл мысал үшін 9 емес, 16 шың қажет болады.

Стектер _-_ Borneq.dot.png

Операциялар

GSSnode* GSS::қосу(GSSnode* алдыңғы, int елем){	int басым = алдыңғы->деңгей;	бекіту(деңгейлер.өлшемі() >= басым + 1);	int деңгей = басым + 1;	егер (деңгейлер.өлшемі() == деңгей)	{		деңгейлер.өлшемін өзгерту(деңгей + 1);	}	GSSnode* түйін = findElemAtLevel(деңгей, елем);	егер (түйін == nullptr)	{		түйін = жаңа GSSnode();		түйін->елем = елем;		түйін->деңгей = деңгей;				деңгейлер[деңгей].push_back(түйін);	}	түйін->қосу(алдыңғы);	қайту түйін;}
жарамсыз GSS::жою(GSSnode* түйін){	егер (деңгейлер.өлшемі() > түйін->деңгей + 1)		егер (findPrevAtLevel(түйін->деңгей + 1, түйін)) лақтыру Ерекше жағдай(«Тек жоғарыдан алып тастай алады.»);	үшін (int мен = 0; мен < деңгейлер[түйін->деңгей].өлшемі(); мен++)		егер (деңгейлер[түйін->деңгей][мен] == түйін)		{			деңгейлер[түйін->деңгей].өшіру(деңгейлер[түйін->деңгей].баста() + мен);			үзіліс;		}	жою түйін;}

Әдебиеттер тізімі

  • Масару Томита. Графикалық құрылымды стек және табиғи тілді талдау. Компьютерлік лингвистика қауымдастығының жыл сайынғы мәжілісі, 1988 ж. [1]
  • Элизабет Скотт, Адриан Джонстон GLL талдау gll.pdf