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.     

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.     

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.     

Ordered attributed grammars

Summary Ordered attributed grammars are defined as a large subclass of semantically well-defined attributed grammars proposed by Knuth. An attributed grammar is ordered if for each symbol a partial order over the associated attributes can be given, such that in any context of the symbol the attributes are evaluable in an order which includes that partial order. The definition does not refer to a predefined strategy for attribute evaluation, e.g. several passes from left to right. For each attributed grammar evaluable by any predefined evaluation strategy such an order exists. The ordering property can be checked by an algorithm, which depends polynomially in time on the size of the input grammar. Visit-sequences are computed from the attribute dependencies given by an ordered attributed grammar. They describe the control flow of an algorithm for attribute evaluation which can be part of an automatically generated compiler.     

A platform for the automatic generation of attribute evaluation hardware systems

Attribute grammars (AG) allow the addition of context-sensitive properties into context free grammars, augmenting their expressional capabilities by using syntactic and semantic notations, making them in this way a really useful tool for a considerable number of applications. AGs have extensively been utilized in applications such as artificial intelligence, structural pattern recognition, compiler construction and even text editing. Obviously, the performance of an attribute evaluation system resides in the efficiency of the syntactic and semantic subsystems. In this paper, a hardware architecture for an attribute evaluation system is presented, which is based on an efficient combinatorial implementation of Earley's parallel parsing algorithm for the syntax part of the attribute grammar. The semantic part is managed by a special purpose module that traverses the parse tree and evaluates the attributes based on a proposed stack-based approach. The entire system is described in Verilog HDL (hardware design language), in a template form that given the specification of an arbitrary attribute grammar, the HDL synthesizable source code of the system is produced on the fly by a proposed automated tool. The generated code has been simulated for validation, synthesized and tested on an Xilinx FPGA (field programmable gate arrays) board for various AGs. Our method increases the performance up to three orders of magnitude compared to previous approaches, depending on the implementation, the size of the grammar and the input string length. This makes it particularly appealing for applications where attribute evaluation is a crucial aspect, like in real-time and embedded systems. Specifically, a natural language interface is presented, based on a question-answering application from the area of airline flights.     

Name analysis for modern languages: a general solution

Classical strategies for matching identifier uses with declarations cannot handle the complexities of modern languages: arbitrarily qualified superclass names, cyclic dependence among lookup operations, and contextual access constraints. We have developed a language‐independent algorithm and supporting data structure that overcome these problems. A well‐defined interface allows introduction of arbitrary code to enforce language‐specific constraints within the basic lookup operations. This paper explains the limitations of the classical strategies, presents the concepts on which our approach is based, and showcases an implementation based on attribute grammars. We explore the major issues through a series of examples and show how one can deal with those issues in a general framework. Many of the issues are specific to a particular language, and in those cases, we explain the solutions that our general interface supports. Although attribute grammars simplify the task of incorporating the model into a compiler, the model itself is completely independent of attribute grammars. We validated our model by using an implementation to process programs in several representative languages. In particular, we mechanically compared the results produced by that implementation with those produced by the Java SE 8 compiler on complete Java programs that are in general use. Performance data obtained during this processing show that our implementation is efficient. Copyright © 2017 John Wiley & Sons, Ltd.     

A Prolog Framework for the Rapid Prototyping of Language Processors with Attribute Grammars

In this paper, we describe PAG (Prototyping with Attribute Grammars), a framework for building Prolog prototypes from specifications based on attribute grammars, which we have developed for supporting rapid prototyping activities in an introductory course on language processors. This framework works for general non-circular attribute grammars with arbitrary underlying context-free grammars, includes a specification language embedded in Prolog that strongly resembles the attribute grammar notations explained in the course cited, and lets students produce comprehensible prototypes from their specifications in a straightforward way.     

String and graph grammar characterizations of bounded regular languages

Two grammatical characterizations of the bounded regular languages are presented: one in terms of graph grammars, the other using string grammars. First it is shown that a class of state graphs recognizing the bounded regular languages can be generated by a particular second-order contextfree graph grammar. Next we call uniquely recursive a right-linear (string) grammar having at most one right-recursive production for each of its nonterminals. It is then established that the class of languages generated by uniquely recursive, sequential right-linear grammars is exactly the bounded regular languages. Some comments on the relationship between string and graph grammars are made.     

The equivalence and inclusion problems for NTS languages

A context-free grammar is said to be NTS if the set of sentential forms it generates is unchanged when the rules are used both ways. We prove that this class of grammars has a decidable equivalence problem. Then we show that one can decide whether a given c.f. grammar is NTS or not. We prove that the class of NTS grammars has an undecidable inclusion problem.     

A comparison of storage optimizations in automatically-generated attribute evaluators

Summary Attribute grammars are a value-oriented, non-procedural extension to context-free grammars that facilitate the specification of translations whose domain is described by the underlying context-free grammar. Just as parsers for context-free languages can be automatically constructed from a context-free grammar, so can translators, called attribute evaluators, be automatically generated from an attribute grammar. A major obstacle to generating efficient attribute evaluators is that they typically use large amounts of memory to represent the attributed parse tree. In this report we investigate the problem of efficient representation of the attributed parse tree by analyzing and comparing the strategies of two systems that have been used to automatically generate a translator from an attribute grammar: the GAG system developed at the Universitat de Karlsruhe and the LINGUIST-86 system written at Intel Corporation. Our analysis will characterize the two strategies and highlight their respective strengths and weaknesses. Drawing on the insights given by this analysis, we propose a strategy for storage optimization in automatically generated attribute evaluators that not only incorporates the best features of both GAG and LINGUIST-86, but also contains novel features that address aspects of the problem that are handled poorly by both systems.This research was partially supported by the National Science Foundation under grant DCR-83-10930, and partially supported by the Defense Advanced Research Projects Agency under contract number N00039-84-C-0165     

A programmer-friendly LL(1) parser generator

LL(1) grammars have the conceptual and practical advantage that they allow the compiler writer to view the grammar as a program; this allows a more natural positioning of semantic actions and a simple attribute mechanism. Resulting parsers can be constructed that achieve fully automatic error-recovery, which allows the compiler writer to ignore totally the issue of syntax errors. Measurement shows that such parsers can be reasonably efficient.     

Context-free hypergraph grammars have the same term-generating power as attribute grammars

Context-free hypergraph grammars and attribute grammars generate the same class of term languages. Extending the context-free hypergraph grammar with a context-free grammar and a semantic domain, a syntax-directed translation device is obtained that is equivalent to the attribute grammar.     

The Generating Power of Total Deterministic Tree Transducers

Attributed tree transducers are abstract models used to study properties of attribute grammars. One abstraction which occurs when modeling attribute grammars by attributed tree transducers is that arbitrary trees over a ranked alphabet are taken as input, instead of derivation trees of a context-free grammar. In this paper we show that with respect to the generating power this isnotan abstraction; i.e., we show that attributed tree transducers and attribute grammars generate the same class of term (or tree) languages. To prove this, a number of results concerning the generating power of top-down tree transducers are established, which are interesting in their own. We also show that the classes of output languages of attributed tree transducers form a hierarchy with respect to the number of attributes. The latter result is achieved by proving a hierarchy of classes of tree languages generated by context-free hypergraph grammars with respect to their rank.     

The covering problem for linear context-free grammars

Language equivalence, grammatical covering and structural equivalence are all notions of similarity defined on context-free grammars. We show that the problem of determining whether an arbitrary linear context-free grammar covers another is complete for the class of languages accepted by polynomially space bounded Turing machines. We then compare the complexity of this problem with the analogous problems for language equivalence and structural equivalence, not only for linear grammars, but also for regular grammars and unrestricted context-free grammars. As a step in obtaining the main result of this paper, we show that the equivalence problem for linear s-grammars is decidable in polynomial time.     

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.     

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.     

<Emphasis Type="SmallCaps">gDelta</Emphasis>: a missing link in the grammar engineering toolchain

The development of precision grammars is an inherently resource-intensive process; their complexity means that changes made to one area of a grammar often introduce unexpected flow-on effects elsewhere in the grammar which may only be discovered after some time has been invested in updating numerous test suite items. In this paper, we present the browser-based gDelta tool, which aims to provide grammar engineers with more immediate feedback on the impact of changes made to a grammar by comparing parser output from two different grammar versions. We describe an attribute weighting algorithm for highlighting components of the grammar that have been strongly impacted by a modification to the grammar, as well as a technique for clustering test suite items whose parsability has changed, in order to locate related groups of effects. These two techniques are used to present the grammar engineer with different views on the grammar to inform them of different aspects of change in a data-driven manner.     

A classification of noncircular attribute grammars based on thelook-ahead behavior

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     

Probabilistic context-free grammars estimated from infinite distributions

In this paper, we consider probabilistic context-free grammars, a class of generative devices that has been successfully exploited in several applications of syntactic pattern matching, especially in statistical natural language parsing. We investigate the problem of training probabilistic context-free grammars on the basis of distributions defined over an infinite set of trees or an infinite set of sentences by minimizing the cross-entropy. This problem has applications in cases of context-free approximation of distributions generated by more expressive statistical models. We show several interesting theoretical properties of probabilistic context-free grammars that are estimated in this way, including the previously unknown equivalence between the grammar cross-entropy with the input distribution and the so-called derivational entropy of the grammar itself. We discuss important consequences of these results involving the standard application of the maximum-likelihood estimator on finite tree and sentence samples, as well as other finite-state models such as hidden Markov models and probabilistic finite automata.     

NEGATIVE AND POSITIVE EXPLANATIONS IN EXPERT SYSTEMS

A methodology for management of constraints in VLSI data bases is presented in this paper. The process of management is based on forma! mechanisms of attribute grammar theory. Examples of a modularized knowledge representation of a circuit at interconnection and logic levels based on attribute grammars illustrate the methodology. The ultimate goal and benefit of the proposed methodology is a well-defined development technique for VLSI design tools that will allow the user to generate a transformation system, a knowledge representation, and a system to manipulate this representation, all from a simple specification. In addition, context-dependent specifications at lower levels are automatically generated from the higher-level specifications.