Chulalongkorn University Theses and Dissertations (Chula ETD)

A development of deterministic parser using data-directed grammar

Other Title (Parallel Title in Other Language of ETD)

การพัฒนาตัวแจงเชิงกำหนดโดยใช้ไวยากรณ์แบบกำหนดด้วยข้อมูล

Year (A.D.)

2001

Document Type

Thesis

First Advisor

Wanchai Rivepiboon

Faculty/College

Faculty of Engineering (คณะวิศวกรรมศาสตร์)

Degree Name

Master of Engineering

Degree Level

Master's Degree

Degree Discipline

Computer Engineering

DOI

10.58837/CHULA.THE.2001.1474

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 (Other language abstract of ETD)

มีแนวคิดสองแบบที่แตกต่างกันในวิธีการแจงคือ แนวคิดของการทำงานแบบบนลงล่าง (top-down) และการทำงานแบบล่างขึ้นบน (bottom-up) โดยที่แนวคิดทั้งสองได้สะท้อนถึงแนวคิดที่สำคัญสองอย่างคือ หลักการใช้เหตุผล หรือแบบกำหนดด้วยเป้าหมาย ซึ่งเน้นความรู้ที่มีอยู่ก่อน และหลักของการทดลอง ประสบการณ์ การสังเกตหรือแบบนำด้วยข้อมูลซึ่งเน้นข้อมูลเป็นหลัก โดยทั่วไปวิธีการแจงแต่ละแบบจะมีรูปแบบไวยากรณ์ของตัวเองรวมถึงข้อมูลเพิ่มเติมเพื่อช่วยในการแจง บางครั้งไวยากรณ์เหล่านั้นก็อาจจะถูกเขียนขึ้นในรูปแบบที่ก่อให้เกิดความกำกวมในการแจงทั้งที่ความจริงอาจไม่ได้ต้องการเช่นนั้น ทั้งนี้เพราะว่าไวยากรณ์เหล่านั้นไม่ได้เขียนโดยใช้รูปแบบที่ไม่กำกวมและมีความชัดเจนเพียงพอ ในวิทยานิพนธ์เล่มนี้เราได้เสนอเทคนิคการแจงเชิงกำหนดจากล่างขึ้นบนแบบใหม่ที่เรียกว่า ตัวแจงแบบนำด้วยข้อมูลซึ่งดำเนินการในความซับซ้อนของเวลาเท่ากับ O(n) และต้องการเพียงกฎไวยากรณ์ที่ถูกกำหนดขึ้นในรูปแบบไวยากรณ์แบบใหม่ที่เรียกว่า Chulalongkorn University Normal Form (CUNF) เท่านั้น CUNF ถูกพัฒนามาจาก Chomsky Normal Form (CNF) มันมีความสามารถเทียบเท่ากับไวยากรณ์ที่ไม่อิงบริบท (Centext-Free Grammar) และสามารถใช้นำเสนอไวยากรณ์จำนวนมากในรูปแบบที่ไม่กำกวมได้ ในวิทยานิพนธ์เรายังได้สาธิตวิธีการประยุกต์ใช้ CUNF กับไวยากรณ์ที่กำกวมประเภทต่างๆ รวมไปถึงการประยุกต์ใช้กับไวยากรณ์ของภาษาเอชทีเอ็มแอล รุ่น 3.2 ไว้ด้วย

Link to Full Text

Share

COinS