ในทางวิทยาการคอมพิวเตอร์ Graph-structured stack คือ directed acyclic graph (กราฟระบุทิศทาง ที่ไม่มี Loop) ชนิดหนึ่ง โดยทิศทางของกราฟจะเป็นตัวบ่งบอกถึงลำดับตาม stack นั่นเอง , แนวคิดนี้เป็นส่วนประกอบหลักของ GLR Parser Algorithm (หรือ เรียกอีกชื่อหนึ่งว่า “Parallel Parser”) ที่นาย มาซารุ โทมิตะ(Masaru Tomita) ได้ค้นคว้าวิจัย เมื่อปี คศ.1984

โดยหลักการที่สำคัญของ Graph-structured Stack คือสามารถกำจัดความซ้ำซ้อนในการดำเนินการใดของกระบวนการเชิงไม่กำหนด (nondeterministic processing) ซึ่งนอกจากจะทำให้สามารถจัดการกับกระบวนการแบบ nondeterministic ได้แล้ว ในหลายๆกรณียังเป็นการเพิ่มประสิทธิภาพให้การทำงานอีกด้วย โดยมากแล้ว Graph-structured Stack มักจะถูกใช้ในการพัฒนา Compiler เพื่อให้ทำการแปลงภาษาธรรมชาติสู่คอมพิวเตอร์ (Natural Language Parsing) หรือก็คือการทำให้คอมพิวเตอร์สามารถทำงานได้จากภาษาที่เหมือนกับภาษาธรรมชาติของมนุษย์มากทีสุดนั่นเอง

ตัวอย่าง : จากกราฟข้างต้น จะบ่งบอกถึง stack ทั้งหมดอยู่ 4 ชุดคือ {7,3,1,0}, {7,4,1,0}, {7,5,2,0}, and {8,6,2,0} เป็นต้น


ซึ่ง หากใช้วิธีธรรมดา จะสามารถทำได้โดยการทำ stack ขึ้นมามากชุดเท่าที่ต้องใช้ ซึ่งจะสังเกตได้ว่า หากเราใช้ graph-structured เราจะมีจุดยอดเพียง 9 จุดจากวิธีปกติที่ต้องใช้ถึง 12 จุด

Graph-Structured Stack มีหลักการสำคัญอยู่ 3 แบบคือ

1. Splitting – เมื่อ stack หนึ่งๆ ต้องถูกนำออกไป(Popped/Reduced) ได้มากกว่า 1 แบบ จะทำให้ส่วน Top นั้นสามารถแตกออกได้มากกว่า 1 ตัวได้ แต่ยังคงมี Bottom เพียงตัวเดียวเท่านั้น

ตัวอย่าง: กำหนดให้ A เป็น Bottom of Stack และ E เป็น Top of Stack

หากเรากำหนดให้ stack นี้สามารถนำออกไปได้ทั้งหมด 3 วิธี ดังนี้

- F <-- D E

- G <--  D E

- H <-- C D E

หลังจากทำการลดรูปตามเงื่อนไขดังกล่าวแล้ว เราจะได้ Stack เป็นดังนี้

2.Combining – เมื่อต้องการจะเพิ่ม(pushed / Shifted ) สมาชิกตัวใด ลงใน stack มากกว่าหนึ่ง stack เราสามารถทำได้โดยการรวม Top of Stack ทั้งสามเข้าไว้ด้วยกันได้

ตัวอย่าง: จากตัวอย่างในข้อที่ 1 หากเราต้องการเพิ่มสมาชิก “I” เข้าไปใน Stack ที่ มี Top เป็น F,G ,H เราจะได้รูปแบบ Stack ดังนี้

3.Local Ambiguity Packing – ถ้าหาก กิ่งย่อย หรือ เส้นทางใดๆของ Stack มีลักษณะที่เหมือนกัน เราจะสามารถรวมเส้นทางเหล่านั้นเป็น เส้นทางเดียวได้(merged and treated as a single branch)

ตัวอย่าง: จากตัวอย่างที่ผ่านมา หากเรากำหนดให้

- J  <-- F I

- J  <-- G I    จะทำให้เราได้รูปแบบของ Stack เป็นดังนี้

_______________________________________________________________________________________
References:
-                    http://en.wikipedia.org/wiki/Graph-structured_stack

-                    http://en.wikipedia.org/wiki/Directed_acyclic_graph

-                    http://en.wikipedia.org/wiki/GLR_parser

-                    http://en.wikipedia.org/wiki/Nondeterministic_algorithm

-                    http://en.wikipedia.org/wiki/LR_parser

-                    http://en.wikipedia.org/wiki/Ambiguous_grammars

-                    ftp://ftp.cs.brown.edu

-                    http://acl.ldc.upenn.edu

 

หากมีข้ิอผิดพลาดทางด้านเนื้อหาประการใด ขออภัยมา ณ ที่นี้

 

Advertisements