Context-free text grammars

A text is a triple=(, ₁, ₂) such that is a labeling function, and ₁ and ₂ are linear orders on the domain of ; hence may be seen as a word (, ₁) together with an additional linear order ₂ on the domain of . The order ₂ is used to give to the word (, ₁) itsindividual hierarchical representation (syntactic structure) which may be a tree but it may be also more general than a tree. In this paper we introducecontext-free grammars for texts and investigate their basic properties. Since each text has its own individual structure, the role of such a grammar should be that of a definition of a pattern common to all individual texts. This leads to the notion of ashapely context-free text grammar also investigated in this paper.     

The formal power of one-visit attribute grammars

Summary An attribute grammar is one-visit if the attributes can be evaluated by walking through the derivation tree in such a way that each subtree is visited at most once. One-visit (1V) attribute grammars are compared with one-pass left-to-right (L) attribute grammars and with attribute grammars having only one synthesized attribute (1S).Every 1S attribute grammar can be made one-visit. One-visit attribute grammars are simply permutations of L attribute grammars; thus the classes of output sets of 1V and L attribute grammars coincide, and similarly for 1S and L-1S attribute grammars. In case all attribute values are trees, the translation realized by a 1V attribute grammar is the composition of the translation realized by a 1S attribute grammar with a deterministic top-down tree transduction, and vice versa; thus, using a result of Duske e.a., the class of output languages of 1V (or L) attribute grammars is the image of the class of IO macro tree languages under all deterministic top-down tree transductions.     

Context-free graph grammars and concatenation of graphs

An operation of concatenation is defined for graphs. This allows strings to be viewed as expressions denoting graphs, and string languages to be interpreted as graph languages. For a class of string languages, is the class of all graph languages that are interpretations of languages from . For the classes REG and LIN of regular and linear context-free languages, respectively, . is the smallest class of graph languages containing all singletons and closed under union, concatenation and star (of graph languages). equals the class of graph languages generated by linear HR (= Hyperedge Replacement) grammars, and is generated by the corresponding -controlled grammars. Two characterizations are given of the largest class such that . For the class CF of context-free languages, lies properly inbetween and the class of graph languages generated by HR grammars. The concatenation operation on graphs combines nicely with the sum operation on graphs. The class of context-free (or equational) graph languages, with respect to these two operations, is the class of graph languages generated by HR grammars. Received 16 October 1995 / 18 September 1996     

k-visit attribute grammars

It is shown that any well-defined attribute grammar isk-visit for somek. Furthermore it is shown that given a well-defined grammarG and an integerk, it is decidable whetherG isk-visit. Finally we show that thek-visit grammars specify a proper hierarchy with respect to translations.     

Guarded attribute grammars

Contrary to a widely-held belief, it is possible to construct executable specifications of language processors that use a top-down parsing strategy and which have structures that directly reflect the structure of grammars containing left-recursive productions. A novel technique has been discovered by which the non-termination that would otherwise occur is avoided by ‘guarding’ top-down left-recursive language processors by non-left-recursive recognizers. The use of a top-down parsing strategy increases modularity and the use of left-recursive productions facilitates specification of semantic equations. A combination of the two is of significant practical value because it results in modular and expressively clear executable specifications of language processors. The new approach has been tested in an attribute grammar programming environment that has been used in a number of projects including the development of natural language interfaces, SQL processors and circuit design transformers within a VLSI design package.     

Apex graph grammars and attribute grammars

Summary Apex graph grammars are a particular type of directed node-label controlled (DNLC) graph grammars: the embedding edges are established between terminal nodes only. Apex graph grammars, slightly generalized, can generate the sets of dependency graphs of attribute grammars. The other way around, every apex graph language can be obtained from such a dependency graph language by a graph replacement (which is an operation analogous to a string homomorphism).     

Inductive attribute grammars

Attribute grammars are traditionally constrained to be noncircular. In using attribute grammars to specify the semantics of programming languages, this noncircularity limitation has restricted attribute grammars to compile-time or static semantics. Inductive attribute grammars add a general form of circularity to this standard approach. Inductive attribute grammars have the expressiveness required to describe the full semantics of programming languages, while at the same time maintaining the declarative character of standard attribute grammars. This expanded view of attribute grammars proves to be useful in interactive language-based programming environments, as inductive attribute grammars allow the environment to provide an interpreter for incremental re-evaluation of programs after small changes to the code. The addition of run-time semantics via circular attribute grammars permits automatically generated environments to be complete, in that incremental static semantic checking and fast incremental execution are now available within a single framework.The authors' present affiliations are the United States Geological Survey and the Northrop Corporation respectively.     

Simple multi-visit attribute grammars

An attribute grammar is simple multi-visit if each attribute of a nonterminal has a fixed visit-number associated with it such that, during attribute evaluation, the attributes of a node which have visit-number j are computed at the jth visit to the node. An attribute grammar is l-ordered if for each nonterminal a linear order of its attributes exists such that the attributes of a node can always be evaluated in that order (cf. the work of Kastens).An attribute grammar is simple multi-visit if and only if it is l-ordered. Every noncircular attribute grammar can be transformed into an equivalent simple multi-visit attribute grammar which uses the same semantic operations.For a given distribution of visit-numbers over the attributes, it can be decided in polynomial time whether the attributes can be evaluated according to these visit-numbers. The problem whether an attribute grammar is simple multi-visit is NP-complete.     

Testing attribute grammars for circularity

Summary The problem of deciding whether a given attribute grammar is noncircular is known to require exponential time for infinitely many grammars. Here the time requirement of a simple circularity test is analyzed. It is shown that the reason for the exponential time requirement is the number of graphs in a collection formed for every nonterminal. By practical experiments it is argued that for real grammars the number is very small. Therefore it is feasible to actually perform the circularity test in practice. Different techniques to improve the implementation of the circularity test are discussed, too.     

Parallel evaluation of attribute grammars

Examines the generation of parallel evaluators for attribute grammars, targeted to shared-memory MIMD computers. Evaluation-time overhead due to process scheduling and synchronization is reduced by detecting coarse-grain parallelism (as opposed to the naive one-process-per-node approach). As a means to more clearly expose inherent parallelism, it is shown how to automatically transform productions of the form X→Y X into list-productions of the form X→Y⁺. This transformation allows for many simplifications to be applied to the semantic rules, which can expose a significant degree of inherent parallelism, and thus further increase the evaluator's performance. Effectively, this constitutes an extension of the concept of attribute grammars to the level of abstract syntax     

A pure embedding of attribute grammars

Attribute grammars are a powerful specification paradigm for many language processing tasks, particularly semantic analysis of programming languages. Recent attribute grammar systems use dynamic scheduling algorithms to evaluate attributes on demand. In this paper, we show how to remove the need for a generator, by embedding a dynamic approach in a modern, object-oriented and functional programming language. The result is a small, lightweight attribute grammar library that is part of our larger Kiama language processing library. Kiama’s attribute grammar library supports a range of advanced features including cached, uncached, higher order, parameterised and circular attributes. Forwarding is available to modularise higher order attributes and decorators abstract away from the details of attribute value propagation. Kiama also implements new techniques for dynamic extension and variation of attribute equations. We use the Scala programming language because of its support for domain-specific notations and emphasis on scalability. Unlike generators with specialised notation, Kiama attribute grammars use standard Scala notations such as pattern-matching functions for equations, traits and mixins for composition and implicit parameters for forwarding. A benchmarking exercise shows that our approach is practical for realistic language processing.     

Modularity and reusability in attribute grammars

An attribute grammar is a declarative specification of dependence among computations carried out at the nodes of a tree. Attribute grammars have proven remarkably difficult to decompose into logical fragments. As a result, they have not yet been accepted as a viable specification technique. By combining the ideas of remote attribute access and inheritance, we have been able to define attribution modules that can be reused in a variety of applications. As an example, we show how to define reusable modules for name analysis that embody different scope rules.     

Semantic equivalence of covering attribute grammars

This paper investigates some methods for proving the equivalence of different language specifications that are given in terms of attribute grammars. Different specifications of the same language may be used for different purposes, such as language definition, program verification, or language implementation. The concept of syntactic coverings is extended to the semantic part of attribute grammars. Given two attribute grammars, the paper discusses several propositions that give sufficient conditions for one attribute grammar to be semantically covered by the other one. These tools are used for a comparison of two attribute grammars that specify syntax and semantics of mixed-type expressions. This example shows a trade-off between the complexity of syntactic and semantic specifications. Another example discussed is the equivalence of different attribute grammars for the translation of the while-statement, as used in compilers for top-down and bottom-up syntax analysis.This work was in part supported by the National Research Council of Canada.     

Circular attribute grammars with remote attribute references and their evaluators

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. Akira Sasaki: He is a research fellow of the Advanced Clinical Research Center in the Institute of Medical Science at the University of Tokyo. He received his BSc and MSc from Tokyo Institute of Technology, Japan, in 1994 and 1996, respectively. His research interests include programming languages, programming language processors and programming environments, especially compiler compilers, attribute grammars and systematic debugging. He is a member of the Japan Society for Software Science and Technology. Masataka Sassa, D.Sc.: He is Professor of Computer Science at Tokyo Institute of Technology. He received his BSc, MSc and DSc from the University of Tokyo, Japan, in 1970, 1972 and 1978, respectively. His research interests include programming languages, programming language processors and programming environments, currently he is focusing on compiler optimization, compiler infrastructure, attribute grammars and systematic debugging. He is a member of the ACM, IEEE Computer Society, Japan Society for Software Science and Technology, and Information Processing Society of Japan.     

Context-free graph languages of bounded degree are generated by apex graph grammars

The apex graph grammars generate precisely the context-free graph languages of bounded degree, independently of whether one considers hyperedge replacement systems or (boundary or confluent) NLC or edNCE graph grammars. The main feature of apex graph grammars is that nodes cannot be passed from nonterminal to nonterminal. The proof is based on a normal form result for arbitrary hyperedge replacement systems that forbids passing chains. This generalizes Greibach Normal Form.     

Speeding up circularity tests for attribute grammars

Summary We present three improvements to be applied to algorithms testing the circularity of attribute grammars. The first one, originally introduced in [10], discards from the set of graphs attached to a nonterminal symbol those graphs that are included in (covered by) others of the same set. The second one, first presented by Chebotar [1], establishes an optimal order for selection of productions and eliminates at each step those graphs that are unnecessary for subsequent stages of the algorithm, thus requiring less time and space. The last one skips recomputations on terminal trees, thus saving time. These three methods can be used alone or together to speed up circularity tests. We also discuss the practical complexity of circularity tests.