CSC 355 Notes
Thursday December 1, 2005 

Topics:

• Finish notes from last time
• Updates & reminders
  • Final Project
    • Thursday December 8 - date for completion
    • In-class demo of your project accomplishments
      • Build & run; show samples; what phases are complete
      • Key accomplishments & challenges
      • Less than 10 minutes per group; be prepared to demo to minimize set-up time
      • Don't provide line by line commentary; this is a chance to share with you classmates
    • Report submission
      • Written report summarizing your accomplishments on the project
      • Include representative/key parts of the specification files - it is note necessary to include the complete files
      • Some expected elements of your document would include
        • Project goals & background
        • Successes
        • Challenges
        • Narrative of your design philosophy with some real examples sprinkled in
  • Final Exam
    • Take Home - distributed 12/8 - due 12/13
    • In Class - Tuesday 12/13 8:00am
  • Register for next semester
    • Several courses offered that cover special topics
    • Forensics, Software Design, AJAX, Enterprise Technology & Assessment
    • Take a chance, learn something new

Setting the stage

• front-end : scanner/parser part of the compiler
• back-end : target language code generation

Intermediate Languages

• representation of the program
• benefits of intermediate form
  • retargeting : combine front/back ends to facilitate different machines and/or language combinations
  • optimization opportunities : study structures to produce better code
• intermediate representation must be expressive enough but should not be too complicated

Examples of intermediate representations

• three-address code

Three-address code

• sequence of statements ; more limited form than a HLL
• basic statements will take forms such as
  • a : = b op c  // Assignment statement
  • goto L // Unconditional jump statements
  • if a relop b goto L  // Conditional jump statement

Observations

• expressions are limited in size
• store results in temporaries to accumulate the actual value of a more complex expression

Translation into 3-address code

• define a translation scheme to map our source language constructs into target language images
• attributes
  • maintain properties, associated with the nonterminals, to produce the 3-address code
  • code, labels, temps, etc.
  • other attributes are of course already in place for type, scope, etc. issues
• attributes we will use
  • code : the 3-address code image of the construct embodied by a nonterminal
  • res : the location (temp) that contains the result of the code
    • making the assumption (design choice) that all code will end with a value in a single location
    • this location becomes the "glue" to allow you to put pieces together

Simple expressions

• S --> id := E	S.code = E.code & id.res := E.res
  E --> E + E	E.res = new_temp
  	E.code = E1.code & E2.code & E.res := E1.res + E2.res
  E --> id	E.res = id.res
  	E.code = ""

While loops

• S --> while E to S	S.start = new_label
  	S.end = new_label
  	S.code = S.start : & E.code & if E.res = 0 goto S.end & S1.code & goto S.start & S.end :

•  

Source language

• continue for other types of statements and expressions
  • loops
  • conditional statements
  • Boolean expressions
  • procedures
• match semantics/behavior of generated code to that of the language
  • short-circuit evaluation - for instance
• loops and conditionals are fairly similar
  • manage labels and jumps
• remember, we are implementing the source language, so the specification rules must be obeyed to have a proper/correct implementation
• this implies, of course, that you know and understand the rules for the language

Consider types and type conversions

• Basic rules for E--> E+E if we include basic types and conversions

• E.res := new_temp
  if E1.type = integer and E2.type = integer then
   begin
     code(E.res := E1.res Int+ E2.res)
     E.type := integer
   end
  else if E1.type = real and E2.type = real then
   begin
     code(E.res := E1.res Real+ E2.res)
     E.type := real
   end
  else if E1.type = integer and E2.type = real then
   begin
     z := newtemp;
     code ( z := int_to_real E1.res)
     code(E.res := z Real+ E2.res)
     E.type := real
   end
  else if E1.type = real and E2.type = integer then
   begin
     z := newtemp;
     code ( z := int_to_real E2.res)
     code(E.res := E1.res Real+ z)
     E.type := real
   end
  else 
   E.type := type_error
   

• That's not so bad
• a = b + c * d  [ a, b: real   c, d: integer ]

• t1 := c Int* d
  t2 := Int2Real t1
  t3 := b Real+ t2
  a := t3

Boolean expressions

• data values true and false
• operators AND, OR, NOT
• also recall: relational expressions produce Boolean results
• in C++, for instance, Booleans can be coerced to a numeric value too
  • 0 : false
  • non-0 : true

Numeric translation of Boolean expressions

• relational expressions produce value 0 or 1
• logical operators work on the numeric values
• a < b

  • if a < b
      r := 1
    else
      r := 0

• a<b or c <d and e < f

• A	if a < b goto D
  B	t1 := 0
  C	goto E
  D	t1 := 1
  E	if c < d goto H
  F	t2 := 0
  G	goto I
  H	t2 := 1
  I	if e < f goto L
  J	t3 := 0
  K	goto M
  L	t3 := 1
  M	t4 := t2 and t3
  N	t5 := t1 or t4

• At the end, t5 will contain a 0 or 1 to indicate the value of the original expression