Parse Trees A parse tree is a tree with the following properties: The root is labeled by the start symbol. Each leaf is labeled by a terminal or by E. -Each interior node is labeled by a non-terminal. If A is the non-terminal labeling some interior node and X,X2,..,Xn are the labels of the children of that node from left to right,then there must be a production A-XX2 X.Here,X,X2,...,Xeach stand for a symbol that is either a terminal or a non- terminal. CS308 Compiler Theory
Parse Trees • A parse tree is a tree with the following properties: – The root is labeled by the start symbol. – Each leaf is labeled by y a terminal or by E. – Each interior node is labeled by a non-terminal. – If A is the non-terminal labeling some interior node and Xl , X2, • • • , Xn are the labels of the children of that node from left to right then there must be a production A the children of that node from left to right, then there must be a production A -> X X ··· 1 2 · · · Xn. Here, X1 , X2 , . . . , Xn each stand for a symbol that is either a terminal or a nonterminal . CS308 Compiler Theory 11
Ambiguity string->string string string-string 0 1 23456789 string string I string X string string string string string 2 9 string + string 9 5 5 2 Figure 2.6:Two parse trees for 9-5+2 CS308 Compiler Theory 12
Ambiguity string -> string + string | string - string | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 CS308 Compiler Theory 12
Operator Associativity and Precedence To resolve some of the ambiguity with grammars that have operators we use: -Operator associativity:-in most programming languages arithmetic operators have left associativity. -E.g.9+5-2=(9+5)-2 However has right associativity,i.e.a=b=c is equivalent to a=(b=c) - Operator Precedence:-if an operator has higher precedence,then it will bind to it's operands first. eg.has higher precedence then +therefore 9+5*2 is equivalent to 9+(5*2) CS308 Compiler Theory
Operator Associativity and Precedence • To resolve some of the ambiguity with grammars that have operators we use: – Operator associativity :- in most programming languages arithmetic operators have left associativit y. – E.g. 9+5-2 = (9+5)-2 – However = has right associativity, i.e. a=b=c is equivalent to a=(b=c) – Operator Precedence :- if an operator has higher precedence, then it will bind to it’s operand fi t srs t. – eg. * has higher precedence then +, therefore 9+5*2 is equivalent to 9+(5*2) CS308 Compiler Theory 13
Syntax-Directed Translation Syntax-directed translation is done by attaching rules or program fragments to productions in a grammar. erpr→expr+term translate exprii translate term; handle + CS308 Compiler Theory 14
Syntax-Directed Translation • Syntax-directed translation is done by attaching rules or program fragments to prodi i uct ions in a grammar. CS308 Compiler Theory 14
Postfix Notation If E is a variable or constant,then the postfix notation for E is E itself. If E is an expression of the form E,op E2,where op is any binary operator,then the postfix notation for E is E'E'2 op,where E'and E'2 are the postfix notations for E and E2,respectively. If E is a parenthesized expression of the form (E)),then the postfix notation for E is the same as the postfix notation for E, ·X=Y==Z+U*V?Y:0 CS308 Compiler Theory 15
Postfix Notation • If E is a variable or constant , then the postfix notation for E is E itself. • If E is an expression of the form E1 op E2 , where op is any binary operator, then the postfix notation for E is E’1 E’2 op, where E’1 and E’2 are the postfix notations for E1 and E2 , respectively. • If E is a parenthesized expression of the form (E1), then the postfix notation for notation for E is the same as the postfix notation for is the same as the postfix notation for E1 · • X Y Z+U*V?Y 0 X=Y==Z+U*V?Y:0 CS308 Compiler Theory 15