图文法综述

计算机科学 ›› 2008, Vol. 35 ›› Issue (8): 10-16.

图文法综述

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文工作得到国家自然科学基金（60571048、60673186）的资助.

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

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

关键词: 形式语言图文法嵌入问题文法类型成员问题

Abstract: It is well known that formal language theory plays an important role in the aevelopment of computer science,and so will be the research on two dimensional graph grammar formalisms, which is an extension of one dimensional string grammars. Based on a summa

Key words: Formal language, Graph grammar, Embedding problem, Grammar classfication, Membership problem

. 图文法综述[J]. 计算机科学, 2008, 35(8): 10-16. https://doi.org/

参考文献

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed