Graph-Structured Stack

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

หลักการ. 

Graph-structured Stack  สามารถกำจัดความซ้ำซ้อนในการดำเนินการ ของกระบวนการเชิงไม่กำหนด (nondeterministic processing) ทำให้สามารถจัดการกับกระบวนการแบบ nondeterministic processing ได้ และในอีกหลายๆกรณียังเป็นการเพิ่มประสิทธิภาพให้การทำงาน

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

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

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

- F <-- D E

- G <--  D E

- H <-- C D E

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

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

โครงสร้างข้อมูล