Please use this identifier to cite or link to this item: http://cuir.car.chula.ac.th/handle/123456789/11184
Title: A development of deterministic parser using data-directed grammar
Other Titles: การพัฒนาตัวแจงเชิงกำหนดโดยใช้ไวยากรณ์แบบกำหนดด้วยข้อมูล
Authors: Meta Citsawat
Advisors: Wanchai Rivepiboon
Other author: Chulalongkorn University. Faculty of Engineering
Advisor's Email: Wanchai.R@Chula.ac.th  
Subjects: Parsing (Computer grammar)
Issue Date: 2001
Publisher: Chulalongkorn University
Abstract: There are two distinct concepts in parsing techniques; top-down and bottom-up parasigms. Both of them reflect two important insights; the rationalist tradition or goal-directed which focuses on the prior knowlege, and the empirical tradition or data-directed which focuses on the data. Generally, each parsing technique will have its own grammar formalisms including addaitional information to help in parsing. Sometimes, those grammars may have been written in the form that could case ambiguous results in parsing despite in fact, they were not intended to be. This is becasue those grammars were not written in the form which is explicity enough to avoid ambiguous resluts. In this thesis, we present a new deterministic botton-up parsing technique called data-directed parser which runs in time complexity equals to O(n). It requires only grammar rules defined in a new grammar formalism called Chulalongkorn University Normal Form (CUNF) grammars. CUNF is derived form Chomsky Normal Form (CNF). It has a generative power equals to context-free grammars, and can be used to represent a large calss of grammars in an unambiguous form. In the thesis, we have also demonstrated how to apply CUNF with various ambiguous grammars including the syntax of Hyper Text Markup Language (HTML) version 3.2.
Other Abstract: มีแนวคิดสองแบบที่แตกต่างกันในวิธีการแจงคือ แนวคิดของการทำงานแบบบนลงล่าง (top-down) และการทำงานแบบล่างขึ้นบน (bottom-up) โดยที่แนวคิดทั้งสองได้สะท้อนถึงแนวคิดที่สำคัญสองอย่างคือ หลักการใช้เหตุผล หรือแบบกำหนดด้วยเป้าหมาย ซึ่งเน้นความรู้ที่มีอยู่ก่อน และหลักของการทดลอง ประสบการณ์ การสังเกตหรือแบบนำด้วยข้อมูลซึ่งเน้นข้อมูลเป็นหลัก โดยทั่วไปวิธีการแจงแต่ละแบบจะมีรูปแบบไวยากรณ์ของตัวเองรวมถึงข้อมูลเพิ่มเติมเพื่อช่วยในการแจง บางครั้งไวยากรณ์เหล่านั้นก็อาจจะถูกเขียนขึ้นในรูปแบบที่ก่อให้เกิดความกำกวมในการแจงทั้งที่ความจริงอาจไม่ได้ต้องการเช่นนั้น ทั้งนี้เพราะว่าไวยากรณ์เหล่านั้นไม่ได้เขียนโดยใช้รูปแบบที่ไม่กำกวมและมีความชัดเจนเพียงพอ ในวิทยานิพนธ์เล่มนี้เราได้เสนอเทคนิคการแจงเชิงกำหนดจากล่างขึ้นบนแบบใหม่ที่เรียกว่า ตัวแจงแบบนำด้วยข้อมูลซึ่งดำเนินการในความซับซ้อนของเวลาเท่ากับ O(n) และต้องการเพียงกฎไวยากรณ์ที่ถูกกำหนดขึ้นในรูปแบบไวยากรณ์แบบใหม่ที่เรียกว่า Chulalongkorn University Normal Form (CUNF) เท่านั้น CUNF ถูกพัฒนามาจาก Chomsky Normal Form (CNF) มันมีความสามารถเทียบเท่ากับไวยากรณ์ที่ไม่อิงบริบท (Centext-Free Grammar) และสามารถใช้นำเสนอไวยากรณ์จำนวนมากในรูปแบบที่ไม่กำกวมได้ ในวิทยานิพนธ์เรายังได้สาธิตวิธีการประยุกต์ใช้ CUNF กับไวยากรณ์ที่กำกวมประเภทต่างๆ รวมไปถึงการประยุกต์ใช้กับไวยากรณ์ของภาษาเอชทีเอ็มแอล รุ่น 3.2 ไว้ด้วย
Description: Thesis (M.Eng.)--Chulalongkorn University, 2001
Degree Name: Master of Engineering
Degree Level: Master's Degree
Degree Discipline: Computer Engineering
URI: http://cuir.car.chula.ac.th/handle/123456789/11184
ISBN: 9740302785
Type: Thesis
Appears in Collections:Eng - Theses

Files in This Item:
File Description SizeFormat 
Meta.pdf1.55 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.