连接文法在并行环境下的语法分析和识别

连接文法是上下文无关文法的扩展,是在形式规则中加入集合的交运算.连接文法比上下文无关文法具有更强的生成能力.通过对连接文法深入的分析,提出了一种在并行环境下的语法分析和识别算法,算法事实是以上下文无关文法并行识别算法为基础提出的.最后以实例详细描述了算法并行处理过程并验证其算法的可行性.     

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

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

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

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

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

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

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

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

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

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

关于上下文无关文法的相伴语言

为研究上下文无关语言,在文讨论了上下文无关文法的相伴语言的结构,获得了上下文无关文法具同型相伴语言的结果,并且给出了后者的一种无歧义性的Greibach文法实现。从而顺便得到,正则文法具正则相伴语言的事实,以及它的一种无歧义性的正则文法实现。     

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

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

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

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

基于完备剩余格值逻辑的下推自动机与上下文无关文法

引入了L-值下推自动机的概念,讨论了L-值下推自动机按2种不同方式所接受的语言类的等价性,并指出了它能识别L-值正则语言。利用广义的子集构造方法,证明了一般的L-值下推自动机与状态转移为分明函数且具有L-值终态的L-值下推自动机的等价性。通过此等价性,给出了L-值上下文无关语言的代数刻画和层次刻画,并证明了L-值上下文无关语言关于正则运算的封闭性。另外,提出了L-值上下文无关文法的概念,给出了与之等价的且带有经典开始符的L-值上下文无关文法。借此等价关系,讨论了L-值下推自动机与L-值上下文无关文法是等价的,并说明了在完备剩余格值逻辑意义下,可采用最左派生、最右派生、Chomsky范式或者Greibach范式中的任何一种来生成L-值上下文无关语言。     

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

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

模糊上下文无关树文法

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

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…     

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

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

编译器前端构造工具及JLUCC的实现

针对多种典型的编译器构造工具存在对文法有限制、嵌入式语义动作有负面影响,目标语言单一和调试维护困难等一些问题,设计并实现了一种新的编译器构造工具--JLUCC(Jilin University Compiler Compil-er).JLUCC使用Earley分析方法,结合反射、面向对象和设计模式等技术,具有词法分析器、语法分析器、抽象语法树和遍历工具等编译器模块的自动生成功能,可以支持任意上下文无关文法、多遍处理和对目标语言的扩展.其功能强大、使用方便、便于维护和扩展,具有广阔的应用前景.展望了未来编译器构造工具的发展趋势.     

Recursive syntactic pattern learning by songbirds

Humans regularly produce new utterances that are understood by other members of the same language community. Linguistic theories account for this ability through the use of syntactic rules (or generative grammars) that describe the acceptable structure of utterances. The recursive, hierarchical embedding of language units (for example, words or phrases within shorter sentences) that is part of the ability to construct new utterances minimally requires a 'context-free' grammar that is more complex than the 'finite-state' grammars thought sufficient to specify the structure of all non-human communication signals. Recent hypotheses make the central claim that the capacity for syntactic recursion forms the computational core of a uniquely human language faculty. Here we show that European starlings (Sturnus vulgaris) accurately recognize acoustic patterns defined by a recursive, self-embedding, context-free grammar. They are also able to classify new patterns defined by the grammar and reliably exclude agrammatical patterns. Thus, the capacity to classify sequences from recursive, centre-embedded grammars is not uniquely human. This finding opens a new range of complex syntactic processing mechanisms to physiological investigation.     

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.