Syntax-directed translation refers to a method of
compiler
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...
implementation where the source language translation is completely driven by the
parser
Parsing, syntax analysis, or syntactic analysis is the process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar. The term ''parsing'' comes from Lati ...
.
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
In linguistics, the grammar of a natural language is its set of structure, structural constraints on speakers' or writers' composition of clause (linguistics), clauses, phrases, and words. The term can also refer to the study of such constraint ...
.
Thus, parsing a string of the grammar produces a sequence of rule applications. SDT provides a simple way to attach
semantics
Semantics (from grc, σημαντικός ''sēmantikós'', "significant") is the study of reference, meaning, or truth. The term can be used to refer to subfields of several distinct disciplines, including philosophy
Philosophy (f ...
to any such
syntax
In linguistics, syntax () is the study of how words and morphemes combine to form larger units such as phrases and sentences. Central concerns of syntax include word order, grammatical relations, hierarchical sentence structure ( constituency) ...
.
Overview
Syntax-directed translation fundamentally works by adding actions to the productions in a
context-free grammar
In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules are of the form
:A\ \to\ \alpha
with A a ''single'' nonterminal symbol, and \alpha a string of terminals and/or nonterminals (\alpha can be empt ...
, resulting in a Syntax-Directed Definition (SDD).
[Aho, Alfred V. Compilers: Principles, Techniques, & Tools. Boston: Pearson/Addison Wesley, 2007.] Actions are steps or procedures that will be carried out when that production is used in a derivation. A grammar specification embedded with actions to be performed is called a ''syntax-directed translation scheme''
[ (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.
]
Metacompilers
Early metacompilers use the terms syntax-driven and syntax-directed translation in their descriptions. They have metaprogramming
Metaprogramming is a programming technique in which computer programs have the ability to treat other programs as their data. It means that a program can be designed to read, generate, analyze or transform other programs, and even modify itself ...
language features for outputting code.
See metacompiler
In computer science, a compiler-compiler or compiler generator is a programming tool that creates a parser, interpreter, or compiler from some form of formal description of a programming language and machine.
The most common type of compiler- ...
, META II
META II is a domain-specific programming language for writing compilers. It was created in 1963–1964 by Dewey Val Schorre at UCLA. META II uses what Schorre called syntax equations. Its operation is simply explained as:
Each ''syntax equation'' ...
, and TREE-META
The TREE-META (or Tree Meta, TREEMETA) Translator Writing System is a compiler-compiler system for context-free languages originally developed in the 1960s. Parsing statements of the metalanguage resemble augmented Backus–Naur form with embedded ...
.
See also
* Attribute grammar An attribute grammar is a formal way to supplement a formal grammar with semantic information processing. Semantic information is stored in attributes associated with terminal and nonterminal symbols of the grammar. The values of attributes are resu ...
References
{{Reflist
Compiler construction