CS 3723
 Programming Languages 
Fall 2014
  Final Exam  
  Topics and Review   

Exam date/time: Thursday, 18 December 2014, 9:45 am - 12:15 pm.

Giving in to popular demand, I'm deleting activation records as a final exam topic.

For what it's worth department:

  1. Recursive-descent Parsers:
    Favorite Question: I might give you an entire grammar for a simple language (or a portion of such a grammar) and ask you to write functions for a recursive-descent parser (or one or more of those functions). For example, it could be like the "odd" language: H7 Problem 3.

  2. The MIPS assembly language as used in our project:
    Types of Questions:
    • We used 4 different jump and branch instructions (for transfer of control, like a goto): j, jr, jal, and the pair c.eq.d and c.eq.d and bc1t. Where were these used and for what purposes?
    • MIPS has two simple instructions beq and bne to branch whether or not the contents of two registers are equal. Why didn't we use one of these?
    • Consider the way we used MIPS memory in the Tiny compiler project.
      Where were the the single-digit double constants kept?
      Where was space for lower-case letter variables?
      Where was space for temporary variables?
      How did we access the memory locations above?
      How much space did each of these variables require?
      What identifier names did we use for the temporary variable locations (trick question)?

  3. Syntax-directed Translation:
    Types of Questions:

    • The end of the page R-D Parsing gives items 2, 3, and 4 that we can do in syntax-directed parsing:

      • (2) leave information, leave it at a node of the parse tree for later use.
      • (3) inheritance, passing information down the parse tree,
      • (4) synthesis, passing information up the parse tree,

      Which of these did we use for the Tiny compiler project and in what circumstances?

    • Given a grammar and a sentence generated from the grammar, a recursive-descent parser doesn't give us the parse tree directly. What does it give instead?

  4. Grammar for Tiny:
    Types of Questions:

    • Questions about the types of notation used (implicit in the next question).

    • Consider the grammar rule that handles the hat or "^ operator: U ---> F '^' U | F. Why couldn't one of the two rules below work instead?

        U ---> U '^' F | F       or

        U ---> F { '^' F }

      (Two separate answers.)

  5. Translating a Tiny Operator:
    Favorite Question: Suppose your program is translating the result of a "*", inside the T( ) function. What inputs does it need? What result does it return? Explain roughly what MIPS instructions are output and how this is accomplished. (The MIPS doesn't have to be perfect.)

  6. Translating Tiny Statements:
    Favorite Questions: For each of the following Tiny constructs below, we can ask roughly the same question as the one above: The function that handles this construct and translates the corresponding input Tiny program to MIPS needs one or more inputs from somewhere and will return either zero or one value:

    • assignment, using function A( )
    • output an expression, using function P( )
    • output a newline, using function P( )
    • input a double, using function G( )
    • handle a while loop, using function W( )
    • handle an if-then-(optional)else statement, using function I( ).

    As before explain roughly what MIPS instructions are output and how this is accomplished. (The MIPS doesn't have to be perfect.)

  7. Erroneous function in the Tiny compiler:
    (I wish I'd put it on the final.) Below is code for the function E( ) in the Tiny compiler. This function handles the '+' and '-' operators. I left off the '-' below.

      def E();
    res = T()
    while next == '+':
        scan()
        arg1 = res
        sys.stdout.write("   l.d  $f2, " + str(arg1) = "($s1)\n")
        arg2 = T()
        sys.stdout.write("   l.d  $f4, " + str(arg2) = "($s1)\n")
        sys.stdout.write("   add.d  $f6, $f2, $f4\n")
        res = next_temp() # starts at 288, incr by 8
        sys.stdout.write("   s.d  $f6, " + str(res) + "($s1)\n")
    return res

    Suppose this function is used in an otherwise error-free Tiny compiler to process the input:

      f = 9 + (7 + 6); $

    Identify the major error in the function, and say roughly what will happen as the compiler translates. [Even if you find, or think you find, simple errors in the code, those are not the error here. This is approximately what a student wrote recently.]

  8. (This topic now deleted.) Activation Records: Types of Questions:

    • What data is stored in the AR?
    • During function call/return, what steps occur involving the AE?
    • Specifics about the use in MIPS to implement recursion.

  9. Relational Operators in Tiny:
    Type of Question: Refer to the section on relational operators in Tiny® Extensions and explain how they are implemented.

  10. Python classes:
    Favorite Question: Specific examples in H11 (fractions) and H12 (time and date).

  11. More Python classes:
    Consider the example below:

Class illustrating inheritance Rest + Output
# accounts.py
import sys

###### Account #######################################
class Account(object):
    num_accounts = 0
    def __init__(self, name, balance):
        self.name = name
        self.balance = balance
        Account.num_accounts += 1
    def __str__(self):
        return "name: " + self.name + \
               ", balance: " + str(self.balance) + \
               ", num accounts: " +
                 str(Account.num_accounts)
    def deposit(self, amt):
        self.balance = self.balance + amt
    def withdraw(self, amt):
        self.balance = self.balance - amt
    def inquiry(self):
        return self.balance
        
a = Account("Albert", 1000.00)
sys.stdout.write(str(a)+'\n')
b = Account("Bill", 10.00)
sys.stdout.write(str(b)+'\n')
sys.stdout.write(str(a.inquiry())+'\n\n')

###### EvilAccount ###################################
# sometimes overstates balance, hope for overdraw
import random # for EvilAccount
class EvilAccount(Account):
    def inquiry(self):
        def __str__(self):
            return super(EvilAccount, self).__init__()
        if random.randint(0,2) == 1: # 0-2 inclusive
            return self.balance * 1.10
        else:
            return self.balance

c = EvilAccount("Claire", 500.00)
sys.stdout.write(str(c)+'\n')
for i in range(0,10):
    sys.stdout.write(str(c.inquiry())+', ')
sys.stdout.write('\n\n')

###### MoreEvilAccount ############################
# Add deposit fee, still overstates balance
class MoreEvilAccount(EvilAccount):
    def deposit(self, amount):
        self.withdraw(5.00)
        super(MoreEvilAccount,self).deposit(amount)

d = MoreEvilAccount("Doug", 300.00)
sys.stdout.write(str(d)+'\n')
for i in range(0,10):
    d.deposit(10)
    sys.stdout.write(str(d.inquiry())+', ')
sys.stdout.write('\n\n')

d.withdraw(360.00)
sys.stdout.write(str(d)+'\n')

% python accounts.py
name: Albert, balance: 1000.0, num accounts: 1
name: Bill, balance: 10.0, num accounts: 2
1000.0

name: Claire, balance: 500.0, num accounts: 3
500.0, 500.0, 500.0, 500.0, 550.0,
500.0, 550.0, 550.0, 500.0, 500.0, 

name: Doug, balance: 300.0, num accounts: 4
305.0, 310.0, 315.0, 352.0, 325.0,
330.0, 368.5, 374.0, 345.0, 385.0, 

name: Doug, balance: -10.0, num accounts: 4

I might give you such an example and ask questions about it, or give you part of such an example and ask you to make additions, or to instantiate some of the classes, etc.

You should look over the example above as well as the one at the end of the page on Python classes.

Not on the Final Exam:
  • Anything about shift-reduce parsing.

  • Anything related to finite automata, including NFAs, DFAs, the subset algorithm, epsilon-moves, and such.

  • Activation Records:

(Revision date: 2014-12-04. Please use ISO 8601, the International Standard.)