Homework 1 Solution

Problem 1
  1. It's easy to demonstrate that this grammar is at least left associative for a given string. For example, we can derive the string "X+Y+Z" from the substitution sequence:
    E → E '+' T → (E '+' T) '+' T → (T '+' T) '+' T → (ID '+' ID) '+' ID
    It's trickier to demonstrate that this is possible for all strings and even more difficult to show that the right-associative parse isn't possible in general. However, this question wasn't asking for a formal proof but rather for intuition. Any answer should be fine if it at least contains the thought: This grammar is left-associative because its rules only refer to themselves on the left side of binary operators.
  2. The rule P must refer to itself on the right side of the exponentiation operator.
    E ::= E + T | T
    T ::= T * P | P
    P ::= ID ** P | ID
  3. "A**B**C" is not valid Ada syntax. This is because the Ada grammar production factor is not recursive and requires a primary (ie: number, variable, etc...) on either side of the exponentiation operator. A common source of confusion appears to have been the loose conventions of some online Ada grammars, where unquoted parentheses are used as terminals rather. Instead of the clearer primary ::= "(" expression ")" you might have instead seen primary ::= (expression). This does not mean that you can substitute expressions for primaries!

    Prof. Schonberg adds: It's worth mentioning that the precedence and associativity of operators is a common source of errors in most languages, because people simply forget what the precedences are (very common source of errors in C, which has something like 13 levels of precedence). The advice is always: "When in doubt, parenthesize", The issue with exponentiation is that most languages make all their grammars left-associative, but Fortran decided that A ** B ** C would be more useful as A ** (B ** C) because (A **B ) ** C is just A ** (B * C). For somebody doing scientific computation that is a reasonable choice, but given that it goes against common rules in other languages, it's just a source of confusion. C decided not to have a exponentiation operation at all, and Ada chose a rule that forces you to parenthesize.
Problem 2
  1. Some interesting properties to the specified language:
    • The number of a's in a string is always greater than or equal to the number of b's.
    • Every string in the language is either empty or starts with an a.
    • The prefix of any string has more a's than b's.
  2. Derivations:
    S → aS → a(aSbS) → aab    
    and
    S → aSbS → a(aS)bS → aab
    The parse trees corresponding to these two derivations should look something like: 
        S              S
    |              |              
    aS            aSbS 
     |             |  \
     aSbS          aS  ε
      | |           |
      ε ε           ε
Problem 3
C++: 
int fast_exp(int base, int exponent) { 
    int result = 1; 
    int power = base;
    while (exponent > 0) { 
      if (exponent % 2) { result *= power; }
      power *= power;
      exponent /= 2;
    }
    return result;
}
Python: 
  def fast_exp(base, exponent):
    result = 1 
    power = base 
    while exponent > 0:
      current_bit = (exponent % 2 == 1)
      if current_bit: result *= power
      power *= power
      exponent /= 2
    return result
OCaml: 
let rec fast_exp x = function 
  | 0 -> 1 
  | n -> 
     let x' = power x (n / 2) in 
     x' * x' * (if n mod 2 == 0 then 1 else x)
Any implementation using the default integer type in C, C++, C#, Java, OCaml, and most other languages will silently overflow when you try to compute 20^20. The desired behavior (implemented by Python and a few other clever languages), is to automatically detect overflow and cast up to an arbitrary-precision integer type.

If you used a floating number type then you will get the correct answer for 20^20 but wrong answers for larger exponents (such as 20^25). Some of you went beyond the requirements of the question and actually implemented an arbitrary-precision number type yourselves, kudos!