关于有限状态文法推断的实用算法

针对目前句法结构模式识别中的一个难题——文法推断进行较深入研究.分析了有限状态文法推断的一些方法.给出有限状态文法推断的一个实用算法.此算法对一般字符串文法都能适用.     

LL(1)文法及其分析算法的构造

本文讨论自由上下文文法(CFG)的子类——LL(1)文法。LL(1)文法是编译技术中广泛使用的递归下降法的形式化描述,并且构造LL~#(1)文法分析算法的思想方法和某些结果可用于构造目前国内外较为重视的SLR(1)文法和LR(1)文法的分析算法。所以讨论LL(1)文法,无论在理论上还是在实践上都有其必要性。本文得到[1]的启发,而在结果的表述上进一步使之精确和形式化。本文的主要结果是:确切地给出了自由上下文文法(以下简称文法)是LL(1)文法的充分必要条件;给出了LL(1)文法分析算法的产生式语言(PL)表示;并进一步给出了这种     

算法与一类等价文法的制约关系

存在着一类文法,虽然它们接受的是相同的语言,但却不能被算符优先分析算法所识别。针对问题产生的原因提出改进方法,该方法要求对文法中的产生式顺序加以限制,即文法除了必需满足算符文法的既定条件以外,还应保持文法中各产生式左部的文法变量必需是可区分的。     

算法与一类等价文法的制约关系

存在着一类文法,虽然它们接受的是相同的语言,但却不能被算符优先分析算法所识别．针对问题产生的原因提出改进方法,该方法要求对文法中的产生式顺序加以限制,即文法除了必需满足算符文法的既定条件以外,还应保持文法中各产生式左部的文法变量必需是可区分的．     

基于Earley算法的关联文法语法分析的并行处理

关联文法是上下文无关文法的扩展,是在形式规则中加入集合的交运算。该文法比上下文无关文法具有更强的生成能力。通过对该文法深入的分析,提出了一种在并行环境下基于Earley算法的语法分析和识别算法。通过实例描述了算法并行处理的过程,验证算法的可行性和正确性。     

算符优先语法分析中句型分界符的处理

算符优先语法分析过程中要处理句型分界符与文法终结符之间的优先关系，但这类优先关系不能由现有的构造算符优先表的算法直接得到。文中提出了一种方案，通过拓广算符优先文法，使句型分界符成为拓广文法的一个终结符，再对拓广文法施行构造算符优先表算法，可同时得到原文法终结符与句型分界符之间的算符优先关系。     

基于人的语言认知行为的汉语文法分析专家系统

从人的语言认知行为的角度探索了汉语文法分析方法。针对文法分析问题采用专家系统的体系结构,构造了一种基于知识的汉语文法分析系统,其核心是构造存储和管理文法知识的知识库和具有语言专家智能行为和文法分析能力的推理机。本系统的知识表达采用的是产生式规则,推理策略从自顶向下、从左到右、深度优先和回溯控制几方面进行分析,并且对语义分析进行了初步的探讨。最后给出了系统的运行实例。     

KMP算法在正则文法中的应用

本文应用KMP算法解决一类“不含莫字符串系列”正则文法。通过KMP算法的匹配思想,自动生成等价于自动机状态集最小化的正则文法（包括左线性文法、右线性文法和混合线性文法）,解决该类正则文法自动生成的技术,使编译程序设计增添一个新的技术手段。     

利用基本文法改写模式解决语法分析冲突

分析了LALR(1)分析器生成系统中语法分析冲突问题的起因和解决冲突的时机及策略,提出改写文法应遵循的4条规则,将常用的文法改写技巧总结为7个基本的文法改写模式。应用案例表明,提出的文法改写规则和基本文法改写模式可有效解决语法分析冲突。     

基于词性标记文法的文本信息隐藏算法

提出了以词性标记文法语言为变换域的文本信息隐藏方法。根据自然语言语法规则构造自由上下文文法,文法的句子是用词性标记符表示的句型;利用模拟函数将秘密信息变换为文法的句子;载体文本用分词与词性标记软件也变换为同一文法的句子;运用字符串匹配技术计算秘密信息句子在载体文本中的位置,位置即为密钥;接收方根据密钥提取文法的句子,再通过语法分析读出秘密信息;给出了信息隐藏容量公式。该算法不改变载体文本,能较好地解决Wayner的载体文本生成技术面临的载体文本合语法但不合语义的问题。     

一类LR(k)文法

本文定义了LR(k)文法的一个新的子集,称为KLR(k)文法;同时给出了构造KLR(k)分扩表的一个算法。KLR(k)文法包含LALR(k)文法作为它的真子集,但KLR(k)分析程序的状态数与LALR(k)分析程序的状态数一样多。此外,在本文中也给出了LR(k)和LALR(k)文法的一个新的判别条件。     

用布尔矩阵求解算符优先表算法的改进

算符文法的算符优先表可以用布尔矩阵理论求解，传统的算法在文法的全部符号集合上定义各类关系，导致布尔矩阵规模较大。对算法进行了改进，将文法符号划分为终结符集合与非终结符集合2个子集，在子集之间定义关系，可降低布尔矩阵规模，提高运算效率。     

链接文法及其应用

链接文法是一种分析自然语言句子的计算机可读文法,词汇的连接要求用连接因子表示.对于一个句子,若存在一条链能把所有的词汇连接起来则是合法的,否则是非法的.链接文法不仅可以用来分析英语句子,也可以用来分析汉语句子.     

基于内外概率算法的音乐节奏自动生成

针对计算机音乐领域中音乐自动生成问题,提出了一种将音乐关系的基本元素分开进行建模、分析、生成、融合的研究方法.基于音乐节奏本身具有可被形式化的特性,定义了一个概率上下文无关文法（PCFG）系统来描述相对独立的音乐节奏元素.该系统对实际音乐作品进行分析学习,将音乐节奏转化为形式化的文法语句.采用内外概率算法得到文法系统每条文法语句被使用的概率值,利用PCFG指导计算机生成新的音乐节奏,并构建了音乐节奏自动生成的原型系统.结果表明,该方法生成的音乐节奏与被分析的音乐节奏类似.     

基于上下文无关文法的数据抽取规则

在对文本数据文件的数据结构深入分析的基础上,提出了利用上下文无关文法表示数据抽取的规则,指明可以利用XML语言的特点,实现文本数据文件结构的表示文法,解决了文本数据ETL技术中涉及的重要问题,即复杂数据表示问题。     

基于文法产生式优化的设计模式识别方法

以精确的设计模式检测结果为目标,为解决设计模式识别的变体问题,提出一种基于文法产生式优化的设计模式识别方法,旨在使用可视化文法产生式描述设计模式参与者角色的属性与联系,并通过增加文法产生式描述的特征信息来识别重叠的设计模式及参与者角色间的附加关系。实验结果表明,该方法减少了设计模式识别的假阳性结果与假阴性结果,通过与主流方法的F-score评估指标比较,显示出该方法的优势。     

《新著国语文法》析句方法述评

以黎锦熙的<新著国语文法>及其开创的句本位语法体系中的析句方法(中心词分析法)为研究对象,简介<新著国语文法>析句方法的研究概况,并探讨中心词分析法的特点及其在当代的研究价值和意义,认为<新著国语文法>形成了完整的现代汉语语法体系,是现代汉语语法学的开创力作.     

LL(1)文法与亚LL(1)文法

本文在LL(1)文法的基础上,提出适应性更广的亚LL(1)文法,得到了LL(1)与亚LL(1)之间的一些关系.     

正规集的若干性质

正规集是对许多语言理论起核心作用的一类语言，研究正规集的性质有助于有限态文法的文法推断和句法分析的研究以及正规集的自动识别。在文献［１］的基础上对正视集的一些重要性质进行了详细讨论，完善了正规集的理论。     

二元属性文法及汉语的句法规则体系

本文在全面分析汉语语言特点的基础上,采用了二元属性文法作为描述形式用于汉语的计算机处理。对汉语短语句法规则进行符号化形式化的分析,给出了句法模型,定义了一整套汉语的句法规则体系及相应的语义处理方案。该文法体系已成功应用于本人设计的汉语句法分析器中。