Code Improvement Techniques in the Transformation of Attribute Grammars into Efficient Action Routines

概要

論文の詳細を見る
This paper presents useful optimization techniques applicable to the transformation of attribute grammars into efficient action routines based on the canonical bottom-up syntax analysis. We show that data-flow techniques such as code motion and constant folding improve the efficiellcy of action routines. We use a technique called global variable introduction by synchronized stacks. This is a technique of evaluating attribute grammars using global variab1es. This technique is directly applicable for transforming attribute grammars into efficient action routines, when attribute grammars contain only synthesized attributes. An action routine description is a set of fragments of programs associated with productions. These fragments of programs are activated according to the ordering given by the canonical bottom-up syntax analyzer. Execution of action routines is generally more efficient than traditional evaluation methods of attribute grammars, because action routines can use both local and global variables freely in the canonical bottom-up syntax analysis ordering. Our techniques such as code motion and constant folding produce natural and efficient action routines. We illustrate the usefulness of our optimization techniques, as an example, using a problem of checking whether or not parentheses are balanced.
一般社団法人情報処理学会の論文
1987-03-31