Syntax-Directed Translation Schemes
Introduction: A syntax directed definition is a generalization of a context free grammar in which each grammar symbol has an associated set of attributes, partitioned into two subsets called the synthesized and inherited attributes of that grammar symbol. All of the applications of syntax-directed definitions can be implemented using syntax-directed translation schemes; a syntax-directed translation scheme (SDT) is a context free grammar with program fragments embedded within production bodies.
The program fragments are called semantic actions and can appear at any position within a production body. By convention, we place curly braces around actions; if braces are needed as grammar symbols, then we quote them.
Any SDT can be implemented by first building a parse tree and then performing the actions in a left-to-right depth-first order; that is, during a preorder traversal.
Typically, SDT's are implemented during parsing, without building a parse tree. In this section, we focus on the use of SDT's to implement two important classes of SDD's:
1. The underlying grammar is LR-parsable, and the SDD is S-attributed.
2. The underlying grammar is LL-parsable, and the SDD is L-attributed.
We shall see how, in both these cases, the semantic rules in an SDD can be converted into an SDT with actions that are executed at the right time. During parsing, an action in a production body is executed as soon as all the grammar symbols to the left of the action have been matched.
SDT's that can be implemented during parsing can be characterized by introducing distinct marker nonterminals in place of each embedded action; each marker M has only one production, M -» e. If the grammar with marker nonterminals can be parsed by a given method, then the SDT can be implemented during parsing.
Typical implementation of languages: