Eliminating Unnecessary Items from the One-Pass Evaluation of Attribute Grammars

Yoshimichi WATANABE  Takehiro TOKUDA  

IEICE TRANSACTIONS on Information and Systems   Vol.E79-D   No.4   pp.312-320
Publication Date: 1996/04/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Software Theory
attribute grammar,  compiler,  formal language,  

Full Text: PDF>>
Buy this Article

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.