Class 24: Semantic Actions

Held: Monday, 29 March 2004

Summary: Today we consider ways to extend parse trees so that they can be used to compute relevant values.

Related Pages:

• EBoard.

Notes:

• I'll admit that I got much less done during break than I had planned. In particular, I still do not have your work graded.

Overview:

• Adding attributes to parse trees
• Example: Evaluating expressions
• Computing the values of attributes
• Example: Typing expressions
• Example: Sequences of assignments

Attributes

• As you know, the parse tree is only one step on the way to compilation of a source text.
• What do we do next? Typically, we add attributes to the nodes of the parse tree.
• An attribute is a computed value associated with a node in the parse tree.
• What can attributes be computed from? Typically values of neighboring nodes (children, parent, siblings).
• How are they computed? Using a rule that is associated with a production in the language.
• Grammars augmented with rules are called attribute grammars.

An Attribute Grammar for Evaluating Expressions

• Let's consider how we might compute a value and type type of arithmetic expressions as they are parsed.
• What attributes will we need?
  • A value attribute (associated with expressions, terms, factors, and numbers) is clearly necessary.
  • In order to compute the values of variables (identifiers), we'll need to look them up in a symbol table. We'll leave that as a subject for future research (perhaps Monday's class).
• Some rules are fairly trivial, as they only involve copying attributes

  Exp ::= Term
    Exp.value = Term.value
    Exp.type = Term.type
  Term ::= Factor
    Term.value = Factor.value
    Term.type = Factor.type
  Factor ::= OPEN Exp CLOSE
    Factor.value = Exp.value
    Facator.type = Exp.type
  

• For the base case of numbers, we simply get the value of the number (we assume that this is computed during the lexical analysis phase)

  Factor ::= NUMBER
    Factor.value = NUMBER.value
    Factor.type = NUMBER.type
  

• If all that we have for tokens is the string representation, we will need to convert it

  Factor ::= NUMBER
    Factor.value = stringToNumber(NUMBER.string)
  

• Similarly, for the base case of identifiers, we simply get the type of the identifier. (We may not get a value.)

  Factor ::= ID
    Factor.type = lookupType(symbols,ID)
  

• Addition and subtraction are also fairly easy

  Exp_0 ::= Exp_1 + Term
    Exp_0.value = Exp_1.value + Term.value
    Exp_0.type = mostGeneral(Exp1.type,Term,type)
  Exp_0 ::= Exp_1 - Term
    Exp_0.value = Exp_1.value - Term.value
    Exp_0.type = mostGeneral(Exp1.type,Term,type)
  

• If we use yacc or bison and pay attention to only values, the rules will look like

  exp : exp '+' exp    { $$ = $1 + $3; }
  exp : exp '-' exp    { $$ = $1 - $3; }
  

• If we treat MULTIPLY and DIVIDE as tokens, we might write something like

  MulOp ::= MULTIPLY
    MulOp.fun = (lambda (x y) (* x y))
  MulOp ::= DIVIDE
    MulOp.fun = (lambda (x y) (/ x y))
  

• We can then add a rule for terms

  Term_0 ::= Term_1 MulOp Factor
    Term_0.value = MulOp.fun(Term_1.value, Factor.value)
    Term_0.type = mostGeneral(Term1.type,Factor,type)
  

Attributes, Revisited

• We've seen one mechanism for computing one kind of attribute. Let's now look more broadly at attributes.
• What kinds of attributes can be computed? A wide variety. We typically compute
  • symbol tables to use in type checking and correctness analysis;
  • values of expressions, as we've just seen;
  • abstract syntax trees that correspond to the structure underlying the parse tree. Such ASTs help eliminate problems of parse trees introduced by changes to the syntax required by parsing techniques;
  • some compilers use attributes to compute code for the parse tree.
• How are the rules applied? In the abstract, one can say that a topological sort of the dependencies is done and the rules are applied in order.
  • If you don't know what a topological sort is, ask someone who took 301.
• In practice, a rule is often applied when the corresponding production is executed by the parser.
  • This limits the types of rules that are allowed.
  • In an LR parser, attributes must by synthesized: computed from the attributes of the children or earlier symbols.
  • In an LL parser, attributes can also be inherited: computed from attributes of the children or left siblings.
• In our compiler, we'll compute attributes in a separate pass or passes.
  • If you modify the grammar, you should probably build the AST during parsing, but can compute other attributes separately.
• In practice, rules can also do things other than compute values. This means that the behavior of the parser depends on the order in which the rules are applied. This is a bad thing, and you should avoid rules that have such side effects.

Symbol Tables

• For the compute a value from other values aspect of the grammar, the value attribute is synthesized, computed only from children.
• But if we also need to make values depend on previously computed values, the values will be inherited.
• Consider a simple extension to the extension grammar in which we use expressions either in assignment statements or print statements.

  S ::= StatementList
  StatementList ::= Statement ';' StatementList
                 |  epsilon
  Statement ::= AssignmentStatement
             |  PrintStatement
  AssignmentStatement ::= ID ASSIGN Exp
  PrintStatement ::= PRINT ID
  

• Now let's consider how to associate values with identifiers.
• We'll start by adding a function, valueOf, that maps every assigned identifier to its value.
  • We generally implement that function as a table and call it a symbol table.
  • I've been teaching enough Scheme that I want to think of it as a function.
• Print statements can use that table

  PrintStatment ::= PRINT ID
    display PrintStatement.valueOf(ID.name)))
  

• Where does it get that function? Presumably, from its parent node.

  Statement ::= PrintStatement
    PrintStatement.valueOf = Statement.valueOf
  

• Where does the statement get the function? Presumably, from its enclosing statement list.

  StatementList_0 ::= Statement ';' StatementList_1
    Statement.valueOf = StatementList_0.valueOf
  

• Where does the statement list get the function? From a combination of prior statements.

  S ::= StatementList
    StatementList.valueOf = (lambda (x) 'undefined)
  StatementList_0 ::= Statement ';' StatementList_1
    StatementList_1.valueOf = 
      extend(StatementList_0.valueOf,Statement.extension)
  

• You can fill in much of the rest.