SC文法功能体系

文法体系的研究一直是自然语言处理研究的核心问题之一.但是,由于自然语言本身所固有的复杂性和非规范性,多义问题始终未能得到圆满的解决.本文提出了SC文法(A SubCategory grammar for integrating Se-mantic and Case analysis),它是一种基于传统的上下文无关文法、语义文法,以及超前与反馈分析技术和格框架约束分析等技术的上下文相关处理文法.该文法不仅能继承传统的上下文无关文法的表示简洁、处理方便的特点,而且能实现语法和语义一体化分析和处理上下文相关以及复杂多义问题.     

一个上下文无关文法获取过程的设计和实现*

文章介绍一个基于复用的上下文无关文法获取过程的设计和实现,该过程用于获取以上下文无关文法表示的概念.它从待获取概念的有限实例和句型以及可能复用的已知概念出发,通过一个交互式文法推断过程,最终得到概念的文法定义.     

一个支持规约获取的形式规约语言

该文介绍了形式规约语言LFC设计的一些主要方面，并通过例子说明了LFC的一些特色。形式规约语言LFC是为支持软件形式规约的获取工作而开发的。该语言以一种新的递归函数，即定义在上下文无关语言上的递归函数为基础，以上下文无关语言为数据类型，在语言级支持规约获取。LFC语言已被用作形式规约获取系统SAQ的一部分。使用表明，LFC是一个能力强、易使用的语言，适合软件形式规约获取之用，并且适合其它一些用途。     

Agent、目标与情景结合的需求方法

本文以面向Agent的软件工程技术研究为核心,提出了一种Agent、目标与情景结合的需求分析方法。该方法以用类自然语言SSDL撰写的一组情景实例为输入,其中每个情景实例均包含参与交互的外部参与者和系统内部提供相应服务的Agent的信息,表明实例要达成的业务目标。根据这些情景实例进行文法的归纳学习,学习的结果是系统的形式需求规约—一种带属性的上下文无关文法,称为系统情景文法。最后,将系统情景文法转化为用Agent-Z语言描述的Agent系统需求模型。     

序言

形式语言的研究是计算机科学的一个重要领域。形式语言大约在1956年左右问世。那时Noam Chomsky给出一种文法的数学模型,这种文法与当时他所研究的自然语言有关。不久当程序设计语言ALGOL的语法由前后文无关文法定义时,便发现了,文法的概念对程序员是非常重要的。这样的研究自然会导致面向语法编译,并产生编译程序之编译程序的概念。自那以后的研究工作相当高涨,其结果致使形式语言和自动机理论之间的关系达到彼此不可分离的程度。时至     

文法推断研究的历史和现状

文法推断属于形式语言的归纳学习问题,它研究如何从语言的有限信息出发,通过归纳推断得到语言的语法定义.文章综述文法推断研究的历史和现状.首先阐述文法推断的理论模型,接着罗列上下文无关文法类及其非平凡子类、隐马尔可夫模型以及随机上下文无关文法的推断方法,最后简介文法推断的应用,并展望其发展趋势.     

前后文无关文法

4.1 前后文无关文法的简化 在本章,我们描述前后文无关文法的某些基本简化并证明几个重要的范式定理。其中一个是Chomsky范式定理,它说明每一个前后文无关语言都由这种文法产生,其中所有生成式的形式都是A→BC或A→b。+这里,A,B和C都是变量,而b是终极符。 另一个是Greibach范式定理,它说明每一个前后文无关语言都由这种文法产生,其中     

分布式操作系统形式化生成系统模型的研究

分布式操作系统形式化系统模型ＤＯＳＦＳ主要由文法ＤＯＳＦＳＧ和语义ＤＯＳＦＳＳ两部分组成。其中文法部分采用了上下文无关文法，语义部分则是一个带操作集的语义系统。ＤＯＳＦＳ按照抽象、描述、细化三个过程自动模拟生成分布式操作系统。本文主要介绍了文法ＤＯＳＦＳＧ的定义、性质，语义系统ＤＯＳＦＳＳ的设计思想、相关的数据结构、操作及其定义等。     

数据结构图的语法

本文给出了一种数据结构图语法的描述方法。数据结构图的抽象结构是一片有序森林。我们首先使用上下文无关文法描述了有序森林的语法，然后以此为基础，描述了每一种数据类型的具体图形表示的语法。     

逻辑程序的实现策略(二)

六、算法的时间复杂性 算法1是严格按Horn子句和上下文无关文法的对应关系用Earley思想设计的。一般来说,Horn子句对应了上下文无关文法的所有可能性,它可能对应无穹界多义文法,有界多义文法,两义文法,非两义文法及在限状态上下文无关文法。正因为Earley算法是极为通用的上下文无关文法,它对任一种上下文无关文法都可求解。所以算法1的功能对所有Horn子句系统亦是通用的,只不过是对不同类型的Horn子句系统,对不同的问题,其算法复杂性是不同的。     

LL(k)-PARSING OF COUPLED-CONTEXT-FREE GRAMMARS

Coupled-context-free grammars are a natural generalization of context-free grammars obtained by combining nonterminals to corresponding parentheses which can only be substituted simultaneously. Refering to the generative capacity of the grammars we obtain an infinite hierarchy of languages that comprises the context-free languages as the first and all the languages generated by TAGs as the second element. Here, we present a generalization of the context-free LL(k) -notion onto coupled-context-free grammars, which leads to a characterization of subclasses of coupled-context-free grammars–and in this way of TAGs as well–which can be parsed in linear time. The parsing procedure described works incrementally so that it can be used for on-line parsing of natural language. Examples show that important elements of the tree-adjoining languages can be generated by LL(k )-coupled-context-free grammars.     

Generalised Stream X-Machines and Cooperating Distributed Grammar Systems

Stream X-machines are a general and powerful computational model. By coupling the control structure of a stream X-machine with a set of formal grammars a new machine called a generalised stream X-machine with underlying distributed grammars, acting as a translator, is obtained. By introducing this new mechanism a hierarchy of computational models is provided. If the grammars are of a particular class, say regular or context-free, then finite sets are translated into finite sets, when ?k, = k derivation strategies are used, and regular or context-free sets, respectively, are obtained for ?k, * and terminal derivation strategies. In both cases, regular or context-free grammars, the regular sets are translated into non-context-free languages. Moreover, any language accepted by a Turing machine may be written as a translation of a regular set performed by a generalised stream X-machine with underlying distributed grammars based on context-free rules, under = k derivation strategy. On the other hand the languages generated by some classes of cooperating distributed grammar systems may be obtained as images of regular sets through some X-machines with underlying distributed grammars. Other relations of the families of languages computed by generalised stream X-machines with the families of languages generated by cooperating distributed grammar systems are established. At the end, an example dealing with the specification of a scanner system illustrates the use of the introduced mechanism as a formal specification model. Received September 1999 / Accepted in revised form October 2000     

Hierarchical structures and complexities of parallel isometric languages

The relationship between parallel isometric array languages and sequential isometric array languages is examined. Their hierarchical structures are investigated and a hierarchy is established by introducing parallel context-free array languages (PCFAL), derivation bounded array languages (DBAL), linear array languages (LAL), and extended regular afray languages (ERAL). It is interesting to find that some fundamental aspects that hold in one-dimensional string languages do not hold in their two-dimensional counterparts. Some parsing techniques are also explored. It is shown that while parallel parsing grammars may be simpler to write and parallel processing usually takes less time than sequential ones, the nature of parallel parsing is very complicated. Finally, several future research topics concerned with parallel isometric array languages including their complexities, hierarchical structures, and application to pattern recognition are discussed.     

Resolution of ambiguity in parsing

Summary The use of context-free grammars to define the syntax of programming languages is complicated by the phenomenon of ambiguity. Ambiguity can be resolved by the specification of a unique canonical parse. A set of rules is given which defines a canonical bottom-up parse, and these rules are implemented in a left-to-right bottom-up parsing algorithm. A second set of rules is given which defines a canonical top-down parse, and these rules are similarly implemented in a left-to-right top-down parsing algorithm.     

An LR parsing technique for extended context-free grammars

Extended context-free grammars allow regular expressions to appear in productions right hand sides, and are a clear and natural way to describe the syntax of programming languages.In this paper an LR parsing technique for extended context-free grammars is presented, which is based on an underlying transformation of the grammar into an equivalent context-free one.The technique is suitable for inclusion in one-pass compilers: the implementation requires little extensions to the algorithms working for normal LR grammars. Besides describing the parsing method, the paper shows also the algorithms for deriving the parsing tables; tables optimization is also discussed. Finally, this technique is compared with other proposals appeared in the literature.     

Tree controlled grammars

Languages are studied which can be generated by context-free grammars under a single simple restriction which must be satisfied by its derivation trees. Using tree controlled grammars (TC grammars for short) all unambigous and some inherently ambigous context-free languages, and also some non context-free languages can be parsed in timeO(n ²). The classes of regular, linear, context-free, EOL, ETOL and type 0 languages can be characterized in a natural manner using TC grammars. A context-free generator for all type 0 languages is exhibited. Some normal forms for TC grammars are established but it is shown that many common normal forms (e. g. Greibach normal form) cannot be obtained for TC grammars in general.     

Dynamic LL(k) parsing

A new class of context-free grammars, called dynamic context-free grammars, is introduced. These grammars have the ability to change the set of production rules dynamically during the derivation of some terminal string. The notion of LL() parsing is adapted to this grammar model. We show that dynamic LL() parsers are as powerful as LR() parsers, i.e. that they are capable to analyze every deterministic context-free language while using only one symbol of lookahead. Received: 24 August 1994 / 5 January 1996     

The parsing problem for affix grammars

Summary Affix grammars are an extension of context-free grammars which retain most of their advantages and eliminate most of their limitations with respect to the definition of programming languages and the specification of their translators. The extension allows definition of context-sensitive syntax features, and also allows semantics to be linked to syntax. In this paper, the parsing problem for affix grammars is explored and shown to be closely related to the parsing problem for context-free grammars. This enables a standard context-free parser constructor to be generalised to a constructor for affix grammars, essentially by addition of a preprocessor. The resulting constructors are compared with previously implemented or proposed constructors.     

Time-bounded controlled bidirectional grammars

We study regularly controlled bidirectional (RCB) grammars from the viewpoint of time-bounded grammars. RCB-grammars are context-free grammars of which the rules can be used in a productive and in a reductive fashion, while the application of these rules is controlled by a regular language. Several modes of derivation can be distinguished for this kind of grammar. A time bound on such a grammar is a measure of its derivational complexity. For some families of time bounds and for some modes of derivation we establish closure properties and a normal form theorem. In addition parsing algorithms are given for some modes of derivation. We conclude with considering generalizations with respect to the family of control languages and the family of bounding functions..     

Learning context-free grammars using tabular representations

We present a novel algorithm using new hypothesis representations for learning context-free grammars from a finite set of positive and negative examples. We propose an efficient hypothesis representation method which consists of a table-like data structure similar to the parse table used in efficient parsing algorithms for context-free grammars such as Cocke-Younger-Kasami algorithm. By employing this representation method, the problem of learning context-free grammars from examples can be reduced to the problem of partitioning the set of nonterminals. We use genetic algorithms for solving this partitioning problem. Further, we incorporate partially structured examples to improve the efficiency of our learning algorithm, where a structured example is represented by a string with some parentheses inserted to indicate the shape of the derivation tree of the unknown grammar. We demonstrate some experimental results using these algorithms and theoretically analyse the completeness of the search space using the tabular method for context-free grammars.