Syntax-Directed Translation CS308 Compiler Theory 1
Syntax-Directed Translation CS308 Compiler Theory 1
Syntax-Directed Translation Grammar symbols are associated with attributes to associate information with the programming language constructs that they represent. Values of these attributes are evaluated by the semantic rules associated with the production rules. Evaluation of these semantic rules: -may generate intermediate codes may put information into the symbol table may perform type checking may issue error messages may perform some other activities -in fact,they may perform almost any activities. An attribute may hold almost any thing. a string,a number,a memory location,a complex record. CS308 Compiler Theory 2
Syntax-Directed Translation • Grammar symbols are associated with attributes to associate information ith the programming lang age constr cts that the information with the programming lang uage constructs that they represent. • Values of these attributes are evaluated by the Values of these attributes are evaluated by the semantic rules semantic rules associated with the production rules. • Evaluation of these semantic rules: – may generate intermediate codes – may put information into the symbol table – ma y p yp g erform type checkin g – may issue error messages – may perform some other activities – in fact, they may perform almost any activities. ivities. • An attribute may hold almost any thing. – a string, a number, a memory location, a complex record. CS308 Compiler Theory 2
Syntax-Directed Definitions and Translation Schemes When we associate semantic rules with productions,we use two notations: Syntax-Directed Definitions Translation Schemes 。 Syntax-Directed Definitions: give high-level specifications for translations hide many implementation details such as order of evaluation of semantic actions. We associate a production rule with a set of semantic actions,and we do not say when they will be evaluated. Translation Schemes: indicate the order of evaluation of semantic actions associated with a production rule. In other words,translation schemes give a little bit information about implementation details. CS308 Compiler Theory 3
Syntax-Directed Definitions and Translation Schemes • When we associate semantic rules with productions, we use two notat ions: – Syntax-Directed Definitions – Translation Schemes • Syntax-Directed Definitions: – give high-level specifications for translations – hide many implementation details such as order of evaluation of semantic actions. – We associate a p yy roduction rule with a set of semantic actions, and we do not sa y when the y will be evaluated. • Translation Schemes: – i di h d f l i f i i i d i h d i l indicate t he or der o f evaluation o f semantic actions associate d wit h a pro duction rule. – In other words, translation schemes give a little bit information about implementation details. CS308 Compiler Theory 3
Syntax-Directed Definitions A syntax-directed definition is a generalization of a context-free grammar in which: -Each grammar symbol is associated with a set of attributes. This set of attributes for a grammar symbol is partitioned into two subsets called synthesized and inherited attributes of that grammar symbol. Each production rule is associated with a set of semantic rules. Semantic rules set up dependencies between attributes which can be represented by a dependency graph. This dependency graph determines the evaluation order of these semantic rules. Evaluation of a semantic rule defines the value of an attribute.But a semantic rule may also have some side effects such as printing a value. CS308 Compiler Theory
Syntax-Directed Definitions • A syntax-directed definition is a generalization of a context-free grammar i hi h n whi c h: – Each grammar symbol is associated with a set of attributes. – This set of attributes for a grammar symbol is partitioned into two subsets called This set of attributes for a grammar symbol is partitioned into two subsets called synthesized and inherited attributes of that grammar symbol. – Each production rule is associated with a set of semantic rules. • Semantic rules set up dependencies between attributes which can be represented by a dependency graph. • This dependency graph determines the evaluation order of these semantic rules. • Evaluation of a semantic rule defines the value of an attribute. But a semantic rule may also have some side effects such as printing a value. CS308 Compiler Theory 4
Annotated Parse Tree A parse tree showing the values of attributes at each node is called an annotated parse tree. The process of computing the attributes values at the nodes is called annotating (or decorating)of the parse tree. Of course,the order of these computations depends on the dependency graph induced by the semantic rules. CS308 Compiler Theory 5
Annotated Parse Tree • A parse tree showing the values of attributes at each node is called an annotated parse tree. • The process of computing the attributes values at the nodes is called annot ti a ng (or d ti ecorating) f th t ) o f the parse tree. • Of course, the order of these computations depends on the dependency graph induced by the semantic rules dependency graph induced by the semantic rules. CS308 Compiler Theory 5
Syntax-Directed Definition In a syntax-directed definition,each production A->a is associated with a set of semantic rules of the form: b=fC,C2,…,Cd where f is a function, and b can be one of the followings: b is a synthesized attribute of A and cc2c are attributes of the grammar symbols in the production A-a). OR b is an inherited attribute one of the grammar symbols in a(on the right side of the production),and cc2...c are attributes of the grammar symbols in the production A-a). CS308 Compiler Theory 6
Syntax-Directed Definition • In a syntax-directed definition, each production A→α is associated wih f i l f h f i t h a set o f semant ic ru les o f t he form: b=f(c 1,c 2,…,c n) where f is a function, and b can be one of the followings: Î b is a synthesized attribute of A and c 1,c 2,…,c n are attributes of the grammar symb l i th d ti ( b o ls in the pro duction ( A→α ). OR Î b i i h i d ib f h b l i is an i n her ite d attribute one o f t he grammar sym b o ls in α ( h on t h e right side of the production), and c 1,c 2,…,c n are attributes of the grammar symb l i th d ti ( b o ls in the pro duction ( A→α ). CS308 Compiler Theory 6
Attribute Grammar ● So,a semantic rule b-fc.c..c indicates that the attribute b depends on attributes cc2...c In a syntax-directed definition,a semantic rule may just evaluate a value of an attribute or it may have some side effects such as printing values. An attribute grammar is a syntax-directed definition in which the functions in the semantic rules cannot have side effects (they can only evaluate values of attributes) CS308 Compiler Theory 7
Attribute Grammar • So, a semantic rule b=f(c 1,c 2,…,c n) indicates that the attribute b d d epen ds o n attributes c 1,c 2,…,c n. • In a syntax-directed definition, a semantic rule may just evaluate a val f tt ib t it h id ff t h lue o f an att rib u te or it may have some side effec ts suc h as printing values. • An attribute grammar is a syntax-directed definition in which the functions in the semantic rules cannot have side effects (they can functions in the semantic rules cannot have side effects (they can only evaluate values of attributes). CS308 Compiler Theory 7
Syntax-Directed Definition --Example Production Semantic Rules L→E return print(E.val) E→E1+T E.val E.val T.val E→T E.val T.val T→T1*F T.val T val F.val T→F T.val F.val F→(E) F.val E.val F→digit F.val digit.lexval Symbols E,T,and F are associated with a synthesized attribute val The token digit has a synthesized attribute lexval(it is assumed that it is evaluated by the lexical analyzer). CS308 Compiler Theory 8
Syntax-Directed Definition -- Example Production Semantic Rules L → E return print(E.val) E → E1 + T E.val = E1.val + T.val E → T E.val = T.val T → T1 * F T.val = T1.val * F.val T → F T lF l .va l = F.va l F → ( E ) F.val = E.val F → digit F val = F.val = digit.lexval • Symbols E T and F are associated with a synthesized attribute Symbols E, T, and F are associated with a synthesized attribute val. • The token digit has a synthesized attribute lexval (it is assumed that it is evaluated by the lexical analyzer). CS308 Compiler Theory 8
Annotated Parse Tree--Example Input:5+3*4 E.val=17 return E.val=5 + T.val=12 T.val=5 T.val=3 F.val=4 F.val=5 F.val=3 digit.lexval=4 digit.lexval=5 digit.lexval=3 CS308 Compiler Theory 9
Annotated Parse Tree -- Example Input: 5+3*4 L E.val=17 return E.val=5 + T.val=12 T.val=5 T.val=3 * F.val=4 F.val=5 F.val=3 digit.lexval=4 digit.lexval=5 digit.lexval=3 CS308 Compiler Theory 9
Dependency Graph Input:5+3*4 E.val=17 平 E.val=5 T.val=12 ↑ T.val=5 T.val=3 F.val=4 ↑ ↑ F.val=5 F.val=3 digit.lexval=4 ↑ digit.lexval=5 digit.lexval=3 CS308 Compiler Theory 10
Dependency Graph Input: 5+3*4 L E.val=17 E.val=5 T.val=12 T.val=5 T.val=3 F.val=4 F.val=5 F.val=3 digit.lexval=4 digit.lexval=5 digit.lexval=3 CS308 Compiler Theory 10