Graph-Structured Stack

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

หลักการ.#edit

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

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

[1]">หลักการสำคัญ 3 แบบ ของ Graph-Structured Stack ^[1][1]" title="Copy link to this section" aria-label="Link to this section">#edit

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)

^[2]

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