標題: 一種有效率的普遍式文法剖析演算法
An Efficient General Parsing Algorithm
作者: 莊正杰
Zhuang, Zheng-Jie
楊武
YANG, WU
資訊科學與工程研究所
關鍵字: 資訊;電腦;剖析演算法;非右遞迴;效率;電腦科學;INFORMATION;COMPUTER;INFORAMTION;COMPUTER-SCIENCE
公開日期: 1995
摘要: Earley的普遍式剖析演算法可以剖析所有的context-free文法,但是它需要O(nΛ2) 的時間來剖析LR(K) 文法。我們提出一種有效率的普遍式文法剖析演算法,它比 Earley的演算法還要有效率。首先,我們使用一種有效率的方法轉換context-free 文法到"非右遞迴"的文法。在這種轉換後,有很大部份的文法都可以在線性時間內剖 析完成。我們稱這一部份的文法為"Simple"文法。"Simple"文法比LR(K) 文法還大。 其它不能在線性時間內剖析完成的文法,我們稱為"RR"文法。最後我們提出"RR"文法 的型式和範例。
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT844394005
http://hdl.handle.net/11536/61204
Appears in Collections:Thesis