Syntax-styrd översättning
Kursen Kompilatorer och interpretatorer |
Föreläsningar:
1
2
3
4
5
6
7
8
9
10
11
12
Det här är ungefär vad jag tänker säga på föreläsningen.
Använd det för förberedelser, repetition och ledning.
Det är inte en definition av kursinnehållet,
och det ersätter inte kursboken.
Idag: Syntax-styrd översättning. Att bygga syntaxträd.
- Bygger vidare på ALSU-07 avsnitt 2.3 (se föreläsning 2)
- ALSU-07 avsnitt 5.1 om syntax-styrd översättning
- ALSU-07 avsnitt 5.3 om att bygga syntax-träd med hjälp av en syntax-styrd översättning
- ALSU-07 avsnitt 6.1 om syntaxträd
- (ASU-86 5.1-5.2)
5. Syntax-directed translation
Remember: syntax-directed translations associate semantic actions or rules
with the productions of a grammar. Two types:
- Syntax-styrd definition (eng: syntax-directed definition): semantiska regler, ingen ordning specificerad
- Syntax-styrt översättningsschema (eng: syntax-directed translation scheme): semantiska aktioner, ordning specificerad
Semantic actions may generate code,
save information in a symbol table,
issue error messages,
or perform any other activities.
5.1 Syntax-directed definitions
Attributes = "record fields in the nodes of the parse tree".
Numbers, strings, pointers...
Attributes:
- Synthesized (ex: value in 2 + 3;) -- compare: Yacc!
- Inherited -- from parents or siblings (ex: type in int x;)
Annotating or decorating a parse tree = calculating attribute values
Attribute x depends on attribute y.
Ex: E.val depends on E1.val and E2.val
(A dependency graph shows dependencies between attributes in nodes,
and can be used to determine the evaluation order of nodes.)
Attribute grammar = no side effects in the semantic rules
S-attributed definitions = a syntax definition with only synthesized (=S) attributes
Attribute values of terminals (=tokens) are supplied by the lexical analyzer.
A token has no inherited attributes.
5.2 Construction of syntax trees
Remember:
- Parse tree = concrete syntax tree = all nonterminals left
- Syntax tree = abstract syntax tree = only "operators" and operands
Ex: a-4+c
Med den här grammatiken:
E -> E1 + T | E1 - T | T
T -> ( E ) | id | num
|
But: terminology!
We can generate code (initermediate or target)
(or calculate a result in a calculator) directly while parsing...
...or we can build a syntax tree, and then generate code
(or caluclate a result)
from the tree.
(Remember from föreläsning 5:)
#define MAX_ARGS 4
enum TreeNodeType { IF, WHILE, PLUS, MINUS, TIMES };
struct TreeNode {
enum TreeNodeType type;
struct TreeNode* args[MAX_ARGS];
};
Building syntax trees for expressions
- mknode(op, left, right)
- mkleaf(ID, symtabentry)
- mkleaf(NUM, value)
Ex igen: a-4+c
ALSU-07 fig. 5.10 (ASU-86 fig. 5.9):
Syntax-directed definition for constructing a syntax tree for an expression:
| Production | Semantic Rule |
|---|
| E -> E1 + T | E.nptr = mknode('+', E1.nptr, T.nptr) |
| E -> E1 - T | E.nptr = mknode('-', E1.nptr, T.nptr) |
| E -> T | E.nptr = T.nptr |
| T -> ( E ) | T.nptr = E.nptr |
| T -> id | T.nptr = mkleaf(ID, id.entry) |
| T -> num | T.nptr = mkleaf(NUM, num.entry) |
Building syntax trees for statements
- Expression statement
- if statement
- while statement
- ...
Directed Acyclic Graphs (DAGs)
- Not a tree!
- "Re-uses" common subexpressions.
- Ex, tree: a + a * (b - c) + (b - c)
- The DAG re-uses a and b - c
- mkleaf and mknode can return old pointers!
- hashing, map< (op,p1,p2) , ... >
Later:
- Evaluating the parse trees -- similar to Yacc directly $$ = $1 + $2)
- Generating code from a parse trees -- similar to emit(...)
Kursen Kompilatorer och interpretatorer |
Föreläsningar:
1
2
3
4
5
6
7
8
9
10
11
12
Thomas Padron-McCarthy
(Thomas.Padron-McCarthy@oru.se)
20 september 2007