基于PRAM模型的CFGs并行识别与语法分析的扩充算法  

Expanded Algorithms of Parallel Context-free Recognition and Parsing on a PRAM Model

作　　者：孙玉强[1] 周蕾[2] 刘三阳[1] 王洪元[3] 张英丽[3] 

机构地区：[1]西安电子科技大学理学院,西安710071 [2]郑州经济管理干部学院计算机系,郑州450052 [3]江苏工业学院计算机系,常州213016

出　　处：《计算机科学》2005年第8期203-204,208,共3页Computer Science

基　　金：河南省基础研究(004061800);自然科学基金(021102600)和(0324220079)

摘　　要：本文介绍了一种PRAM模型上的上下文无关文法的并行识别和改进的并行语法分析方法——金字塔结构,并对该方法进行了修改和补充,使其对非Chomsky规范形式,即文法的产生式右部候选式(即规则)有两个以上的非终结符连接的,或者候选式中既有非终结符,又有终结符的情况,扩充的算法也能识别和分析。In this paper a method of parallel context-free recognition and parsing on a PRAM model is presented, which structure is pyramid. And it is revised and mended, in order that this method can also be applied no matter the given grammar G is Chomsky Normal Form or not, that is, this method can also be applied to a grammar G, whose right side of each production （or rule） is consisted of more than two non-terminals or terminals mingled with non-terminals.

关 键 词：上下文无关文法 语法分析 算法 扩充 PRAM模型 语法分析方法 并行识别 非终结符 金字塔结构 规范形式 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP314[自动化与计算机技术—计算机科学与技术]