Report

Attribute Grammars Prabhaker Mateti ACK: Assembled from many sources About Attribute Grammars • Attribute grammars (AGs) add semantic info on parse tree nodes • Used for semantic checking and other compile-time analyses, e.g., type checking in a compiler • Used for translation, e.g., parse tree to assembly code • A traversal of the parse tree and the computation of information. CS784 2 Attribute Grammars: Definition • An attribute grammar is a context-free grammar G = (S, N, T, P) with the following additions. • For each terminal and non-terminal X, disjoint sets S(X) synthesized attributes and I(X) inherited attributes: – A(X) = S(X) ∪ I(X) • X0 ::= X1 ... Xn • S(X0) = f(I(X0), A(X1), ... , A(Xn)) • I(Xj) = g(A(X0), ... , A(Xn)) – depends on the attribute value at parent and those of siblings. • Each rule has a set of predicates/ conditions to check for attribute consistency: P( A(X0), A(X1), A(X2), …, A(Xn) ) CS784 3 Example-1: Binary Numbers 1. 2. 3. 4. N N N N • CFGs do not provide semantics. CGGs provide only syntax, that too without context-sensitive details • CS784 ::= ::= ::= ::= 0 1 N0 N1 1. N.val:= 0 2. N.val:= 1 3. N.val:= 2*N.rhs.val 4. N.val:= 2*N.rhs.val+1 • N.val is an attribute associated with node N of the parse tree • N.rhs Node corresponding to the rhs • Synthesized Attributes 4 Example-2: Type Checking 1. E ::= n 2. E ::= x 3. E ::= E1 + E2 4. E ::= E1 * E2 • Semantics we wish to add – n is an int, x is a real. – op + returns an int if both the operands are int, otherwise a real. CS784 1. E.type := int 2. E.type := real 3. if E1.type = E2.type then E.type := E1.type else E.type := real fi • • Item 3 derived version of the semantics Static semantics 5 Example-3: Assignment Arithmetic • • • • stm ::= var := exp | stm; stm exp ::= var + var | var var ::= A | B | C synthesized actual-type for var and exp • inherited expected-type for exp • lookup (var.string) a helper function; gives the actual type of A, B, C • exp ::= var1 + var2 – subscripts added • exp.actual-type := var1.actual-type • exp.expected-type – from parent in the parse tree • Predicates: – var1.actual-type == var2.actual-type – exp.expected-type == exp.actual-type – var ::= A | B | C • var.actual-type := lookup (var.string) CS784 6 Inherited Attributes Example • Declaration and Use { int i, j, k; i := i + j + j; } • assign ::= var := exp – env: environment – var.env := assign.env – exp.env := assign.env CS784 7 Information Flow inherited computed available synthesized ... CS784 ... 8 Attribute Value Computation • If all attributes were inherited, the tree could be decorated in top-down order. Inherited Attributes pass information – down the parse tree, or – from left siblings to the right siblings • If all attributes were synthesized, the tree could be decorated in bottom-up order. Synthesized Attributes pass information up the parse tree • In many cases, both kinds of attributes are used, and it is some combination of top-down and bottom-up that must be used. • Initially, there are intrinsic attributes on the leaves • If a condition in a tree evaluates to false, an error occurs. CS784 9 Prolog for Example-2 1. 2. 3. 4. type(n, int). type(x, real). type(+(E, F), T) :- type(E, T), type(F, T). type(+(E, F), real) :- type(E, T1), type(F, T2), T1 \= T2. 5. Type Checking ?- type(+(n, x), real). 6. Type Inference ?- type(+(n, x), T). • (Definite Clause Grammars) CS784 10 Example-4: Fractions in Binary 1. F ::= . N 2. N ::= 0 3. N ::= 1 4. N ::= 0 N 5. N ::= 1 N • Synthesized: val, value • Inherited: pow, the number of bits between left of a non-terminal and the binary point • Nr: N-right, Nl: N-left CS784 1: 2: 3: 4: 4: 5: F.val:= N.val; N.pow:= 1 N.val := 0 N.val := (1/2^N.pow) Nl.val := Nr.val Nr.pow := 1 + Nl.pow Nl.Val := Nr.val+(1/2^N.pow) 5: Nr.pow := 1 + Nl.pow 11 Ex4: Synthesized Attributes Only • Binary Fractions, same grammar as before: 1. F ::= . N 2. N ::= 0 3. N ::= 1 4. N ::= 0 N 5. N ::= 1 N CS784 • Alternate computation based on synthesized attribute val only 1: F.val := N.val / 2 2: N.val := 0 3: N.val := 1 4: N.val := N.val / 2 5: N.val := N.val / 2 + 1 12 Example-5: Distinct Identifiers • Compute the number of distinct identifiers in a straight-line program. • Semantics specified in terms of sets of identifiers. • Attributes – var – exp – stm CS784 id ids ids num 13 Example-5: Distinct Identifiers • exp::= var – exp.ids = { var.id } • exp::= exp1 + exp2 – exp.ids = exp1.ids U exp2.ids • stm::= var:= exp – stm.ids = { var.id } U exp.ids – stm.num = | stm.ids | • stm::= stm1;stm2 – stm.ids = stm1.ids U stm2.ids – stm.num = | stm.ids | CS784 14 Example-5: Using Lists • Attributes – envi: list of vars in preceding context – envo: list of vars for following context – dnum: number of new variables • exp ::= var exp.envo = if member(var.id, exp.envi) then exp.envi else cons(var.id, exp.envi) fi CS784 15 Example-5: Using Lists • • • • • • • • • exp ::= exp1 + exp2 envi envi envi envo envo envo dnum dnum dnum exp1.envi := exp.envi exp2.envi := exp1.envo exp.envo := exp2.envo exp.dnum := length(exp.envo) exp.envo = append-sans-duplicates(exp1.envo, exp2.envo ) CS784 16 Complete Evaluation Rules • Synthesized attribute associated with N: – Each alternative in “N ::= …” should contain a rule for evaluating the Synthesized attribute. • Inherited attribute associated with N: – For every occurrence of N in “… ::= … N …” there must be a rule for evaluating the Inherited attribute. • Whenever you create an attribute grammar (in home work/ exams), make sure it satisfies these requirements. CS784 17 One Pass Attribute Computation • To enable one-pass top-down left-to-right computation of the attributes: – each inherited attribute of the right-hand side symbol can depend on all the attributes associated with preceding right-hand side symbols and the inherited attribute of the left-hand side non-terminal. – Similarly, the synthesized attribute of the left-hand side non-terminal can depend on all the attributes associated with all the right-hand side symbols and the inherited attribute of the left-hand side nonterminal. CS784 18 More than Context-Free Power • LABC = { a^nb^nc^n | n > 0 } – Unlike LAB = { a^nb^n | n > 0 }, here we need explicit counting of a’s, b’s and c’s • LWCW = { wcw | w ∈{a, b}* } – The “flavor” of checking whether identifiers are declared before their uses • LABC, LWCW cannot be defined with a contextfree grammar • Syntax analysis (i.e., parser based on CFGs) cannot handle semantic properties CS784 19 LABC = { a^n b^n c^n | n > 0 } • ls ::= as bs cs – ExpNb(bs) := Na(as); ExpNc(cs) := Na(as) • as ::= a | a as1 – Na(as) := 1; Na(as) := Na(as1) + 1 • bs ::= b | b bs1 – cond(ExpNb(bs) = 1); ExpNb(bs1) := ExpNb(bs) - 1 • cs ::= c | c cs1 – Cond(ExpNc(cs) = 1); ExpNc(cs1) := ExpNc(cs) – 1 • Na: • ExpNb: • ExpNc: CS784 synthesized by as inherited from bs inherited from cs 20 Uses of Attribute Grammars • Compiler Generation – Top-down Parsers (LL(1)) • FIRST sets, FOLLOW sets, etc – Code Generation Computations • Type, Storage determination, etc. • Databases – Optimizing Bottom-up Query Evaluation (Magic Sets) • Programming and Definitions CS784 21 Uses of Inherited Attributes • ex: 5.0 + 2 – need to generate code to coerce int 2 to real 2.0 • Determination of un-initialized variables • Determination of reachable non-terminals • Evaluation of an expression containing variables CS784 22 Use of Attribute Grammars • Useful for expressing arbitrary cycle-free computational walks over CFG derivation trees – Synthesized and inherited attributes – Conditions to reject invalid parse trees – Evaluation order depends on attribute dependencies • Realistic applications: – type checking – code generation • “Global” data structures must be passed around as attributes • Any container data structure (sets, etc.) can be used • The evaluation rules can call auxiliary/helper functions but the functions cannot have side effects CS784 23 References • T. K. Prasad, Attribute Grammars and their Applications, In: Encyclopedia of Information Science and Technology, pp. 268-273, 2008. Attribute-Grammars.pdf • PL Text Book Sections – Pagan: 2.1, 2.2, 2.3, 3.2 – Stansifer: 2.2, 2.3 – Slonneger and Kurtz: 3.1, 3.2 CS784 24