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