COP 5555 - PRINCIPLES OF PROGRAMMING LANGUAGESNOTES ON ATTRIBUTE GRAMMARS.I. Introduction.These notes are intended to supplement class lectures on attribute grammars. We will begin withfunctional graphs, and describe methods of evaluating them. Then we will introduce attribute grammars,showanexample of their use, and proceed to give anattribute grammar for Tiny.II. Functional graphs.Definition:Afunctional graph is a directed graph in whichi) Nodes represent functions,a. Incoming edges are parameters.b. Outgoing edges represent functional values.ii) Edges represent transmission of data among functions.Example:23 + 5Here we have three functions:i- Constant function 2.ii- Constant function 3.iii- Binary function + (addition).After some delay,the value of the addition function is five.Question:What effect does a cycle in a functional graph have?Answer:Acycle can makesense only if the graph can achieve a steady state, in which no more changesin the values occur.Example:1 + ?No steady state is achieved, because the value of ? keeps incrementing.PLP Notes Attribute Grammars-2-Example:true and ?Asteady state is achieved, because regardless of the initial value of the feedback loop, it does not changeafter the first AND operation, and remains with that value. However, ifthe "AND" were changed to a"NAND", there would be no steady state.In general, it is impossible to detect whether a steady state will everoccur (the problem is undecid-able, i.e. as difficult as deciding whether a Turing machine will halt).If we assume that each node in the graph is a single processor,then the graph can be thought of as anetwork of parallel processors. We will also assume that all functional graphs are acyclic.Evaluation of Functional Graphs:Functional graphs are evaluated by first inserting registers, and then propagating values along theedges.Register insertion:Givenedges E1...En from a node A to nodes B1...Bn,weinsert a register so that there is one edgefrom A to the register,and n edges from the register to B1...Bnrespectively.Example:A B2B1BnGETS CONVERTED TO A B2B1Bn... ...All registers must be initialized to some "undefined" value, which must be outside of the domains ofall functions.Foranoutgoing edge from a "top-most" node, a register is simply added to the graph, so that the edgegoes from the node to the register.Note that this is the same as the first case, with n=0.Functional value propagation:There are twoways to propagate values along the functional graph. The first, called "data flowanaly-sis", makes several passes on the graph, evaluating functions whose inputs (registers) are defined. Theother,called "lazy evaluation", uses a stack to perform a depth-first search, backwards (i.e. the oppositedirection of the edges), for the "bottom-most" nodes of the graph. The functions are then evaluated in theorder specified by the contents of the stack.PLP Notes Attribute Grammars-3-Data FlowDriver:while anytop-most register is undefined dofor each node N in the graph doif all inputs of N come from a defined register thenevaluate function and update N’soutput registerfiododLazy Evaluation:for each top-most register R dopush (stack, R)odwhile stack not empty docurrent := top (stack)if current = undefinedthencomputable := truefor each R in dependency(current), while computable doif R = undefined thencomputable := falsepush (stack,R)fiodif computable thencompute_value(current)pop_stackfielse pop (stack)fiodData FlowAnalysis starts at constants and propagate values forward. There is no stack. The algorithmcomputes ALL values, whether theyare needed or not. Lazy evaluation starts at the target nodes andchases the dependencies backwards. The algorithm evaluates functions ONLYiftheyare needed. It ismore expensive instorage, because of the use of a stack.III. Attribute grammars.Attribute grammars are used to associate constructs in an AST with segments of a functional graph.An attribute grammar is essentially a context-free grammar,inwhich each rule has been augmented with aset of axioms. The axioms specify segments of the functional graph. As the AST is built (typically bot-tom-up), the segments of the functional graph are "pasted" together.Upon completion of the AST,thefunctional graph’sconstruction also concludes, and one proceeds to evaluate it, using one of the twometh-ods described above.After the evaluation, the top-most register(s) of the functional graph will presumablycontain the output of the translation process.PLP Notes Attribute Grammars-4-Definition:Anattribute grammar consists of1) A context-free grammar describing the structure of the parse tree.2) A set of attributes ATT.Each attribute "decorates" some node in the AST,and later in fact becomes aregister in the functional graph.3) A set of axioms that express relationships among attributes.Example:Binary Numbers.String-to-tree transduction grammar:S → N=>.→N.N =>.N→ND =>cat→ DD → 0=>0D→1=>1Abstract Syntax Tree Grammar:S → <.NN>→ <.N>N → <cat N D >→ DD → 0→ 1The first grammar specifies the transduction from strings to AST’s. The second one (which we willuse for the attribute grammar) generates trees in prefix form. There are twotypes of attributes:1) Synthesized: used to pass information from the sibling to the parent node in the tree.2) Inherited: used to pass information from the parent to the sibling in the tree.In general, the type of attribute defines the type of tree walking required (bottom-up or top-down). Ifthe tree is processed recursively,via say,asingle procedure called ProcessNode, inherited attributes areinput parameters to ProcessNode (to be used by it), whereas synthesized attributes are output parameters ofProcessNode (i.e. to be produced by it).Forbinary numbers, we have ATT = { value, length, exp }, wherevalue: the decimal value of the binary number denoted by the subtree.length: the number of binary digits occurring to the left of the right-most binary digit in the sub-tree. This will be used to generate negative exponents, for the fractional part (if any) of thebinary number.exp: the exponent (of 2) that is to be multiplied by the right-most binary digit in the subtree.The synthesized and inherited attributes are specified by twosubsets of ATT:SATT = { value, length }IATT = { exp }Note: In this particular case, SATT and IATT are disjoint. This is not always the case, as we shall see later.Attributes are associated with nodes in the AST via twofunctions:PLP Notes Attribute Grammars-5-S: