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.

5. Syntax-directed translation

Remember: syntax-directed translations associate semantic actions or rules with the productions of a grammar. Two types: 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:

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: 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

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)

Result for a-4+c:

Building the syntax tree

Building syntax trees for statements

Directed Acyclic Graphs (DAGs)

Later:

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) 26 september 2010