Syntax-directed translation

Syntax-directed translation refers to a method of compiler implementation where the source language translation is completely driven by the parser.

A common method of syntax-directed translation is translating a string into a sequence of actions by attaching one such action to each rule of a grammar.^[1] Thus, parsing a string of the grammar produces a sequence of rule applications. SDT provides a simple way to attach semantics to any such syntax.

Overview

Syntax-directed translation fundamentally works by adding actions to the productions in a context-free grammar, resulting in a Syntax-Directed Definition (SDD).^[2] Actions are steps or procedures that will be carried out when that production is used in a derivation. By convention, we place curly braces around actions; if braces are needed as grammar symbols, then we quote them. A grammar specification embedded with actions to be performed is called a syntax-directed translation scheme^[1] (sometimes simply called a 'translation scheme'.)

Each symbol in the grammar can have an attribute, which is a value that is to be associated with the symbol. Common attributes could include a variable type, the value of an expression, etc. Given a symbol X, with an attribute t, that attribute is referred to as X.t

Thus, given actions and attributes, the grammar can be used for translating strings from its language by applying the actions and carrying information through each symbol's attribute.

Implementation

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. SDT's can be used to import classes of SDD's:

The underlying grammar is LR-parsable, and the SDD is S-attributed.
The underlying grammar is LL-parsable, and the SDD is L-attributed.

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→ε. If the grammar with marker non-terminals can be parsed by a given method, then the SDT can be implemented during parsing.^[2]

Postfix translation schemes

By far the simplest SDD implementation occurs when we parse the grammar bottom-up and the SDD is S-attributed. In that case, we can construct an SDT in which each action is placed at the end of the production and is executed along with the reduction of the body to the head of that production. SDT's with all actions at the right ends of the production bodies are called postfix SDT's.

Metacompilers

Early metacompilers use the terms syntax-driven and syntax-directed translation in their descriptions. They have metaprogramming language features for outputing code.

See metacompiler, META II, and TREE-META.

References

1 2 Gurari, Eitan M. "Syntax-Directed Translation Schemes (SDTS's)." Web. 23 Sept. 2010. <http://www.cse.ohio-state.edu/~gurari/course/cse756/cse756su33.xht>.
1 2 Aho, Alfred V. Compilers: Principles, Techniques, & Tools. Boston: Pearson/Addison Wesley, 2007. Print.

This article is issued from Wikipedia - version of the 9/23/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.