一種有效率的普遍式文法剖析演算法

標題:	一種有效率的普遍式文法剖析演算法 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