Search

The paper describes a system that can automatically generate tree adjoining grammars from abstract specifications. Our system is based on the use of tree descriptions to specify a grammar by separately defining pieces of tree structure that encode independent syntactic principles. Various individual specifications are then combined to form the elementary trees of the grammar. The system enables efficient development and maintenance of a grammar, and also allows underlying linguistic constructions (such as wh-movement) to be expressed explicitly. We have carefully designed our system to be as language independent as possible and tested its performance by constructing both English and Chinese grammars, with significant reductions in grammar development time. Provably consistent abstract specifications for different languages also offer unique opportunities for investigating how languages relate to themselves and to each other. For instance, the impact of a linguistic structure such as wh-movement can be traced from its specification to the descriptions that it combines with, to its actual realization in trees. By focusing on syntactic properties at a higher level, our approach allowed a unique comparison of our English and Chinese grammars.

Describing the static semantics of programming languages with attribute grammars is eased when the formalism allows direct dependencies to be induced between rules for nodes arbitrarily far away in the tree. Such direct non-local dependencies cannot be analyzed using classical methods, which enable efficient evaluation.This article defines an attribute grammar extension (“remote attribute grammars”) to permit references to objects with fields to be passed through the attribute system. Fields may be read and written through these references. The extension has a declarative semantics in the spirit of classical attribute grammars. It is shown that determining circularity of remote attribute grammars is undecidable.The article then describes a family of conservative tests of noncircularity and shows how they can be used to “schedule” a remote attribute grammar using standard techniques. The article discusses practical batch and incremental evaluation of remote attribute grammars.

There have been many arguments that the underlying structure of natural languages is beyond the descriptive capacity of context-free languages. A well-known example is tree adjoining grammars; less common are spine grammars, linear indexed grammars, head grammars, and combinatory categorial grammars. It is known that these models of grammars have the same generative power of string languages and fall into the class of mildly context-sensitive grammars. For an automaton, it is known that the class of languages accepted by transfer pushdown automata is exactly the class of linear indexed languages. In this paper, deterministic transfer pushdown automata is introduced. We will show that the language accepted by a deterministic transfer pushdown automaton is generated by an unambiguous spine grammar. Moreover, we will show that there exists an inherently ambiguous language.

Tile rewriting grammars (TRG) are a new model for defining picture languages. A rewriting rule changes a homogeneous rectangular subpicture into an isometric one tiled with specified tiles. Derivation and language generation with TRG rules are similar to context-free grammars. A normal form and some closure properties are presented. We prove this model has greater generative capacity than the tiling systems of Giammarresi and Restivo and the grammars of Matz, another generalization of context-free string grammars to 2D. Examples are shown for pictures made by nested frames and spirals.

State-alternating context-free grammars are introduced, and the language classes obtained from them are compared to the classes of the Chomsky hierarchy as well as to some well-known complexity classes. In particular, state-alternating context-free grammars are compared to alternating context-free grammars (Theoret. Comput. Sci. 67 (1989) 75–85) and to alternating pushdown automata. Further, various derivation strategies are considered, and their influence on the expressive power of (state-) alternating context-free grammars is investigated.

For modelling agents and their actions, as well as their interactions with the environment, we propose eco-array grammars (multilevel n-dimensional parallel array grammars). Even complex system behavior can be captured by adding attributes to this syntactic description model.

Resolving an open problem of Ravikumar and Quan, we show that equivalence of prefix grammars is complete in PSPACE. We also show that membership for these grammars is complete in P (it was known that this problem is in P) and characterize the complexity of equivalence and inclusion for monotonic grammars. For grammars with several premises we show that membership is complete in EXPTIME and hard for PSPACE for monotonic grammars.

In this paper, subclasses of monadic context-free tree grammars (CFTGs) are compared. Since linear, nondeleting, monadic CFTGs generate the same class of string languages as tree adjoining grammars (TAGs), it is examined whether the restrictions of linearity and nondeletion on monadic CFTGs are necessary to generate the same class of languages.

Attribute Grammars are the specification language of many tools that automatically generate programming language implementations. We consider the problem of verifying properties of attribute grammar specifications, particularly properties that are not well supported by existing tools. Rather than propose methods for extending existing tool implementation techniques, we propose the use of off-the-shelf formal methods tools as the basis for attribute grammar verification. Off-the-shelf tools can provide significant expressive power at a much lower cost than extending an existing evaluator generator. As a specific example, we describe how to use the Alloy model finding and checking tool to verify properties of remote attribution constructs in the LIDO attribute grammar specification language. A naive application of this approach has significant performance overheads; we discuss techniques for limiting the scope of the problems that are solved to make the approach tractable.

This paper is concerned with how two different computational approaches to design – shape grammars and space syntax – can be combined into a single common framework for formulating, generating, and evaluating designs. The main goal is to explore how the formal principles applied in the design process interact with the spatial properties of the designed objects. Results suggest that space syntax is (1) useful in determining the universe of solutions generated by the grammar and (2) in evaluating the evolving designs in terms of spatial properties and, therefore, in guiding the generation of designs.

Common LR parser generators lack abstraction facilities for defining recurring patterns of productions. Although there are generators capable of supporting regular expressions on the right hand side of productions, no generator supports user defined patterns in grammars.Parameterized LR parsing extends standard LR parsing technology by admitting grammars with parameterized non-terminal symbols. A generator can implement such a grammar in two ways, either by expansion or directly. We develop the theory required for the direct implementation and show that it leads to significantly smaller parse tables and that it has fewer parsing conflicts than the expanded grammar. Attribute evaluation for a parameterized non-terminal is possible in the same way as before, if the semantic functions related to the non-terminal are polymorphic with respect to the parameter.We have implemented parameterized LR parsing in the context of Essence, a partial-evaluation based LR parser generator for Scheme.

Four different kinds of grammars that can define crossing dependencies in human language are compared here: (i) context sensitive rewrite grammars with rules that depend on context, (ii) matching grammars with constraints that filter the generative structure of the language, (iii) copying grammars which can copy structures of unbounded size, and (iv) generating grammars in which crossing dependencies are generated from a finite lexical basis. Context sensitive rewrite grammars are syntactically, semantically and computationally unattractive. Generating grammars have a collection of nice properties that ensure they define only “mildly context sensitive” languages, and Joshi has proposed that human languages have those properties too. But for certain distinctive kinds of crossing dependencies in human languages, copying or matching analyses predominate. Some results relevant to the viability of mildly context sensitive analyses and some open questions are reviewed.

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. (C) 2004 Elsevier Inc. All rights reserved.

Drozd's critique of Crain & Thornton's (C&T) (1998) book Investigations in Universal Grammar (IUG) raises many issues concerning theory and experimental design within generative approaches to language acquisition. I focus here on one of the strongest theoretical claims of the Modularity Matching Model (MMM): continuity of processing. For reasons different to Drozd, I argue that the assumption is tenuous. Furthermore, I argue that the focus of the MMM and the methodological prescriptions contained in IUG are too narrow to capture language acquisition.

Tomita's general parsing algorithm is linear on LR(1) grammars but fails to terminate on grammars with hidden left recursion and is not efficient in the presence of $\epsilon$ -rules. When Right Nulled (RN) parse tables are used Tomita style GLR algorithms operate correctly and more efficiently on all context free grammars. However, an RN table may contain more conflicts than the corresponding LR table, making the construction of parts of the internal structure redundant. We show that in certain cases conflicts can be removed from an RN table without compromising the correctness of the associated parser. In particular, all conflicts can be removed if the grammar is LR(1). This improves the performance of the parser and allows resolved RN tables for LR(1) grammars to be used with standard (deterministic) LR stack-based parsing algorithms, adding the `short-circuiting' of right nullable reductions to the armoury of efficient implementation techniques for such algorithms.

Object-based models offer abstract constructions to describe complex systems. The Object-Based Graph Grammar (OBGG) is a formalism that may be used to describe this kind of system. This formalism is very intuitive, however, up to now, there are no automatic tools for verification of OBGGs. In this work we propose a translation from Object-Based Hypergraph Grammars into π-Calculus. So, we may be able to prove properties of the systems modeled in this kind of graph grammars through this translation and automatic checkers for π-calculus.

We consider a representation of the structure of derivations in Ajdukiewicz and Lambek categorial grammars called derived trees. We define derived tree languages of those grammars based on syntactic calculi formalized in Gentzen style and in natural deduction format and examine their relation to the families of local and regular tree languages.

Attribute grammars (AGs) are a suitable formalism for the development of language processing systems. However, for languages including unrestricted labeled jumps, such as “goto” in C, the optimizers in compilers are difficult to write in AGs. This is due to two problems that few previous researchers could deal with simultaneously, i.e., references of attribute values on distant nodes and circularity in attribute dependency. This paper proposescircular remote attribute grammars (CRAGs), an extension of AGs that allows (1) direct relations between two distant attribute instances through pointers referring to other nodes in the derivation tree, and (2) circular dependencies, under certain conditions including those that arise from remote references. This extension gives AG programmers a natural means of describing language processors and programming environments for languages that include any type of jump structure. We also show a method of constructing an efficient evaluator for CRAGs called amostly static evaluator. The performance of the proposed evaluator has been measured and compared with dynamic and static evaluators.

We present an algorithm for the inference of context-free graph grammars from examples. The algorithm builds on an earlier system for frequent substructure discovery, and is biased toward grammars that minimize description length. Grammar features include recursion, variables and relationships. We present an illustrative example, demonstrate the algorithm's ability to learn in the presence of noise, and show real-world examples.

In general, it is undecidable if an arbitrary context-free grammar has a regular solution. Past work has focused on special cases, such as one-letter grammars, non self-embedded grammars and the finite-language grammars, for which regular counterparts have been proven to exist. However, little is known about grammars with the self-embedded property. Using systems of equations, we highlight a number of subclasses of grammars, with self-embeddedness terms, such as $X \alpha X$ and $\gamma X \gamma$, that can still have regular languages as solutions. Constructive proofs that allow these subclasses of context-free grammars to be transformed to regular expressions are provided. We also point out a subclass of context-free grammars that is inherently non-regular. Our latest results can help demarcate more precisely the known boundaries between the regular and non-regular languages, within the context-free domain.

The generalisation of confluent node rewriting, a context-free graph grammar approach, to hypergraphs yields the most powerful known context-free technique to define hypergraph languages. This paper, which summarises part of the author's doctoral thesis, substantiates that claim by reporting on the generative power of the so-called C-hNCE grammars.

In this paper we make a comparison between two methods for the enumeration of combinatorial objects, namely the ECO method and object grammars, both based on a recursive description for the examined class of objects. In particular, we study the problem of passing from an object grammar to an “equivalent” ECO system. First, we solve this problem for any unidimensional, unambiguous, and complete object grammar, with any linear parameter. Then we treat the more complex cases of q-linear parameters, and of multidimensional object grammars, giving some explanatory examples. In particular, we determine a new ECO system for the class of directed convex polyominoes.

This paper establishes computational equivalence of two seemingly unrelated concepts: linear conjunctive grammars and trellis automata. Trellis automata, also studied under the name of one-way real-time cellular automata, have been known since early 1980s as a purely abstract model of parallel computers, while linear conjunctive grammars, introduced a few years ago, are linear context-free grammars extended with an explicit intersection operation. Their equivalence implies the equivalence of several other formal systems, including a certain restricted class of Turing machines and a certain type of language equations, thus giving further evidence for the importance of the language family they all generate.

We exhibit a new class of grammars with the help of weightfunctions. They are characterized by decreasing the weight during the derivation process. A decision algorithm for the emptiness problem is developed. This class contains non-contextfree grammars. The corresponding language class is identical to the class of ultralinear languages.

We present a computational language learning algorithm that can induce massively probabilistic grammars from treebank data. The paper is based on chapter 6 in my forthcoming thesis “Discontinuous Grammar: A dependency-based model of human parsing and language learning.” We start in section 1 by introducing the prerequisites from probability theory and statistics that are needed in the rest of the paper. In section 2, we define weighted grammars and massively probabilistic grammars, and discuss their relationship to standardly used grammars. In section 3, we address the problem of estimating probability distributions for hierarchically structured categorical data, and present an estimation algorithm that selects a hierarchical partition model by means of local search. We also describe a simulation study that shows that the algorithm performs well unless the distribution that generated the data is highly symmetric. Finally, in section 4, we outline how the algorithm can be used to learn massively p...

Constructive methods for obtaining regular grammar counterparts for some sub-classes of context-free grammars (CFGs) have been investigated by many researchers. An important class of grammars for which this is always possible is the one-letter CFG. We show in this paper a new constructive method for transforming an arbitrary one-letter CFG to an equivalent regular expression of star-height 0 or 1. Our new result is considerably simpler than a previous construction by Leiss, and we also propose a new normal form for a regular expression with only a single-star occurrence. Through an alphabet factorization theorem, we show how to go beyond the one-letter CFG in a straight-forward way.

The present paper introduces and discusses forbidding ET0L grammars whose productions have some attached strings, called forbidding conditions. These grammars can make a derivation step only by using productions whose forbidding conditions do not appear in the rewritten sentential form. The paper demonstrates that some well-known relationships concerning the language families resulting from ordinary ET0L grammars do not hold in terms of the forbidding ET0L grammars. Most interestingly, while E0L grammars are less powerful than ET0L grammars, their forbidding versions with conditions of length one are equally powerful. On the other hand, while EP0L grammars are as powerful as E0L grammars, FEP0L grammars are less powerful than FE0L grammars.

Conjunctive grammars are basically context-free grammars with an explicit set intersection operation added to the formalism of rules. This paper presents a cubic-time recognition and parsing algorithm for this family of grammars, which is applicable to an arbitrary conjunctive grammar without any initial transformations.The algorithm is in fact an extension of the context-free recognition and parsing algorithm due to Graham, Harrison and Ruzzo, and it retains the cubic time complexity of its prototype. It is shown that for the case of linear conjunctive grammars this algorithm can be modified to work in quadratic time and use linear space.The given algorithm is then applied to solve the membership problem for conjunctive grammars in polynomial time, and subsequently to prove the problem's P-completeness, as well as P-completeness of the membership problem for linear conjunctive grammars.

In this paper, a methodology for the generation of benchmarks in pattern recognition is described. The patterns are represented by means of an attributed plex language, which are based on plex grammars augmented by attributes. It is shown that the generated patterns are particularly suitable for the extraction of graph-based representations. As a result, databases of artificial pictures and correspondent graphs can be generated. These collections of graphs are very appropriate for benchmarks in the area of structural pattern recognition, since they are originated from a grammar and not from random distributions. The tools for creating the databases are public domain and have been already used for benchmarking artificial neural networks operating on structured domains.

We use random context picture grammers to generate pictures through successive refinement. The productions of such a grammar are context free, but their application is regulated by context randomly distributed in the developing picture. Grammars using this relatively weak context often succeed where context-free grammars fail, e.g., in generating the typical iteration sequence of the Sierpiński carpet. On the other hand, it proved possible to develop iteration theorems for three subclasses of these grammars; finding necessary conditions is problematic in the case of most models of context-free picture grammars with context-sensing ability, since they consider a variable and its context as a connected unit.We present a property of all picture sets generated with random context picture grammers, and then construct a picture set that does not belong to this class.

To make any sort of optimality argument, or rational engineering decision, one needs a fairly precise understanding of the problem to be tackled. Thus...

In this paper a new method of description of pictures of digitized rectangular arrays is introduced based on contextual grammars. Parallel contextual array grammars are defined and their properties are studied.

Attribute grammars provide a concise way to describe traits of a wide family of structures. Structures defined by context-free grammars have been well studied by Delest, Fédou, and more recently by Duchon. One of the principle benefits of this approach is the easy access to multivariate generating function equations from which average and higher moments are easily accessible. This work extends these notions to a wider class of structures and considers the application to algorithm analysis.

In this paper, we introduce some new variants of contextual grammars and investigate their generative power. We'consider a restricted version of depth-first contextual grammars, which depends on length of the inserting contexts. Using this variant, we give a solution to the open problem P14 listed in [8]. We also introduce random context contextual grammars and compare its generative power with the families IC , ICC , EC , ECC , TC . Time-varying contextual grammars are introduced which resemble time-varying grammars. We compare the generative power of this variant with the families of internal, external, total, matrix, and programmed contextual grammars.

A new systematic approach for the specification of bijections between sets of combinatorial objects is presented. It is based on the notion of object grammars. Object grammars give recursive descriptions of objects and generalize context-free grammars. The study of a particular substitution in these object grammars confirms once more the key role of Dyck words in the domain of enumerative and bijective combinatorics.

We propose and study a model of the graphical syllable using Marcus contextual grammars. For this purpose we introduce two new variants of Marcus contextual grammars: total Marcus contextual grammar with total leftmost derivation, and total Marcus contextual grammar with total leftmost derivation constrained by maximal use of selectors.

In Moortgat (1996) the Lambek Calculus L(Lambek, 1958) is extended by a pair of residuation modalities ♦ and □↓. Categorial Grammars based on the resulting logic L♦ are attractive for the purpose of modelling linguistic phenomena since they offer a compromise between the strict constituent structures imposed by context free grammars and related formalisms on the one hand, and the complete absence of hierarchical information in Lambek grammars on the other hand. The paper contains some results on the generative capacity of Categorial Grammars based on L♦. First it is shownthat adding residuation modalities does not extend the weak generative capacity. This is proved by extending the proof for the context freeness of L-grammars from Pentus (1993) to L♦. Second, the strong generative capacity of L♦-grammars is compared to context free grammars. The results are mainly negative; the set of tree languages generated by L♦-grammars neither contains nor is contained in the class of context free tree languages.

The aim of this paper is at least 2 fold: to give prospective PhD students in the area hints at where to start a promising research; and to supplement earlier reference lists on parallel grammars, trying to cover recent papers as well as ``older'' papers which were somehow neglected in other reviews. Together with the nowadays classical book on L systems by G. Rozenberg and A. Salomaa and with the articles on L systems in the Handbook of Formal Languages, researchers will be equipped with a hopefully comprehensive list of references and ideas around parallel grammars.

Earley's parsing algorithm is shown to be an abstract interpretation of a refinement of the derivation semantics of context-free grammars.

Syntactic analysis forms a foundation of many source analysis and reverse engineering tools. However, a single standard grammar is not always appropriate for all source analysis and manipulation tasks. Small custom modifications to the grammar can make the programs used to implement these tasks simpler, clearer and more efficient. This leads to a new paradigm for programming these tools: agile parsing. In agile parsing the effective grammar used by a particular tool is a combination of two parts: the standard base grammar for the input language, and a set of explicit grammar overrides that modify the parse to support the task at hand. This paper introduces the basic techniques of agile parsing in TXL and discusses several industry proven techniques for exploiting agile parsing in software source analysis and transformation.

We developed a spatial parser generator, SPG, which can automatically create a spatial parser if CMG(Constraint Multiset Grammars) grammars for a visual language are provided by the user with GUI(Graphical User Interface). SPG has the following features. (1) The user uses a visual editor to define the grammars of a virtual language and draw the visual language which should be parsed. (2) The user roughly defines CMG grammars in a visual wan at first. Then the user modifies them and defines final grammars. (3) Because SPG has a constraint solver, it maintains constraints in the parsed virtual language according to the grammars.

We consider the problem of inductively inferring a grammar for a language, given (positive) examples of the language and putative (possibly faulty) grammars for the complement of the language. The criterion of success is identification in the limit, defined by E. M. Gold (1967, Inform. and Control10, 447–474). Additional information is useful insofar as it allows the identification of language classes that would not be identified with positive examples alone. An infinite sequence of grammars past some finite position are correct for the complement of the input language, is not as useful a form of additional information as a single correct grammar for the complement. Grammars that are almost correct for the complement (that is, that make finitely many errors) are not as useful as correct grammars, and the usefulness of a grammar decreases with increasing numbers of errors.

We propose a family of static evaluators for subclasses of the well-defined (i.e., noncircular) attribute grammars. These evaluators augment the evaluator for the absolutely noncircular attribute grammars with look-ahead behaviors. Because this family covers exactly the set of all well-defined attribute grammars, well-defined attribute grammars may be classified into a hierarchy, called the NC hierarchy, according to their evaluators in the family. The location of a noncircular attribute grammar in the NC hierarchy is an intrinsic property of the grammar. The NC hierarchy confirms a result of Riis and Skyum (1981), which says that all well-defined attribute grammars allow a (static) pure multivisit evaluator by actually constructing such an evaluator. We also show that, for any finite m, an NC(m) attribute grammar can be transformed to an equivalent NC(0) grammar.

Abramov and Glück have recently introduced a technique called URA for inverting first order functional programs. Given some desired output value, URA computes a potentially infinite sequence of substitutions/restrictions corresponding to the relevant input values. In some cases this process does not terminate.In the present paper, we propose a new program analysis for inverting programs. The technique works by computing a finite grammar describing the set of all input that relate to a given output. During the production of the grammar, the original program is implicitly transformed using so-called driving steps. Whereas URA is sound and complete, but sometimes fails to terminate, our technique always terminates and is complete, but not sound. As an example, we demonstrate how to derive type inference from type checking.The idea of approximating functional programs by grammars is not new. For instance, the second author has developed a technique using tree grammars to approximate termination behaviour of deforestation. However, for the present purposes it has been necessary to invent a new type of grammar that extends tree grammars by permitting a notion of sharing in the productions. These dag grammars seem to be of independent interest.

Given two context-free grammars (CFGs), G1 and G2, the language generated by the union of the grammars is not the union of the languages generated by each grammar: L(G1∪ G2)≠ L(G1∪ L(G2). In order to account for modularity of grammars, another way of defining the meaning of grammars is needed. This paper adapts results from the semantics of logic programming languages to CFGs. We discuss alternative approaches for defining the denotation of a grammar, culminating in one which we show to be both compositional and fully-abstract. We then show how grammar modules can be defined such that their semantics retains these desirable properties. This gives a clear, mathematically sound way for composing parts of grammars.

This paper studies systems of language equations that are resolved with respect to variables and contain the operations of concatenation, union and intersection. Every system of this kind is proved to have a least fixed point, and the equivalence of these systems to conjunctive grammars is established. This allows us to obtain an algebraic characterization of the language family generated by conjunctive grammars.

The Generalized LR parsing algorithm for context-free grammars, introduced by Tomita in 1986, is a polynomial-time implementation of nondeterministic LR parsing that uses graph- structured stack to represent the contents of the nondeterministic parser's pushdown for all possible branches of computation at a single computation step. It has been specifically developed as a solution for practical parsing tasks arising in computational linguistics, and indeed has proved itself to be very suitable for natural language processing. Conjunctive grammars extend context-free grammars by allowing the use of an explicit intersection operation within grammar rules. This paper develops a new LR-style parsing algorithm for these grammars, which is based on the very same idea of a graph-structured pushdown, where the simultaneous existence of several paths in the graph is used to perform the mentioned intersection operation. The underlying finite automata are treated in the most general way: instead of showing the algorithm's correctness for some particular way of constructing automata, the paper defines a wide class of automata usable with a given grammar, which includes not only the traditional LR(k) automata, but also, for instance, a trivial automaton with a single reachable state. A modification of the SLR(k) table construction method that makes use of specific properties of conjunctive grammars is provided as one possible way of making finite automata to use with the algorithm. It is shown that the algorithm is applicable to any conjunctive grammar and can be implemented to work in no more than cubic time. Additionally, the algorithm can be made to work in linear time for the Boolean closure of the family of deterministic context-free languages.

This study focus on defining a new variant of regulated grammars called multiset controlled grammars as well as investigating their computational power. We apply a constructive theoretical approach; the intent of which is to provide new theories based on computational methods where the results are appeared in the form of examples, lemmas and theorems. In the study, we have found that multiset is powerful and yet a simple method in regulated rewriting theory. We have proved that multiset controlled grammars are at least as powerful as additive valence grammars, and they are at most powerful as matrix grammars.