可交换上下文无关文法

本文提出了可交换上下文无关文法及其该文法产生的语言——可交换上下文无关语言,证明了正规语言类是可交换上下文无关语言类的一个子集,而可交换上下文无关语言类是上下文无关语言类的一个子集;讨论了可交换上下文无关语言的结构特点,并给出了可交换上下文无关语言的Pumping引理。     

上下文无关语言的可重复序列及其性质

通过分析下推自动机的运行规律和特点,提出上下文无关语言的可重复序列的概念,将其划分为平衡重复序列、增重复序列、减重复序列三类;研究了这三类可重复序列在下推自动机的状态转换图中的结构表现和性质,通过分析下推自动机状态转换图中标注回路与可重复序列之间的关系,给出求解可重复序列的计算方法;证明了不同类型的可重复序列对上下文无关语言性质的影响,利用可重复序列揭示了上下文无关语言的Pumping引理的本质特征,并给出正规语言判定的一个充分必要条件.     

基于上下文无关文法的可逆变换模型

可逆变换和双向变换等数据转换问题一直是近年来的研究热点,研究人员针对该问题提出了大量相关的语言和模型。但是,这些实现往往建立在一种新的计算模型上,从而导致需要花费较大的学习成本去了解计算模型。另一方面,作为语法解析的基本工具,上下文无关文法对于绝大多数程序员来说都是不陌生的。提出了一种基于上下文无关文法的计算模型,用来构造字符串上的可逆变换,并对其性质和表达能力进行了探讨。采用Scheme语言实现了该计算模型,并通过在MIPS指令集上进行汇编和反汇编开发验证了该模型。验证结果表明,该模型具有较强的表达能力,在添加小型的公共数值变换模块后,可以完整地实现MIPS指令集上的汇编和反汇编。     

上下文无关语言的同步运算及其性质

针对上下文无关语言,引入了语言的可重复序列的依赖运算和同步运算,分析了两种运算的性质、特点,给出了可重复序列的依赖表达式、同步串约束表达式;提出了同步串约束上下文无关语言,给出了该类语言的构造规则:对于字母表上的同步串约束上下文无关语言L,都是由该字母表上的一个正规语言R与该正规语言R中某些可重复序列之间的依赖约束所形成的;证明了同步串约束上下文无关语言与同步串约束表达式所描述的语言等价,且该类语言是上下文无关语言的真子集.     

量化上下文无关语言的代数性质

通过引入量化下推自动机与量化上下文无关文法的定义,研究了以两种不同方式接受语言的量化下推自动机等价性问题,证明了在可交换的双幺赋值幺半群上,量化下推自动机接受的语言与量化上下文无关文法生成的语言相同。     

一个上下文无关文法的构造定理及其在推断中的应用

递归概念可以在句子中重复派生、循环出现。对这样的句子推断时,若为递归概念的每一个派生部分引进一个递归概念来描述,将推断出多个与之有相似的产生式结构的递归概念,同时也构造出一个新文法。本文先给出新文法的形式化构造方法,证明了新文法与原文法的等价性。在文章的后部,通过实例,介绍该定理在简化复杂文法推断中的应用。     

面向上下文无关语言的信息提取模块化设计

为实现白盒测试的源文件信息提取，提出了通过Lex和Yacc对使用上下文无关文法定义的语言进行词法和语法分析，构建独立的信息提取模块的思想。在函数信息提取部分提出了块和级的概念，用语句结构和语句链表结构将函数定义信息表示出来。在类信息提取部分通过识别出类声明中的成员变量和成员函数的声明信息，建立成员链表结构；识别类声明信息，建立类结构。然后将这些结构信息存入数据库，以供后续模块使用，充分做到了模块独立性和可重用性。这样只需要设计不同的信息提取模块，就可以将目前已经实现的面向C／C＋＋语言的软件测试工具WBoxTool推广应用到其它面向上下文无关文法的语言。     

量子上下文无关文法的代数性质

提出了量子上下文无关文法（l-VCFG）的概念,并研究了其具有的代数性质;证明了量子上下文无关文法（l-VCFG）和Chomsky范式文法（l-VCNF）以及Greibach范式文法（l-VGNF）的相互等价性;详细研究了量子上下文无关语言的代数刻画以及对于正则运算的封闭性。     

一种有效的结点标号上下文无关图文法分析算法

本文讨论了上下文无关图文法的性质，并证明了图文法推导具有独立性．本文还给出了一种有效的上下文无关图文法分析算法，它具有多项式时间复杂性，并给出了算法的正确性证明．该算法已经用Ｃ语言实现．     

ω上下文无关语言和语言的附着之间的关系

文章研究了用重复集生成的ω语言和语言的附着之间的关系,指出并证明了上下文无关语言附着类是ω上下文无关语言类的真子类,正规语言附着类是ω正规语言类的真子类．作为上下文无关语言的一个真子类——线性语言的附着类是ω正规语言类的真子类.     

上下文无关Petri网语言的Pumping引理

Petri网语言可分为正规Petri网语言、上下文无关Petri网语言和Petri网语言三类,Pumping引理反映了一类语言的共性.对于正规Petri网语言类和Petri网语言类都已给出了其相应的Pumping引理,而对于上下文无关Petri网语言类的Pumping引理却一直未给出.本文通过分析上下文无关Petri网语言的结构性质,给出了上下文无关Petri网语言的Pumping引理,并且正规Petri网语言的Pumping引理是上下文无关Petri网语言的Pumping引理的一种特殊形式,而上下文无关Petri网语言的Pumping引理又是Petri网语言Pumping引理的一种特殊形式,从而完整地解决了三类Petri网语言Pumping引理以及它们之间的关系.     

基于IDA处理器模块扩充的描述语言建立

目前的IDA不能支持所有处理器模型的反汇编。为此,给出一种适用于IDA处理器模块自动生成的反汇编描述语言,为IDA处理器模块插件的扩充提供支持。该描述语言采用基于上下文无关文法的属性文法表现形式,包括对处理器存储系统的声明以及对处理器指令集的语法和语义描述。应用结果表明,该方法适用于IDA处理器模块插件的扩充。     

A note on bicoloured digraph grammar systems

The family of BDG languages with a particular yield operation is shown to be exactly the family of programmed languages.     

一种上下文无关语言语法树的存储模式及其应用

针对上下文无关语言的句子所对应的语法树G树的表示形式提出了一种关系数据库的存储形式.这种存储形式的优点是：表示形式一致;句子分析简单;语句执行速度快.这种存储形式作为一种上下文无关语言的中间语言的形式可以直接交付解释器（抽象机）执行.同时介绍基于这种表示形式的上下文无关句子的编辑器.编辑器是基于Web的交互式语法制导生成方式实现的.这种表示与存储形式被用于一种描述过程性知识的函数式语言.