Re: syntax directed translation
- From: Allan Jost <jost@xxxxxxxxx>
- Date: 2 Jan 2006 22:50:37 -0500
aegis wrote:
> Are syntax directed translation and syntax directed definition
> synonymous?
>
> [I've never heard of syntax directed definition. -John]
I'm a little surprised this term does not seem to be better known in
this circle. In the classic compilers text (Aho, Sethi, & Ullman's
"Dragon" Book"), both terms are given definitions right in the
introductory chapters. On page 33 they write: "A syntax-directed
definition uses a context-free grammar to specify the syntactic
structure of the input. With each grammar symbol, it associates a set
of attributes, and with each production, a set of semantic rules for
computing values of the attributes associated with the symbols
appearing in that production. The grammar and the set of semantic
rules constitute the syntax-directed definition."
(I would note that this notational form treats the production rules
and the semantic rules as separate items that are paired with each
other. )
Then, at the bottom of page 37, they state: "A translation scheme is a
context-free grammar in which program fragments called semantic
actions are embedded within the right sides of productions. A
translation scheme is like a syntax-directed definition, except that
the order of the evaluation of the semantic rules is explicitly shown.
The position at which an action is to be executed is shown by
enclosing it between braces and writing it within the right side of a
production, as in
rest --> + term { print('+') } rest
A translation scheme generates an output for each sentence x generated
by the underlying grammar be executing the actions in the order they
appear during a depth-first traversal of a parse tree for x."
(In this form, the "actions" are "built-in" to the grammar productions
where each action is like a pseudo-symbol that is now a part of the
RHS of a production. It also corresponds pretty much exactly to the
way "actions" are embedded in a bison or yacc grammar.)
There is some context missing here (they are talking about a specific
example), but the essence of the difference as they define it is that
a "syntax-directed definition" is more of a mathematical concept, in
which the "rules" are mathematical statements of the relationships
between the attributes (without regard to how they might actually be
computed), while the "actions" called for in a "translation scheme"
are procedural in nature, and they carry out a translation by being
"executed" in some defined order related to the traversal of a parse
tree (which happens to correspond to the order in which the conceptual
parse tree would be traversed during a top-down or bottom-up parse).
I don't know if this helps the original inquirer or not, but I'll let
it stand on its own as a direct quotation from the book.
--
Allan G. Jost, Ph.D.
Professor and Program Director
Faculty of Computer Science
Dalhousie University
Halifax, NS, Canada
[Hmmn, just goes to show how long it's been since I actually read through
the dragon book. -John]
.
- Prev by Date: Twenty years of comp.compilers
- Next by Date: Call For Papers: ISMM 2006 (International Symposium on Memory Management) (Ottawa, Jun 06)
- Previous by thread: Twenty years of comp.compilers
- Next by thread: Re: syntax directed translation
- Index(es):
Relevant Pages
|
