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

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

本文介绍了一种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.