ในทางวิทยาการคอมพิวเตอร์ 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
หากมีข้ิอผิดพลาดทางด้านเนื้อหาประการใด ขออภัยมา ณ ที่นี้
TornXero's Blog 