3. Dependency graph ae The directed raph that represents the interdepe erited attributes at nodes in the parse tree is called dependency graph. For the rule XYZ the semantic action is given by X.x i= {(¥-y, Zz) then Synthesized attribute is X.x and X.x depends upon attributes Y.y and 2.2. endencies between nynthesize day im=> Example 3.1: Design the dependency graph for the following grammar. E> E+E E - BE," By Solution : The semantic rules for the above grammar is as given below. Production rulo Semantic rulo Eeval:=E, evaltE, «val E eval:=E, «val X Ep val The dependency graph is as shown in Fig. 3.4. Eval E-val + Eeval Eyval * — Ezeval Fig. 3.4 Dependency graph ‘The synthesized attributes can be represented by «val. Hence the synthesized attributes are given by Eval, Ej +val and E, val. The dependencies among the nodes is given by solid arrows. The arrows from E, and E, show that value of E depends upon E, and Fy We have represented parse tree using dotted lines. mmm> Example 3.2: Design the dependency graph for the following grammar. S > T List T = int Scanned with CamScanner neT = float T > char T — double List — Listy, id List — id solution : The dotted line is for representing the parse tree. The semantic rules for the above grammar is as given below. List — List,, id List,.in:=Listin Enter_type( id.entry, List.in) Enter_type( id.entry, Listin) ‘The dependency graph is as shown in Fig. 3.5. Fig. 3.5 Dependency graph Scanned with CamScannerCompiler Desig EB Sy ong the nodes can be shown be solid arrows IN the aborg fe ee inherited from the parent or sy’ S| jependi the values can be a Ry oa SY re Be aa for the attributes is inherited attributes. ling aa | wn, 4. Evaluation order : i valuation order j i dency graph decides the eval er The topological sort of the depen ; c : ns tree. In deciding evaluation order the semantic rules in oe roadie definite S used. Thus the translation is specified by syntax-directed efinitions. Therefore the ie definition of syntax-directed definition is required. s Type __-elistin = int @) | @ int “~~ @ Uistin = ing 4 °® \ \ \ v @ tistin= int * r® | Fi of Fig. 3.6 Evaluation order The evaluation order can be decided as follows. 1. The type int is obtained from lexical analyzer by analyzing the input token. 2 The List.in is assigned the type int from the sibling T.type. 3, The entry in the symbol table for identifier ¢ gets associated with the type ist Hence variable ¢ becomes of integer type. 4. The List.in is assigned the type int from the parent List.in. 5. The entry in the symbol table for identifier b gets associated with the ype # Hence variable b becomes of integer type. 6. The List.in is assigned the type int from the parent List.in. 7. The entry in the symbol table for identifier a gets associated with the type itt Hence variable a becomes of integer type. Thus by evaluation the semantic rules in this order sto int in the sya table entry for each identifier a, b and c, ee(inh | | L De pendency — Garg laren : &9t IM the ake oe fort’ veprovact dot interdlepodtency heteuees synteta ect & tinfieutted ccttr= Nerde ot node th ue paue freer A Debordemey graph reperrest INC Plocd of. fowrrectihn Among 4 cttrhtcte In Ot ULE Aree HK Depndenty qeapr. are eufel fer detectecting Evaluation Sordex for Atinbbetes th a fuchees A lottle ay Annotated fate toe Abowd! die ualut of- AHA » @ oltporoline gach derectia tow HERE Val ats crn be “comptottae eee Remant's Kuler Bevatls Eprund +7 vad Evals Tuad Te val = Guat de Fruad Tinal> Arual ee aie at obit: lenual > Drrasa ita Depmctinty Grable. for Hat fp Strings (SHIA) mi eG kee sn Pariera Ola rterar * pa 3 NOTES = Reprevart_ with anow 4 Node numba — Cott cofll redece) urtvile ‘envating Depenctency gropte