Graph-Structured Stack
![]() | ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
Graph-structured stack เป็นการฟกราฟระบุทิศทาง ที่ไม่มี Loop ชนิดหนึ่งโดยทิศทางของกราฟจะเป็นตัวบ่งบอกถึงลำดับตาม stack ( directed acyclic graph) แนวคิดนี้เป็นส่วนประกอบหลักของ “Parallel Parser” หรือ อีกชื่อหนึ่ง GLR Parser Algorithm ซึ่งถูกคิดค้นโดย มาซารุ โทมิตะ(Masaru Tomita) ในปีปี ค.ศ. 1984
หลักการ.
[แก้]![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/77/Graph-structured_stack_-_Borneq.png/219px-Graph-structured_stack_-_Borneq.png)
Graph-structured Stack สามารถกำจัดความซ้ำซ้อนในการดำเนินการ ของกระบวนการเชิงไม่กำหนด (nondeterministic processing) ทำให้สามารถจัดการกับกระบวนการแบบ nondeterministic processing ได้ และในอีกหลายๆกรณียังเป็นการเพิ่มประสิทธิภาพให้การทำงาน
โดยการใช้งานส่วนใหญ่ Graph-structured Stack มักจะถูกใช้ในการพัฒนา Compiler เพื่อให้ทำการแปลงภาษาธรรมชาติสู่คอมพิวเตอร์ (Natural Language Parsing) หรือก็คือการทำให้คอมพิวเตอร์สามารถทำงานได้จากภาษาที่เหมือนกับภาษาธรรมชาติของมนุษย์
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/73/Stacks_-_Borneq.dot.png/220px-Stacks_-_Borneq.dot.png)
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)