Graph-Structured Stack

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

หลักการ.

 

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

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

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

 

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

หลักการสำคัญ 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)

1. https://tornxero.wordpress.com/2011/02/13/graph-structured-stack/
2. https://smerity.com/articles/2011/gss.html