Today in CS362: Attribute Grammars Missing Ananta, Erik, Mark Admin Start your parsers soon. Overview Attributes Computing Attributes Example: Evaluating Expressions Example, Extended: Typing Expressions Example, Extended: Sequencing Assignments Obsevation: While parse trees are "wicked neat", they seem pretty limited in that they can only be used for "proving" language membership. We'd like to use parse trees to compute other values: the value of an arithmetic expression the "value" of a program Question: How? Standard Technique: "Attribute Grammars" Key ideas 1: Extend nonterminals with associated values ("attributes") Examples for expressions: Value of the expression Type Code to compute the expression Where will these values come from? For leaf nodes, we often need to compute them from the token itself. Normally, from "nearby" nodes in the parse tree How do we figure out how to compute the attributes? We add rules for computing the values of attributes (Each rule is associated with a particular production). E0 -> E1 '+' T E0.val = E1.val + T.val E1.symtab = E0.symtab T.symtab = E0.symtap E1.symtab_in = E0.symtab_in T.symtab_in = E1.symtab_out E0 -> E1 ADDOP T E0.val = ADDOP.fun(E1.val,T.val) ADDOP -> '+' ADDOP.fun = lambda (x,y) (+ x y) E0.val = E1.val + T.val OLD VIEW: Compute your attributes while you parse An attribute is *synthesized* if it depends on the attributes of children An attribute is *inherited* if it depends on the attributes of parents or siblings LL parsing is appropriate for inherited attributes LR parsing is appropriate for synthesized attributes Program -> StatementList StatementList.inTable = lambda (x) . undefined StatementList0 -> Statement ';' StatementList1 Statement.inTable = StatementList0.intable StatementList1.inTable = Statement.outTable StatementList -> epsilon Statement -> AssignmentStatement AssignmentStatement.inTable = Statement.inTable Statement.outTable = AssignmentStatement.outTable Statement -> PrintStatement PrintStatement.table = Statement.inTable Statement.outTable = Statement.inTable AssignmentStatement -> id '=' E E.table = AsssignmentStatement.inTable AssignmentStatement.outTable = extend(AssignmentStatement.inTable, associate E.value with id) PrintStatement -> printop '(' id ')' print lookup(id.string,PrintStatement.table) E0 -> E1 '+' T E0.val = E1.val + T.val E1.table = E0.table T.table = E1.table E -> T E.val = T.val T.table = E.table T0 -> T1 '*' F T0.val = T1.val * F.val T1.table = T0.table F.table = T0.table T -> F T.val = F.val F.table = T.table F -> num F.val = atoi(num.string) F -> id F.val = lookup(id.string,F.table) F -> '(' E ')' F.val = E.val E.table = F.table THOUGHT QUESTIONS FOR MONDAY! Does StatementList need an outtable attribute? Do we need to compute any attributes for StatementList -> epsilon