图文法并行归约的研究

摘要

随着计算机科学,特别是软件技术的发展,图、表等作为计算机处理的二维对象的使用更加广泛和深入。而乔姆斯基形式文法对一维对象的处理方式显然已无法满足这种需求。作为一维文法的扩展,图文法便应运而生。但在对原图进行归约的过程中,通常使用顺序的归约方式,这种方式的效率较低。本文在对图文法EGG[1]原理研究的基础上,对并行归约进行了研究,总结了归约时图柄之间的关系,并对每种情况的并行归约的条件进行了简要的分析。