We present two efficient attribute evaluator construction methods for a wide subclass of L-attributed grammars by enumeration of attributed items during one-pass bottom-up parsing. We have already proposed a construction method of a parser/evaluator for the subclass of L-attributed grammar. However the evaluator produced by our previous method uses a great number of attributed items to evaluate all attributes of a given input string. In this paper we propose two generalized methods to reduce the number of attributed itmes used in attribute evaluation. Our methods allow us to evaluate all attributes taking advantage of the use of available lookahead information.

We present a transformation method for reducing the number of states of bypassed Knuth LR(k) parsers. Bypassed Knuth LR(k) parsers behave like Knuth LR(k) parsers except that they perform syntactic analysis without reducing productions of the form X::Y (X and Y are grammar symbols) that have empty semantic actions. Using a characterization of correct bypassed LR(k) parsing obtained by parsing contexts approach of this paper, we show that the transformation of merging of states having same core preserves the validity of the parsers provided that the parsers are free from parsing action conflicts. (Note that in general this property cannot be guaranteed in other type of Bypassed LR(k) parsers than Bypassed Knuth LR(k) parsers.) Using this transformation we can construct a faster LR(k) parser having reasonable number of states. This result is a significant reduction in the size of bypassed LR(k) parsers.

This paper gives a method for transforming attribute grammars into efficient action routines. An action routine description is a set of fragments of programs associated with production rules. Those fragments of programs are activated according to the ordering given by a bottom-up syntax analyzer. We present a transformation method which we call patch introduction. Patch introduction consists of techniques which we call extended postfix transformation and broadcast type inherited attribute elimination. Extended postfix transformation is an extension of simple postfix transformation. Broadcast type inherited attribute elimination is a technique of making the evaluation into a one-pass bottom-up evaluation. The scenario of patch introduction is as follows. First we reverse the flow of broadoast type inherited attributes, and transform those inherited attributes into synthesized attributes whose values are sets of addresses. Then we introduce generation of incomplete code where code is an extended postfix attribute, and introduce patch operations at the point where values of the broadcast type inherited attributes are determined. We illustrate the usefulness of our patch introduction method using a problem of translation of Boolean expressions into an intermediate code of short-circuit evaluation form.

This paper gives methods for computing a delta file of two two-dimensional arrays of characters which we call character planes. A delta file is a description of the difference between two text files. Our methods compute the largest matching of two character planes in a tow-dimensional manner, and consequently give the minimum modification from one text file to the other using deletion and insertion characters in a two-dimensional way. Our first method computes the largest matching of two character planes based on the tabulation of a recurrence relation of matchings of character planes. Our second method computes the largest matching of two character planes based on divide-and-conquer of character planes. Our third method computes the largest matching of two character planes based on dynamic programming on trees. Those methods are natural extensions of longest common subsequence algorithms. As an application of our methods, viewing a tree-structured text file produced by a structure editor as a character plane, we can extract natural common portions of two tree-structured text files in a two-dimensional manner.