关联文法语法推导树的并行构造算法

通过对关联文法语法推导树的详细分析,提出了具有共享子树的语法推导树算法。该算法实现了不仅叶子节点可以共享,其中任意相同子树均可以共享,有效节省了存储空间。针对共享子树的特点,提出了并行构造共享子树的算法,并通过实例详细描述了算法并行处理过程,验证了算法的可行性和正确性。

树邻接语法

树邻接语法是一种基于树图形的形式语法,本文比较了这种语法与短语结构语法的异同,介绍了树邻接语法的基本组成要素及其操作模式,重点介绍了接插和替换两种操作,并介绍了推导关系树、树集合、串语言等概念,最后介绍树邻接语法的新发展———词汇化树邻接语法。

代数语言学与英语的歧义现象

代数语言学与英语的歧义现象白世云代数语言学是运用离散数学的大法研究语言的数学模型，从而对语言的有关现象进行严格、精确的描述，建立语言的模型理论。目前，用代数语言学建立的语言模型主要有三种，它们是生成性模型、分析性模型和识别性模型。形式文法和转换文法就...

CFL句子计数和分层词典序枚举

通过按推导树高度对句子分层,建立了句子集合中的分层词典序,进而发展出一种基于文法的,依分层词典序的,CFL句子计数和枚举方法,获得句子枚举的多个高效算法,对于无二义CFG,首先提出一个基础算法N2L,时间复杂度为O(n·lg(n)),n是被枚举句子的长度．对N2L进行改造,得到两个算法TD和BU,时间复杂度均为O(n)．对任意CFG,利用其推导树文法为工具后,文法无二义的限制被去除．对于一般的CFG,不论是否二义文法,也得到了依分层词典序的,时间复杂度为O(n)的枚举算法,同时枚举出句子及其推导树．该文的结果,从正面圆满回答了D(?)m(?)si提出的未决问题,即是否有按词典序,时间复杂度为O(n)的枚举算法?以及是否时间复杂度仅依赖于文法结构,及被枚举字之前同样长度的字的个数?本文给出的解答甚至比原问题所期望的更好．