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

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

改进的上下文无关文法及其语法分析

针对一些语言的实际应用情况,对标准的上下文无关文法作了改进,将标准的上下文无关文法定义中的非终结符集合和终结符集合进行细化,使得单词推导和句子推导可以使用同一个过程,即词法分析和语法分析可以在同一个语法分析过程完成.还给出了改进后文法的分析算法及算法的时间复杂度分析,证明用这种改进的方法进行语言文法定义更直观、简洁,其分析算法的时间复杂度优于标准上下文无关文法的分析算法.     

对上下文无关文法中的非终止符的相似性和等价性的判定

通过对具体文法的分析 ,定义了上下文无关文法中非终止符的相似性概念 ,提出了判定算法 ,并证明 :若两个非终止符的相似性达到一定程度 ,那么它们必定等价。利用上述结论 ,最终得到了一个判断上下文无关文法语言相同的充分性条件     

改进的上下文无关文法及其语法分析

针对一些语言的实际应用情况，对标准的上下文无关文法作了改进，将标准的上下文无关文法定义中的非终结符集合和终结符集合进行细化，使得单词推导和句子推导可以使用同一个过程，即词法分析和语法分析可以在同一个语法分析过程完成．还给出了改进后文法的分析算法及算法的时间复杂度分析，证明用这种改进的方法进行语言文法定义更直观、简洁。其分析算法的时间复杂度优于标准上下文无关文法的分析算法．     

求解复杂约束问题的基因表达式编程文法模型

基因表达式编程GEP是进化计算算法家族的新成员.GEP富有特色的个体编码能很方便地表达和解决一批NP问题. 但基本GEP难以表达和求解复杂约束. 主要工作包括:(1) 提出了GEP的上下文无关文法模型gepGram; (2) 从理论上证明了gepGram的表达能力和含单个非终结符的上下文无关文法相同; (3) 给出了gepGram文法可描述约束问题的GEP求解算法, 算法与基因长度具有线性伸缩性; (4) 实验证明了本文提出算法具有较高的效率,当基因长度为106时,解码仅需0.4 s.     

上下文无关格值词语言研究

文章在格半群意义下，提出基于词计算的上下文无关格值文法，证明由其生成的格值词语言关于并与连接运算封闭，及其与乔姆斯基范式文法等价．     

Fuzzy上下文无关文法与Fuzzy上下文无关语言的性质

Ｆｕｚｚｙ下推自动机与Ｆｕｚｚｙ上下文无关文法有紧密的关系,讨论了Ｆｕｚｚｙ上下文无关文法及其产生Ｆｕｚｚｙ上下文无关语言的一些性质。     

应用模块法杂凑语言的上下文无关文法

编译程序的编制过程中,人们首先接触是语言,而上下文无关文法是作为程序设计语言重要的语法描述工具。因此,只有将语言用上下文无关文法表示才能使用现有的技术,从而用计算机自动实现。通过应用模块法将语言进行模块化划分,并在模块内实现杂凑,能够成功地、方便地实现语言到上下文无关文法的转换。     

基于LL(1)分析表的布尔文法语法分析算法

布尔文法是针对特定的形式语言提出的一种新的描述形式,文法以上下文无关文法为基础,在形式规则中加入集合论的相关运算。传统的LL算法只能处理上下文无关文法,通过对布尔文法深入的分析,提出了一种基于LL(1)分析表的布尔文法的语法分析算法。通过实例详细描述了算法处理的过程,验证算法的可行性和正确性。     

模糊上下文无关树文法

定义了模糊上下文无关树文法(PCFTG)，讨论了其构造性质，给出其分解定理及表现定理，进而讨论了由模糊上下文无关树文法生成的语言IO(Inside-out)，模糊IO树语言的封闭性．     

一个有效的LR(K)分析机的分级构造算法及其文法的分划

本文提出了一个上下文无关文法的LR(k)分析机的分级构造算法及其文法的分划方法。并对K=1的情况进行了详细的讨论。该方法不仅适用于任何实际LR(K)文法并且较之[5]中方法更加有效。文中对算法的正确性进行了证明,同时指出由本文建立的强相容性标准是所有合并同心状态的相容性标准中最宽的一个。根据获得的结果。用本文中算法构造的LR(K)分析机中的状态个数与LALR(K)分析机中的状态个数相同或略多。     

P systems with array objects and array rewriting rules

Array P systems were introduced by Paun Gh. which is linking the two areas of membrane computing and picture grammars. Puzzle grammars were introduced by us for generating connected picture arrays in the two-dimensional plane, motivated by the problem of tiling the plane. On the other hand, incorporating into arrays the developmental type of generation used in the well-known biologically motivated L systems, Siromoney and Siromoney proposed a very general rectangular array generating model, called extended controlled tabled L array system (ECTLAS). In this paper we introduce two variations of the array P system, called BPG array P system and parallel array P system. The former has in the regions array objects and basic puzzle grammar rules (BPG), which are a specific kind of puzzle grammar rules. In the latter, the regions have rectangular array objects and tables of context-free rules. We examine these two types of P systems for their array generative power.     

P systems with array objects and array rewriting rules

Array P systems were introduced by Paun Gh. which is linking the two areas of membrane computing and picture grammars. Puzzle grammars were introduced by us for generating connected picture arrays in the two-dimensional plane, motivated by the problem of tiling the plane. On the other hand, incorporating into arrays the developmental type of generation used in the well-known biologically motivated L systems, Siromoney and Siromoney proposed a very general rectangular array generating model, called extended controlled tabled L array system (ECTLAS). In this paper we introduce two variations of the array P system, called BPG array P system and parallel array P system. The former has in the regions array objects and basic puzzle grammar rules (BPG), which are a specific kind of puzzle grammar rules. In the latter, the regions have rectangular array objects and tables of context-free rules. We examine these two types of P systems for their array generative power.     

一般上下文无关文法的一个分析算法

本文给出一般上下文无关文法的一个分析算法。该算法可以看成是LR分析算法的推广,它既是自底向上,又是从左到右。理论分析表明本算法对一般文法具有时间界O(n~3)这里n是输入句子的长度);对有界歧义文法时间界为O(n~2),而对LR文法时间界为O(n)。由于本算法是先将文法转换成分析表,然后用分析表来指导对句子的分析。因而在实际应用中本算法一般要比Earley算法快,另外本算法输出中包含输入句子的所有可能的分析,并且仅需一简单枚举就可从此输出中找出句子的一个分析。     

Machine Translation Using Constraint-Based Synchronous Grammar

Introduction In machine translation,analysis of the structural devia-tions of the languages pairs is key to transforming one language into another.This analysis requires a large number of structural transformations,both grammati-cally and conceptually.The…