An undecidable property of context-free linear orders

We prove that there exists no algorithm to decide whether the language generated by a context-free grammar is dense with respect to the lexicographic ordering. As a corollary to this result, we show that it is undecidable whether the lexicographic orderings of the languages generated by two context-free grammars have the same order type.     

Büchi context-free languages

We define context-free grammars with Büchi acceptance condition generating languages of countable words. We establish several closure properties and decidability results for the class of Büchi context-free languages generated by these grammars. We also define context-free grammars with Müller acceptance condition and show that there is a language generated by a grammar with Müller acceptance condition which is not a Büchi context-free language.     

基于量子逻辑的自动机和文法理论

初步建立了基于量子逻辑的自动机和文法理论的基本框架.引入了量子文法(称为l值文法),特别是证明了任意l值正规文法生成的语言(称为量子语言)等价于某种基于量子逻辑且含动作(的自动机(称为l值自动机)识别的语言,反之,任意l值自动机识别的语言等价于某l值正规文法生成的语言.建立了l值泵引理,并得到量子语言的判定性刻画.最后简要讨论了正规文法与量子文法(即l值正规文法)的关系.因此,为进一步研究更复杂的量子自动机(如量子下推自动机和Turing机)和量子文法(如量子上下文无关文法和上下文有关文法)奠定了基础.     

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

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

The Equivalence of Tree Adjoining Grammars and Monadic Linear Context-free Tree Grammars

The equivalence of leaf languages of tree adjoining grammars and monadic linear context-free grammars was shown about a decade ago. This paper presents a proof of the strong equivalence of these grammar formalisms. Non-strict tree adjoining grammars and monadic linear context-free grammars define the same class of tree languages. We also present a logical characterisation of this tree language class showing that a tree language is a member of this class iff it is the two-dimensional yield of an MSO-definable three-dimensional tree language.     

Parsing of edNLC-graph grammars for scene analysis

An edNLC-graph grammar, introduced by Janssens,⁽⁴⁾ is a strong formalism for generating scene representations. This grammar generates directed node- and edge-labelled graphs, EDG-graphs. A method of construction of unambiguous string EDG-graph representation is briefly described. The characteristics of edNLC-graph grammar for syntactic pattern recognition allows us to construct the parsing algorithm. The deterministic top-down syntax analyzer is constructed for the subfamily of an edNLC-graph grammar, called an ETL/1-graph grammar. An ETL/1-graph grammar is parallel to a finite state string grammar. The notions introduced in the paper are useful for researches in less restricted edNLC-graph grammars, for example grammars analogical to context-free string grammars.     

The language intersection problem for non-recursive context-free grammars

We prove that, given as input two context-free grammars, deciding non-emptiness of intersection of the two generated languages is PSPACE-complete if at least one grammar is non-recursive. The problem remains PSPACE-complete when both grammars are non-recursive and deterministic. Also investigated are generalizations of the problem to several context-free grammars, of which a certain number are non-recursive.     

On the structure of context-sensitive grammars

It is well known that the family of context-sensitive grammars generate languages which are not context-free and that it is undecidable whether a context-sensitive grammar generates a context-free language. However, the mechanism by which the use of context allows a non-context-free language to be generated is not well understood. In this paper we attempt to focus on this problem by surveying some of the results which speak to two questions: (i) What constraints can be placed on the form of the rules of context-sensitive grammars without restricting the weak generative capacity? (ii) What (nontrivial) constraints can be placed on the form of the rules of context-sensitive grammars such that only context-free languages will be generated?     

Closure properties of linear context-free tree languages with an application to optimality theory

Context-free tree grammars, originally introduced by Rounds [Math. Systems Theory 4(3) (1970) 257–287], are powerful grammar devices for the definition of tree languages. The properties of the class of context-free tree languages have been studied for more than three decades now. Particularly important here is the work by Engelfriet and Schmidt [J. Comput. System Sci. 15(3) (1977) 328–353, 16(1) (1978) 67–99]. In the present paper, we consider a subclass of the class of context-free tree languages, namely the class of linear context-free tree languages. A context-free tree grammar is linear, if no rule permits the copying of subtrees. For this class of linear context-free tree languages we show that the grammar derivation mode, which is very important for the general class of context-free tree languages, is immaterial. The main result we present is the closure of the class of linear context-free tree languages under linear frontier-to-root tree transduction mappings. Two further results are the closure of this class under linear root-to-frontier tree transduction mappings and under intersection with regular tree languages.     

Formes de langages et de grammaires

Summary This paper is devoted to the study of context-free languages over infinite alphabets. This work can be viewed as a new attempt to study families of grammars, replacing the usual grammar forms and giving a new point of view on these questions. A language over an infinite alphabet or I-language appears as being a model for a family of usual languages; an interpretation is an homomorphism from the infinite alphabet to any finite alphabet. Using this notion of interpretation we can associate to each family of I-languages an image, called its shadow, which is a family of usual languages.The closure properties of families, generalizing to infinite alphabets the family of context-free languages, lead to define rational transductions between infinite alphabets or I-transductions, and then, families of I-languages closed under I-transductions, or I-cones. We study here relations between the closure properties of a family of I-languages and these of its shadow. As a result, we obtain that any union closed rational cone of context-free languages, principal or not, is the shadow of a principal I-cone.This work leads to new results about the classical theory of context-free languages. For instance, we prove that any principal rational cone of context-free languages can be generated by a context-free language, whose grammar has only 6 variables. This work also leads to more general considerations about the adequacy of some generating devices to the generated languages. It appears that the context-free grammars are fair, in a sense that we define, for generating context-free languages but that non-expansive context-free grammars are not for generating non-expansive context-free languages. This point of view raises a number of questions.     

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     

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.     

Analyzing ambiguity of context-free grammars

It has been known since 1962 that the ambiguity problem for context-free grammars is undecidable. Ambiguity in context-free grammars is a recurring problem in language design and parser generation, as well as in applications where grammars are used as models of real-world physical structures.We observe that there is a simple linguistic characterization of the grammar ambiguity problem, and we show how to exploit this by presenting an ambiguity analysis framework based on conservative language approximations. As a concrete example, we propose a technique based on local regular approximations and grammar unfoldings. We evaluate the analysis using grammars that occur in RNA analysis in bioinformatics, and we demonstrate that it is sufficiently precise and efficient to be practically useful.     

Grammar Engineering Support for Precedence Rule Recovery and Compatibility Checking

A wide range of parser generators are used to generate parsers for programming languages. The grammar formalisms that come with parser generators provide different approaches for defining operator precedence. Some generators (e.g. YACC) support precedence declarations, others require the grammar to be unambiguous, thus encoding the precedence rules. Even if the grammar formalism provides precedence rules, a particular grammar might not use it. The result is grammar variants implementing the same language. For the C language, the GNU Compiler uses YACC with precedence rules, the C-Transformers uses SDF without priorities, while the SDF library does use priorities. For PHP, Zend uses YACC with precedence rules, whereas PHP-front uses SDF with priority and associativity declarations.The variance between grammars raises the question if the precedence rules of one grammar are compatible with those of another. This is usually not obvious, since some languages have complex precedence rules. Also, for some parser generators the semantics of precedence rules is defined operationally, which makes it hard to reason about their effect on the defined language. We present a method and tool for comparing the precedence rules of different grammars and parser generators. Although it is undecidable whether two grammars define the same language, this tool provides support for comparing and recovering precedence rules, which is especially useful for reliable migration of a grammar from one grammar formalism to another. We evaluate our method by the application to non-trivial mainstream programming languages, such as PHP and C.     

Multipass precedence analysis

Summary This paper defines a hierarchy of languages which is properly contained in the context sensitive languages and which starts with the context free family. The hierarchy is defined inductively by controlling labeled linear grammars with languages in one family to yield languages in the next larger family. The families of the hierarchy have properties analogous to those of the context free family, in particular, the new mechanism introduced is very suitable for parsing.A language in the n-th family is specified by a sequence of n — 1 labeled linear grammars and a context free grammar. By assuming that the reversals of the first n — 1 grammars and the last labeled linear grammar are precedence grammars, the concepts and parsing algorithm of Wirth and Weber extend to yield a parsing algorithm within the hierarchy. This considerably enhances the usefulness of the construction and allows much of the power of the context sensitive languages to become accessible in measured amounts for potential programming applications.     

格值下推自动机与格值上下文无关文法

引入了格值下推自动机、格值上下文无关文法及它们的语言的概念,证明了格值下推自动机以两种不同方式接受的语言类的等价性,研究了格值Chomsky范式文法、格值上下文无关文法及其派生所产生的语言的等价条件,揭示了在一定条件下,格值下推自动机接受的语言类与格值上下文无关文法产生的语言类的等价性,证明了有理格值语言均被格值下推自动机识别。     

Controlled bidirectional grammars

We investigate context-free grammars the rules of which can be used in a productive and in a reductive fashion, while the application of these rules is controlled by a regular language. We distinguish several modes of derivation for this kind of grammar. The resulting language families (properly) extend the family of context-free languages. We establish some closure properties of these language families and some grammatical transformations which yield a few normal forms for this type of grammar. Finally, we consider some special cases (viz. the context-free grammar is linear or left-linear), and generalizations, in particular, the use of arbitrary rather than regular control languages.     

Extended linear macro grammars,iteration grammars,and register programs

Summary Extended macro grammars (of the linear basic type only) are introduced as a generalization of those in [5], and it is shown that they have the same language generating power as (parallel) iteration grammars. In particular the IO and OI versions of extended macro grammars correspond to the deterministic and the (usual) nondeterministic iteration grammars respectively. Hence iterated substitution can be formulated using extended macro grammars.A nondeterministic register program without tests may be viewed as a macro grammar. IO-extension of this macro grammar corresponds to the use of nonrecursive function procedures in the register program. OI-extended macro grammars correspond to register programs which compute on sets. Hence these features of register programs can be investigated by means of (extended) parallel rewriting systems.The work of the first author has been supported by the Netherlands Organization for the Advancement of Pure Research (Z.W.O.).     

一种特殊的上下文无关文法及其语法分析

SAQ系统是一个进行软件规约获取、检验和复用的实验系统，其中以上下文无关文法表示的概念是规约的一部分.SAQ要求将概念的词法和句法定义结合在一个上下文无关文法中.如果用常规的上下文无关文法描述诸如程序设计语言和自然语言等一些复杂概念的语法，则需要把诸如空格和回车等没有实质意义的分隔符包含到语法中去(这种描述方法称为朴素表示法),使得语法描述很累赘.为此，作者设计了一种特殊的上下文无关文法,它把通常上下文无关文法定义中的非终极符集合和终极符集合进行细化.用这种文法可以相对简洁地描述程序语言和自然语言等复杂概