A.W.Bojanczyk,T.D.kimura,蒋涵民
. 1987, 13(06): 62-71.
本文考虑如何在一个二维处理机陈列上对二线视觉程序设计语言Show-Tell进行分析(Parsing)。 用Show-Tell语言书写的程序是一个位映射加bit mapped)二维模式,后者满足一组文法规则。模式由一些用直线围成的盒和一些箭头构成的半序集组成。盒和箭头分布在n×n的象素区域空间里。相应的向图称为盒图,其中盒为结点,箭头为有向边。一个Show-Tell程序对应的盒图中不应存在循环(cycle)。循环检测是分析Show-Tell程序时最耗计算的工作。 本文建议,在分析Show-Tell程序设计语言时,采用伸缩阵列的概念。给定一个位模式,可以将它映射到一个n×n的筛状连结的处理机阵列上(映射的方式是将一个象素指派给一个处理成员)。本文给出的循环检测算法的运行时间正比于盒图大小。单个处理机的复杂性正比于n,其中n是描述阵列大小的参数。