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