一般上下文无关文法的一个分析算法

CORC > 北京大学 > 计算机科学技术研究所

	一般上下文无关文法的一个分析算法
	潘培琛
刊名	北京大学学报自然科学版
	1989
关键词	上下文无关文法语法分析算法设计与分析
英文摘要	本文给出一般上下文无关文法的一个分析算法。该算法可以看成是LR分析算法的推广,它既是自底向上,又是从左到右。理论分析表明本算法对一般文法具有时间界O(n~3)这里n是输入句子的长度);对有界歧义文法时间界为O(n~2),而对LR文法时间界为O(n)。由于本算法是先将文法转换成分析表,然后用分析表来指导对句子的分析。因而在实际应用中本算法一般要比Earley算法快,另外本算法输出中包含输入句子的所有可能的分析,并且仅需一简单枚举就可从此输出中找出句子的一个分析。; 中国科学引文数据库(CSCD); 0; 05; 615-625
语种	中文
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/161941]
专题	计算机科学技术研究所
推荐引用方式 GB/T 7714	潘培琛. 一般上下文无关文法的一个分析算法[J]. 北京大学学报自然科学版,1989.
APA	潘培琛.(1989).一般上下文无关文法的一个分析算法.北京大学学报自然科学版.
MLA	潘培琛."一般上下文无关文法的一个分析算法".北京大学学报自然科学版 (1989).