图文法综述

形式语言理论对计算机科学的发展起了重大的作用，作为对传统字符文法扩展的图文法的形式化研究，其重要意义是不言而喻的。本文在概述图文法的产生、发展和现状的基础上，着重介绍了从一维字符文法扩展到二维图文法所出现的新问题，以及在形式化处理上引出的新方法，其中最主要的是嵌入问题的解决、文法类型的划分和成员问题的判定。文中以目前较为流行的图文法为例，特别是一些典型的上下文无关和上下文相关的图文法，对上述的问题进行了深入的讨论，指出了现有方法中的一些不足之处，并展望了图文法今后值得研究的问题和方向。