Question? Leave a message!

Syntax Directed Translation

Syntax Directed Translation
Syntax Directed Translation www.ThesisScientist.comOutline  Syntax Directed Definitions  Evaluation Orders of SDD’s  Applications of Syntax Directed Translation  Syntax Directed Translation Schemes www.ThesisScientist.comIntroduction  We can associate information with a language construct by attaching attributes to the grammar symbols.  A syntax directed definition specifies the values of attributes by associating semantic rules with the grammar productions. Semantic Rule Production E.code=E1.codeT.code’+’ EE1+T • We may alternatively insert the semantic actions inside the grammar E E1+T print ‘+’ www.ThesisScientist.comSyntax Directed Definitions  A SDD is a context free grammar with attributes and rules  Attributes are associated with grammar symbols and rules with productions  Attributes may be of many kinds: numbers, types, table references, strings, etc.  Synthesized attributes  A synthesized attribute at node N is defined only in terms of attribute values of children of N and at N it  Inherited attributes  An inherited attribute at node N is defined only in terms of attribute values at N’s parent, N itself and N’s siblings www.ThesisScientist.comExample of Sattributed SDD Production Semantic Rules 1) L E n L.val = E.val 2) E E1 + T E.val = E1.val + T.val 3) E T E.val = T.val 4) T T1 F T.val = T1.val F.val 5) T F T.val = F.val 6) F (E) F.val = E.val 7) F digit F.val = digit.lexval www.ThesisScientist.comExample of mixed attributes Production Semantic Rules 1) T FT’ T’.inh = F.val T.val = T’.syn 2) T’ FT’1 T’1.inh = T’.inhF.val T’.syn = T’1.syn 3) T’ ε T’.syn = T’.inh 1) F digit F.val = F.val = digit.lexval www.ThesisScientist.comEvaluation orders for SDD’s  A dependency graph is used to determine the order of computation of attributes  Dependency graph  For each parse tree node, the parse tree has a node for each attribute associated with that node  If a semantic rule defines the value of synthesized attribute A.b in terms of the value of X.c then the dependency graph has an edge from X.c to A.b  If a semantic rule defines the value of inherited attribute B.c in terms of the value of X.a then the dependency graph has an edge from X.c to B.c  ExampleOrdering the evaluation of attributes  If dependency graph has an edge from M to N then M must be evaluated before the attribute of N  Thus the only allowable orders of evaluation are those sequence of nodes N1,N2,…,Nk such that if there is an edge from Ni to Nj then ij  Such an ordering is called a topological sortof a graph  Example www.ThesisScientist.comSAttributed definitions  An SDD is Sattributed if every attribute is synthesized  We can have a postorder traversal of parsetree to evaluate attributes in Sattributed definitions postorder(N) for (each child C of N, from the left) postorder(C); evaluate the attributes associated with node N;  SAttributed definitions can be implemented during bottomup parsing without the need to explicitly create parse trees www.ThesisScientist.comLAttributed definitions  A SDD is LAttributed if the edges in dependency graph goes from Left to Right but not from Right to Left.  More precisely, each attribute must be either  Synthesized  Inherited, but if there us a production AX1X2…Xn and there is an inherited attribute Xi.a computed by a rule associated with this production, then the rule may only use:  Inherited attributes associated with the head A  Either inherited or synthesized attributes associated with the occurrences of symbols X1,X2,…,Xi1 located to the left of Xi  Inherited or synthesized attributes associated with this occurrence of Xi itself, but in such a way that there is no cycle in the graph www.ThesisScientist.comApplication of Syntax Directed Translation  Type checking and intermediate code generation (chapter 6)  Construction of syntax trees  Leaf nodes: Leaf(op,val)  Interior node: Node(op,c1,c2,…,ck)  Example: Production Semantic Rules 1) E E1 + T E.node=new node(‘+’, E1.node,T.node) 2) E E1 T E.node=new node(‘’, E1.node,T.node) 3) E T E.node = T.node 4) T (E) T.node = E.node 5) T id T.node = new Leaf(id,id.entry) 6) T num T.node = new Leaf(num,num.val) www.ThesisScientist.comSyntax tree for Lattributed definition Production Semantic Rules + E.node=E’.syn 1) E TE’ E’.inh=T.node E1’.inh=new node(‘+’, E’.inh,T.node) 2) E’ + TE1’ E’.syn=E1’.syn 3) E’ TE1’ E1’.inh=new node(‘+’, E’.inh,T.node) E’.syn=E1’.syn 4) E’  E’.syn = E’.inh 5) T (E) T.node = E.node 6) T id T.node=new Leaf(id,id.entry) 7) T num T.node = new Leaf(num,num.val) www.ThesisScientist.comSyntax directed translation schemes  An SDT is a Context Free grammar with program fragments embedded within production bodies  Those program fragments are called semantic actions  They can appear at any position within production body  Any SDT can be implemented by first building a parse tree and then performing the actions in a lefttoright depth first order  Typically SDT’s are implemented during parsing without building a parse tree www.ThesisScientist.comPostfix translation schemes  Simplest SDDs are those that we can parse the grammar bottomup and the SDD is sattributed  For such cases we can construct SDT where each action is placed at the end of the production and is executed along with the reduction of the body to the head of that production  SDT’s with all actions at the right ends of the production bodies are called postfix SDT’s www.ThesisScientist.comExample of postfix SDT 1) L E n print(E.val); 2) E E1 + T E.val=E1.val+T.val; 3) E T E.val = T.val; 4) T T1 F T.val=T1.valF.val; 5) T F T.val=F.val; 6) F (E) F.val=E.val; 7) F digit F.val=digit.lexval; www.ThesisScientist.comParseStack implementation of postfix SDT’s  In a shiftreduce parser we can easily implement semantic action using the parser stack  For each nonterminal (or state) on the stack we can associate a record holding its attributes  Then in a reduction step we can execute the semantic action at the end of a production to evaluate the attribute(s) of the nonterminal at the leftside of the production  And put the value on the stack in replace of the rightside of production www.ThesisScientist.comExample L E n print(stacktop1.val); top=top1; E E1 + T stacktop2.val=stacktop2.val+stack.val; top=top2; E T T T1 F stacktop2.val=stacktop2.val+stack.val; top=top2; T F F (E) stacktop2.val=stacktop1.val top=top2; F digit www.ThesisScientist.comSDT’s with actions inside productions  For a production BX a Y  If the parse is bottomup then we perform action “a” as soon as this occurrence of X appears on the top of the parser stack  If the parser is top down we perform “a” just before we expand 1) L E n Y 2) E print(‘+’); E1 + T  Sometimes we cant do things as 3) E T 4) T print(‘’); T1 F easily as explained above 5) T F  One example is when we are 6) F (E) 7) F digit print(digit.lexval); parsing this SDT with a bottom up parserSDT’s with actions inside productions (cont) L  Any SDT can be E implemented as follows 1. Ignore the actions and print(‘+’); produce a parse tree E + T 2. Examine each interior T F node N and add actions as new children at the print(4); print(‘’); T F correct position digit print(5); 3. Perform a postorder F digit traversal and execute actions when their nodes print(3); are visited digit www.ThesisScientist.comSDT’s for LAttributed definitions  We can convert an Lattributed SDD into an SDT using following two rules:  Embed the action that computes the inherited attributes for a nonterminal A immediately before that occurrence of A. if several inherited attributes of A are dpendent on one another in an acyclic fashion, order them so that those needed first are computed first  Place the action of a synthesized attribute for the head of a production at the end of the body of the production www.ThesisScientist.comExample S while (C) S1 L1=new(); L2=new();;; C.true=L2; S.code=labelL1C.codelabelL2S1.code S while ( L1=new();L2=new();;C.true=L2; C); S1S.code=labelL1C.codelabelL2S1.code; www.ThesisScientist.comReadings  Chapter 5 of the book
Document Information
User Name:
User Type:
Uploaded Date: