CS 3721 Programming Languages
Syntax Directed Translation
|
Overview:
The term semantic action refers to extra code added to
a parser so that it will carry out some task, often translating
from the language the grammar describes to some other language.
During the course of the parse, the function calls implicitly
carry out a complete traversal of the parse tree, though the
actual parse tree is not constructed. The tricky part is to insert
extra code, so that (at run time) during the traversal,
the translation will be carried out.
This process is known as syntax-directed translation.
Initial Examples of Semantic Actions:
Consider a recursive descent parser for the grammar giving
arithmetic expressions.
| Arithmetic Expressions |
|---|
P ---> E '$'
E ---> T {('+'|'-') T}
T ---> S {('*'|'/') S}
S ---> F '^' S | F
F ---> '(' E ')' | char
|
It is easy to add extra code to this parser so that it will
translate arithmetic expressions in to reverse Polish notation
(RPN). So little additional code is needed that this example
illustrates the power of this approach.
- Translator (in C) of arithmetic expressions to RPN
(Reverse Polish Notation):
- Same translator (in Java) of arithmetic expressions to RPN
(Reverse Polish Notation):
Here is another example of semantic actions: an evaluator
of arithmetic expressions:
- Evaluator (in C) of arithmetic expressions, producing a double:
Further examples of semantic actions:
- Writing and reading binary
trees:
This example shows how one can use a lisp-like
representation for binary search trees. A program creates
such a tree and writes it out in sequential (or "flattened") form
as a linear sequence of characters. Then a separate program
can use a recursive descent parser to read these "flattened"
binary trees and convert them into internal form.
Revision date: 2004-11-02.
(Please use ISO
8601, the International Standard.)