Semantic evaluation from left to right
- 1 February 1976
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 19 (2) , 55-62
- https://doi.org/10.1145/359997.359999
Abstract
This paper describes attribute grammars and their use for the definition of programming languages and compilers; a formal definition of attribute grammars and a discussion of some of its important aspects are included. The paper concentrates on the evaluation of semantic attributes in a few passes from left to right over the derivation tree of a program. A condition for an attribute grammar is given which assures that the semantics of any program can be evaluated in a single pass over the derivation tree, and an algorithm is discussed which decides how many passes from left to right are in general necessary, given the attribute grammar. These notions are explained in terms of an example grammar which describes the scope rules of Algol 60. Practical questions, such as the relative efficiency of different evaluation schemes, and the ease of adapting the attribute grammar of a given programming language to the left-to-right evaluation scheme are discussed.Keywords
This publication has 8 references indexed in Scilit:
- On the complexity of the circularity test for attribute grammarsPublished by Association for Computing Machinery (ACM) ,1975
- Attributed translationsJournal of Computer and System Sciences, 1974
- Semantic attributes and improvement of generated codePublished by Association for Computing Machinery (ACM) ,1974
- Types are not setsPublished by Association for Computing Machinery (ACM) ,1973
- Generating parsers for affix grammarsCommunications of the ACM, 1972
- The design of a pascal compilerSoftware: Practice and Experience, 1971
- Semantics of context-free languagesTheory of Computing Systems, 1968
- The design of the GIER ALGOL compiler Part IBIT Numerical Mathematics, 1963