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.     

Modelling of space-efficient one-pass translation using attribute grammars

Automatic production of one-pass compilers from attribute grammars is considered. An examination of a one-pass grammar for the programming language Euclid shows that the present definition of one-pass grammars is too general: the space behaviour of the produced compilers differs from that found in conventional hand-written compilers. A new class of attribute grammars is defined. The class models naturally the use of space in a hand-written compiler. This implies that the compiler produced automatically on the basis of the grammar uses space in the same way as a practical hand-written recursive descent compiler. Furthermore, a graphical notation is introduced as a design tool for obtaining grammars in the proposed class.     

A poor man's realization of attribute grammars

An approach is described in this paper for realizing attribute grammars. A system called STAR has been implemented according to this approach. The system is based on the STAGE2 macroprocessor. It is simple, portable, it can run even on small machines, it can be quickly implemented and it has a convenient to the user metalanguage. The system, however, disregards efficiency and is limited to small size problems.     

Monolithic and modular termination analyses for higher-order attribute grammars

In this paper we describe a sound, but not complete, analysis to prove the termination of higher-order attribute grammar evaluation caused by the creation of an unbounded number of (finite) trees as local tree-valued attributes, which are then themselves decorated with attributes. The analysis extracts a set of term-rewriting rules from the grammar that model creation of new syntax trees during the evaluation of higher-order attributes. If this term rewriting system terminates, then only a finite number of trees will be created during attribute grammar evaluation. The analysis places an ordering on nonterminals to handle the cases in which higher-order inherited attributes are used to ensure that a finite number of trees are created using such attributes. When paired with the traditional completeness and circularity analyses for attribute grammars and the assumption that each attribute equation defines a terminating computation, this analysis can be used to show that attribute grammar evaluation will terminate normally. This analysis can be applied to a wide range of common attribute grammar idioms and has been used to show that evaluation of our specification of Java 1.4 terminates. We also describe a modular version of the analysis that is performed on independently developed language extension grammars and the host language being extended. If the extensions individually pass the modular analysis then their composition is also guaranteed to terminate.     

On the relationship between the LL(k) and LR(k) grammars

In the literature various proofs of the inclusion of the class of LL(k) grammars into the class of LR(k) grammars can be found. Some of these proofs are not correct, others are informal, semi-formal or contain flaws. Some of them are correct but the proof is less straightforward than demonstrated here.     

Domain-specific program profiling and its application to attribute grammars and term rewriting

We present a method for profiling programs that are written using domain-specific languages. Instead of reporting execution in terms of implementation details as in most existing profilers, our method operates at the level of the problem domain. Program execution generates a stream of events that summarises the execution in terms of domain concepts and operations. The events enable us to construct a hierarchical model of the execution. A flexible reporting system summarises the execution along developer-chosen model dimensions. The result is a flexible way for a developer to explore the execution of their program without requiring any knowledge of the domain-specific language implementation.These ideas are embodied in a new profiling library called dsprofile that is independent of the problem domain so it has no specific knowledge of the data and operations that are being profiled. We illustrate the utility of dsprofile by using it to profile programs that are written using our Kiama language processing library. Specifically, we instrument Kiama's attribute grammar and term rewriting domain-specific languages to use dsprofile to generate events that report on attribute evaluation and rewrite rule application. Examples of typical language processing tasks show how domain-specific profiling can help to diagnose problems in Kiama-based programs without the developer needing to know anything about how Kiama is implemented.     

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.     

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.     

Software visualization of LR parsing and synthesized attribute evaluation

Visual YACC is a tool that automatically creates visualizations of the YACC LR parsing process and synthesized attribute computation. The Visual YACC tool works by instrumenting a standard YACC grammar with graphics calls that draw the appropriate data structures given the current actions by the parser. The new grammar is processed by the YACC tools and the resulting parser displays the parse stack and parse tree for every step of the parsing process of a given input string. Visual YACC was initially designed to be used in compiler construction courses to supplement the teaching of parsing and syntax directed evaluation. We have also found it to be useful in the difficult task of debugging YACC grammars. In this paper, we describe this tool and how it is used in both contexts. We also detail two different implementations of this tool: one that produces a parser written in C with calls to Motif; and a second implementation that generates Java source code. Copyright © 1999 John Wiley & Sons, Ltd.     

Semantic specification using two-level grammars: Blocks, procedures and parameters

Formal specifications are presented for the complete syntax and semantics of an ALGOL-like language fragment, using a recently introduced definitional technique employing two-level grammars (W-grammars). The fragment contains several important features whose dynamic semantics have not previously been treated by means of this technique: block structure, (recursive) procedures, and parameters passed by value, by reference, and by name. The degree of conciseness, clarity, etc., of the specifications is comparable to that obtainable with other approaches to formal seamantics, and it is concluded that two-level grammars must currently be regarded as a competitive approach for progress in language specification.     

Reversible logic grammars for natural language parsing and generation

The use of a single grammar in natural language parsing and generation is most desirable for a variety of reasons, including efficiency, perspicuity, integrity, robustness, and a certain amount of elegance. These characteristics have been noted before by several researchers, but it was only recently that more serious attention started to be paid to the problem of creating a bidirectional system for natural language processing. In this paper we discuss a somewhat more radical version of the problem: given a parser for a language, can we reverse it so that it becomes an efficient generator for the same language? Furthermore, since both the parser and the generator are based upon the same grammar, are there any normalization conditions upon the form of the grammar that must be met in order to assure the maximum efficiency of the reversed program? Can other grammars be transformed into the normal form? We describe the results of an experiment with PROLOG-based logic grammar which has been derived from a substantial-coverage string grammar for English. We present an alogorithm for automated inversion of a unification parser into an efficient unification generator, using the collections of minimal sets of essential arguments for predicates. We discuss the scope of the present version of the algorithm and then point out several possible avenues for extension. We also outline a preliminary solution to the question of grammar's “normal form” and suggest a handful of normalizing transformations that can be used to enhance the efficiency of the generator. This research interacts closely with a Japanese-English machine translation project at New York University, for which the first implementation of the inversion algorithm has been prepared.     

Function simulation,graph grammars and colourings

We prove that to any partial function ? defined on a finite set, there corresponds an infinite class of graphs that could be generated by a graph grammar such that each graph in the class represents the function in the sense that evaluation of the function at any point x of its domain can be simulated by finding the unique extension of a partial vertex colouring of the graph specified by x. We show that in the proposed setup, generating such simulator graphs as well as finding the colouring extensions can be computed effectively in polynomial time. We also discuss some applications of this scenario in producing instances of the graph colouring problem near its phase transition that can be applied in a cryptographic setting.     

Propagation of constraints along model transformations using triple graph grammars and borrowed context

Fundamental properties of model transformations based on triple graph grammars (TGGs) have been studied extensively including syntactical correctness, completeness, termination and functional behavior. But up to now, it is an open problem how domain specific properties that are valid for a source model can be preserved along model transformations such that the transformed properties are valid for the derived target model. This question shows up in enterprise modeling. Here, modeling activities related to different domains are handled by different parties, and their models need to be consistent and integrated into one holistic enterprise model later on. So, support for decentralized modeling processes is needed. One technical aspect of the needed support in this case is the (bidirectional) propagation of constraints because that enables one party to understand and check the constraints of another party. Therefore, we analyze in the framework of TGGs how to propagate constraints from a source model to an integrated model and, afterwards, to a target model, such that, whenever the source model satisfies the source constraint, also the integrated and target model satisfy the corresponding integrated and target constraint. In our main new results we show under which conditions this is possible.     

Development of communication protocols using algebraic and temporal specifications

The paper pursues two main goals. First, an attempt is made to specify and verify protocols in a completely rigorous manner using the formalisms of temporal logic and algebraic specification. Second––and even more important––the protocol specifications are not presented as monolithic pieces of text, but rather are developed in a stepwise process, evolving from simple genotypes into the final complex products. This is illustrated with selected fragments of the TCP/IP protocol.     

Automation and optimisation of Family Mould Cavity and Runner Layout Design (FMCRLD) using genetic algorithms and mould layout design grammars

Family Mould Cavity Runner Layout Design (FMCRLD) is the most demanding and critical task in the early Conceptual Mould Layout Design (CMLD) phase. Traditional experience-dependent manual FCMRLD workflow causes long design lead time, non-optimum designs and human errors. However, no previous research can support FMCRLD automation and optimisation. The nature of FMCRLD is non-repetitive and generative. The complexity of FMCRLD optimisation involves solving a complex two-level combinatorial layout design optimisation problem. Inspired by the theory of evolutionary design in nature “Survival of the Fittest” and the biological genotype–phenotype mapping process of the generation of form in living systems, this research first proposes an innovative evolutionary FMCRLD approach using Genetic Algorithms (GA) and Mould Layout Design Grammars (MLDG) that can automate and optimise such generative and complex FMCRLD with its explorative and generative design process embodied in a stochastic evolutionary search. Based on this approach, an Intelligent Conceptual Mould Layout Design System (ICMLDS) prototype has been developed. The ICMLDS is a powerful intelligent design system as well as an interactive design-training system that can encourage and accelerate mould designers’ design alternative exploration, exploitation and optimisation for better design in less time. This research innovates the traditional manual FMCRLD workflow to eliminate costly human errors and boost the less-experienced mould designer’s ability and productivity in performing FCMRLD during the CMLD phase.